Non-permutation flow shop scheduling with order acceptance and weighted tardiness

• Published in: Applied mathematics and computation 2015-11, Vol.270, p.312-333
• Main Authors: Xiao, Yiyong, Yuan, Yingying, Zhang, Ren-Qian, Konak, Abdullah
• Format: Article
• Language: English
• Subjects: Flow shop scheduling; Genetic algorithm; Order acceptance; Weighted tardiness
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2015.08.011

•Model the problem of non-permutation flow shop scheduling with order acceptance.•The model is transformed to linear MIP that is optimally solved by commercial solver.•Theorems that are favorable for developing algorithms are presented.•An efficient two-phase genetic algorithm (TP-GA) is proposed.•The heuristic yields high quality non-permutation solutions. This paper studies the non-permutation solution for the problem of flow shop scheduling with order acceptance and weighted tardiness (FSS-OAWT). We formulate the problem as a linear mixed integer programming (LMIP) model that can be optimally solved by AMPL/CPLEX for small-sized problems. In addition, a non-linear integer programming (NIP) model is presented to design heuristic algorithms. A two-phase genetic algorithm (TP-GA) is developed to solve the problem of medium and large sizes based on the NIP model. The properties of FSS-OAWT are investigated and several theorems for permutation and non-permutation optimum are provided. The performance of the TP-GA is studied through rigorous computational experiments using a large number of numeric instances. The LMIP model is used to demonstrate the differences between permutation and non-permutation solutions to the FSS-OAWT problem. The results show that a considerably large portion of the instances have only an optimal non-permutation schedule (e.g., 43.3% for small-sized), and the proposed TP-GA algorithms are effective in solving the FSS-OAWT problems of various scales (small, medium, and large) with both permutation and non-permutation solutions.