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