| 一类两阶段杂交流水作业的近似算法? |
| |
| 引用本文： | 魏麒,蒋义伟. 一类两阶段杂交流水作业的近似算法?[J]. 软件学报, 2013, 0(5) |
| |
| 作者姓名： | 魏麒 蒋义伟 |
| |
| 作者单位： | 1. 浙江大学 宁波理工学院,浙江 宁波,315100
2. 浙江理工大学 理学院,浙江 杭州,310018 |
| |
| 基金项目： | 国家自然科学基金，浙江省自然科学基金 |
| |
| 摘 要： | 讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务：第1个任务可以在任何一台机器上加工，第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时，两个任务之间不能有停顿，则称其为不可等待的模型，记作 NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工，则称其为允许等待的模型，记作SHFS.对于SHFS模型，在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型，首先证明它是NP-难的，并且给出了一种最坏情况界为5/3的多项式时间近似算法.
|
| 关 键 词： | 流水作业 计算复杂性 近似算法 最坏情况界 最后完工工件完工时间 |
Approximation Algorithms for a Two-Stage Hybrid Flow Shop |
| |
| WEI Qi , JIANG Yi-Wei. Approximation Algorithms for a Two-Stage Hybrid Flow Shop[J]. Journal of Software, 2013, 0(5) |
| |
| Authors: | WEI Qi JIANG Yi-Wei |
| |
| Abstract: | |
| |
| Keywords: | flowshop scheduling computational complexity approximation algorithm worst-case ratio makespan |
| 本文献已被 万方数据 等数据库收录！ |
