Nowadays many industry consider an interval time as a due date instead of precise points in time. In this study, the hybrid flow shop scheduling problem with basic blocking constraint is tackled. Where jobs, if done within a due window, are deemed on time. Therefore, the criterion is to minimize the sum of weighted earliness and tardiness. This variant of the hybrid flowshop problem is not investigated to the best of our knowledge. we introduced a new metaheuristic centered on the iterated greedy approach. to evaluate the proposed method we start by the re-implementation and the comparison of seven well-selected procedures that treat the hybrid flowshop problem. In order to prove the robustness of our method, we evaluated it using a new benchmark of more than 1000 instances. The experimental results demonstrated that the proposed algorithm is effective and produces a very high solution.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021076
Keywords: Hybrid flow shop, scheduling, blocking, iterated greedy, due date window
@article{RO_2021__55_3_1603_0,
author = {Missaoui, Ahmed and Boujelbene, Youn\`es},
title = {An effective iterated greedy algorithm for blocking hybrid flow shop problem with due date window},
journal = {RAIRO. Operations Research},
pages = {1603--1616},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {3},
doi = {10.1051/ro/2021076},
mrnumber = {4272450},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021076/}
}
TY - JOUR AU - Missaoui, Ahmed AU - Boujelbene, Younès TI - An effective iterated greedy algorithm for blocking hybrid flow shop problem with due date window JO - RAIRO. Operations Research PY - 2021 SP - 1603 EP - 1616 VL - 55 IS - 3 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021076/ DO - 10.1051/ro/2021076 LA - en ID - RO_2021__55_3_1603_0 ER -
%0 Journal Article %A Missaoui, Ahmed %A Boujelbene, Younès %T An effective iterated greedy algorithm for blocking hybrid flow shop problem with due date window %J RAIRO. Operations Research %D 2021 %P 1603-1616 %V 55 %N 3 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021076/ %R 10.1051/ro/2021076 %G en %F RO_2021__55_3_1603_0
Missaoui, Ahmed; Boujelbene, Younès. An effective iterated greedy algorithm for blocking hybrid flow shop problem with due date window. RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1603-1616. doi: 10.1051/ro/2021076
[1] , , and , Automatic algorithm design for hybrid flowshop scheduling problems., Eur. J. Oper. Res. 282 (2020) 835–845. | MR | DOI
[2] and , Two efficient nature inspired meta-heuristics solving blocking hybrid flow shop manufacturing problem. Eng. Appl. Artif. Intell. 100 (2021) 104196. | DOI
[3] , , and , Experimental Methods for the Analysis of Optimization Algorithms. Springer (2010). | MR | Zbl | DOI
[4] and , A scheduling problem in blocking hybrid flow shop robotic cells with multiple robots. Comput. Oper. Res. 40 (2013) 2543–2555. | MR | DOI
[5] and , A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Gener. Comput. Syst. 20 (2004) 1083–1095. | DOI
[6] and , Iterated greedy local search methods for unrelated parallel machine scheduling. Eur. J. Oper. Res. 207 (2010) 55–69. | MR | Zbl | DOI
[7] , and , Manufacturing scheduling systems. In: An Integrated View on Models, Methods and Tools (2014) 51–63. | MR
[8] and , Nowy algorytm tabu search dla zagadnienia kolejnościowego przep lywowego. Automatyka/Akademia Górniczo-Hutnicza im. Stanis lawa Staszica w Krakowie 3 (1999) 125–133.
[9] , , and , Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287–326. | MR | Zbl | DOI
[10] and , A survey of machine scheduling problems with blocking and no-wait in process. Oper. Res. 44 (1996) 510–525. | MR | Zbl | DOI
[11] and , Bounding strategies for the hybrid flow shop scheduling problem. Appl. Math. Comput. 217 (2011) 8248–8263. | MR | Zbl
[12] , , and , An effective iterated greedy algorithm for the distributed permutation flowshop scheduling with due windows. Appl. Soft Comput. 96 (2020) 106629. | DOI
[13] , , and , An application of effective genetic algorithms for solving hybrid flow shop scheduling problems. Int. J. Comput. Intell. Syst. 1 (2008) 134–147. | DOI
[14] and , Scheduling hybrid flowshop with sequence-dependent setup times and due windows to minimize total weighted earliness and tardiness. Comput. Ind. Eng. 135 (2019) 780–792. | DOI
[15] , , , and , Solving the multi objective flow shop scheduling problems using an improved nsga-ii. Int. J. Oper. Quant. Manage. 24 (2018) 211–230.
[16] , Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling. Appl. Soft Comput. 12 (2012) 2237–2245. | DOI
[17] , , and , Heuristic algorithms for scheduling hybrid flow shops with machine blocking and setup times. J. Braz. Soc. Mech. Sci. Eng. 40 (2018) 40. | DOI
[18] , , and , An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Syst. Appl. 36 (2009) 9625–9633. | DOI
[19] , , and , Scheduling blocking flowshops with setup times via constraint guided and accelerated local search. Comput. Oper. Res. 109 (2019) 64–76. | MR | DOI
[20] , , , and , An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process. IEEE Trans. Autom. Sci. Eng. 10 (2012) 307–322. | DOI
[21] , , and , Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times. Appl. Math. Comput. 303 (2017) 89–112. | MR
[22] , and , Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows. Comput. Oper. Res. 80 (2017) 50–60. | MR | DOI
[23] , and , A genetic algorithm for the flexible job-shop scheduling problem. Comput. Oper. Res. 35 (2008) 3202–3212. | Zbl | DOI
[24] and , A decomposition algorithm for the single machine total tardiness problem. Oper. Res. Lett. 1 (1982) 177–181. | Zbl | DOI
[25] and , An iterated greedy metaheuristic for the blocking job shop scheduling problem. J. Heurist. 22 (2016) 587–611. | DOI
[26] , and , An improved hybrid multi-objective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines. Int. J. Adv. Manuf. Technol. 49 (2010) 1129–1139. | DOI
[27] , and , An iterated greedy algorithm for the flowshop scheduling problem with blocking. Omega 39 (2011) 293–301. | DOI
[28] , and , An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem. Expert Syst. Appl. 121 (2019) 347–361. | DOI
[29] and , A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur. J. Oper. Res. 177 (2007) 2033–2049. | Zbl | DOI
[30] and , The hybrid flow shop scheduling problem. Eur. J. Oper. Res. 205 (2010) 1–18. | MR | Zbl | DOI
[31] , and , Iterated greedy methods for the distributed permutation flowshop scheduling problem. Omega 83 (2019) 213–222. | DOI
[32] , A scheduling algorithm for flexible flow lines with limited intermediate buffers. Appl. Stoch. Models Data Anal. 9 (1993) 127–138. | DOI
[33] , , and , Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion. Comput. Oper. Res. 77 (2017) 111–126. | MR | DOI
[34] , and , A genetic algorithm for hybrid flowshop problem with mixed blocking constraints. In: IFAC Conference on Manufacturing, Modelling, Management and Control (2013).
[35] , and , Application of em algorithm to hybrid flow shop scheduling problems with a special blocking. In: 2009 IEEE Conference on Emerging Technologies & Factory Automation. IEEE (2009) 1–7.
[36] and , A hbrid flow shop scheduling model for loading outbound containers in container terminals. In: Proceedings of the Eastern Asia Society for Transportation Studies Vol. 6 (The 7th International Conference of Eastern Asia Society for Transportation Studies, 2007). Eastern Asia Society for Transportation Studies (2007) 381.
[37] , , and , Hybrid flow shop problem with blocking and multi-product families in a maritime terminal. In: 2013 10th IEEE International Conference on Networking, Sensing and Control (ICNSC). IEEE (2013) 59–64. | DOI
Cité par Sources :
