Minimizing the Total Completion Time in a Two-machine Flowshop with Release Times
In this paper, we study a two-machine flowshop scheduling problem where a discrete processing machine is followed by a single batching machine, and each job is associated by the processing time and a release time on the first machine. The discrete machine processes one job at a time and the batching machine processes several jobs simultaneously. The objective is to find an optimal schedule which minimizes the total completion time of all jobs. We prove that the problem is strongly NP-hard, and further show that the problem with two distinct release times is NP-hard. When the job sequence is predetermined, this problem can be optimally solved in polynomial time.
Scheduling Batching machine Flowshop
Hua Gong Daheng Chen
College of Science, Shenyang Ligong University, Shenyang 100159, China Department of Logistics, Shenyang Ligong University, Shenyang 100159, China
国际会议
The 24th Chinese Control and Decision Conference (第24届中国控制与决策学术年会 2012 CCDC)
太原
英文
4153-4157
2012-05-23（万方平台首次上网日期，不代表论文的发表时间）