Conventionally, in scheduling problems it is assumed that each job visits each machine once. This paper studies a novel shop scheduling called cycle shop problems where jobs might return to each machine more than once. The problem is first formulated by two mixed integer linear programming models. The characteristics of the problem are analyzed, and it is realized that the problem suffers from a shortcoming called redundancy, i.e., several sequences represents the same schedule. In this regard, some properties are introduced by which the redundant sequences can be recognized before scheduling. Three constructive heuristics are developed. They are based on the shortest processing time first, insertion neighborhood search and non-delay schedules. Then, a metaheuristic based on scatter search is proposed. The algorithms are equipped with the redundancy prevention properties that greatly reduce the computational time of the algorithms. Two sets of experiments are conducted. The proposed model and algorithms are evaluated. The results show the high performance of model and algorithms.
Mots-clés : Scheduling, cycle shop, mixed integer linear programming model, metaheuristic algorithm, constructive heuristics
@article{RO_2019__53_1_111_0,
author = {Naderia, Bahman and Goharib, Sheida},
title = {The cycle shop scheduling: mathematical model, properties and solution algorithms},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {111--128},
publisher = {EDP-Sciences},
volume = {53},
number = {1},
year = {2019},
doi = {10.1051/ro/2017086},
zbl = {1414.90238},
mrnumber = {3904271},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2017086/}
}
TY - JOUR AU - Naderia, Bahman AU - Goharib, Sheida TI - The cycle shop scheduling: mathematical model, properties and solution algorithms JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 111 EP - 128 VL - 53 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2017086/ DO - 10.1051/ro/2017086 LA - en ID - RO_2019__53_1_111_0 ER -
%0 Journal Article %A Naderia, Bahman %A Goharib, Sheida %T The cycle shop scheduling: mathematical model, properties and solution algorithms %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 111-128 %V 53 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2017086/ %R 10.1051/ro/2017086 %G en %F RO_2019__53_1_111_0
Naderia, Bahman; Goharib, Sheida. The cycle shop scheduling: mathematical model, properties and solution algorithms. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 111-128. doi : 10.1051/ro/2017086. http://www.numdam.org/articles/10.1051/ro/2017086/
[1] , Introduction to Sequencing and Scheduling. Wiley, NewYork, USA (1974).
[2] , , , and , Handbook of Scheduling: From Theory to Applications. Springer, Germany (2007). | Zbl
[3] and , Tabu search algorithms for cyclic machine scheduling problems, in The Fifth Metaheuristics International Conference, Japan (2003). | MR | Zbl
[4] and , A polynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line. Oper. Res. Lett. 33 (2005) 274–284. | DOI | MR | Zbl
[5] , and , Hybrid tabu search for re-entrant permutation flow-shop scheduling problem. Expert Syst. Appl. 34 (2008) 1924–1930. | DOI
[6] , and , A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem. Expert Syst. Appl. 34 (2008) 570–577. | DOI
[7] , , and , Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm. Comput. Ind. Eng. 61 (2011) 529–541. | DOI
[8] , and , New multi-objective method to solve reentrant hybrid flow shop scheduling problem. Eur. J. Oper. Res. 203 (2010) 22–31. | DOI | MR | Zbl
[9] , and , A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput. Oper. Res. 35 (2008) 2892–2907. | DOI | MR | Zbl
[10] , and , Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan. Appl. Soft Comput. 11 (2011) 4530–4539. | DOI
[11] , and , A scheduling algorithm for the reentrant shop: an application in semiconductor manufacture. Int. J. Adv. Manuf. Technol. 35 (2007) 566–574. | DOI
[12] and , A scatter search algorithm for the distributed flowshop scheduling problem. Eur. J. Oper. Res. 239 (2014) 323–334. | DOI | MR | Zbl
[13] and , Permutation flowshops in group scheduling with sequence-dependent setup times. Eur. J. Ind. Eng. 6 (2012) 177–198. | DOI
[14] , and , Algorithms for a realistic variant of flowshop scheduling. Comput. Oper. Res. 37 (2010) 236–246. | DOI | MR | Zbl
[15] , and , A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. Omega 11 (1983) 91–95. | DOI
[16] , and , Using genetic algorithm for job-shop scheduling problems with reentrant product flows, in 7th IEEE International Conference on Emerging Technologies and Factory Automation, Spain (1999).
[17] , A study of integer programming formulations for scheduling problems. Int. J. Syst. Sci. 28 (1997) 33–41. | DOI | Zbl
[18] , Scheduling Theory, Algorithms, and Systems, 3rd edn. LLC, Springer, New York (2008). | MR | Zbl
[19] , Taguchi Techniques for Quality Engineering. McGraw-Hill, USA (1989).
[20] and , A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization. Int. J. Adv. Manuf. Technol. (2009) 44 781–794. | DOI
[21] , and , A review of production planning and scheduling models in the semiconductor industry, part 1: system characteristics, performance evaluation and production planning. IIE Trans. 24 (1992) 47–61. | DOI
[22] , and , Scheduling of a hub reentrant job shop to minimize makespan. Int. J. Adv. Manuf. Technol. 56 (2011) 743–753. | DOI
Cité par Sources :
