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

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

单位：北京科技大学经济管理学院 北京100083 钢铁生产制造执行系统技术教育部工程研究中心 北京100083