研究了最小化总加权提前损失单机排序问题, 其中提前损失是工件在工期之前完成的各部分的持续加工时间. 首先, 文章分析了总加权提前损失问题在中断情况下的复杂性, 提出了中断排序算法, 用算例进行了验证; 接着通过设计拟多项式动态规划算法, 说明该问题在非中断情况下是一般意义下NP难的, 并进行了数据实验, 验证了该算法的有效性.

In this paper, we consider the single machine scheduling problem to minimize the total weighted early work. The early work of a job is a duration of the parts of the job completed prior to its due-date. First, this paper analyzes the complexity of the total weighted early work problem with preemptive case, and proposes an Interruption Scheduling Algorithm. Second, the problem without preemptive case is illustrated to be NP-hard by designing a quasi-polynomial dynamic programming algorithm, and data experiments are performed to verify the effectiveness of the algorithm.