Batching identical jobs
Batching identical jobs
复制标题
DOI：
10.1007/s001860000088
复制
发表时间：
2000-12
影响因子：
1.2
通讯作者：
P. Baptiste
中科院分区：
文献类型：
--
作者：
P. Baptiste
本文研究了两种不同类型的机器上，具有不同交货期和相同加工时间的工件排序问题。同一批的所有作业同时开始和完成。在串行并行机上，一个批的长度等于它的工件的处理时间之和，当一个新批开始时，出现一个恒定的准备时间。在并行机上，每批最多有b个工件，一批工件的长度是它的工件的最大处理时间。我们表明，在这两种环境中，一个大类的所谓的“有序”的目标函数，问题是多项式可解的动态规划。这使我们能够推导出的问题，其中的目标是最小化的加权数量的迟到的工作，或加权流时间，或总延误，或最大延误是多项式。换句话说，我们证明1| p-batch，B<n，ri，pi=p| Fand 1| s-batch，ri，pi=p| F ∈{∑wiUi，∑wiCi，∑Ti，Tmax}是多项式.这些问题的复杂程度以前是未知的。
We study the problems of scheduling jobs, with different release dates and equal processing times, on two types of batching machines. All jobs of the same batch start and are completed simultaneously. On a serial batching machine, the length of a batch equals the sum of the processing times of its jobs and, when a new batch starts, a constant setup timesoccurs. On a parallel batching machine, there are at mostbjobs per batch and the length of a batch is the largest processing time of its jobs. We show that in both environments, for a large class of so called “ordered” objective functions, the problems are polynomially solvable by dynamic programming. This allows us to derive that the problems where the objective is to minimize the weighted number of late jobs, or the weighted flow time, or the total tardiness, or the maximal tardiness are polynomial. In other words, we show that 1|p-batch,b<n,ri,pi=p|Fand 1|s-batch,ri,pi=p|F, are polynomial forF∈{∑wiUi,∑wiCi,∑Ti,Tmax}. The complexity status of these problems was unknown before.