论文部分内容阅读
研究了有关交货期窗口的单机调度问题。在过去的10年中,准时化的概念对中国工业的影响很大。早于或晚于交货期窗口的任务都不受欢迎,且将导致提前或拖期惩罚。如果任务的完工时间偏离了交货期窗口,就要受到固定的惩罚,惩罚量与提前或拖期完工无关。目标是极小化所有惩罚的和。设如果任务在交货期准时完工,则不受惩罚;目标就是寻找一个最优调度极小化提前和拖期任务的总数。给出了确定最优调度的多项式时间算法,最后的例子说明了算法的有效性
The single machine scheduling problem with regard to the delivery window was studied. In the past 10 years, the concept of justification has had a great impact on Chinese industry. Tasks that are earlier or later than the delivery window are unpopular and will result in early or tardiness penalties. If the task’s completion time deviates from the delivery window, it will be subject to a fixed penalty. The amount of punishment has nothing to do with early or tardiness. The goal is to minimize the sum of all punishments. Let’s assume that if the task is completed on time, the delivery date is not punished; the goal is to find an optimal schedule that minimizes the total number of advance and tardiness tasks. A polynomial-time algorithm for determining optimal scheduling is given. The last example illustrates the effectiveness of the algorithm.