DOI:
https://doi.org/10.14483/23448393.21162Published:
2024-01-13Issue:
Vol. 29 No. 1 (2024): January-AprilSection:
Computational IntelligenceTransgenic Algorithm Applied to the Job Shop Rescheduling Problem
Algoritmo transgénico aplicado al Job Shop Rescheduling Problem
Keywords:
disruptions, efficiency, stability, job shop, rescheduling, transgenic algorithm (en).Keywords:
interrupciones, eficiencia, estabilidad, job shop, rescheduling, algoritmo transgénico (es).Downloads
Abstract (en)
Context: Job sequencing has been approached from a static perspective, without considering the occurrence of unexpected events that might require modifying the schedule, thereby affecting its performance measures.
Method: This paper presents the development and application of a genetic algorithm to the Job Shop Rescheduling Problem (JSRP), a reprogramming of the traditional Job Shop Scheduling Problem. This novel approach seeks to repair the schedule in such a way that theoretical models accurately represent real manufacturing environments.
Results: The experiments designed to validate the algorithm aim to apply five classes of disruptions that could impact the schedule, evaluating two performance measures. This experiment was concurrently conducted with a genetic algorithm from the literature in order to facilitate the comparison of results. It was observed that the proposed approach outperforms the genetic algorithm 65% of the time, and it provides better stability measures 98% of the time.
Conclusions: The proposed algorithm showed favorable outcomes when tested with well-known benchmark instances of the Job Shop Scheduling Problem, and the possibility of enhancing the tool's performance through simulation studies remains open.
Abstract (es)
Contexto: La secuenciación de trabajos ha sido abordada desde un enfoque estático, sin considerar la aparición de eventos inesperados que requieran modificar el cronograma, lo que incide en sus medidas de desempeño.
Método: Este artículo expone el desarrollo y aplicación de un algoritmo transgénico al Job Shop Rescheduling Problem (JSRP), una reprogramación del tradicional Job Shop Scheduling Problem. Este enfoque novedoso busca reparar el cronograma de modo que los modelos teóricos representen los entornos de manufactura reales.
Resultados: Los experimentos diseñados para validar el algoritmo pretenden aplicar cinco clases de interrupciones que pueden afectar el cronograma, evaluando dos medidas de desempeño. Este experimento se realizó simultáneamente en un algoritmo genético de la literatura para facilitar la comparación de los resultados. Se observó que el enfoque propuesto tiene un desempeño superior al del algoritmo genético el 65 % de las veces y lo supera en la medida de estabilidad el 98 % de las veces.
Conclusiones: El algoritmo propuesto mostró buenos resultados al ser probado con instancias de comparación reconocidas del Job Shop Scheduling Problem (JSSP), y queda abierta la posibilidad de mejorar el desempeño de la herramienta por medio de estudios de simulación.
References
J. K. Lenstra and A. H. G. R. Kan, "Computational complexity of discrete optimization problems," A. Discrete Math., vol. 4, 2005, pp. 121-140. https://doi.org/10.1016/S0167-5060(08)70821-5
J. R. King, "The theory-practice gap in job-shop scheduling," Prod. Eng., vol. 55, no. 3, pp. 137-143, 1976. https://doi.org/10.1049/tpe.1976.0044
G. E. Vieira, J. W. Herrmann, and E. Lin, "Resheduling manufacturing system: A framework of strategies, policies, and methods," J. Sched., vol. 6, no. 1, pp. 39-62, 2003. https://doi.org/10.1023/A:1022235519958
H.-L. Fang, P. Ross, and D. Corne, "A promising genetic algorithm approach to job-shop scheduling, rescheduling, and open-shop scheduling problems," in Fifth Int. Conf. Genet. Algorithms, no. 623, pp. 375-382, 1993.
H. Li, Z. Li, L. X. Li, and B. Hu, "A production rescheduling expert simulation system," Eur. J. Oper. Res., vol. 124, no. 2, pp. 283-293, 2000. https://doi.org/10.1016/S0377-2217(99)00381-1
Y.-C. E. Li and W. H. Shaw, "Simulation modeling of a dynamic job shop rescheduling with machine availability constraints," Comput. Ind. Eng., vol. 35, no. 1-2, pp. 117-120, 1998. https://doi.org/10.1016/S0360-8352(98)00034-5
P. Moratori, S. Petrovic, and A. Vázquez, "Match-up strategies for job shop rescheduling," in Int. Conf. Ind. Eng. Other App. Applied Intel. Sys., 2008, pp. 119-128. https://doi.org/10.1007/978-3-540-69052-8_13
R. E. M. Bastos, "Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação," doctoral thesis Universidade Federal do Rio Grande do Norte, Natal, 2023.
E. Gouvêa and M. Goldbarg, "ProtoG: A computational transgenetic algorithm," in MIC 2001-4th Metaheuristics, 2001, pp. 625-630.
M. Goldbarg, E. Goldbarg, and P. Quadr, "Transgenética computacional: Uma aplicação ao problema quadrático de alocação," Pesqui. Operacional, vol. 22, pp. 359-386, 2002. https://doi.org/10.1590/S0101-74382002000300005
E. F. G. Goldbarg, M. C. Goldbarg, and L. B. Bagi, "Transgenetic algorithm: A new evolutionary perspective for heuristics design," in Proc. GECCO 2007 Genet. Evol. Comput. Conf. Companion Mater., pp. 2701-2708, 2007. https://doi.org/10.1145/1274000.1274040
M. C. Goldbarg and E. Gouvêa, "Extra-intracellular transgenetic algorithm applied to the graph coloring problem," Design, pp. 321-326, 2001.
E. F. G. Goldbarg, M. C. Goldbarg, and W. E. Costa, "A transgenetic algorithm for the permutation flow-shop sequencing problem," WSEAS Trans. Syst., vol. 1, no. 3, pp. 40-45, 2004.
E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys, "Sequencing and scheduling: Algorithms and complexity," Handbooks Oper. Res. Manag. Sci., vol. 4, pp. 445-522, 1993. https://doi.org/10.1016/S0927-0507(05)80189-6
M. L. Pinedo, Scheduling: Theory, algorithms, and systems, 6th ed., New York, NY, USA: Springer, 2022. https://doi.org/10.1007/978-3-031-05921-6
R. Cheng, M. Gen, and Y. Tsujimura, "A tutorial survey of job-shop scheduling problems using genetic algorithms. I. Representation," Comput. Ind. Eng., vol. 30, no. 4, pp. 983-997, 1996. https://doi.org/10.1016/0360-8352(96)00047-2
V. Suresh and D. Chaudhuri, "Dynamic scheduling: A survey of research," Int. J. Prod. Economics, vol. 32, no. 1, pp. 53-63, 1993. https://doi.org/10.1016/0925-5273(93)90007-8
Y. An, X. Chen, K. Gao, L. Zhang, Y. Li, and Z. Zhao, "A hybrid multi-objective evolutionary algorithm for solving an adaptive flexible job-shop rescheduling problem with real-time order acceptance and condition-based preventive maintenance," Expert Syst. App., vol. 212, art. 118711, Feb. 2023. https://doi.org/10.1016/j.eswa.2022.118711
C. Bierwirth and D. C. Mattfeld, "Production scheduling and rescheduling with genetic algorithms," Evol. Comput., vol. 7, no. 1, pp. 1-17, 1999. https://doi.org/10.1162/evco.1999.7.1.1
S. F. Smith, "Reactive scheduling systems," in Intelligent scheduling systems, New York, NY, USA: Springer, 1995, pp. 155-192. https://doi.org/10.1007/978-1-4615-2263-8_7
J. C. Bean, J. R. Birge, J. Mittenthal, and C. E. Noon, "Matchup scheduling with multiple resources, release dates and disruptions," Oper. Res., vol. 39, no. 3, pp. 470-483, 1991. https://doi.org/10.1287/opre.39.3.470
Y. Zhang and F. Tao, Optimization of manufacturing systems using the internet if things, London, UK: Academic Press, 2016.
R.-K. Li, Y.-T. Shyu, and S. Adiga, "A heuristic rescheduling algorithm for computer-based production scheduling systems," Int. J. Prod. Res., vol. 31, no. 8, pp. 1815-1826, 1993. https://doi.org/10.1080/00207549308956824
H.-H. Wu and R.-K. Li, "A new rescheduling method for computer based scheduling systems," Int. J. Prod. Res., vol. 33, no. 8, pp. 2097-2110, 1995. https://doi.org/10.1080/00207549508904804
L. K. Church and R. Uzsoy, "Analysis of periodic and event-driven rescheduling policies in shops," Int. J. Comput. Integr. Manuf., vol. 5, no. 3, pp. 153-163, 1992. https://doi.org/10.1080/09511929208944524
G. E. Vieira, J. W. Herrmann, and E. Lin, "Analytical models to predict the performance of a single-machine system under periodic and event-driven rescheduling strategies," Int. J. Prod. Res., vol. 38, no. 8, pp. 1899-1915, 2000. https://doi.org/10.1080/002075400188654
M. Tomassini, "A survey of genetic algorithms," in Annual reviews of computational physics III, X., Ed., Singapore: World Scientific, 1995, pp. 87-118. https://doi.org/10.1142/9789812830647_0003
J. H. Holland et al., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, Cambridge, MA, USA: MIT Press, 1992. https://doi.org/10.7551/mitpress/1090.001.0001
Z. H. Ahmed, "A hybrid genetic algorithm for the bottleneck traveling salesman problem," ACM Trans. Embedded Comp. Syst., vol. 12, no. 1, pp. 1-10, 2013. https://doi.org/10.1145/2406336.2406345
G. M. Morris et al., "Automated docking using a Lamarckian genetic algorithm and an empirical binding free energy function," J. Comput. Chem., vol. 19, no. 14, pp. 1639-1662, 1998. https://doi.org/10.1002/(SICI)1096-987X(19981115)19:14<1639::AID-JCC10>3.0.CO;2-B
P. Moscato and C. Cotta, "A gentle introduction to memetic algorithms," in Handbook of Metaheuristics, Boston, MA, USA: Kluwer Academic Publishers, 2003, pp. 105-144. https://doi.org/10.1007/0-306-48056-5_5
N. Krasnogor and J. Smith, "A tutorial for competent memetic algorithms: Model, taxonomy, and design issues," IEEE Trans. Evol. Comput., vol. 9, no. 5, pp. 474-488, Oct. 2005. https://doi.org/10.1109/TEVC.2005.850260
H. C. Plotkin, "Non-genetic transmission of information: Candidate cognitive processes and the evolution of culture," Behav. Processes, vol. 35, no. 1, pp. 207-213, 1995. https://doi.org/10.1016/0376-6357(95)00056-9
E. Chattoe-Brown, "Just how (un)realistic are evolutionary algorithms as representations of social processes?" J. Artif. Soc. Soc. Simul., vol. 1, no. 3, pp. 1-2, 1998.
P. Merz and B. Freisleben, "A comparison of memetic algorithms, tabu search, and ant colonies for the quadratic assignment problem," in 1999 Cong. Evol. Comp.-CEC99 (Cat. No. 99TH8406), 1999, vol. 3, pp. 2063-2070.
N. J. Radcliffe and P. D. Surry, "Formal memetic algorithms," Evolutionary Computing: AISB Workshop, 1994. https://doi.org/10.1007/3-540-58483-8_1
R. Wright, "Nonzero: The logic of human destiny," Vintage, vol. 46, no. 46, art. 11, 2002.
E. O. Wilson, "Consilience: The unity of knowledge," Vintage, vol. 31, 1999.
A. O. Barboza, "Simulação e técnicas da computação evolucionária aplicadas a problemas de programação linear inteira mista," doctoral thesis, Universidade Tecnológica Federal do Paraná, Curitiba, 2005.
Goldbarg, E. F. G., Castro, M. P., and Goldbarg M. C., "A transgenetic algorithm for the gas network pipe sizing problem," Computational Methods, vol. 1, pp. 893-904, 2006.
J. S. Dhingra, K. L. Musser, and G. L. Blankenehip, "Reactive operations scheduling for flexible manufacturing systems," in 24th Conf. Winter Sim., 1993. https://doi.org/10.1145/167293.167745
A. Dutta, "Reacting to scheduling exceptions in FMS environments," IIE Trans., vol. 22, no. 4, pp. 300-314, 1990. https://doi.org/10.1080/07408179008964185
V. Subramaniam and A. S. Raheja, "mAOR: A heuristic-based reactive repair mechanism for job shop schedules," Int. J. Adv. Manuf. Technol., vol. 22, no. 9-10, pp. 669-680, 2003. https://doi.org/10.1007/s00170-003-1601-6
A. Arisha, P. Young, and M. El Baradie, "Job shop scheduling problem: An overview," in Int. Conf. Flex. Autom. Intell. Manuf. (FAIM 01), 2001, pp. 682-693.
H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, Englewood Cliffs, NJ, USA: Prentice Hall, 1963.
J. Adams, E. Balas, and D. Zawack, "The shifting bottleneck procedure for job shop scheduling," Manage. Sci., vol. 34, no. 3, pp. 391-401, Mar. 1988. https://doi.org/10.1287/mnsc.34.3.391
T. Yamada and R. Nakano, "A genetic algorithm applicable to large-scale job-shop problems," Parallel Prob. Solv. Nature, vol. 2, pp. 283-292, 1992.
D. Applegate and W. J. Cook, "A computational study of the job-shop scheduling problem," INFORMS J. Comput., vol. 3, pp. 149-156, 1991. https://doi.org/10.1287/ijoc.3.2.149
S. Lawrence, "Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques," graduate thesis, Carnegie-Mellon University, 1984.
E. Taillard, "Benchmarks for basic scheduling problems," Eur. J. Oper. Res., vol. 64, no. 2, pp. 278-285, 1993. https://doi.org/10.1016/0377-2217(93)90182-M
M. Zweben and M. Fox, Intelligent scheduling, San Francisco, CA, USA: Morgan Kaufman Publishers Inc., 1994.
G. A. Deac and D. T. Lancu, "Trading strategy hyper-parameter optimization using genetic algorithm" in 24th Int. Conf. Control Syst. Comp. Sci. (CSCS), 2023, pp. 121-127. https://doi.org/10.1109/CSCS59211.2023.00028
K. Gao, F. Yang, M. Zhou, Q. Pan, and P. N. Suganthan, "Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm," IEEE Trans. Cybernetics, vol. 49, no. 5, pp. 1944-1955, May 2019. https://doi.org/10.1109/TCYB.2018.2817240
L. Wang, C. Luo, and J. Cai, "A variable interval rescheduling strategy for dynamic flexible job shop scheduling problem by improved genetic algorithm," J. Adv. Trans., vol. 2017, pp. 1-12, Jan. 2017. https://doi.org/10.1155/2017/1527858
N. Kundakci and O. Kulak, "Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem," Comp. Ind. Eng., vol. 96, pp. 31-51, Jun. 2016. https://doi.org/10.1016/j.cie.2016.03.011
How to Cite
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Download Citation
License
Copyright (c) 2024 Néstor Andrés Beltrán-Bernal, José Ignacio Rodríguez-Molano, Diego Ernesto Mendoza-Patiño
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
From the edition of the V23N3 of year 2018 forward, the Creative Commons License "Attribution-Non-Commercial - No Derivative Works " is changed to the following:
Attribution - Non-Commercial - Share the same: this license allows others to distribute, remix, retouch, and create from your work in a non-commercial way, as long as they give you credit and license their new creations under the same conditions.
2.jpg)
