Skip to main navigation menu Skip to main content Skip to site footer

Vol. 26 No. 44 (2017)

Papers

A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem

https://doi.org/10.19053/01211129.v26.n44.2017.5776

Published 2017-01-25

  • Henry Lamos-Díaz
    • ,
  • Karin Aguilar-Imitola
    • ,
  • Yuleiny Tatiana Pérez-Díaz
    • ,
  • Silvia Galván-Núñez

Henry Lamos-Díaz
Ph. D. Universidad Industrial de Santander (Bucaramanga-Santander, Colombia).

Karin Aguilar-Imitola
M. Sc. Universidad Industrial de Santander (Bucaramanga-Santander, Colombia).

Yuleiny Tatiana Pérez-Díaz
Esp. Universidad Industrial de Santander (Bucaramanga-Santander, Colombia).

Silvia Galván-Núñez
M. Sc. Universidad Industrial de Santander (Bucaramanga-Santander, Colombia).

Abstract

The Job Shop Scheduling Problem (JSP) is a combinatorial optimization problem cataloged as type NP-Hard. To solve this problem, several heuristics and metaheuristics have been used. In order to minimize the makespan, we propose a Memetic Algorithm (MA), which combines the exploration of the search space by a Genetic Algorithm (GA), and the exploitation of the solutions using a local search based on the neighborhood structure of Nowicki and Smutnicki. The genetic strategy uses an operation-based representation that allows generating feasible schedules, and a selection probability of the best individuals that are crossed using the JOX operator. The results of the implementation show that the algorithm is competitive with other approaches proposed in the literature.

Keywords

Job Shop Schedule, local search, memetic algorithm, metaheuristics

PDF XML

