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

Two-Stage Flowshop Scheduling Problems with Identical and Batch Processors

作　　者：王文伟[1] 何龙敏[1] 孙世杰[1] 

机构地区：[1]上海大学理学院,上海200444

出　　处：《上海大学学报（自然科学版）》2009年第4期380-387,共8页Journal of Shanghai University:Natural Science Edition

基　　金：国家自然科学基金资助项目(60874039);上海大学创新基金资助项目

摘　　要：讨论一类二阶段流水作业问题,其中第一阶段由m台同型机组成,第二阶段为1台批处理机,目标函数是最小化各工件完工时间之和.工件在同型机和批处理机上分别有相同加工时间的情况下,给出了计算量为O(n3)的最优算法.相应工件在同型机上有相同加工时间,但在批处理机上具有任意加工时间的情况下,指出其强NP-hard后给出了近似算法,并作了性能比分析.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（ n^3） 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[理学—运筹学与控制论]