A Discrete Squirrel Search Algorithm applied to the Job Shop problem with skilled operators

Authors

DOI:

https://doi.org/10.17981/ingecuc.15.2.2019.14

Keywords:

Combinatorial Optimization, swarm intelligence, scheduling with operators, smallest position value, valid particle generator, combinatorial optimization

Abstract

Introduction: The Job Shop problem With Skilled Operators (JSSO) is an extension of the classic Job Shop in which, an operation must be executed by a limited set of workers, aiming to minimize jobs total termination time or Makespan. This situation can represent different applications in daily life. JSSO is a complex problem and its classified as NP-HARD..

Objective: In this article, the JSSO problem is addressed. It is made by adapting an algorithm known as Squirrel Search Algorithm (SSA).

Method:  A discrete encoding scheme is proposed for the SSA algorithm and the Smallest Position Value (SPV) method are used. Also, solutions that can violate the precedent relationships are corrected with the Valid Particle Generator (VPG) method, which guarantees feasible solutions. Two versions of the algorithm were tested in 28 instances proposed in the literature to valid their performance.

Results: Computer experiments show that the proposed algorithms reach optimal solutions in 25 and 28 analyzed instances. In addition, for the instances where optimality was not achieved, the average gap does not exceed the 2% for both versions of the proposed algorithms.

Conclusions: The proposed encoding scheme guarantees the discretization of the algorithms, generating solutions that converge towards the optimum. In addition, the proposed encoding allows natural use of movement operators originally proposed for the algorithms used. Performance obtained by the algorithms is adequate and of high quality.

Downloads

Download data is not yet available.

Author Biographies

César Andrés López Martínez, Universidad Pontificia Bolivariana. Montería, (Colombia)

Graduado del programa de Ingeniería Industrial en el año 2010 de la Universidad De Córdoba (Montería, Colombia).  Es candidato a Magister en Ingeniería De Producción de la Universidad Tecnológica De Bolívar (Cartagena De Indias, Colombia). Sus intereses investigativos incluyen tópicos en Metaheurísticas, Investigación De Operaciones, Programación De Producción, Optimización. Actualmente es Docente interno en la facultad de Ingeniería Industrial de la Universidad Pontificia Bolivariana (Montería, Colombia). https://orcid.org/0000-0003-2750-7699

Helman Enrique Hernández Riaño, Universidad de Córdoba. Montería, (Colombia)

Graduado del programa de Ingeniería Industrial en el año 1999 de la Universidad Distrital (Bogotá, Colombia). Es Magister en Gestión de Organizaciones de la Universidad EAN (Bogotá, Colombia). Es Doctor en Ingeniería Industrial de la Universidad del Norte (Barranquilla, Colombia). Sus intereses investigativos incluyen tópicos en Metaheurísticas, Investigación de Operaciones, Programación de Producción, Logística y Optimización. Actualmente es Profesor Titular del Departamento de Ingeniería Industrial de la Universidad de Córdoba (Montería, Colombia). https://orcid.org/0000-0003-3042-2573

Manuel Jesús Soto de la Vega, Universidad Tecnológica de Bolivar. Cartagena, (Colombia)

Graduado del programa de Ingeniería Industrial en el año 2012 de la Universidad de Córdoba. Es Magister en Ingeniería Industrial de la Universidad de los Andes (Bogotá, Colombia). Actualmente profesor de la Universidad Tecnológica De Bolívar vinculado al programa de Ingeniería Industrial. Áreas de trabajo en investigación de operaciones, incluyendo trabajos en optimización y simulación de procesos.

 

References

A. Agnetis, G. Murgia and S. Sbrilli, “A job shop scheduling problem with human operators in handicraft production,” Int. J. Prod. Res., vol. 52, no. 13, pp. 3820–3831, Jul. 2014. https://doi.org/10.1080/00207543.2013.831220

M. Abdel-Basset, L. Abdel-Fatah and A. K. Sangaiah, “Metaheuristic Algorithms: A Comprehensive Review,” in Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications. Cambridge, MA, USA: Elsevier Inc., 2018, pp. 185–231. https://doi.org/10.1016/B978-0-12-813314-9.00010-4

M. Jain, V. Singh and A. Rani, “A novel nature-inspired algorithm for optimization: Squirrel search algorithm,” Swarm Evol. Comput., vol. 44, pp. 148–175, Feb. 2019. https://doi.org/10.1016/j.swevo.2018.02.013

L. Gao, X. Li, X. Wen, C. Lu and F. Wen, “A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem,” Comput. Ind. Eng., vol. 88, pp. 417–429, Oct. 2015. https://doi.org/10.1016/j.cie.2015.08.002

K. Z. Gao, P. N. Suganthan, T. J. Chua, C. S. Chong, T. X. Cai and Q. K. Pan, “A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion,” Expert Syst. Appl., vol. 42, no. 21, pp. 7652–7663, Nov. 2015. https://doi.org/10.1016/j.eswa.2015.06.004

K. Z. Gao, P. N. Suganthan, Q. K. Pan, T. J. Chua, C. S. Chong and T. X. Cai, “An improved artificial bee colony algorithm for flexible job-shop scheduling problem with fuzzy processing time,” Expert Syst. Appl., vol. 65, pp. 52–67, Dec. 2016. https://doi.org/10.1016/j.eswa.2016.07.046

A. Maroosi, R. C. Muniyandi, E. Sundararajan and A. M. Zin, “A parallel membrane inspired harmony search for optimization problems: A case study based on a flexible job shop scheduling problem,” Appl. Soft Comput. J., vol. 49, pp. 120–136, Dec. 2016. https://doi.org/10.1016/j.asoc.2016.08.007

