An evolutionary approach for solving the job shop scheduling problem in a service industry

(1) Milad Yousefi Mail (Departamento de Engenharia Mecânica, Universidade Federal de Minas Gerais - UFMG, Brazil)
(2) Moslem Yousefi Mail (Centre of Advanced Mechatronics and Robotics, College of Engineering, University Tenaga Nasional (UNITEN), Malaysia)
(3) * Danial Hooshyar Mail (Department of Software Engineering, Faculty of Computer Science and Information Technology, University of Malaya, Kuala Lumpur, Malaysia)
(4) Jefferson Ataide de Souza Oliveira Mail (Departamento de Engenharia Mecânica, Universidade Federal de Minas Gerais - UFMG, Brazil)
*corresponding author


In this paper, an evolutionary-based approach based on the discrete particle swarm optimization (DPSO) algorithm is developed for finding the optimum schedule of a registration problem in a university. Minimizing the makespan, which is the total length of the schedule, in a real-world case study is considered as the target function. Since the selected case study has the characteristics of job shop scheduling problem (JSSP), it is categorized as a NP-hard problem which makes it difficult to be solved by conventional mathematical approaches in relatively short computation time.


Scheduling; Job shop scheduling problem; Optimization; Discrete particle swarm optimization



Article metrics

Abstract views : 2441 | PDF views : 570




Full Text



M. Yousefi and R. M. Yusuff, “Minimizing Earliness and Tardiness Penalties in a Single Machine Scheduling Against Common Due Date using Genetic Algorithm,” Res. Appl. Serv., vol. 4, no. 9, pp. 1205–1210, 2012.

Y. Zheng, L. Lian, Z. Fu, and K. Mesghouni, “Evolutional Algorithm in Solving Flexible Job Shop Scheduling Problem with Uncertainties,” in In LISS 2013, Springer Berlin Heidelberg, 2015, pp. 1009–1015.

A. S. Manne, “On the job-shop scheduling problem,” Oper. Res., vol. 8, no. 2, pp. 219–223, 1960.

M. Held and R. M. Karp, “A dynamic programming approach to sequencing problems,” J. Soc. Ind. Appl. Math., vol. 10, no. 1, pp. 196–210, 1962.

A. Ponsich and C. A. C. Coello, “A hybrid differential evolution-tabu search algorithm for the solution of job-shop scheduling problems,” Appl. Soft Comput., vol. 13, no. 1, pp. 462–474, 2013.

P. Brucker, B. Jurisch, and B. Sievers, “A branch and bound algorithm for the job-shop scheduling problem,” Discret. Appl. Math., vol. 49, no. 1, pp. 107–127, 1994.

M. Yousefi, M. Yousefi, and A. N. Darus, “A modified imperialist competitive algorithm for constrained optimization of plate-fin heat exchangers,” Proc. Inst. Mech. Eng. Part A J. Power Energy, vol. 226, no. 8, pp. 1050–1059, 2012.

M. Yousefi and R. M. Yusuff, “Minimising earliness and tardiness penalties in single machine scheduling against common due date using imperialist competitive algorithm,” Int. J. Prod. Res., vol. 51, no. 16, pp. 4797–4804, 2013.

S. Meeran and M. S. Morshed, “A hybrid genetic tabu search algorithm for solving job shop scheduling problems: a case study,” J. Intell. Manuf., vol. 23, no. 4, pp. 1063–1078, 2012.

S. S. Panwalkar and W. Iskander, “A survey of scheduling rules,” Oper. Res., vol. 25, no. 1, pp. 45–61, 1977.

T.-C. Chiang and L.-C. Fu, “Using dispatching rules for job shop scheduling with due date-based objectives,” Int. J. Prod. Res., vol. 45, no. 14, pp. 3245–3262, 2007.

J. C. Tay and N. B. Ho, “Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems,” Comput. Ind. Eng., vol. 54, no. 3, pp. 453–473, 2008.

J. Adams, E. Balas, and D. Zawack, “The shifting bottleneck procedure for job shop scheduling,” Manage. Sci., vol. 34, no. 3, pp. 391–401, 1988.

E. Demirkol, S. Mehta, and R. Uzsoy, “A computational study of shifting bottleneck procedures for shop scheduling problems,” J. Heuristics, vol. 3, no. 2, pp. 111–137, 1997.

C.-L. Chen and C.-L. Chen, “Bottleneck-based heuristics to minimize total tardiness for the flexible flow line with unrelated parallel machines,” Comput. Ind. Eng., vol. 56, no. 4, pp. 1393–1401, 2009.

R. Zhang and C. Wu, “A hybrid approach to large-scale job shop scheduling,” Appl. Intell., vol. 32, no. 1, pp. 47–59, 2010.

J. F. Gonçalves, J. J. de Magalhães Mendes, and M. G. C. Resende, “A hybrid genetic algorithm for the job shop scheduling problem,” Eur. J. Oper. Res., vol. 167, no. 1, pp. 77–95, 2005.

R. Zhang and C. Wu, “A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardinessobjective,” Comput. Oper. Res., vol. 38, no. 5, pp. 854–867, 2011.

J. Kennedy and R. C. Eberhart, “A discrete binary version of the particle swarm algorithm,” in Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., 1997 IEEE International Conference on, 1997, vol. 5, pp. 4104–4108.

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

International Journal of Advances in Intelligent Informatics
ISSN 2442-6571  (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
E: (paper handling issues) (publication issues)

View IJAIN Stats

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0