×

zbMATH — the first resource for mathematics

A matheuristic for parallel machine scheduling with tool replacements. (English) Zbl 07356152
Summary: This paper addresses the problem of scheduling a set of jobs with tool requirements on identical parallel machines in a work center. This problem considers the following characteristics. First, each job may consist of an ordered set of operations due to reentrance to the work center. Moreover, operations have release times and due dates, and the processing of operations requires different tool sets of different sizes. Last, the objective is to minimize both tardiness of operations and tool setup times. Decisions concern the assignment of operations to machines, sequencing of operations, and replacement of tool sets on machines. We propose a mathematical model for the problem and a new matheuristic that combines a genetic algorithm and an integer linear programming formulation to solve industry-size instances. In the matheuristic, we propose two crossover operators which exploit the structure of the problem. We illustrate this approach through real-world case studies. Computational experiments show that our matheuristic outperforms the mathematical model and a practitioner heuristic. We also generate managerial insights by quantifying the potential room for improvement in current practice.
MSC:
90Bxx Operations research and management science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmadi, E.; Goldengorin, B.; Süer, G. A.; Mosadegh, H., A hybrid method of 2-TSP and novel learning-based GA for job sequencing and tool switching problem, Applied Soft Computing, 65, 214-229 (2018)
[2] Al-Fawzan, M.; Al-Sultan, K., A tabu search based algorithm for minimizing the number of tool switches on a flexible machine, Computers & Industrial Engineering, 44, 1, 35-47 (2003)
[3] Amaya, J. E.; Cotta, C.; Fernández, A. J., A memetic algorithm for the tool switching problem, (Blesa, M. J.; Blum, C.; Cotta, C.; Fernández, A. J.; Gallardo, J. E.; Roli, A.; Sampels, M., Hybrid metaheuristics. Hybrid metaheuristics, Lecture Notes in Computer Science, 5296 (2008), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 190-202
[4] Amaya, J. E.; Cotta, C.; Fernández-Leiva, A. J., Memetic cooperative models for the tool switching problem, Memetic Computing, 3, 3, 199-216 (2011)
[5] Amaya, J. E.; Cotta, C.; Fernandez-Leiva, A. J., Solving the tool switching problem with memetic algorithms, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 26, 2, 221-235 (2012)
[6] Amaya, J. E.; Cotta, C.; Leiva, A. J.F., A memetic cooperative optimization schema and its application to the tool switching problem, (Schaefer, R.; Cotta, C.; Kołodziej, J.; Rudolph, G., Parallel problem solving from nature, ppsn xi. Parallel problem solving from nature, ppsn xi, Lecture Notes in Computer Science, 6238 (2010), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 445-454
[7] Baykasoğlu, A.; Ozsoydan, F. B., Minimizing tool switching and indexing times with tool duplications in automatic machines, The International Journal of Advanced Manufacturing Technology, 89, 5, 1775-1789 (2017)
[8] Baykasoğlu, A.; Ozsoydan, F. B., Minimisation of non-machining times in operating automatic tool changers of machine tools under dynamic operating conditions, International Journal of Production Research, 56, 4, 1548-1564 (2018)
[9] Beezão, A. C.; Cordeau, J.-F.; Laporte, G.; Yanasse, H. H., Scheduling identical parallel machines with tooling constraints, European Journal of Operational Research, 257, 3, 834-844 (2017) · Zbl 1394.90263
[10] Box, G.; Hunter, J.; Hunter, W., Statistics for experimenters: Design, innovation, and discovery (2005), Wiley-Interscience · Zbl 1082.62063
[11] Burger, A. P.; Jacobs, C. G.; van Vuuren, J. H.; Visagie, S. E., Scheduling multi-colour print jobs with sequence-dependent setup times, Journal of Scheduling, 18, 2, 131-145 (2015) · Zbl 1312.90019
[12] Calmels, D., The job sequencing and tool switching problem: state-of-the-art literature review, classification, and trends, International Journal of Production Research, 57, 15-16, 5005-5025 (2019)
[13] Catanzaro, D.; Gouveia, L.; é, M., Improved integer linear programming formulations for the job Sequencing and tool Switching Problem, European Journal of Operational Research, 244, 3, 766-777 (2015) · Zbl 1348.90485
[14] Chaves, A.; Lorena, L.; Senne, E.; Resende, M., Hybrid method with CS and BRKGA applied to the minimization of tool switches problem, Computers & Operations Research, 67, 174-183 (2016) · Zbl 1349.90326
[15] Crama, Y.; Kolen, A. W.J.; Oerlemans, A. G.; Spieksma, F. C.R., Minimizing the number of tool switches on a flexible machine, International Journal of Flexible Manufacturing Systems, 6, 1, 33-54 (1994)
[16] Dang, Q.-V.; Nguyen, C. T.; Rudová, H., Scheduling of mobile robots for transportation and manufacturing tasks, Journal of Heuristics, 25, 2, 175-213 (2019)
[17] Djellab, H.; Djellab, K.; Gourgand, M., A new heuristic based on a hypergraph representation for the tool switching problem, International Journal of Production Economics, 64, 1, 165-176 (2000)
[18] Du, K.-L.; Swamy, M. N.S., Search and optimization by metaheuristics: Techniques and algorithms inspired by nature (2016), Springer, Switzerland · Zbl 1351.90002
[19] Fathi, Y.; Barnette, K. W., Heuristic procedures for the parallel machine problem with tool switches, International Journal of Production Research, 40, 1, 151-164 (2002) · Zbl 1175.90163
[20] Furrer, M.; Mütze, T., An algorithmic framework for tool switching problems with multiple objectives, European Journal of Operational Research, 259, 3, 1003-1016 (2017) · Zbl 1402.90045
[21] Gao, J.; Sun, L.; Gen, M., A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems, Computers & Operations Research, 35, 9, 2892-2907 (2008) · Zbl 1144.90379
[22] Gen, M.; Cheng, R.; Lin, L., Network models and optimization: Multiobjective genetic algorithm approach (2008), Springer, London · Zbl 1193.90006
[23] Ghiani, G.; Grieco, A.; Guerriero, E., Solving the job sequencing and tool switching problem as a nonlinear least cost Hamiltonian cycle problem, Networks, 55, 4, 379-385 (2010) · Zbl 1200.90061
[24] Ghrayeb, O. A.; Phojanamongkolkij, N.; Finch, P. R., A mathematical model and heuristic procedure to schedule printed circuit packs on sequencers, International Journal of Production Research, 41, 16, 3849-3860 (2003)
[25] Goldberg, D. E.; Lingle, R., Alleles, loci, and the traveling salesman problem, (Grefenstette, J. J., Proceedings of the first international conference on genetic algorithms (1985), L. Erlbaum Associates Inc.: L. Erlbaum Associates Inc. Hillsdale, NJ, USA), 154-159
[26] Guimarães, L.; Klabjan, D.; Almada-Lobo, B., Pricing, relaxing and fixing under lot sizing and scheduling, European Journal of Operational Research, 230, 2, 399-411 (2013) · Zbl 1317.90123
[27] Gökgür, B.; Hnich, B.; Özpeynirci, S., Parallel machine scheduling with tool loading: A constraint programming approach, International Journal of Production Research, 56, 16, 5541-5557 (2018)
[28] Hertz, A.; Laporte, G.; Mittaz, M.; Stecke, K. E., Heuristics for minimizing tool switches when scheduling part types on a flexible machine, IIE Transactions, 30, 8, 689-694 (1998)
[29] Jans, R., Solving lot-sizing problems on parallel identical machines using symmetry-breaking constraints, INFORMS Journal on Computing, 21, 1, 123-136 (2009) · Zbl 1243.90147
[30] Karakayalı, İ.; Azizoğlu, M., Minimizing total flow time on a single flexible machine, International Journal of Flexible Manufacturing Systems, 18, 1, 55-73 (2006) · Zbl 1197.90211
[31] Keung, K. W.; Ip, W. H.; Lee, T. C., A genetic algorithm approach to the multiple machine tool selection problem, Journal of Intelligent Manufacturing, 12, 4, 331-342 (2001)
[32] Keung, K. W.; Ip, W. H.; Lee, T. C., The solution of a multi-objective tool selection model using the GA approach, The International Journal of Advanced Manufacturing Technology, 18, 11, 771-777 (2001)
[33] Khan, B. K.; Gupta, B. D.; Gupta, D. K.S.; Kumar, K. D., A generalized procedure for minimizing tool changeovers of two parallel and identical CNC machining centres, Production Planning & Control, 11, 1, 62-72 (2000)
[34] Laporte, G.; Salazar-González, J. J.; Semet, F., Exact algorithms for the job sequencing and tool switching problem, IIE Transactions, 36, 1, 37-45 (2004)
[35] Lin, L.; Shinn, S. W.; Gen, M.; Hwang, H., Network model and effective evolutionary approach for AGV dispatching in manufacturing system, Journal of Intelligent Manufacturing, 17, 4, 465-477 (2006)
[36] Lin, S.-W.; Ying, K.-C., Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics, Omega, 64, 115-125 (2016)
[37] Paiva, G. S.; Carvalho, M. A.M., Improved heuristic algorithms for the job sequencing and tool switching problem, Computers & Operations Research, 88, 208-219 (2017) · Zbl 1391.90228
[38] Rabbani, M.; Montazeri, M.; Farrokhi-Asl, H.; Rafiei, H., A multi-objective genetic algorithm for a mixed-model assembly U-line balancing type-I problem considering human-related issues, training, and learning, Journal of Industrial Engineering International, 12, 4, 485-497 (2016)
[39] Raduly-Baka, C.; Knuutila, T.; Nevalainen, O. S., Minimising the Number of Tool Switches with Tools of Different Sizes, TUCS Technical Reports (2005), Turku Centre for Computer Science
[40] Reeves, C. R., Genetic Algorithms, (Gendreau, M.; Potvin, J.-Y., Handbook of metaheuristics. Handbook of metaheuristics, International Series in Operations Research & Management Science (2010), Springer US), 109-139
[41] Salonen, K.; Raduly-Baka, C.; Nevalainen, O. S., A note on the tool switching problem of a flexible machine, Computers & Industrial Engineering, 50, 4, 458-465 (2006)
[42] Sarmadi, H.; Gholami, S., Modeling of tool switching problem in a flexible manufacturing cell: with two or more machines, (Xie, Y., Proceeding of the international conference on mechanical and electrical technology, 3rd, (ICMET-China 2011), Volumes 1-3 (2011), ASME Press), 2345-2349
[43] Schwerdfeger, S.; Boysen, N., Order picking along a crane-supplied pick face: The SKU switching problem, European Journal of Operational Research, 260, 2, 534-545 (2017) · Zbl 1403.90174
[44] Sherali, H. D.; Smith, J. C., Improving discrete model representations via symmetry considerations, Management Science, 47, 10, 1396-1407 (2001) · Zbl 1232.90309
[45] Shivanand, H. K.; Benal, M. M.; Koti, V., Flexible manufacturing system (2006), New Age International
[46] Solimanpur, M.; Rastgordani, R., Minimising tool switching and indexing times by ant colony optimisation in automatic machining centres, International Journal of Operational Research, 13, 4, 465-479 (2012) · Zbl 1362.90376
[47] Tang, C. S.; Denardo, E. V., Models arising from a flexible manufacturing machine, part I: minimization of the number of tool switches, Operations Research, 36, 5, 767-777 (1988) · Zbl 0665.90044
[48] Tzur, M.; Altman, A., Minimization of tool switches for a flexible manufacturing machine with slot assignment of different tool sizes, IIE Transactions, 36, 2, 95-110 (2004)
[49] Unlu, Y.; Mason, S. J., Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems, Computers & Industrial Engineering, 58, 4, 785-800 (2010)
[50] Van Hop, N., The tool-switching problem with magazine capacity and tool size constraints, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 35, 5, 617-628 (2005)
[51] Van Hop, N.; Nagarur, N. N., The scheduling problem of pcbs for multiple non-identical parallel machines, European Journal of Operational Research, 158, 3, 577-594 (2004) · Zbl 1056.90075
[52] Weng, M. X.; Ren, H., An efficient priority rule for scheduling job shops to minimize mean tardiness, IIE Transactions, 38, 9, 789-795 (2006)
[53] Woo, Y.-B.; Kim, B. S., Matheuristic approaches for parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities, Computers & Operations Research, 95, 97-112 (2018) · Zbl 1458.90373
[54] Özpeynirci, S.; Gökgür, B.; Hnich, B., Parallel machine scheduling with tool loading, Applied Mathematical Modelling, 40, 9-10, 5660-5671 (2016) · Zbl 1465.90030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.