带准备时间和强制工期的单机排序问题

Single machine scheduling with ready times and deadlines

讨论了带准备时间和强制工期的单机排序问题.在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,首先考虑了问题的可行性.通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法.对于可行问题,给出了一个算法在多项式时间内获得最优排序.

This paper discusses the scheduling problem that jobs with ready times and deadlines have to be processed on a single machine.The objective is to find a preemptive job sequence so as to minimize the maximum earliness considering the idle insert.Since tardy jobs are prohibited,we consider the feasibility primarily.The method of determining the feasibility is proposed through transforming the problem to a corresponding directed graph with capacity constraint,and adopting the algorithm of solving maximum network flow problem.A polynomial time algorithm is developed to achieve optimality for the feasible problem.