80 / 2024-04-19 12:18:47

Coordination mechanism design for the multiprocessor task scheduling problem

scheduling game,coordination mechanism design,Price of Anarchy

The multiprocessor-task scheduling problem, in which tasks may simultaneously occupy multiple servers, is an important problem in various domains such as cloud computing scheduling, production scheduling, and transportation scheduling, etc. This paper focuses on the coordination mechanism design for the multiprocessor-task scheduling when the tasks selfishly select a set of consecutive severs to process. We design the WF (Widest First) mechanism, proving that the Price of Anarchy (PoA) is upper bounded by 4-3/m, while providing a close lower bound for the PoA. Moreover, through numerical experiments, it shows the excellent performance of the WF mechanism in the average case, with the PoA significantly lower than the theoretical upper bound. Further improvement of the tie-breaking rules for participants could refine the experimental PoA value to around 1.05 (with only a 5% deviation from the optimal solution).