文献类型：期刊文献

中文题名：三机流水作业问题若干特殊情形的NP困难性(英文)

英文题名：NP-Hardness of Some Special Cases of the Three-Machine Flow-Shop Problem

作者：刘朝晖[1];俞文魮[1]

机构：[1]华东理工大学数学系与应用数学研究所,上海200237

年份：2000

卷号：4

期号：1

起止页码：43

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

收录：CSTPCD;;CSCD:【CSCD2011_2012】；

基金：National Science Foundation of China.

语种：中文

中文关键词：时间表;加工时间;NP困难性;三机流水作业问题

外文关键词：scheduling, flow-shop, NP-hardness

摘要：本文研究以加工总长为目标函数的三台机器流水作业问题的特殊情形的计算复杂性，证明了下列情形为ＮＰ困难的：所有工件在第二台机器上有相同的加工时间；所有工件在第一和第三台机器上有相同的加工时间；每个工件至少有一个零工序；每个工件有一个丢失的工序。
In this paper, we investigate the computational complexity of some special cases of the three-machine flow-shop problem to minimize the makespan. NP-hardness is estab- lished for each of the following cases: all jobs require the same processing time on the second machine; all jobs require the same processing time on the first machine and the last machine; each job has at least one zero operation; each job contains a missing operation.