A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines

摘要

This paper studies a multi-agent scheduling problem on two identical parallel machines. There are g agents, and each agent's objective is to minimize its makespan. We present an approximation algorithm such that the performance ratio of the makespan achieved by our algorithm relative to the minimum makespan is no more than for the ith completed agent. Moreover, we show that the performance ratio is tight.