文献类型：期刊文献

中文题名：含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性

英文题名：Strong NP-Hardness of the Makespan of the Three-Stage Flow-Shop with Some Batch Machines in Some Cases

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

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

年份：2003

卷号：7

期号：4

起止页码：86

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

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

基金：自然科学基金;校科研基金资助项目.

语种：中文

中文关键词：批处理机;强NP困难性;单机;流水作业;多项式变换;排序问题

外文关键词：OR, scheduling, flow-shop, batch machine, makespan, NP-hardness

摘要：本文研究含有批处理机的三台机器流水作业加工总长问题在某些情形下的计算复杂性.在批处理机上同时加工的工件组成一个工件批,一个工件批的所有工件同时开始、同时结束.当批处理机的容量有限时,我们证明了下列情形为强NP困难的;第一台机器是批处理机、其余两台机器是单机;第二台机器是单机、其余两台机器是批处理机;第三台机器是批处理机、其余两台机器是单机.
In this paper, we investigate the computational complexity of the makespan of the three-stage flow-shop with some batch machines in some cases. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. When the batch machine has finite capacity, strong NP-hardness is established for each of the following cases: the first machine is a batch machine and the other two are discrete machines; the second machine is a discrete machine and the other two are batch machines; the third machine is a batch machine and the other two are discrete machines.