A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. (English) Zbl 1079.90061
Summary: After 50 years of research in the field of flowshop scheduling problems the scientific community still observes a noticeable gap between the theory and the practice of scheduling. In this paper we aim to provide a metaheuristic, in the form of a genetic algorithm, to a complex generalized flowshop scheduling problem that results from the addition of unrelated parallel machines at each stage, sequence dependent setup times and machine eligibility. Such a problem is common in the production of textiles and ceramic tiles. The proposed algorithm incorporates new characteristics and four new crossover operators. We show an extensive calibration of the different parameters and operators by means of experimental designs. To evaluate the proposed algorithm we present several adaptations of other well-known and recent metaheuristics to the problem and conduct several experiments with a set of 1320 random instances as well as with real data taken from companies of the ceramic tile manufacturing sector. The results indicate that the proposed algorithm is more effective than all other adaptations.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Adler, L.; Fraiman, N.; Kobacker, E.; Pinedo, M.; Plotnicoff, J. C.; Wu, T. P., BPSS: A scheduling support system for the packaging industry, Operations Research, 41, 4, 641-648 (1993) |
| [2] | Aghezzaf, E.H., Artiba, A., Moursli, O., Tahon, C., 1995. Hybrid flowshop problems, a decomposition based heuristic approach. In: Proceedings of the International Conference on Industrial Engineering and Production Management, IEPM’95, Marrakech. FUCAM-INRIA, pp. 43-56.; Aghezzaf, E.H., Artiba, A., Moursli, O., Tahon, C., 1995. Hybrid flowshop problems, a decomposition based heuristic approach. In: Proceedings of the International Conference on Industrial Engineering and Production Management, IEPM’95, Marrakech. FUCAM-INRIA, pp. 43-56. |
| [3] | Alcaraz, J.; Maroto, C.; Ruiz, R., Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms, Journal of the Operational Research Society, 54, 614-626 (2003) · Zbl 1095.90541 |
| [4] | Aldowaisan, T.; Allahvedi, A., New heuristics for no-wait flowshops to minimize makespan, Computers & Operations Research, 30, 1219-1231 (2003) · Zbl 1047.90053 |
| [5] | Allahverdi, A.; Gupta, J. N.D.; Aldowaisan, T., A review of scheduling research involving setup considerations, OMEGA, The international Journal of Management Science, 27, 219-239 (1999) |
| [6] | Andrés, C., 2001. Programación de la Producción en Talleres de Flujo Hı́bridos con Tiempos de Cambio de Partida Dependientes de la Secuencia. Modelos, Métodos y Algoritmos de Resolución. Aplicación a Empresas del Sector Cerámico. PhD thesis, Departamento de Organización de Empresas. Universidad Politécnica de Valencia (in Spanish).; Andrés, C., 2001. Programación de la Producción en Talleres de Flujo Hı́bridos con Tiempos de Cambio de Partida Dependientes de la Secuencia. Modelos, Métodos y Algoritmos de Resolución. Aplicación a Empresas del Sector Cerámico. PhD thesis, Departamento de Organización de Empresas. Universidad Politécnica de Valencia (in Spanish). |
| [7] | Arthanary, T. S.; Ramaswamy, K. G., An extension of two machine sequencing problem, OPSEARCH, The Journal of the Operational Research Society of India, 8, 4, 10-22 (1971) |
| [8] | Brah, S. A.; Hunsucker, J. L., Branch and bound algorithm for the flow shop with multiple processors, European Journal of Operational Research, 51, 88-99 (1991) · Zbl 0732.90040 |
| [9] | Campbell, H. G.; Dudek, R. A.; Smith, M. L., A heuristic algorithm for the \(n\) job, \(m\) machine sequencing problem, Management Science, 16, 10, B630-B637 (1970) · Zbl 0194.50504 |
| [10] | Chen, C.-L.; Vempati, V. S.; Aljaber, N., An application of genetic algorithms for flow shop problems, European Journal of Operational Research, 80, 389-396 (1995) |
| [11] | Dudek, R. A.; Panwalkar, S. S.; Smith, M. L., The lessons of flowshop scheduling research, Operations Research, 40, 1, 7-13 (1992) · Zbl 0825.90554 |
| [12] | Ford, F. N.; Bradbard, D. A.; Ledbetter, W. N.; Cox, J. F., Use of operations research in production management, Production and Inventory Management, 28, 3, 59-62 (1987) |
| [13] | Gourgand, M., Grangeon, N., Norre, S., 1999. Metaheuristics for the deterministic hybrid flow shop problem. In: Proceedings of the International Conference on Industrial Engineering and Production Management, IEPM’99, Glasgow. FUCAM-INRIA, pp. 136-145.; Gourgand, M., Grangeon, N., Norre, S., 1999. Metaheuristics for the deterministic hybrid flow shop problem. In: Proceedings of the International Conference on Industrial Engineering and Production Management, IEPM’99, Glasgow. FUCAM-INRIA, pp. 136-145. · Zbl 1190.90087 |
| [14] | Graves, S. C., A review of production scheduling, Operations Research, 29, 4, 646-675 (1981) · Zbl 0464.90034 |
| [15] | Guinet, A. G., Textile production systems: A succession of non-identical parallel processor shops, Journal of the Operational Research Society, 42, 8, 655-671 (1991) · Zbl 0729.90754 |
| [16] | Guinet, A. G.; Solomon, M. M., Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time, International Journal of Production Research, 34, 6, 1643-1654 (1996) · Zbl 0927.90033 |
| [17] | Gupta, J. N.D., Two-stage, hybrid flowshop scheduling problem, Journal of the Operational Research Society, 39, 4, 359-364 (1988) · Zbl 0639.90049 |
| [18] | Gupta, J. N.D.; Hariri, A. M.A.; Potts, C. N., Scheduling a two-stage hybrid flow shop with parallel machines at the first stage, Annals of Operations Research, 69, 171-191 (1997) · Zbl 0880.90071 |
| [19] | Gupta, J. N.D.; Tunc, E. A., Schedules for a two-stage hybrid flowshop with parallel machines at the second stage, International Journal of Production Research, 29, 7, 1489-1502 (1991) |
| [20] | Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359 |
| [21] | Kurz, M. E.; Askin, R. G., Comparing scheduling rules for flexible flow lines, International Journal of Production Economics, 85, 371-388 (2003) |
| [22] | Kurz, M.E., Askin, R.G., in press. Scheduling flexible flow lines with sequence-dependent setup times. European Journal of Operational Research.; Kurz, M.E., Askin, R.G., in press. Scheduling flexible flow lines with sequence-dependent setup times. European Journal of Operational Research. · Zbl 1067.90045 |
| [23] | Ledbetter, W. N.; Cox, J. F., Operations research in production management: An investigation of past and present utilization, Production and Inventory Management, 18, 3, 84-91 (1977) |
| [24] | Leon, V. J.; Ramamoorthy, B., An adaptable problem-space-based search method for flexible flow line scheduling, IIE Transactions, 29, 115-125 (1997) |
| [25] | Linn, R.; Zhang, W., Hybrid flow shop scheduling: A survey, Computers and Industrial Engineering, 37, 57-61 (1999) |
| [26] | MacCarthy, B. L.; Liu, J., Addressing the gap in scheduling research: A review of optimization and heuristic methods in production scheduling, International Journal of Production Research, 31, 1, 59-79 (1993) |
| [27] | McKay, K. N.; Pinedo, M.; Webster, S., Practice-focused research issues for scheduling systems, Production and Operations Management, 11, 2, 249-258 (2002) |
| [28] | McKay, K. N.; Safayeni, F. R.; Buzacott, J. A., Job-shop scheduling theory: What is relevant?, Interfaces, 4, 18, 84-90 (1988) |
| [29] | Michalewicz, Z., Genetic Algorithms+Data Structures=Evolution Programs (1996), Springer-Verlag: Springer-Verlag Berlin · Zbl 0841.68047 |
| [30] | Montgomery, D. C., Design and Analysis of Experiments (2000), John Wiley |
| [31] | Murata, T.; Ishibuchi, H.; Tanaka, H., Genetic algorithms for flowshop scheduling problems, Computers and Industrial Engineering, 30, 4, 1061-1071 (1996) |
| [32] | Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem, OMEGA, The International Journal of Management Science, 11, 1, 91-95 (1983) |
| [33] | Nowicki, E.; Smutnicki, C., The flow shop with parallel machines: A tabu search approach, European Journal of Operational Research, 106, 226-253 (1998) · Zbl 0991.90059 |
| [34] | Olhager, J.; Rapp, B., Operations research techniques in manufacturing planning and control systems, International Transactions in Operational Research, 2, 1, 29-43 (1995) |
| [35] | Osman, I. H.; Potts, C. N., Simulated annealing for permutation flow-shop scheduling, OMEGA, The International Journal of Management Science, 17, 6, 551-557 (1989) |
| [36] | Portmann, M. C.; Vignier, A.; Dardilhac, D.; Dezalay, D., Branch and bound crossed with GA to solve hybrid flowshops, European Journal of Operational Research, 107, 389-400 (1998) · Zbl 0943.90038 |
| [37] | Rajendran, C.; Chaudhuri, D., A multi-stage parallel-processor flowshop problem with minimum flowtime, European Journal of Operational Research, 57, 111-122 (1992) · Zbl 0767.90040 |
| [38] | Rajendran, C.; Chaudhuri, D., Scheduling in \(n\)-jobs, \(m\)-stage flowshops with parallel processors to minimize makespan, International Journal of Production Economics, 27, 137-143 (1992) |
| [39] | Rajendran, C.; Ziegler, H., Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155, 426-438 (2004) · Zbl 1045.90032 |
| [40] | Reeves, C. R., A genetic algorithm for flowshop sequencing, Computers & Operations Research, 22, 1, 5-13 (1995) · Zbl 0815.90097 |
| [41] | Riane, F.; Artiba, A.; Elmaghraby, S. E., A hybrid three-stage flowshop problem: Efficient heuristics to minimize makespan, European Journal of Operational Research, 109, 321-329 (1998) · Zbl 0937.90035 |
| [42] | Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, 165, 479-494 (2005) · Zbl 1066.90038 |
| [43] | Ruiz, R.; Maroto, C.; Alcaraz, J., Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics, European Journal of Operational Research, 165, 34-54 (2005) · Zbl 1112.90338 |
| [44] | Ruiz, R., Maroto, C., Alcaraz, J., in press. Two new robust genetic algorithms for the flowshop scheduling problem. OMEGA, the International Journal of Management Science.; Ruiz, R., Maroto, C., Alcaraz, J., in press. Two new robust genetic algorithms for the flowshop scheduling problem. OMEGA, the International Journal of Management Science. · Zbl 1095.90541 |
| [45] | Salvador, M.S., 1973. A solution to a special case of flow shop scheduling problems. In: Elmaghraby, S.E. (Ed.), Symposium of the Theory of Scheduling and Applications, Springer-Verlag, New York, pp. 83-91.; Salvador, M.S., 1973. A solution to a special case of flow shop scheduling problems. In: Elmaghraby, S.E. (Ed.), Symposium of the Theory of Scheduling and Applications, Springer-Verlag, New York, pp. 83-91. · Zbl 0297.90036 |
| [46] | Santos, D. L.; Hunsucker, J. L.; Deal, D. E., An evaluation of sequencing heuristics in flow shops with multiple processors, Computers and Industrial Engineering, 30, 4, 681-692 (1996) |
| [47] | Sherali, H. D.; Sarin, S. C.; Kodialam, M. S., Models and algorithms for a two-stage production process, Production Planning and Control, 1, 1, 27-39 (1990) |
| [48] | Soewnadi, H.; Elmaghraby, S. E., Sequencing three-stage flexible flowshops with identical machines to minimize makespan, IIE Transactions, 31, 985-993 (2001) |
| [49] | Sriskandarajah, C.; Sethi, S. P., Scheduling algorithms for flexible flowshops: Worst and average case performance, European Journal of Operational Research, 43, 143-160 (1989) · Zbl 0691.90038 |
| [50] | Vallada, E.; Maroto, C.; Ruiz, R.; Segura, B., Análisis de la Programación de la Producción en el Sector Azulejero, Boletı́n de la Sociedad Española de Cerámica y Vidrio, 44, 1, 39-44 (2005), (in Spanish) |
| [51] | Vignier, A.; Billaut, J. C.; Proust, C., Les Problèmes D’Ordonnancement de Type Flow-Shop Hybride: État de L’Art, RAIRO Recherche opérationnelle, 33, 2, 117-183 (1999), in French · Zbl 0960.90042 |
| [52] | Voss, S., The two-stage hybrid flowshop scheduling problem with sequence-dependent setup times, (Fandel, G.; Gulledge, T.; Jones, A., Operations Research in Production Planning and Control (1993), Springer: Springer Berlin), 336-352 |
| [53] | Widmer, M.; Hertz, A., A new heuristic method for the flow shop sequencing problem, European Journal of Operational Research, 41, 186-193 (1989) · Zbl 0671.90040 |
| [54] | Wittrock, R. J., Scheduling algorithms for flexible flow lines, IBM Journal of Research and Development, 29, 4, 401-412 (1985) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
