An effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem

Keywords: Critical path, Genetic algorithm, Job shop scheduling, Metaheuristic, Uniform crossover.

Abstract

This work presents an effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem with the objective of makespan minimization (GA-CPG-GT). Even though passing important traits from parents to offspring is known to be an important feature of any uniform crossover operator, most of the proposed operators adopt random exchange of genetic materials between parents; this is probably due to the fact that it is tricky to identify the genetic materials that hold the important traits. For that reason, in this work, a new selective exchange of genetic materials is proposed. In the proposed approach, at first, the genetic materials that hold the important traits are identified according to some domain specific information provided by the critical paths of the parents, and then the exchange is made on favor of them. The properties of critical path are usually utilized by the local search methods such as tabu search and simulating annealing; however, in this work, they are utilized in the global search method GA during the crossover operator. The implications of the proposed approach are investigated using the Giffler and Thompson crossover operator, which is a uniform crossover combined with the G&T algorithm. The proposed approach is tested on 55 benchmarks, with the proposed selective exchange, and without it using the random one, and also compared with other 5 similar works reported in the literature. The computational results validate the enhancements accomplished by the proposed selective exchange, and show the superiority of the proposed algorithm over the compared works in terms of solution quality, and validate its effectiveness.

Downloads

Download data is not yet available.

References

J. Carlier, E. Pinson, “An algorithm for solving the job-shop problem”, Manag Sci, vol. 35, no. 2, pp. 164-176, 1989. https://doi.org/10.1287/mnsc.35.2.164

J. Adams, E. Balas, D. Zawack, “The shifting bottleneck procedure for job shop scheduling”, Manag Sci, vol. 34, no. 3, pp. 391-401, 1988. https://doi.org/10.1287/mnsc.34.3.391

J.H. Blackstone, D.T. Phillips, G.L. Hogg, “A state-of-the-art survey of dispatching rules for manufacturing job shop operations”, Int J Prod Res, vol. 20, no. 1, pp. 27-45, 1982. https://doi.org/10.1080/00207548208947745

T. Satake, K. Morikawa, K. Takahashi, N. Nakamura, “ Simulated annealing approach for minimizing the makespan of the general job-shop”,Int J Prod Econ, pp. 60–61, pp. 515-522, 1999. https://doi.org/10.1016/S0925-5273(98)00171-6

E. Nowicki, C. Smutnicki, “An advanced tabu search algorithm for the job shop problem”, J Sched, vol. 8, no. 2, pp. 145-159, 2005. https://doi.org/10.1007/s10951-005-6364-5

N. Fığlalı, C. Özkale, O. Engin, A. Fığlalı, “Investigation of ant system parameter interactions by using design of experiments for job-shop scheduling problems”, Comput Ind Eng, vol. 56, no. 2, pp. 538-559, 2009. https://doi.org/10.1016/j.cie.2007.06.001

L. Asadzadeh, “A parallel artificial bee colony algorithm for the job shop scheduling problem with a dynamic migration strategy”, Comput Ind Eng, vol 102, pp. 359-367, 2016. https://doi.org/10.1016/j.cie.2016.06.025

K. &. R. C. Rameshkumar, “A novel discrete PSO algorithm for solving job shop scheduling problem to minimize makespan”. In IOP Conference Series: Materials Science and Engineering, vol. 310, no. IOP Publishing, 2018.

https://doi.org/10.1088/1757-899X/310/1/012143 [9] Atay, Y., & Kodaz, H. “Optimization of job shop scheduling problems using modified clonal selection algorithm”. Turk J Elec Eng & Comp Sci, vol. 22, no. 6, pp. 1528-1539, 2014. https://doi.org/10.3906/elk-1212-26

Dao, T. K., Pan, T. S., & Pan, J. S.“Parallel bat algorithm for optimizing makespan in job shop scheduling problems”, J Intell Manuf, vol. 29, no. 2, pp. 451-462, 2018.

https://doi.org/10.1007/s10845-015-1121-x

G. Zobolas, C. Tarantilis, G. Ioannou, “Exact, heuristic and meta-heuristic algorithms for solving job shop scheduling problems”, F. Xhafa, A. Abraham (Eds.), Metaheuristics for scheduling in industrial and manufacturing applications, Springer, Berlin (2008), pp. 1-40

https://doi.org/10.1007/978-3-540-78985-7_1

A.S. Jain, S. Meeran, “Deterministic job-shop scheduling: past, present and future”, Eur J Oper Res, vol. 113, no. 2, pp. 390-434, 1999. https://doi.org/10.1016/S0377-2217(98)00113-1

"R. Cheng, M. Gen, Y. Tsujimura A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation Comput Ind Eng, vol. 30, no. 4, pp. 983-997, 1996.

https://doi.org/10.1016/0360-8352(96)00047-2

M. Watanabe, K. Ida, M. Gen, "A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem", Comput Ind Eng, vol. 48, no. 4, pp. 743-752, 2005 https://doi.org/10.1016/j.cie.2004.12.008

M. Kurdi, “A new hybrid island model genetic algorithm for job shop scheduling problem”, Comput Ind Eng, vol. 88, 273-28, 2015.

https://doi.org/10.1016/j.cie.2015.07.015

R. Yusof, M. Khalid, G.T. Hui, S. Md Yusof, M.F. Othman,

“Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm”, Appl Soft Comput, vol. 11, no. 8, pp. 5782-5792, 2011. https://doi.org/10.1016/j.asoc.2011.01.046

M. Kurdi, ”An effective new island model genetic algorithm for job shop scheduling problem”, Comput Oper Res, vol. 67, pp. 132-142, 2016.

https://doi.org/10.1016/j.cor.2015.10.005

R. Cheng, M. Gen, Y. Tsujimura, "A tutorial survey of job-shop scheduling problems using genetic algorithms, Part II: Hybrid genetic search strategies", Comput Ind Eng, vol. 36, no. 2, pp. 343-364,1999.

https://doi.org/10.1016/S0360-8352(99)00136-9

T .Yamada, R. Nakano, “A genetic algorithm applicable to large-scale job-shop problems”. In Proc. the 2nd international workshop on parallel problem solving from nature, Brussels, Belgium, 1992, pp. 281–290.

H. P. Lee, S. Salim, “A modified Giffler and Thompson genetic algorithm on the job shop scheduling problem”, MATEMATIKA, 2006, vol. 22, no. 2, pp. 91-107, 2006.

https://doi.org/10.11113/matematika.v22.n.178

M. Moonen, G. Janssens, “A Gifler-Thompson Focused Genetic Algorithm for the Static Job-Shop Scheduling Problem”, Journal of Information and Computational Science, 4(2). pp. 629-642, 2007.

http://hdl.handle.net/1942/10029

F .Werner, ” A survey of genetic algorithms for shop scheduling problems,. P. Siarry: Heuristics: Theory and Applications, Nova Science Publishers, (2013), pp. 161-222.

M. Kurdi, “An improved island model memetic algorithm with a new cooperation phase for multi-objective job shop scheduling problem”, Comput Ind Eng, vol. 111, pp.183-201, 2007.

https://doi.org/10.1016/j.cie.2017.07.021

A.P. Engelbrecht, “ Computational intelligence: an introduction

(Second Edition)”, John Wiley & Sons, West Sussex, England (2007)

A. Hertz, D. Kobler, “A framework for the description of evolutionary algorithms”, Eur J Oper Res, vol. 126, no. 1, pp. 1-12, 2000. https://doi.org/10.1016/S0377-2217(99)00435-X

L. Gao,G. Zhang, L. Zhang, , X. Li, "An efficient memetic algorithm for solving the job shop scheduling problem", Comput Ind Eng, vol. 60, no. 4, pp. 699-705, 2011.

https://doi.org/10.1016/j.cie.2011.01.003

L. Davis, “Job shop scheduling with genetic algorithms”, In Proc. An international conference on genetic algorithms and their applications, Carnegie-Mellon University, Pittsburgh, PA, USA (1985), pp. 136-140

D. Goldberg, “Genetic algorithms in search, optimization and machine learning”, Addison-Wesley, MA (1989)

T. Yamada, "Studies on metaheuristics for jobshop and flowshop scheduling problems, Doctoral dissertation, Kyoto University, Japan, 2003. https://repository.kulib.kyoto- https://repository.kulib.kyoto- u.ac.jp/dspace/bitstream/2433/148279/1/yjohr00047.pdf

M. Gen, R. Cheng, “Genetic algorithms and engineering design,

John Wiley & Sons, New York (1997).

H. Fisher, G.L. Thompson,” Probabilistic learning combinations of local job-shop scheduling rules”, J. Muth, G. Thompson (Eds.), Industrial scheduling, Prentice-Hall, Englewood Cliffs, NJ (1963), pp. 225-251.

S. Lawrence, “Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques“ (supplement), Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania (1984).

D. Applegate, W. Cook, “A computational study of the job shop scheduling problem”, ORSA J Comput, vol. 3, no. 2, pp. 149-156, 1991. https://doi.org/10.1287/ijoc.3.2.149

J. Adams, E. Balas, D. Zawack, “The shifting bottleneck procedure for job shop scheduling”, Manag Sci, vol. 34, no. 3, pp. 391-401, 1988. https://doi.org/10.1287/mnsc.34.3.391

L. Asadzadeh, K. Zamanifar, “ An agent-based parallel approach for the job shop scheduling problem”, Math Comput Model, vol. 52, no. (11–12),pp.1957-1965,2010. https://doi.org/10.1016/j.mcm.2010.04.019

M. Seo, D. Kim, “Ant colony optimisation with parameterised search space for the job shop scheduling problem”, Int J Prod Res, vol. 48, no. 4, pp. 1143-1154, 2010. https://doi.org/10.1080/00207540802538021

G.G. Yen, B. Ivers, “Job shop scheduling optimization through multiple independent particle swarms”, Int J Intell Comput Cybern, vol. 2, no. 1, pp. 5-33, 2009. https://doi.org/10.1108/17563780910939237

R. Yusof, M. Khalid, G.T. Hui, S. Md Yusof, M.F. Othman,

“Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm”, Appl Soft Comput, vol. 11, no. 8, pp. 5782-5792, 2011. https://doi.org/10.1016/j.asoc.2011.01.046

Published
2019-03-20
How to Cite
[1]
M. Kurdi, “An effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem”, IJISAE, vol. 7, no. 1, pp. 13-18, Mar. 2019.
Section
Research Article