两机无等待流水车间调度问题的性质

针对两机无等待流水车间调度问题, 提出目标函数最大完工时间最小化的快速算法, 并给出算法的复杂度. 分析两机无等待流水车间调度问题的排列排序性质, 证明了两机无等待流水车间调度问题的可行解只存在于排列排 序中, 排列排序的最优解一定是两机无等待流水车间调度问题的最优解. 最后研究了同时包含普通工件和无等待工 件的两机流水车间调度问题的复杂性, 为进一步研究两机无等待流水车间调度问题提供了理论依据.