Two-machine chain-reentrant flow shop with the no-wait constraint

被引：0
作者：
Amrouche K. [1 ,2 ]
Boudhar M. [2 ]
Sami N. [2 ]
机构：
[1] University of Algiers, 3, 2 Street Ahmed Oueked, Dely Brahim, Algiers
[2] RECITS Laboratory, Faculty of Mathematics, USTHB University, BP 32 Bab-Ezzouar, El-Alia, Algiers
来源：
Amrouche, Karim (amrouche-karim@hotmail.com) | 1600年 / Inderscience Publishers卷 / 14期
关键词：
Chain-reentrant flow shop; Dynamic programming; Heuristics; Mathematical formulation; No-wait constraint; Simulated annealing;
D O I：
10.1504/EJIE.2020.108577
中图分类号：
学科分类号：
摘要：
This paper addresses the chain-reentrant flow shop scheduling problem with two machines and n non-preemptive jobs in the presence of the no-wait constraint; we assume that each job passes from the first machine to the second and returns back to the first machine. The objective is to minimise the makespan. The general problem is NP-hard in the strong sense. Based on a dynamic programming algorithm, we prove that the problem is polynomially solvable when the execution order of the jobs through the machines is a fixed permutation. For the resolution of the general problem, we propose a linear mathematical model, local search heuristics, a simulated annealing metaheuristic and lower bounds with numerical experiments. Copyright © 2020 Inderscience Enterprises Ltd.
引用
收藏
页码：573 / 597
页数：24
相关论文
共 30 条
  • [1] Allahverdi A., Aydilek H., Aydilek A., No-wait flowshop scheduling problem with two criteria
  • [2] total tardiness and makespan, European Journal of Operational Research, (2018)
  • [3] Allahverdi A., A survey of scheduling problems with no-wait in process, European Journal of Operational Research, 255, 3, pp. 665-686, (2016)
  • [4] Amrouche K., Boudhar M., Two machines flow shop with reentrance and exact time lag, RAIRO, Operation Research, 50, 2, pp. 223-232, (2016)
  • [5] Amrouche K., Boudhar M., Bendraouche M., Yalaoui F., Chain-reentrant shop with an exact time lag: New results, International Journal of Production Research, 55, 1, pp. 285-295, (2017)
  • [6] Arenas G.A., Castillo P.A., Mora A.M., Merelo J.J., Laredo J.L.J., Sanchez P.G., Pireto A., Statistical analysis of the parameters of the simulated annealing algorithm, IEEE Congress on Evolutionary Computation, (2010)
  • [7] Framinan J.M., Nagano M.S., Moccellin J.V., An efficient heuristic for total flowtime minimization in no-wait flowshops, International Journal of Advanced Manufacturing Technology, 46, 9-12, pp. 1049-1057, (2010)
  • [8] Behjat S., Salmasi N., Total completion time minimisation of no-wait flowshop group scheduling problem with sequence dependent setup times, European J. Industrial Engineering, 11, 1, pp. 22-48, (2017)
  • [9] Cerny V., Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimisation Theory and Applications, 45, 1, pp. 41-45, (1985)
  • [10] Fondrevelle J., Oulamara A., Portmann M.C., Permutation flowshop scheduling problems with time lags to minimize the weighted sum of machine completion times, International Journal of Production Economics, 33, 1, pp. 168-176, (2007)
123