F′2|m_1=1,m_2=2|C_(max)排序问题的计算复杂性研究

Study of Computational Complexity for F′2|m_1=1, m_2=2|C_(max) Scheduling Problems

研究了装配式流水作业排序问题的一个新模型 ,并对该模型相应的排序问题的计算复杂性进行了探讨 ,且证明了其在优化指标为作业排序长度的条件下该问题是NP 完全问题 ,没有多项式时间算法。

A new model of scheduling problems in assembly line is researched. The computational complexity for F′2|m 1=1, m 2=2|C max of this model is studied. This model is proved to be an NP Complete problem which does not involve polynomial time algorithm when the optimized parameters are the makespans.