Abstract
This paper presents a hybrid evolutionary algorithm with marriage of genetic algorithm (GA) and extremal optimization (EO) for solving a class of production scheduling problems in manufacturing. The scheduling problem, which is derived from hot rolling production in steel industry, is characterized by two major requirements: (i) selecting a subset of orders from manufacturing orders to be processed; (ii) determining the optimal production sequence under multiple constraints, such as sequence-dependant transition costs, non-execution penalties, earliness/tardiness (E/T) penalties, etc. A combinatorial optimization model is proposed to formulate it mathematically. For its NP-hard complexity, an effective hybrid evolutionary algorithm is developed to solve the scheduling problem through combining the population-based search capacity of GA and the fine-grained local search efficacy of EO. The experimental results with production scale data demonstrate that the proposed hybrid evolutionary algorithm can provide superior performances in scheduling quality and computation efficiency.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Abbreviations
- GA:
-
genetic algorithm
- MGA:
-
modified genetic algorithm
- EO:
-
extremal optimization
- GEO:
-
genetic extremal optimization
- E/T:
-
earliness/tardiness
- PCTSP:
-
prize collecting traveling salesman problem
References
Balas E (1999) New classes of efficiently solvable generalized Traveling Salesman Problems. Ann Oper Res 86:529–558
Balas E, Martin G (1985) Roll-a-Round: Software package for scheduling the rounds of a rolling mill. Balas and Martin Associates, Pittsburgh
Feillet D, Dejax P, Gendreau M (2005) Traveling salesman problems with profits. Transport Sci 39(2):188–205
Lopez L, Carter MW, Gendreau M (1998) The hot strip mill production scheduling problem: A tabu search approach. Eur J Oper Res 106:317–335
Tang LX, Wang XP (2006) Iterated local search algorithm based on very large-scale neighborhood for prize-collecting vehicle routing problem. Int J Adv Manuf Technol 29(11–12):1246–1258
Feo TA, Sarathy K, McGahan J (1996) A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties. Comput Oper Res 23(9):881–895
Shin HJ, Kim CO, Kim SS (2002) A tabu search algorithm for single machine scheduling with release times, due dates, and sequence-dependent set-up times. Int J Adv Manuf Technol 19:859–866
Pugazhendhi S, Thiagarajan S, Rajendran C, Anantharaman N (2004) Generating non-permutation schedules in flowline-based manufacturing systems with sequence-dependent setup times of jobs: a heuristic approach. Int J Adv Manuf Technol 23:64–78
Rubin PA, Ragatz GL (1995) Scheduling in a sequence dependent setup environment with genetic search. Comput Oper Res 22(1):85–99
Ruben R, Concepcion M, Javier A (2005) Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics. Eur J Oper Res 165:34–54
Liu CY, Chang SC (2000) Scheduling flexible flow shops with sequence-dependent setup effects. IEEE Trans Robot Autom 16(4):408–419
Refael H, Mati S (2005) Machine scheduling with earliness, tardiness and non-execution penalties. Comput Oper Res 32:683–705
Boettcher S, Percus AG (1999) Extremal optimization: Methods derived from Co-Evolution. In: Proceedings of the genetic and evolutionary computation conference, pp 825–832
Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs. Springer-Verlag, London, UK
Han J (2005) Local evaluation functions and global evaluation functions for computational evolution. Complex Systems 05:1–41 http://dx.doi.org/SFI-WP 03-09-048
Boettcher S, Percus AG (2000) Nature’s way of optimizing. Artif Intell 119:275–286
Boettcher S, Percus AG (2003) Optimization with extremal dynamics. Complexity (Wiley Periodicals, Inc.) 8(2):57–62
De Sousa FL, Vlassov V, Ramos FM (2004) Generalized extremal optimization: An application in heat pipe design. Appl Math Model 28:911–931
Chang WA, Ramakrishna RS (2002) A genetic algorithm for shortest path routing problem and the sizing of population. IEEE Trans Evol Comput 6(6):566–579
Larraòaga P, Kuijpers CMH, Murga RH, Inza I, Dizdarevic S (1999) Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artif Intell Rev 13:129–170
Cowling P (2003) A flexible decision support system for steel hot rolling mill scheduling. Comput Ind Eng 45:307–321
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, YW., Lu, YZ. & Yang, GK. Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization for production scheduling. Int J Adv Manuf Technol 36, 959–968 (2008). https://doi.org/10.1007/s00170-006-0904-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-006-0904-9