带不可用时间段的不允许等待柔性流水排序问题  

Minimizing the makespan in the no-wait flexible flowshop problem with availability constraint

作　　者：王海明[1] 刘吉红[1] 王庆磊[1] 

机构地区：[1]兰州大学数学与统计学院,甘肃兰州730000

出　　处：《兰州大学学报（自然科学版）》2007年第1期130-134,共5页Journal of Lanzhou University(Natural Sciences)

基　　金：国家自然科学基金资助项目(10471058)

摘　　要：给出了极小化时间表长带不可用时间段限制的不允许等待柔性流水车间排序问题的模型,并对其算法复杂性进行分析．分析的结果表明,该问题在几乎所有情况下都不存在具有有限最坏比的多项式时间算法．In this paper we study the no-wait flexible flow shop scheduling problem with availability constraint to minimize the makespan. We explore the approximability of our model and prove that the problem are almost all APX-hard, i.e, none polynomial time algorithm with a finite worst case bound can be found unless P = NP.

关 键 词：不允许等待 柔性 流水车间 APX-困难 

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