论文部分内容阅读
讨论了flow-shop问题中极小化加工全长问题的复杂性,其中每个工件在其加工期间内需一个货盘.M. Wang et al. [3] 证明了m≥2 , K≥3 及 m≥3 , K≥2 时问题分别为强NP难和一般意义下的NP难的, 这里 m 为机器的台数,K 为系统中货盘的只数. 我们证明了当 m≥3,K≥2 时仍为强NP-难的,从而回答了M. Wang et al. [3] 所提出的一个待解决的问题.