单机作业在成组加工下的极小迟后范围问题

Minimizing the Range of Lateness on a Single Machine with the Workpieces Processed in Batches

有时刻零到达的n个工件需在同台机器上加工,工件具各自所需的加工时间和应交工时间,这些工件分属b个不同组。加工时,同组工件必须一起或连续或同时加工。要求适当排列这些工件,包括各组工件间的排列和各组中工件的排列以使各工件的迟后范围达到极小。对这样一个成组加工排序问题,文中证得了一些性质并给出了伪多项式时间算法。

There are n workpieces to be processed at time zero. The length of time needed for processing them varies with each workpiece. The workpieces are divided into b batches, and all the workpieces in the same batch must be processed together, successively or at same time. The problem under consideration is to minimize the range of lateness. To solve such a scheduling problem, this paper determines some properties and constructs corresponding pseudopolynomial algorithms.