Single Machine Group Scheduling with Two Ordered Criteria
研究单机分组调度问题，其中作业按组连续加工，组间有独立于序列的准备时间。目标是在主准则（总加权完工时间）最优的前提下，最小化次要准则（最大成本），并提出了多项式时间算法。
The problem of scheduling jobs on a single machine is considered. It is assumed that the jobs are classified into several groups and the jobs of the same group have to be processed contiguously. A sequence independent set-up time is incurred between each two consecutively scheduled groups. A schedule is specified by a sequence for the groups and a sequence for the jobs in each group. The quality of a schedule is measured by two critera ordered by their relative importance. The objective is to minimize the maximum cost, the secondary criterion, subject to the schedule is optimal with respect to total weighted completion time, the primary criterion. A polynomial time algorithm is presented to solve this bicriterion group scheduling problem. It is shown that this algorithm can also be modified to solve the single machine group scheduling problem with several ordered maximum cost criteria and arbitrary precedence constraints.