| 同型机和批处理机组成的二阶段流水作业问题 |
| |
| 引用本文： | 王文伟,何龙敏,孙世杰.同型机和批处理机组成的二阶段流水作业问题[J].上海大学学报(自然科学版),2009,15(4):380-387. |
| |
| 作者姓名： | 王文伟 何龙敏 孙世杰 |
| |
| 作者单位： | 上海大学 理学院,上海 200444 |
| |
| 基金项目： | 国家自然科学基金资助项目，上海大学创新基金 |
| |
| 摘 要： | 讨论一类二阶段流水作业问题,其中第一阶段由m台同型机组成,第二阶段为1台批处理机,目标函数是最小化各工件完工时间之和.工件在同型机和批处理机上分别有相同加工时间的情况下，给出了计算量为O(n3)的最优算法.相应工件在同型机上有相同加工时间,但在批处理机上具有任意加工时间的情况下，指出其强NP-hard后给出了近似算法，并作了性能比分析.
|
| 关 键 词： | 排序 流水作业 同型机 批处理机 |
| 收稿时间： | 2008-05-15 |
Two-Stage Flowshop Scheduling Problems with Identical and Batch Processors |
| |
| WANG Wen-wei,HE Long-min,SUN Shi-jie.Two-Stage Flowshop Scheduling Problems with Identical and Batch Processors[J].Journal of Shanghai University(Natural Science),2009,15(4):380-387. |
| |
| Authors: | WANG Wen-wei HE Long-min SUN Shi-jie |
| |
| Affiliation: | College of Sciences, Shanghai University, Shanghai 200444, China |
| |
| Abstract: | This paper considers a two-stage flowshop scheduling problems with m identical parallel machines at stage one and a batch processor at stage two, and minimizes the total completion time. We get optimal solution in time of the order O(n3) when all jobs have the same processing time at stage one and stage two respectively. In the case that all jobs have same processing time at stage one but have arbitrary processing time at stage two, we analyze the worst-case of an approximation algorithm and show that the problem is strongly NP-hard in this case. |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《上海大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《上海大学学报(自然科学版)》下载全文 |
|
