Batch Delivery Scheduling with Limited Waiting Time Constraint on a Single Machine
In this paper, we study a batch delivery scheduling problem on a single machine in which the waiting time of a finished job on the machine is no more than a limited value. The waiting time of a job is defined as the difference between its completion time and the delivery date of the batch to which it belongs. The objective is to minimize the sum of the batch delivery cost and the makespan. We analyze some properties for the optimal schedule and prove the strong NP-hardness of the problem. When there is no long job, we propose a heuristic algorithm with worst-case 3. When there are some long jobs, we propose a heuristic with worst-case ratio 4.
Batch delivery Single machine Limited waiting time Heuristic
Hua Gong Lixin Tang
College of Science, Shenyang Ligong University, Shenyang 110168, China Liaoning Key Laboratory of Ma Liaoning Key Laboratory of Manufacturing System and Logistics The Logistics Institute, Northeastern
国际会议
2009年中国控制与决策会议(2009 Chinese Control and Decision Conference)
广西桂林
英文
2755-2759
2009-06-17（万方平台首次上网日期，不代表论文的发表时间）