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

作     者：DONG Jian-ming HU Jue-liang CHEN Yong 

作者机构：Department of MathematicsZhejiang Sci-Tech University Institute of Operational Research and Cybernetics Hangzhou Dianzi University 

出 版 物：《Applied Mathematics(A Journal of Chinese Universities)》 (高校应用数学学报（英文版）（B辑）)

年 卷 期：2013年第28卷第3期

页      面：358-368页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 0701[理学-数学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Supported by the National Natural Science Foundation of China(11071220,11001242,11201428) Zhejiang Provincial Natural Science Foundation of China(LY13A010015) Educational Commission of Zhejiang Province of China(Y201019076) 

主　　题：hybrid flow shop open shop Heuristic algorithm. 

摘      要：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.