| 带运输时间的Flow-shop时间表问题 |
| |
| 引用本文： | 时凌. 带运输时间的Flow-shop时间表问题[J]. 湖北民族学院学报(自然科学版), 2004, 22(2): 56-59 |
| |
| 作者姓名： | 时凌 |
| |
| 作者单位： | 湖北民族学院理学院 湖北 |
| |
| 基金项目： | 湖北省教育厅重点项目(2002X13). |
| |
| 摘 要： | 研究带运输时间的流水作业时间表问题，同一工件在一台机器上完工之后，在另一台机器上开始加工，且运输过程只能由机器R完成，证明在只有两台机器的情况下，该问题是强NP-困难的，并构造一个启发式算法，证明该算法的紧界为2。
|
| 关 键 词： | 运输时间 流水作业 复杂性 NP-困难 |
| 文章编号： | 1008-8423(2004)02-0056-04 |
| 修稿时间： | 2003-11-19 |
Flow- shop Scheduling Problem with Transportation Times and A Single Robot |
| |
| SHI Ling. Flow- shop Scheduling Problem with Transportation Times and A Single Robot[J]. Journal of Hubei Institute for Nationalities(Natural Sciences), 2004, 22(2): 56-59 |
| |
| Authors: | SHI Ling |
| |
| Abstract: | In this paper,we study flow -shop scheduling problem with transportation times and a single robot. Addi-tionaly, transportation times are considered if a job changes from one machine to another and all transportations have to be done by a single robot. For the two - machine case, we prove that this problem is NP - hard in the strong sense and an improved heuristic algorithm guarantees a tight worst - case ratio of 2. |
| |
| Keywords: | transportation time flow - shop scheduling problem complexity NP - hard |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
