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

Authors：陈可嘉; 王潇

Source：控制与决策, 2013, (10): 1502.

• 两机流水车间调度
• 无等待
• 目标函数
• 排列排序
• 复杂性 two-machine flowshop scheduling
• no-wait
• objective function
• permutation schedule
• complexity

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

• Institution
  福州大学