Parallelism and Hybridization in Differential Evolution to solve the Flexible Job Shop Scheduling Problem

Carolina Salto; Franco  Morero; Carlos  Bermúdez

doi:10.24215/16666038.20.e04

Authors

Carolina Salto Universidad Nacional de La Pampa
Franco Morero LISI - Facultad de Ingeniería, Universidad Nacional de La Pampa, General Pico, Argentina
Carlos Bermúdez LISI - Facultad de Ingeniería, Universidad Nacional de La Pampa, General Pico, Argentina

DOI:

https://doi.org/10.24215/16666038.20.e04

Keywords:

differential evolution, parallelism, flexible job shop scheduling

Abstract

Flexible Job Shop Scheduling Problem (FJSP) is one of the most challenging combinatorial optimization problems, with practical applicability in a real production environment. In this work, we propose a simple Differential Evolution (DE) algorithm to tackle this problem. To represent an FJSSP solution, a real value representation is adopted, which requires a very simple conversion mechanism to obtain a feasible schedule. Consequently, the DE algorithm still works on the continuous domain to explore the problem search space of the discrete FJSSP. Moreover, to enhance the local searchability and to balance the exploration and exploitation capabilities, a simple local search algorithm is embedded in the DE framework. Also, the parallelism of the DE operations is included to improve the efficiency of the whole algorithm. Experiment results confirm the significant improvement achieved by integrating the propositions introduced in this study. Additionally, test results show that our algorithm is competitive when compared with most existing approaches for the FJSSP.

Downloads

Download data is not yet available.

References

M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer Publishing Company, Incorporated, 3rd ed., 2008.

M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Math. Oper. Res., vol. 1, pp. 117–129, May 1976.

E.-G. Talbi, Metaheuristics: From Design to Implementation. Wiley, 2009.

G. Luque and E. Alba, Parallel Genetic Algorithms: Theory and Real World Applications. Springer Publishing Company, Incorporated, 2013.

J. Tang, G. Zhang, B. Lin, and B. Zhang, “A hybrid algorithm for flexible job-shop scheduling problem,” Procedia Engineering, vol. 15, pp. 3678 – 3683, 2011.

L. Wang, S. Wang, Y. Xu, G. Zhou, and M. Liu, “A bipopulation based estimation of distribution algorithm for the flexible job-shop scheduling problem,” Computers & Industrial Engineering, vol. 62, no. 4, pp. 917 – 926, 2012.

L. Wang, J. Cai, M. Li, and Z. Liu, “Flexible job shop scheduling problem using an improved ant colony optimization,” Scientific Programming, pp. 1–11, 2017.

R. Storn and K. Price, “Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces,” Journal of Global Optimization, vol. 11, no. 4, pp. 341–359, 1997.

B. Teoh, S. Ponnambalam, and G. Kanagaraj, “Differential evolution algorithm with local search for capacitated vehicle routing problem,” Int. J. Bio-Inspired Comput., vol. 7, no. 5, pp. 321–342, 2015.

R. Greco and I. Vanzi, “New few parameters differential evolution algorithm with application to structural identification,” Journal of Traffic and Transportation Engineering (English Edition), vol. 6, no. 1, pp. 1 – 14, 2019.

P. Hull, M. Tinker, and G. Dozier, “Evolutionary optimization of a geometrically refined truss,” Structural and Multidisciplinary Opt., vol. 31.

R. M. K. Rout, “Simultaneous selection of optimal parameters and tolerance of manipulator using evolutionary optimization techniques,” Structural and Multidisciplinary Optimization, vol. 40, no. 1-6, pp. 513–528, 2010.

Y. Yuan and H. Xu, “Flexible job shop scheduling using hybrid differential evolution algorithms,” Computers & Industrial Eng., vol. 65, no. 2, pp. 246–260, 2013.

F. Morero, C. Bermudez, and C. Salto, “A simple differential evolution algorithm to solve the flexible job shop scheduling problem,” XXV Congreso Argentino de Ciencias de la Computaci´on, pp. 1–10, 2019.

T. Eltaeib and A. Mahmood, “Differential evolution: A survey and analysis,” Applied Sciences, vol. 8, no. 10, 2018.

I.Kacem, S.Hammadi, and P. Borne, “Approach by localization and multi objective evolutionary optimization for flexible job-shop scheduling problems,” IEEE Trans. Syst. Man Cybern. C, Appl., vol. 1, pp. 1–, 2002.

R. Storn and K. Price, “Differential evolution: a simple and efficient adaptive scheme for global optimization over continuous spaces,” tech. rep., ICSI,USA,Tech. Rep. TR-95-012,, 1995.

S. Das, S. S. Mullick, and P. Suganthan, “Recent advances in differential evolution – an updated survey,” Swarm and Evolutionary Computation, vol. 27, pp. 1 –30, 2016.

K. Price, R. M. Storn, and J. A. Lampinen, Differential Evolution: A Practical Approach to Global Optimization (Natural Computing Series). Berlin, Heidelberg: Springer-Verlag, 2005.

J. H. Holland, Adaptation in Natural and Artificial Systems. Cambridge, Massachusetts: The MIT Press, first ed., 1975.

R. G¨amperle, S. M¨uller, and P. Koumoutsakos, “A parameter study for differential evolution,” in WSEAS Int. Conf. on Advances in Intelligent Systems, Fuzzy Systems, Evolutionary Computation, pp. 293–298, Press, 2002.

J. C. Bean, “Genetic algorithms and random keys for sequencing and optimization,” ORSA Journal on Computing, vol. 6, no. 2, pp. 154–160, 1994.

C. Bierwirth, “A generalized permutation approach to job shop scheduling with genetic algorithms,” Operations-Research-Spektrum, vol. 17, pp. 87–92,1995.

N. Nedjah, E. Alba, and L. de Macedo Mourelle, Parallel Evolutionary Computations. Springer-Verla, 2006.

P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Annals of Operations Research, vol. 41, pp. 157–183, 1993.

B. Chapman, G. Jost, and R. van der Pas, Using OpenMP: Portable Shared Memory Parallel Programming. MIT Press, 2007.

E. Alba, Parallel Metaheuristics: A New Class of Algorithms. Wiley, 2005.