等待时间受限的两阶段流水车间调度问题性质研究

摘要：

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

关键词：两阶段流水车间、等待时间受限、复杂性分析、排列排序

所属期刊栏目：25

分类号：F406.2(工业经济理论)

资助基金：国家自然科学基金资助项目70771008,70371057

在线出版日期：2011-05-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：88-93