A DP algorithm for minimizing makespan and total completion time on a series-batching machine

作者：He Cheng^*; Lin Yixun; Yuan Jinjiang

来源：Information Processing Letters, 2009, 109(12): 603-607.

DOI：10.1016/j.ipl.2009.02.007

• Multicriteria scheduling
• Series-batching machine
• Makespan
• Total completion time
• Pareto optimal solutions
• Computational complexity

This paper studies a bicriteria scheduling problem on a series-batching machine with objective of minimizing makespan and total completion time simultaneously. A series-batching machine is a machine that can handle up to b jobs in a batch and the completion time of all jobs in a batch is equal to the finishing time of the last job in the batch and the processing time of a batch is the sum of the processing times of jobs in the batch. In addition, there is a constant setup time s for each batch. For the problem we can find all Pareto optimal solutions in O (n(2)) time by a dynamic programming algorithm, where in denotes the number of jobs.

• 出版日期2009-5-31
• 单位郑州大学; 中国人民解放军信息工程大学