批处理机和同型机组成的混合流水作业问题  

Flexible flowshop problem with batch machine and identical processors

作　　者：刘冬梅[1] 何龙敏[1] 程明宝[2] 

机构地区：[1]上海大学理学院,上海200444 [2]广东工业大学管理学院,广州510520

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

基　　金：国家自然科学基金资助项目(11372170;60874039);教育部人文社会科学青年基金资助项目(11YJCZH019);上海市重点学科建设资助项目(S30104)

摘　　要：讨论目标函数为最小完工时间之和的两阶段混合流水作业问题,第一阶段为批处理机且工件在其上的加工时间相等,第二阶段为同型机且工件在其上的加工时间任意.指出该问题为强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.

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

分 类 号：O223[理学—运筹学与控制论]