| 三机流水作业问题若干特殊情形的NP困难性 |
| |
| 引用本文： | 刘朝晖,俞文魮.三机流水作业问题若干特殊情形的NP困难性[J].运筹学学报,2000,4(1):43-49. |
| |
| 作者姓名： | 刘朝晖 俞文魮 |
| |
| 作者单位： | 华东理工大学数学系与应用数学研究所,上海,200237 |
| |
| 基金项目： | Supported by National Science Foundation of China. |
| |
| 摘 要： | 本文研究以加工总为目标函数的三台机器流水作业问题的特殊情形的计算复杂性，证明了下列情形为ＮＰ困难的：所有工作在第二台机器上有相同的加工时间；所有工作在第一和第三台机器上有相册的加工时间；每个工件至少有一个零工序；每个工件有一个丢失的工序。
|
| 关 键 词： | 时间表 加工时间 NP困难性 三机流水作业问题 |
| 修稿时间： | 1999-08-05 |
NP-Hardness of Some Special Cases of the Three-Machine Flow-Shop Problem |
| |
| ZHAOHUI LIU,WENCI YU.NP-Hardness of Some Special Cases of the Three-Machine Flow-Shop Problem[J].OR Transactions,2000,4(1):43-49. |
| |
| Authors: | ZHAOHUI LIU WENCI YU |
| |
| Institution: | ZHAOHUI LIU
,WENCI YU
(East China University of Science and Technology, Shanghai 200237, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | scheduling flow-shop NP-hardness |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
