Two-agent Makespan Minimization Scheduling Problem On Parallel Machines

The classic scheduling problem considers that the jobs only belong to one agent.However in the multiagent scheduling problem,there are several agents,each of which is interested in a subset of jobs.Each agent has its own performance measure which depends on the schedule of its jobs only.All the jobs have to share common resources.To satisfy the distinct requirements of the agents,the decision makers need to trade-off the balance between the goals of the agents.In this paper,a two-agent scheduling problem on parallel machines is considered.The two agents are agent A and agent B respectively,our objective is to minimize the makespan for agent A,subject to an upper bound on the makespan for agent B.It has been proved that all these problems are NP hard,Zhao and Lu[1]provided a dynamic programming algorithm to prove that the problem can be solved in pseudo-polynomial time.Furthermore,for this problem,Zhao and Lu[2]proposed an A-LS algorithm and proved that the worst case performance ratio of the A-LS algorithm is 2-1/m.In this paper,we propose a new algorithm:the CLPT algorithm.On the one hand,we compare the performance ratio between the CLPT algorithm and the optimal solution,found that the solution obtained by the CLPT algorithm is very close to the optimal solution.On the other hand,we design three experimental frameworks to compare the performance ratio of the two algorithms,the CLPT algorithm and the A-LS algorithm.A large number of numerical simulation results show that the CLPT algorithm outperforms the A-LS algorithm.