Author(s)

Siqi Zheng^*, Zhaohui Liu

School of Mathematics, East China University of Science and Technology, Shanghai, China.

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.

Parallel Machines, Makespan, Approximation Algorithm, Two-Agent, Empirical Results

Zheng, S. and Liu, Z. (2023) Two-Agent Makespan Minimization Problem on Parallel Machines. Journal of Applied Mathematics and Physics, 11, 1693-1706. doi: 10.4236/jamp.2023.116110.