Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage

被引：0
作者：
Jian-ming Dong
Jue-liang Hu
Yong Chen
机构：
[1] Zhejiang Sci-Tech University,Department of Mathematics
[2] Hangzhou Dianzi University,Institute of Operational Research and Cybernetics
来源：
Applied Mathematics-A Journal of Chinese Universities | 2013年 / 28卷
关键词：
hybrid flow shop; open shop; Heuristic algorithm; 90B35; 90C27;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper considers a scheduling problem in two-stage hybrid flow shop, where the first stage consists of two machines formed an open shop and the other stage has only one machine. The objective is to minimize the makespan, i.e., the maximum completion time of all jobs. We first show the problem is NP-hard in the strong sense, then we present two heuristics to solve the problem. Computational experiments show that the combined algorithm of the two heuristics performs well on randomly generated problem instances.
引用
收藏
页码：358 / 368
页数：10
相关论文
共 39 条
[1]  
Dessouky M M(1998)Flow shop scheduling with identical jobs and uniform parallel machines European J Oper Res 109 620-631
[2]  
Dessouky M I(1976)Open shop scheduling to minimize finish time J ACM 23 665-679
[3]  
Verma S K(1996)Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard European J Oper Res 89 172-175
[4]  
Gonzales T(1998)A two-stage hybrid flow shop with uniform machines and setup times Math Comput Modelling 27 27-45
[5]  
Sahni S(1954)Optimal two- and three-machine production schedules with setup times included Naval Res Logist 1 61-68
[6]  
Hoogeveen J(1997)A comparison of sequencing rules in static and dynamic hybrid flow systems Internat J Production Res 35 1359-1384
[7]  
Lenstra J(1997)A note on scheduling hybrid flow systems Internat J Prod Res 35 1491-1494
[8]  
Veltman B(2006)A note on makespan minimization in two-stage flexible flow shops with uniform machines European J Oper Res 175 1321-1327
[9]  
Huang W(1994)Minimizing makespan in hybrid flowshops Oper Res Lett 16 149-158
[10]  
Li S(1999)Hybrid flow shop scheduling: A survey Comput Ind Eng 37 57-61
1234