TITLE:
Two-Agent Makespan Minimization Problem on Parallel Machines
AUTHORS:
Siqi Zheng, Zhaohui Liu
KEYWORDS:
Parallel Machines, Makespan, Approximation Algorithm, Two-Agent, Empirical Results
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.11 No.6,
June
30,
2023
ABSTRACT: A two-agent scheduling problem on parallel machines is considered in this paper. Our objective is to minimize the makespan for agent A, subject to an upper bound on the makespan for agent B. In this paper, we provide a new approximation algorithm called CLPT. On the one hand, we compare the performance between the CLPT algorithm and the optimal solution and find that the solution obtained by the CLPT algorithm is very close to the optimal solution. On the other hand, we design different experimental frameworks to compare the CLPT algorithm and the A-LS algorithm for a comprehensive performance evaluation. A large number of numerical simulation results show that the CLPT algorithm outperformed the A-LS algorithm.