A. Ahmadi-Javid and P. Hooshangi-Tabrizi, “Integrating employee timetabling with scheduling of machines and transporters in a job-shop environment: A mathematical formulation and an Anarchic Society Optimization algorithm,” Comput. Oper. Res., vol. 84, pp. 73–91, Aug. 2017. https://doi.org/10.1016/j.cor.2016.11.017

H. Piroozfard, K. Y. Wong and A. D. Asl, “An improved biogeography-based optimization for achieving optimal job shop scheduling solutions,” Procedia Comput. Sci., vol. 115, pp. 30–38, Aug. 2017. https://doi.org/10.1016/j.procs.2017.09.073

N. Sharma, H. Sharma and A. Sharma, “Beer froth artificial bee colony algorithm for job-shop scheduling problem,” Appl. Soft Comput. J., vol. 68, pp. 507–524, Jul. 2018. https://doi.org/10.1016/j.asoc.2018.04.001

B. Marzouki, O. B. Driss and K. Ghédira, “Solving Distributed and Flexible Job shop Scheduling Problem using a Chemical Reaction Optimization metaheuristic,” Procedia Comput. Sci., vol. 126, pp. 1424–1433, Jan. 2018. https://doi.org/10.1016/j.procs.2018.08.114

A. Agnetis, M. Flamini, G. Nicosia and A. Pacifici, “A job-shop problem with one additional resource type,” J. Sched., vol. 14, no. 3, pp. 225–237, Jun. 2011. https://doi.org/10.1007/s10951-010-0162-4

M. R. Sierra, C. Mencía and R. Varela, “New schedule generation schemes for the job-shop problem with operators,” J. Intell. Manuf., vol. 26, no. 3, pp. 511–525, Jul. 2013. https://doi.org/10.1007/s10845-013-0810-6

B. Giffler and G. L. Thompson, “Algorithms for Solving Production-Scheduling Problems,” Oper. Res., vol. 8, no. 4, pp. 487–503, Aug. 1960. https://doi.org/10.1287/opre.8.4.487

R. Mencia, M. R. Sierra, C. Mencia and R. Varela, “Genetic Algorithm for Job-Shop Scheduling with Operators,” in New Challenges on Bioinspired Applications, 4th Inter­national Work-conference on the Interplay Between Natural and Artificial Computation, IWINAC 2011, La Palma, Canary Islands, Spn, 30 May. - 3 Jun. 2011, pp. 305–314. https://doi.org/10.1007/978-3-642-21326-7

R. Mencía, M. R. Sierra, C. Mencía and R. Varela, “A genetic algorithm for job-shop scheduling with operators enhanced by weak Lamarckian evolution and search space narrowing,” Nat. Comput., vol. 13, no. 2, pp. 179–192, May. 2013. https://doi.org/10.1007/s11047-013-9373-x

F. Barber, J. Escamilla, C. Mencia, M. Rodriguez-Molins, M. A. Salido and M. R. Sierra, “Robust solutions to job-shop scheduling problems with operators,” Proc. - Int. Conf. Tools with Artif. Intell. ICTAI, Athens, Greece, 7-9 Nov. 2012. https://doi.org/10.1109/ICTAI.2012.48

M. F. Tasgetiren, M. Sevkli, Y.-Ch. Liang and G. Gencyilmaz, “Particle swarm optimization algorithm for single machine total weighted tardiness problem,” Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753), Portland, OR, USA, USA, 19-23 Jun. 2004, pp. 1412–1419. https://doi.org/10.1109/CEC.2004.1331062

R. Chaudhry, S. Tapaswi and N. Kumar, “Forwarding Zone enabled PSO routing with Network lifetime maximization in MANET,” Appl. Intell., vol. 48, no. 9, pp. 3053–3080, Sept. 2018. https://doi.org/10.1007/s10489-017-1127-5

I. Dubey and M. Gupta, “Uniform mutation and SPV rule based optimized PSO algorithm for TSP problem,” Proc. 2017 4th Int. Conf. Electron. Commun. Syst., ICECS 2017, Coimbatore, India, 24-25 Feb. 2017, pp. 168–172. https://doi.org/10.1109/ECS.2017.8067862

N. Kumar and D. P. Vidyarthi, “A model for resource-constrained project scheduling using adaptive PSO,” Soft Comput., vol. 20, no. 4, pp. 1565–1580, Feb. 2015. https://doi.org/10.1007/s00500-015-1606-8

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. R. Kan, “Optimization and approximation in deterministic machine scheduling: a survey,” Ann. Discret. Math., vol. 5, pp. 287–326, 1979. https://doi.org/10.1016/S0167-5060(08)70356-X

R Core Team, “R: A language and environment for statistical computing” R Foundation for Statistical Computing, 2019. Disponible: https://www.r-project.org/

Downloads

Published

2019-12-02

How to Cite

López Martínez, C. A., Hernández Riaño, H. E., & Soto de la Vega, M. J. (2019). A Discrete Squirrel Search Algorithm applied to the Job Shop problem with skilled operators. INGE CUC, 15(2), 143–154. https://doi.org/10.17981/ingecuc.15.2.2019.14

Issue

Vol. 15 No. 2 (2019): (July-December)

Section

In Press

License

Copyright (c) 2019 INGE CUC

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Published papers are the exclusive responsibility of their authors and do not necessary reflect the opinions of the editorial committee. 

INGE CUC Journal respects the moral rights of its authors, whom must cede the editorial committee the patrimonial rights of the published material. In turn, the authors inform that the current work is unpublished and has not been previously published. 

All articles are licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Licencia Creative Commons

Most read articles by the same author(s)