Abstract
This article presents some results from the application of a genetic search algorithm to solve a job scheduling problem where setup costs depend on the order of the jobs. An empirical study shows that, for small problems, the solutions given by the genetic algorithm are as good as those obtained with a mixed-integer linear program. For larger problems that are computationally infeasible, we benchmark the genetic solutions against traditional scheduling heuristics. We also study different population management strategies that can improve the performance of the algorithm. Finally, future research avenues are discussed.
Zusammenfassung
Betrachtet wird ein dynamisches Problem der Reihenfolgeplanung in einem Walzwerk. Ziel ist die Minimierung der Summe aus Lagerkosten für Halbfertigfabrikate und reihenfolgeabhängigen Rüstkosten. Zur Lösung wird ein genetischer Algorithmus benutzt. Zur Beurteilung der Leistungsfähigkeit des Verfahrens werden für kleinere Probleme exakte Lösungen herangezogen, für größere Probleme erfolgt ein Vergleich mit prioritätsregelbasierten Verfahren.
Similar content being viewed by others
References
Baker KR (1977) An Experimental Study of the Effectiveness of Rolling Schedules in Production Planning. Dec Sci 8:(1) 19–27
Bookbinder JH, Tan J-Y (1988) Strategies for the Probabilistic Lot-Sizing Problem with Service-Level Constraint. Manag Sci 34:(9) 1096–1108
Davis L (1991) Handbook og Genetic Algorithms. Van Nostrand Reinhold, New York
DeJong KA (1975) An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Dissertation Abstracts Int 36:5140B
Della Croce F, Tadei R, Volta G (1992) A Genetic Algorithm for the Job Shop Problem. D.A.I. Politecnico di Milano, Italy
Glover FW (1990) Tabu Search: A Tutorial. Interfaces 20:(4)74–94
Goldberg DE (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, Mass
Holland JH (1980) Adaptive Algorithms for Discovering and Using General Patterns in Growing Knowledge-Bases. Int J Policy Anal Inf Syst 4:217–240
Jeffcoat DE, Bulfin RL (1993) Simulated Annealing for Resource-Constrained Scheduling. Eur J Oper Res 70:43–51
Jobin M-H (1990) Optimisation des politiques d'ordonnancement et de réglage à l'aide d'un modèle de simulation visuelle pour un laminoir à froid. CEFRIO. Document E-3
Laguna M, Barnes JW, Glover FW (1991) Tabu Search Methods for a Single Machine Scheduling Problem. J Intelligent Manufacturing 2:63–74
Lefrançois P, Alie Y (1990) A Service-Level Oriented Heuristic Approach to Production Planning in a Robotized Spinning-Mill. Int J Product Res 28:(7) 1293–1304
Lefrançois P, Montreuil B (1994) An Object-Oriented Knowledge Representation for Intelligent Control of Manufacturing Work-stations. IIE Transact 26:11–26
Lefrançois P, Roy M-C, Gamache G (1990) Estimation of the Mean Flow Time in a Rollingmill Facility. J Manufacturing Oper Manag 3:134–152
Matsuo H, Suh CJ, Sullivan RS (1988) A Controlled Search Simulated Annealing Method for the General Jobshop Scheduling Problem, Working Paper 03-04-88, Department of Management, The University of Texas at Austin
Morton TE, Pentico DW (1993) Heuristic Scheduling Systems. John Wiley & Sons, New York
Syswerda G (1991) Schedule Optimization Using Genetic Algorithms. Handbook of Genetic Algorithms. Davis L (ed) Van Nostrand Reinhold, New York, pp 332–349
Van Laarhoven PJM, Aarts EHL (1987) Simulated Annealing: Theory and Applications. Kluwer, Boston
Van Laarhoven PJM, Aarts EHL, Lenstra JK (1992) Job Shop Scheduling by Simulated Annealing. Oper Res 40:113–125
Whitley D, Starkweather T, Shaner D (1991) The Traveling Salesman and Sequence Scheduling: Quality Solutions Using Genetic Edge Recombination. Handbook of Genetic Algorithms. Davis L (ed) Van Nostrand Reinhold, New York, pp 350–372
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mayrand, É., Lefrançois, P., Kettani, O. et al. A genetic search algorithm to optimize job sequencing under a technological constraint in a rolling-mill facility. OR Spektrum 17, 183–191 (1995). https://doi.org/10.1007/BF01719263
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01719263