Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes

详细信息    查看全文

• 作者：Jun-Qiang Wang ; ^a ; ^b ; ^{wangjq@nwpu.edu.cn} ; Guo-Qiang Fan^a ; ^b ; Yingqian Zhang^c ; Cheng-Wu Zhang^a ; ^b ; Joseph Y.-T. Leung^d
• 关键词：Scheduling ; Heuristics ; Parallel-batching machine ; Two-agent scheduling ; NP-hardness
• 刊名：European Journal of Operational Research
• 出版年：2017
• 出版时间：16 April 2017
• 年：2017
• 卷：258
• 期：2
• 页码：478-490
• 全文大小：1293 K
• 卷排序：258

文摘

We schedule two agents on a single p-batching machine with non-identical job sizes. We minimize the makespan of one agent under a bounded makespan of the other agent. We show that no polynomial-time algorithm with a finite bound exists, unless P = NP. We propose an effective algorithm to obtain a lower bound of the optimal solution. We propose two heuristics and illustrate the effectiveness by computational studies.