TY - JOUR
T1 - Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes
AU - Wang, Jun Qiang
AU - Fan, Guo Qiang
AU - Zhang, Yingqian
AU - Zhang, Cheng Wu
AU - Leung, Joseph Y.T.
N1 - Funding Information:
We thank the editors and anonymous referees for their helpful comments on earlier versions of our paper. This research was supported by the National Natural Science Foundation of China (Grant nos. 51275421 and 51675442 ), the 111 Project of NPU , China (Grant No. B13044 ) and the Fundamental Research Funds for the Central Universities, China.
Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2017/4/16
Y1 - 2017/4/16
N2 - We schedule the jobs from two agents on a single parallel-batching machine with equal processing time and non-identical job sizes. The objective is to minimize the makespan of the first agent subject to an upper bound on the makespan of the other agent. We show that there is no polynomial-time approximation algorithm for solving this problem with a finite worst-case ratio, unless P=NP. Then, we propose an effective algorithm LB to obtain a lower bound of the optimal solution, and two algorithms, namely, reserved-space heuristic (RSH) and dynamic-mix heuristic (DMH), to solve the two-agent scheduling problem. Finally, we evaluate the performance of the proposed algorithms with a set of computational experiments. The results show that Algorithm LB works well and tends to perform better with the increase of the number of jobs. Furthermore, our results demonstrate that RSH and DMH work well on different cases. Specifically, when the optimal makespan on the first agent exceeds the upper bound of the makespan of the other agent, RSH outperforms or equals DMH, otherwise DMH is not less favorable than RSH.
AB - We schedule the jobs from two agents on a single parallel-batching machine with equal processing time and non-identical job sizes. The objective is to minimize the makespan of the first agent subject to an upper bound on the makespan of the other agent. We show that there is no polynomial-time approximation algorithm for solving this problem with a finite worst-case ratio, unless P=NP. Then, we propose an effective algorithm LB to obtain a lower bound of the optimal solution, and two algorithms, namely, reserved-space heuristic (RSH) and dynamic-mix heuristic (DMH), to solve the two-agent scheduling problem. Finally, we evaluate the performance of the proposed algorithms with a set of computational experiments. The results show that Algorithm LB works well and tends to perform better with the increase of the number of jobs. Furthermore, our results demonstrate that RSH and DMH work well on different cases. Specifically, when the optimal makespan on the first agent exceeds the upper bound of the makespan of the other agent, RSH outperforms or equals DMH, otherwise DMH is not less favorable than RSH.
KW - Heuristics
KW - NP-hardness
KW - Parallel-batching machine
KW - Scheduling
KW - Two-agent scheduling
UR - http://www.scopus.com/inward/record.url?scp=85006173697&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85006173697&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2016.10.024
DO - 10.1016/j.ejor.2016.10.024
M3 - Article
AN - SCOPUS:85006173697
SN - 0377-2217
VL - 258
SP - 478
EP - 490
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -