文献类型：期刊文献

中文题名：含有批处理机的三机流水作业加工总长问题的计算复杂性

英文题名：Computational complexity of the makespan of the three-stage flow-shop with some batch machines

作者：成岗[1];鲁习文[1]

机构：[1]华东理工大学理学院数学系,上海200237

年份：2005

卷号：20

期号：4

起止页码：417

中文期刊名：高校应用数学学报（A辑）

外文期刊名：Applied Mathematics A Journal of Chinese Universities(Ser.A)

收录：CSTPCD;;北大核心:【北大核心2004】；CSCD:【CSCD2011_2012】；

基金：国家自然科学基金(19731001);校科研基金资助项目(XD20K01211)

语种：中文

中文关键词：流水作业;批处理机;加工总长;NP困难性

外文关键词：flow-shop ; batch machine ; makespan ; NP-hardness

摘要：研究含有批处理机的三台机器流水作业加工总长问题的计算复杂性.不仅考虑了批处理机容量有限的情形,还考虑了批处理机容量无限的情形.证明了当第二台机器是批处理机、其余两台机器是单机时,该问题是NP困难的.至此,含有批处理机的三台机器流水作业加工总长问题在所有情形下的计算复杂性得到了解决.
In this paper, the computational complexity of the three-stage flow-shop with some batch machines to minimize the makespan is studied. Both the situation when batch machines have finite capacity and the situation when batch machines have infinite capacity are considered. When the second machine is a batch machine and the other two are discrete machines, NP-hardness of this problem is proved. So far, the computational complexity of the makespan of the three-stage flow-shop with some batch machines in all situations is completely solved.