作　　者： ; ; ;

机构地区： 上海大学理学院

出　　处： 《应用数学与计算数学学报》 2013年第3期295-305,共11页

摘　　要： 讨论目标函数为最小完工时间之和的两阶段混合流水作业问题,第一阶段为批处理机且工件在其上的加工时间相等,第二阶段为同型机且工件在其上的加工时间任意.指出该问题为强NP-hard后,给出一近似算法并证明其性能比小于等于2. This paper analyzes the total completing time minimization m a two- stage flexible flowshop scheduling problem. All jobs have the same processing time at stage one, which is composed of a batch machine, and have arbitrary processing time at stage two, which is composed of rn identical processors. It is pointed out that the problem is strongly NP-hard, and then a heuristic algorithm H is provided. It is proved hat the performance ratio of the algorithm is less than or equal to 2.

关 键 词： 排序 混合流水作业 批处理机 同型机 性能比

领　　域： [理学] [理学]