工件可预处理的单台机排序问题

Single-machine scheduling with job can be processed in advance

考虑一个工件可预处理的单机排序问题.要求在所有工件能够按时完工的前提下,使得预处理工件的费用最小.证明了对于一般情况,该问题是NP-难的,并给出了动态规划算法.进一步,得到当每个工件的预处理费用都相同时该问题是多项式可解的,并给出了强多项式时间算法.

A single machine scheduling where jobs can be preprocessed before they are scheduled to the machine is considered. The objective is to minimize the cost for preprocessing under the constraint that no job is tardy. The problem is showed to be NP-hard and a pesudo-polynomial time algorithm is presented. For the case that the costs for preprocessing jobs are the same, a strongly polynomial time algorithm is presented.