工件存在不同交货宽容期的最大加权超前延误问题

本文考虑下述排序问题：有n个工件需在同一台机器上加工，对各工件有一宽容交货期，若一工件在其宽容期前完工则受加权超前惩罚，若在其宽容期后完工则受加权延误惩罚，要求适当安排一加工方式使最大惩罚最小，文中相应某指定工件需准时完工的上述问题证得了Np-hard性，给出了最优算法，并作了一些讨论。

The Maximum Weighted Earliness Tardiness Problem with Different Due Window of Jobs

This paper considers the following scheduling problem: n jobs are need to be processed on same machine and there exists a due window for each job. If a job finishes its processing ahead of its due window, it will be suffered with a weighted earliness penalty, and if a job finishes its processing after its due window, then it will be suffered with a weighted tardiness penalty. The task is to schedule the n jobs such that the maximum penalty is minimized. For such a scheduling problem with a given job must be finished just in time. This paper proves its Np-hardiness, construct an optimal algorithm for it and do some discussion.