| 带不可用时间段的不允许等待柔性流水排序问题 |
| |
| 引用本文： | 王海明,刘吉红,王庆磊. 带不可用时间段的不允许等待柔性流水排序问题[J]. 兰州大学学报(自然科学版), 2007, 43(1): 130-134 |
| |
| 作者姓名： | 王海明 刘吉红 王庆磊 |
| |
| 作者单位： | 兰州大学数学与统计学院,甘肃 兰州 730000;兰州大学数学与统计学院,甘肃 兰州 730000;兰州大学数学与统计学院,甘肃 兰州 730000 |
| |
| 摘 要： | 给出了极小化时间表长带不可用时间段限制的不允许等待柔性流水车间排序问题的模型,并对其算法复杂性进行分析.分析的结果表明,该问题在几乎所有情况下都不存在具有有限最坏比的多项式时间算法.
|
| 关 键 词： | 不允许等待 柔性 流水车间 APX-困难 |
| 文章编号： | 0455-2059（2007）01-0130-05 |
| 修稿时间： | 2005-05-102006-02-16 |
Minimizing the makespan in the no-wait flexible flowshop problem with availability constraint |
| |
| WANG Hai-ming,LIU Ji-hong,WANG Qing-lei. Minimizing the makespan in the no-wait flexible flowshop problem with availability constraint[J]. Journal of Lanzhou University(Natural Science), 2007, 43(1): 130-134 |
| |
| Authors: | WANG Hai-ming LIU Ji-hong WANG Qing-lei |
| |
| Affiliation: | School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, China |
| |
| Abstract: | 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. |
| |
| Keywords: | no-wait flexible flowshop APX-hard |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
