同型机和批处理机组成的二阶段流水作业问题

上海大学学报(自然科学版) ›› 2009, Vol. 15 ›› Issue (4): 380-387.

同型机和批处理机组成的二阶段流水作业问题

王文伟何龙敏孙世杰

上海大学理学院,上海 200444

收稿日期:2008-05-15 出版日期:2009-08-30 发布日期:2009-06-30
通讯作者: 何龙敏(1958～),男,副教授,博士,研究方向为组合最优化. E-mail:hlm@shu.edu.cn
基金资助:
国家自然科学基金资助项目（60874039）;上海大学创新基金资助项目

Two-Stage Flowshop Scheduling Problems with Identical and Batch Processors

College of Sciences, Shanghai University, Shanghai 200444, China

Received:2008-05-15 Online:2009-08-30 Published:2009-06-30

摘要/Abstract

摘要：

讨论一类二阶段流水作业问题,其中第一阶段由m台同型机组成,第二阶段为1台批处理机,目标函数是最小化各工件完工时间之和.工件在同型机和批处理机上分别有相同加工时间的情况下，给出了计算量为O(n3)的最优算法.相应工件在同型机上有相同加工时间,但在批处理机上具有任意加工时间的情况下，指出其强NP-hard后给出了近似算法，并作了性能比分析.

关键词: 排序；流水作业；同型机；批处理机

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.

中图分类号:

O223

王文伟何龙敏孙世杰. 同型机和批处理机组成的二阶段流水作业问题[J]. 上海大学学报(自然科学版), 2009, 15(4): 380-387.

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 Edition）, 2009, 15(4): 380-387.