Single machine batch scheduling with sequential job processing
Single machine batch scheduling with sequential job processing
复制标题
DOI：
10.1080/07408170108936839
复制
发表时间：
2001-05
期刊：
影响因子：
--
通讯作者：
T. Cheng;M. Kovalyov
中科院分区：
文献类型：
--
作者：
T. Cheng;M. Kovalyov
研究了单机上n个工件分批排序问题，目标是极小化某些正则费用函数。每个批中的作业都是按顺序处理的，这样，一个批的处理时间等于该批中所包含的作业的处理时间之和。当该批中的最后一个作业完成处理时，同一批中的作业也同时完成。在处理每个批次之前，都有一个恒定的设置时间。每个批中的作业数由某个值B限定。如果B < n，则问题称为有界问题。否则，它是无界的。对于有界和无界问题，给出了最小化最大延迟、延迟工件数、总拖期、总加权完工时间和总加权拖期的动态规划算法。更有效的算法推导出一些特殊情况下的有界和无界的问题，其中所有的交货期和/或处理时间是相等的。有界问题的几种特殊情况被证明是NP-困难的。因此，提供了一个全面的分类的特殊情况下的计算复杂性。
The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both the bounded and unbounded problems in which all due dates and/or processing times are equal. Several special cases of the bounded problem are shown to be NP-hard. Thus, a comprehensive classification of the computational complexities of the special cases is provided.