کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4626250 | 1631784 | 2015 | 22 صفحه PDF | دانلود رایگان |
• 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.
Journal: Applied Mathematics and Computation - Volume 270, 1 November 2015, Pages 312–333