A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem
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
References
- 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
- M. R. Garey and D. S. Johnson, Computer and Intractability: A Guide to the Theory of NPCompleteness. 1979.
- J. R. Jackson, “Scheduling a production to minimize maximum tardiness,” Res. Report. Manag. Sci. Res. Proj., vol. 43, 1955.
- 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
- 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
- B. Roy and B. Sussmann, “Les problems d’ordonnancement avec constraintes disjonctives,” Note D.S. 9, SEMA, 1964.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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.
- 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
- 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
- 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
- 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
- J. Schönberger, “Memetic Algorithm Vehicle Routing,” in Operational Freight Carrier Planning, Berlin/Heidelberg: Springer-Verlag, 2005, pp. 65–76.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- M. A. González Fernández, Soluciones metaheurísticas al ‘job-shop scheduling problem with sequence-dependent setup times, 2011.
- 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.