Abstract
This chapter presents a general framework of Differential Evolution algorithm for combinatorial optimization problems. We define the differences between a given pair of solutions in the differential mutation as a set of elementary movements in the discrete search space. In this way, the search mechanism and self-adaptive behavior of the differential evolution is preserved and generalized to combinatorial problems. These ideas are then applied to n-job m-machine flow shop scheduling in order to illustrate its application in an important problem in combinatorial optimization. The method was applied to the 120 Taillard instances of the permutation flow shop scheduling problem, and compared against the results obtained by other metaheuristic algorithms in the literature. Although relying only on the differential mutation and the local search performed on the best individual, dDE ranks fairly well against more sophisticated metaheuristics. The results are promising and illustrate the applicability of the proposed approach for combinatorial optimization using differential evolution.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abbass, H.A., Sarkar, R., Newton, C.: A pareto differential evolution approach to vector optimisation problems. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC, pp. 971–978. IEEE Press (2001)
Aldowaisan, T., Allahverdi, A.: New heuristics for no-wait flowshops to minimize makespan. Computers & Operational Research 30, 1219–1231 (2003)
Allahverdi, A., Ng, C.T., Cheng, T.C.E., Kovalyov, M.Y.: A survey of scheduling problems with setup times or costs. European Journal of Operational Research 187(3), 985–1032 (2008)
Baker, K.R.: Introduction to Sequencing and Scheduling. Wiley, New York (1974)
Batista, L.S., Guimarães, F.G., Ramírez, J.A.: A differential mutation operator for the archive population of multi-objective evolutionary algorithms. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC, pp. 1108–1115. IEEE Press (2009)
Chakraborty, U.K. (ed.): Advances in Differential Evolution. SCI, vol. 143. Springer, Heidelberg (2008)
Chen, C.-L., Vempati, V.S., Aljaber, N.: An application of genetic algorithms for flow shop problems. European Journal of Operational Research 80(2), 389–396 (1995)
Davis, L.: Job shop scheduling with genetic algorithms. In: Proceedings of the 1st International Conference on Genetic Algorithms, pp. 136–140. L. Erlbaum Associates Inc., Hillsdale (1985)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Natural Computing Series. Springer (2003)
Feoktistov, V.: Differential Evolution: In Search of Solutions. Springer Optimization and Its Applications, 1st edn. Springer (October 2006)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979)
Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research 1, 117–129 (1976)
Gong, W., Cai, Z.: A multiobjective differential evolution algorithm for constrained optimization. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC, pp. 181–188. IEEE Press (June 2008)
Kim, H.-K., Chong, J.-K., Park, K.-Y., Lowther, D.A.: Differential evolution strategy for constrained global optimization and application to practical engineering problems. IEEE Transactions on Magnetics 43(4), 1565–1568 (2007)
Lichtblau, D.: Relative position indexing approach. In: Onwubolu, G.C., Davendra, D. (eds.) Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization. SCI, vol. 175, ch. 4, pp. 81–120. Springer (2009)
Linn, R., Zhang, W.: Hybrid flow shop scheduling: a survey. Computers & Industrial Engineering 37(1-2), 57–61 (1999)
Madavan, N.K.: Multiobjective optimization using a Pareto differential evolution approach. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC, vol. 2, pp. 1145–1150. IEEE Press (May 2002)
Mezura-Montes, E., Velazquez-Reyes, J., Coello Coello, C.A.: A comparative study of differential evolution variants for global optimization. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO, pp. 485–492. ACM (2006)
Murata, T., Ishibuchi, H., Tanaka, H.: Genetic algorithms for flowshop scheduling problems. Computers & Industrial Engineering 30, 1061–1071 (1996)
Onwubolu, G.C.: Design of hybrid differential evolution and group method of data handling networks for modeling and prediction. Information Sciences 178, 3616–3634 (2008)
Onwubolu, G.C., Davendra, D. (eds.): Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization. SCI, vol. 175. Springer (2009)
Onwubolu, G.C., Davendra, D.: Scheduling flow shops using differential evolution algorithm. European Journal of Operational Research 171(2), 674–692 (2006)
Osman, I.H., Potts, C.N.: Simulated annealing for permutation flow-shop scheduling. Omega 17(6), 551–557 (1989)
Pan, Q.K., Wang, L., Qian, B.: A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problem. Computers & Operations Research 36(8), 2498–2511 (2009)
Pan, Q.-K., Tasgetiren, M.F., Liang, Y.-C.: A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering 55, 795–816 (2008)
Pinedo, M.: Scheduling: Theory, Algorithms and Systems. Prentice-Hall (2002)
Price, K.V.: An introduction to differential evolution. In: Corne, D., Dorigo, M., Glover, F. (eds.) New Ideas in Optimisation. Advanced Topics in Computer Science, pp. 79–108. McGraw-Hill (1999)
Price, K.V., Storn, R.M.: Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization 11(4), 341–359 (1997)
Price, K.V., Storn, R.M., Lampinen, J.A.: Differential Evolution: A Practical Approach to Global Optimization, 1st edn. Natural Computing Series. Springer (December 2005)
Qian, B., Wang, L., Hu, R., Wang, W.-L., Huang, D.-X., Wang, X.: A hybrid differential evolution method for permutation flow-shop scheduling. The International Journal of Advanced Manufacturing Technology 38, 757–777 (2008)
Rajendran, C., Ziegler, H.: Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research 155(2), 426–438 (2004)
Reeves, C.R.: A genetic algorithm for flowshop sequencing. Computers & Operational Research 22, 5–13 (1995)
Ruiz, R., Maroto, C., Alcaraz, J.: Two new robust genetic algorithms for the flowshop scheduling problem. Omega 34(5), 461–476 (2006)
Ruiz, R., Stützle, T.: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research 177, 2033–2049 (2007)
Stützle, T.: Applying iterated local search to the permutation flow shop problem. Technical report, AIDA-98-04, FG Intellektik, FB Informatik, TU Darmstadt (1998)
Taillard, E.: Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research 47(1), 65–74 (1990)
Taillard, E.: Benchmarks for basic scheduling problems. European Journal Of Operational Research 64(2), 278–285 (1993)
Wang, Y., Cai, Z., Zhang, Q.: Differential evolution with composite trial vector generation strategies and control parameters. IEEE Transactions on Evolutionary Computation 15(1), 55–66 (2011)
Widmer, M., Hertz, A.: A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research 41(2), 186–193 (1989)
Xue, F., Sanderson, A.C., Graves, R.J.: Pareto-based multi-objective differential evolution. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC, vol. 2, pp. 862–869. IEEE Press (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Guimarães, F.G., Silva, R.C.P., Prado, R.S., Neto, O.M., Davendra, D.D. (2013). Flow Shop Scheduling Using a General Approach for Differential Evolution. In: Zelinka, I., Snášel, V., Abraham, A. (eds) Handbook of Optimization. Intelligent Systems Reference Library, vol 38. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30504-7_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-30504-7_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30503-0
Online ISBN: 978-3-642-30504-7
eBook Packages: EngineeringEngineering (R0)