The Coordination of Two Parallel Machines Scheduling and Batch Deliveries

摘要：

In this paper, we consider a two-identical-parallelmachine scheduling problem with batch delivery. Although NP-hardness of this problem has been already proved by Hall and Potts, but they did not give the pseudo-polynomial-time algorithm for the problem. We prove the problem is NP-hard in the ordinary sense by constructing a pseudo-polynomial-time algorithm for the problem. We also give a polynomial-time algorithM to solve the case when the job assignment to parallel machines is given.

作者: Hua Gong Lixin Tang

作者单位: The Logistics Institute, Northeastern University,Shenyang,China;College of Science,Shenyang Ligong U The Logistics Institute, Northeastern University,Shenyang,China

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 670-677

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）