References

  1. M. Frutos and F. Tohmé, “A Multi-objective Memetic Algorithm for the Job-Shop Scheduling Problem,” Oper. Res., vol. 13 (2), pp. 233–250, Jul. 2013. DOI: http://doi.org/10.1007/s12351-012-0125-y. DOI: https://doi.org/10.1007/s12351-012-0125-y
  2. M. R. Garey and D. S. Johnson, Computer and Intractability: A Guide to the Theory of NPCompleteness. 1979.
  3. J. R. Jackson, “Scheduling a production to minimize maximum tardiness,” Res. Report. Manag. Sci. Res. Proj., vol. 43, 1955.
  4. S. M. Johnson, “Optimal two and three stage production schedules with setup times included,” Naval. Res. Logist. Quart., vol. 1 (1), pp. 61–68, Mar. 1954. DOI: http://doi.org/10.1002/nav.3800010110. DOI: https://doi.org/10.1002/nav.3800010110
  5. S. B. Akers and J. Friedman, “A Non-Numerical Approach to Production Scheduling Problems,” Oper. Res., vol. 3 (4), pp. 429–442, 1955. DOI: http://doi.org/10.1287/opre.3.4.429. DOI: https://doi.org/10.1287/opre.3.4.429
  6. B. Roy and B. Sussmann, “Les problems d’ordonnancement avec constraintes disjonctives,” Note D.S. 9, SEMA, 1964.
  7. E. Balas, “Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm,” Oper. Res., vol. 17 (6), pp. 941–957, Dec. 1969. DOI: http://doi.org/10.1287/opre.17.6.941. DOI: https://doi.org/10.1287/opre.17.6.941
  8. D. Applegate and W. Cook, “A Computational Study of the Job Shop Scheduling Problem,” ORSA J. Comput., vol. 3 (2), pp. 149–156, May. 1991. DOI: http://doi.org/10.1287/ijoc.3.2.149. DOI: https://doi.org/10.1287/ijoc.3.2.149
  9. P. Brucker, B. Jurisch, and B. Sievers, “A branch and bound algorithm for the job-shop scheduling problem.” Discr. Appl. Math., vol. 49, pp. 107–127, 1994. DOI: http://doi.org/10.1016/0166-218X(94)90204-6. DOI: https://doi.org/10.1016/0166-218X(94)90204-6
  10. C. Mencía, M. R. Sierra, and R. Varela, “Depthfirst heuristic search for the job shop scheduling problem,” Ann. Oper. Res., vol. 206 (1), pp. 265–296, Jul. 2013. DOI: http://doi.org/10.1007/s10479-012-1296-x. DOI: https://doi.org/10.1007/s10479-012-1296-x
  11. Y. Tan and Z. Jiang, “A branch and bound algorithm and iterative reordering strategies for inserting additional trains in real time: A case study in Germany.” Math. Probl. Eng., vol. 2015, pp. 1–12, 2015. DOI: http://doi.org/10.1155/2015/289072. DOI: https://doi.org/10.1155/2015/289072
  12. K. Hadavi, Y.-W. Hou, W.-L. Hsu, D. Levy, and M. Pinedo, “Dispatching Issues in Job Shop Scheduling,” in New Directions for Operations Research in Manufacturing - Chapter 14, Berlin, Heidelberg: Springer Berlin Heidelberg, 1992, pp. 234–245. DOI: http://doi.org/10.1007/978-3-642-77537-6_14. DOI: https://doi.org/10.1007/978-3-642-77537-6_14
  13. S. Yokoyama, H. Iizuka, and M. Yamamoto, “Priority rule-based reconstruction for total weighted tardiness minimization of job-shop scheduling problem,” J. Adv. Mech. Des. Syst. Manuf., vol. 8 (5), pp. 1–6, 2014. DOI: http://doi.org/10.1299/jamdsm.2014jamdsm0073. DOI: https://doi.org/10.1299/jamdsm.2014jamdsm0073
  14. J. Adams, E. Balas, and D. Zawack, “The Shifting Bottleneck Procedure for Job Shop Scheduling,” Manage. Sci., vol. 34 (3), pp. 391–401, Mar. 1988. DOI: http://doi.org/10.1287/mnsc.34.3.391. DOI: https://doi.org/10.1287/mnsc.34.3.391
  15. R. M. Silva, C. Cubillos, and D. Cabrera Paniagua, “A Constructive Heuristic for Solving the Job- Shop Scheduling Problem,” IEEE Latin Am Trans, vol. 14 (6), pp. 2758–2763, Jun. 2016. DOI: http://doi.org/10.1109/TLA.2016.7555250. DOI: https://doi.org/10.1109/TLA.2016.7555250
  16. M. Dell’Amico and M. Trubian, “Applying tabu search to the job-shop scheduling problem,” Ann. Oper. Res., vol. 41 (1-4), pp. 231–252, Sep. 1993. DOI: http://doi.org/10.1007/BF02023076. DOI: https://doi.org/10.1007/BF02023076
  17. E. Nowicki and C. Smutnicki, “An advanced tabu search algorithm for the job shop problem,” J. Sched., vol. 8 (2), pp. 145–159, Apr. 2005. DOI: http://doi.org/10.1007/s10951-005-6364-5. DOI: https://doi.org/10.1007/s10951-005-6364-5
  18. C. Zhang, P. Li, Z. Guan, and Y. Rao, “A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem,” Comput. Oper. Res., vol. 34 (11), pp. 3229–3242, Nov. 2007. DOI: http://doi.org/10.1016/j.cor.2005.12.002. DOI: https://doi.org/10.1016/j.cor.2005.12.002
  19. Y. K. Lin and C. S. Chong, “A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem,” JIMO, vol. 12 (2), pp. 703–717, Jun. 2015. DOI: http://doi.org/10.3934/jimo.2016.12.703. DOI: https://doi.org/10.3934/jimo.2016.12.703
  20. P. J. M. van Laarhoven, E. H. L. Aarts, and J. K. Lenstra, “Job Shop Scheduling by Simulated Annealing,” Operations Res., vol. 40 (1), pp. 113–125, Feb. 1992. DOI: http://doi.org/10.1287/opre.40.1.113. DOI: https://doi.org/10.1287/opre.40.1.113
  21. M. Rojas-Santiago, P. Damodaran, S. Muthuswamy, and M. C. Vélez-Gallego, “Makespan minimization in a job shop with a BPM using simulated annealing,” Int. J. Adv. Manuf. Technol., vol. 68 (9–12), pp. 2383–2391, Oct. 2013. DOI: http://doi.org/10.1007/s00170-013-4858-4. DOI: https://doi.org/10.1007/s00170-013-4858-4
  22. 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 (5), pp. 854–867, May. 2011. DOI: http://doi.org/10.1016/j.cor.2010.09.014. DOI: https://doi.org/10.1016/j.cor.2010.09.014
  23. D. Merkle and M. Middendorf, “A New Approach to Solve Permutation Scheduling Problems with Ant Colony Optimization,” Springer Berlin Heidelberg, 2001, pp. 484–494. DOI: http://doi.org/10.1007/3-540-45365-2_50. DOI: https://doi.org/10.1007/3-540-45365-2_50
  24. A. Udomsakdigool and V. Kachitvichyanukul, “Multiple colony ant algorithm for job-shop scheduling problem,” Int. J. Prod. Res., vol. 46 (15), pp. 4155–4175, Aug. 2008. DOI: http://doi.org/10.1080/00207540600990432. DOI: https://doi.org/10.1080/00207540600990432
  25. Z. Rui, W. Shilong, Z. Zheqi, and Y. Lili, “An ant colony algorithm for job shop scheduling problem with tool flow,” Proc. Inst. Mech. Eng. Part B J. Eng. Manuf., vol. 228 (8), pp. 959–968, Aug. 2014. DOI: http://doi.org/10.1177/0954405413514398. DOI: https://doi.org/10.1177/0954405413514398
  26. P. Korytkowski, S. Rymaszewski, and T. Wisniewski, “Ant colony optimization for job shop scheduling using multi-attribute dispatching rules,” Int. J. Adv. Manuf. Technol., vol. 67 (1-4), pp. 231–241, Jul. 2013. DOI: http://doi.org/10.1007/s00170-013-4769-4. DOI: https://doi.org/10.1007/s00170-013-4769-4
  27. R. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” in Proceedings of the Sixth International Symposium on Micro Machine and Human Science, pp. 39–43, Aug. 2002. DOI: http://doi.org/10.1109/mhs.1995.494215. DOI: https://doi.org/10.1109/MHS.1995.494215
  28. D. Y. Sha and H.-H. Lin, “A multi-objective PSO for job-shop scheduling problems,” Expert Syst. Appl., vol. 37 (2), pp. 1065–1070, Mar. 2010. DOI: http://doi.org/10.1016/j.eswa.2009.06.041. DOI: https://doi.org/10.1016/j.eswa.2009.06.041
  29. T.-L. Lin et al., “An efficient job-shop scheduling algorithm based on particle swarm optimization?,” Expert Syst. Appl., vol. 37 (3), pp. 2629–2636, Mar. 2010. DOI: http://doi.org/10.1016/j.eswa.2009.08.015. DOI: https://doi.org/10.1016/j.eswa.2009.08.015
  30. F. Zhao, J. Tang, J. Wang, and Jonrinaldi, “An improved particle swarm optimization with decline disturbance index (DDPSO) for multi-objective job-shop scheduling problem,” Comput. Oper. Res., vol. 45, pp. 38–50, May. 2014. DOI: http://doi.org/10.1016/j.cor.2013.11.019. DOI: https://doi.org/10.1016/j.cor.2013.11.019
  31. T. Watanabe, H. Tokumaru, and Y. Hashimoto, “Job-shop scheduling using neural networks,” Control Eng. Pract., vol. 1 (6), pp. 957–961, Dec. 1993. DOI: http://doi.org/10.1016/0967-0661(93)90005-C. DOI: https://doi.org/10.1016/0967-0661(93)90005-C
  32. G. R. Weckman, C. V. Ganduri, and D. A. Koonce, “A neural network job-shop scheduler,” J. Intell. Manuf., vol. 19 (2), pp. 191–201, Apr. 2008. DOI: http://doi.org/10.1007/s10845-008-0073-9. DOI: https://doi.org/10.1007/s10845-008-0073-9
  33. D. C. Mattfeld and C. Bierwirth, “An efficient genetic algorithm for job shop scheduling with tardiness objectives,” Eur. J. Oper. Res., vol. 155 (3), pp. 616–630, Jun. 2004. DOI: http://doi.org/10.1016/S0377-2217(03)00016-X. DOI: https://doi.org/10.1016/S0377-2217(03)00016-X
  34. J.-T. Tsai, T.-K. Liu, W.-H. Ho, and J.-H. Chou, “An improved genetic algorithm for job-shop scheduling problems using Taguchi-based crossover,” Int. J. Adv. Manuf. Technol., vol. 38 (9–10), pp. 987–994, Sep. 2008. DOI: http://doi.org/10.1007/s00170-007-1142-5. DOI: https://doi.org/10.1007/s00170-007-1142-5
  35. I. Essafi, Y. Mati, and S. Dauzere-Peres, “A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem,” Comput. Oper. Res., vol. 35 (8), pp. 2599–2616, Aug. 2008. DOI: http://doi.org/10.1016/j.cor.2006.12.019. DOI: https://doi.org/10.1016/j.cor.2006.12.019
  36. L. Wang, J.-C. Cai, and M. Li, “An adaptive multi-population genetic algorithm for jobshop scheduling problem,” Adv. Manuf., vol. 4 (2), pp. 142–149, Jun. 2016. DOI: http://doi.org/10.1007/s40436-016-0140-y. DOI: https://doi.org/10.1007/s40436-016-0140-y
  37. P. Moscato and M. G. Norman, “A memetic approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems,” Proc. Parallel Comput. Transputer Appl., vol. 28 (1), pp. 177–186, 1992.
  38. X. Guo, Z. Wu, and G. Yang, “A Hybrid Adaptive Multi-objective Memetic Algorithm for 0/1 Knapsack Problem,” Springer Berlin Heidelberg, 2005, pp. 176–185. DOI: http://doi.org/10.1007/11589990_20. DOI: https://doi.org/10.1007/11589990_20
  39. H. Ishibuchi, Y. Hitotsuyanagi, N. Tsukamoto, and Y. Nojima, “Implementation of Multiobjective Memetic Algorithms for Combinatorial Optimization Problems: A Knapsack Problem Case Study,” Studies in Computational Intelligence-Chapter 2, vol. 171, pp. 27–49, 2009. DOI: http://doi.org/10.1007/978-3-540-88051-6_2. DOI: https://doi.org/10.1007/978-3-540-88051-6_2
  40. A. Rezoug, D. Boughaci, and M. Badr-El-Den, “Memetic Algorithm for Solving the 0-1 Multidimensional Knapsack Problem,” Springer International Publishing, 2015, pp. 298–304. DOI: https://doi.org/10.1007/978-3-319-23485-4_31
  41. C. Prins and S. Bouchenoua, “A Memetic Algorithm Solving the VRP, the CARP and General Routing Problems with Nodes, Edges and Arcs,” Studies in Fuzziness and Soft Computing-Chapter 4, vol. 166, pp. 65–85, 2005. DOI: http://doi.org/10.1007/3-540-32363-5_4. DOI: https://doi.org/10.1007/3-540-32363-5_4
  42. J. Schönberger, “Memetic Algorithm Vehicle Routing,” in Operational Freight Carrier Planning, Berlin/Heidelberg: Springer-Verlag, 2005, pp. 65–76.
  43. J. Nalepa and M. Blocho, “Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows,” Soft Comput., vol. 20 (6), pp. 2309–2327, Jun. 2016. DOI: http://doi.org/10.1007/s00500-015-1642-4. DOI: https://doi.org/10.1007/s00500-015-1642-4
  44. J.-F. Cordeau, M. Gaudioso, G. Laporte, and L. Moccia, “A Memetic Heuristic for the Generalized Quadratic Assignment Problem,” INFORMS J. Comput., vol. 18 (4), pp. 433–443, Nov. 2006. DOI: http://doi.org/10.1287/ijoc.1040.0128. DOI: https://doi.org/10.1287/ijoc.1040.0128
  45. U. Benlic and J.-K. Hao, “Memetic search for the quadratic assignment problem,” Expert Syst. Appl., vol. 42 (1), pp. 584–595, Jan. 2015. DOI: http://doi.org/10.1016/j.eswa.2014.08.011. DOI: https://doi.org/10.1016/j.eswa.2014.08.011
  46. T. Fischer and P. Merz, “A Memetic Algorithm for the Optimum Communication Spanning Tree Problem,” in Hybrid Metaheuristics, Springer Berlin Heidelberg, pp. 170–184. DOI: https://doi.org/10.1007/978-3-540-75514-2_13
  47. H.-C. Cheng, T.-C. Chiang, and L.-C. Fu, “A two-stage hybrid memetic algorithm for multiobjective job shop scheduling,” Expert Syst. Appl., vol. 38 (9), pp. 10983–10998, Sep. 2011. DOI: http://doi.org/10.1016/j.eswa.2011.02.142. DOI: https://doi.org/10.1016/j.eswa.2011.02.142
  48. M. R. Raeesi N. and Z. Kobti, “A memetic algorithm for job shop scheduling using a critical-path-based local search heuristic,” Memetic Comp, vol. 4 (3), pp. 231–245, Sep. 2012. DOI: http://doi.org/10.1007/s12293-012-0084-0. DOI: https://doi.org/10.1007/s12293-012-0084-0
  49. Y. Yuan and H. Xu, “Multiobjective Flexible Job Shop Scheduling Using Memetic Algorithms,” IEEE Trans Automat Sci Eng, vol. 12 (1), pp. 336–353, Jan. 2015. DOI: http://doi.org/10.1109/TASE.2013.2274517. DOI: https://doi.org/10.1109/TASE.2013.2274517
  50. R. Mencía, M. R. Sierra, C. Mencía, and R. Varela, “Memetic algorithms for the job shop scheduling problem with operators,” Appl. Soft Comput., vol. 34, pp. 94–105, Sep. 2015. DOI: http://doi.org/10.1016/j.asoc.2015.05.004. DOI: https://doi.org/10.1016/j.asoc.2015.05.004
  51. E. Nowicki and C. Smutnicki, “A Fast Taboo Search Algorithm for the Job-Shop Problem,” Manage. Sci., vol. 42 (6), pp. 797–813, Jun. 1996. DOI: http://doi.org/10.1287/mnsc.42.6.797. DOI: https://doi.org/10.1287/mnsc.42.6.797
  52. L. Gao, G. Zhang, L. Zhang, and X. Li, “An efficient memetic algorithm for solving the job shop scheduling problem,” Comput. Ind. Eng., vol. 60(4), pp. 699–705, May. 2011. DOI: http://doi.org/10.1016/j.cie.2011.01.003. DOI: https://doi.org/10.1016/j.cie.2011.01.003
  53. J. E. Beasley, “OR-Library: Distributing Test Problems by Electronic Mail,” J. Oper. Res. Soc., vol. 41 (11), p. 1069, Nov. 1990. DOI: http://doi.org/10.1057/jors.1990.166. DOI: https://doi.org/10.2307/2582903
  54. M. A. González Fernández, Soluciones metaheurísticas al ‘job-shop scheduling problem with sequence-dependent setup times, 2011.
  55. S. M. Kumrul Hasan, R. Sarker, D. Essam, and D. Cornforth, “Memetic algorithms for solving job-shop scheduling problems,” Memetic Comp, vol. 1 (1), pp. 69–83, Mar. 2009. DOI: http://doi.org/10.1007/s12293-008-0004-5. DOI: https://doi.org/10.1007/s12293-008-0004-5

Downloads

Download data is not yet available.

Most read articles by the same author(s)

Similar Articles

You may also start an advanced similarity search for this article.