对等待时间受限的两阶段流水车间调度问题的基本性质进行了研究。在问题的复杂性方面,证明了任何基于排列排序的调度规则都不能保证具有最优性,而且问题是强NP难的。在原问题和排列排序问题之间的关系方面,证明了满足排列排序要求的任一工件加工序列均可构成相应的可行调度;当满足一定条件时,排列排序的最优解也是原问题的最优解。这些性质为设计求解算法提供了理论基础。
科研之友
微信
新浪微博
Facebook
分享链接
