| 含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性 |
| |
| 引用本文： | 成岗,鲁习文.含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性[J].运筹学学报,2003,7(4):86-96. |
| |
| 作者姓名： | 成岗 鲁习文 |
| |
| 作者单位： | 华东理工大学数学系,上海,200237 |
| |
| 基金项目： | 自然科学基金，校科研基金资助项目. |
| |
| 摘 要： | 本文研究含有批处理机的三台机器流水作业加工总长问题在某些情形下的计算复杂性。在批处理机上同时加工的工件组成一个工件批，一个工件批的所有工件同时开始、同时结束。当批处理机的容量有限时，我们证明了下列情形为强NP困难的：第一台机器是批处理机、其余两台机器是单机；第二台机器是单机、其余两台机器是批处理机；第三台机器是批处理机、其余两台机器是单机。
|
| 关 键 词： | 批处理机 强NP困难性 单机 流水作业 多项式变换 排序问题 |
| 修稿时间： | 2003年2月10日 |
Strong NP-Hardness of the Makespan of the Three-Stage Flow-Shop with Some Batch Machines in Some Cases |
| |
| GANG CHENG XIWEN LU East China University of Science and Technology,Shanghai ,China..Strong NP-Hardness of the Makespan of the Three-Stage Flow-Shop with Some Batch Machines in Some Cases[J].OR Transactions,2003,7(4):86-96. |
| |
| Authors: | GANG CHENG XIWEN LU East China University of Science and Technology Shanghai China |
| |
| Institution: | GANG CHENG XIWEN LU East China University of Science and Technology,Shanghai 200237,China. |
| |
| Abstract: | 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. |
| |
| Keywords: | OR scheduling flow-shop batch machine makespan NP-hardness |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
