Abstract
This paper presents a stochastic method based on the differential evolution (DE) algorithm to address a wide range of sequencing and scheduling optimization problems. DE is a simple yet effective adaptive scheme developed for global optimization over continuous spaces. In spite of its simplicity and effectiveness the application of DE on combinatorial optimization problems with discrete decision variables is still unusual. A novel solution encoding mechanism is introduced for handling discrete variables in the context of DE and its performance is evaluated over a plethora of public benchmarks problems for three well-known NP-hard scheduling problems. Extended comparisons with the well-known random-keys encoding scheme showed a substantially higher performance for the proposed. Furthermore, a simple slight modification in the acceptance rule of the original DE algorithm is introduced resulting to a more robust optimizer over discrete spaces than the original DE.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abdul-Razaq, T.S., C.N. Potts, and L.N. Van Wassenhove. (1990). “A Survey of Algorithms for the Single Machine Total Weight Tardiness Scheduling Problem.” Discrete Applied Mathematics 26, 235–253.
Ali, M.M. and A. Törn. (2004). “Population Set-based Global Optimization Algorithms: Some Modifications and Numerical Studies.” Computers & Operations Research 31, 1703–1725.
Ali, M.M., C. Khompatraporn, and Z.B. Zabinsky. (2005). “A Numerical Evaluation of Several Stochastic Algorithms on Selected Continues Global Optimization Test Problems.” Journal of Global Optimization 31, 635–672.
Baker, K. and G. Scudder. (1990). “Sequencing with Earliness and Tardiness Penalties: A Review.” Operations Research 38, 22–36.
Bean, J. (1994). “Genetics and Random Keys for Sequencing and Optimization.” ORSA Journal on Computing 6(2), 154–160.
Biskup, D., and M. Feldmann. (2001). “Benchmarks for Scheduling on a Single Machine Against Restrictive and Unrestrictive Common Due Dates.” Computers and Operations Research 28, 787–801.
Cheng, S.-L. and C. Hwang. (2001). “Optimal Approximation of Linear Systems by a Differential Evolution Algorithm.” IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans 31(6), 698–707.
Crauwels, H.A.J., C.N. Potts, and L.N. Van Wassenhove. (1998). “Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem.” INFORMS Journal on Computing 10(3), 341–350.
Kaelo, P. and M.M. Ali. (2006). “A numerical study of some modified differential evolution algorithms.” European Journal of Operational Research 171, 674–692.
Lin, Y.-C., K.S. Hwang, and F.-S. Wang. (2004). “A Mixed-Coding Scheme of Evolutionary Algorithms to Solve Mixed-Integer Nonlinear Programming Problems.” Computers & Mathematics with Applications 47(8–9), 1295–1307.
Nearchou, A.C. (2006). “Meta-Heuristics from Nature for the Loop Layout Design Problem.” International Journal of Production Economics 101/2, 312–328. %%%available online since 18 March 2005.
Onwubolu, G.C. (2004). “Optimizing CNC Drilling Machine Operations: Traveling Salesman Problem-Differential Evolution Approach.” In Onwubolu, G. C. and Babu, B. V. (eds.), New Optimization Techniques in Engineering, Springer-Verlag, Heidelberg, Germany, pp. 537–565.
Potts, C.N. and L.N. Van Wassenhove. (1991). “Single Machine Tardiness Sequencing Heuristics.” IEE Transactions 23, 346–354.
Rinnooy, A.H.G. Kan (1976). Machine Scheduling Problems: Classification, Complexity and Computations. Martinus Nijhoff, The Hague.
Storn, R. and K. Price. (1997). “Differential Evolution—A Simple and Efficient Heuristic for Global Optimization Over Continuous Spaces.” Journal Global Optimization 11, 241–354.
Sun, J., Q. Zhang, and E.P.K. Tsang. (2005). “DE/EDA: A New Evolutionary Algorithm for Global Optimization.” Information Sciences 169(3–4), 249–262.
Taillard, E. (1990). “Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem”. European Journal of Operational Research 47, 65–74.
Taillard, E. (1993). “Benchmarks for Basic Scheduling Problems.” European Journal of Operational Research 64, 278–285.
Zaharie, D. (2002). “Critical Values for the Control Parameters of Differential Evolution Algorithms.” In: Matouek, Radek and Omera, Pavel (eds.). Proc. of MENDEL 2002, 8th Int. Mendel Conference on Soft Computing, Brno, Czech Republic, pp. 62–67.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Nearchou, A.C., Omirou, S.L. Differential evolution for sequencing and scheduling optimization. J Heuristics 12, 395–411 (2006). https://doi.org/10.1007/10732-006-3750-x
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/10732-006-3750-x