准时化(JIT)思想下有关交货期窗口的单机调度问题

Single-Machine Scheduling Problem about Due Windows for Just-In-Time Ideas

研究了有关交货期窗口的单机调度问题。在过去的10年中,准时化的概念对中国工业的影响很大。早于或晚于交货期窗口的任务都不受欢迎,且将导致提前或拖期惩罚。如果任务的完工时间偏离了交货期窗口,就要受到固定的惩罚,惩罚量与提前或拖期完工无关。目标是极小化所有惩罚的和。设如果任务在交货期准时完工,则不受惩罚;目标就是寻找一个最优调度极小化提前和拖期任务的总数。给出了确定最优调度的多项式时间算法。

Concerned with the scheduling problems about due windows on a single machine. The just-in-time (JIT) concept has had a great impact on Chinese industry in the last decade. Early or tardy its due window of the job is highly discouraged, and it will incur earliness or tardiness penalty. The penalty is a fixed cost for each job if a job is completed. The objective is to minimize the total cost incurred for all penalized jobs. A time-polynomial algorithm is presented to find the optimal scheduling. Finally, an example is shown the effective of the algorithm.