A Multi-objective Reinforcement Learning Algorithm for JSSP | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Multi-objective Reinforcement Learning Algorithm for JSSP

  • Conference paper
  • First Online:
Artificial Neural Networks and Machine Learning – ICANN 2019: Theoretical Neural Computation (ICANN 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11727))

Included in the following conference series:

Abstract

Scheduling is a decision making process that takes care of the allocation of resources to tasks over time. The Job Shop scheduling problem is one of the most complex scheduling scenarios and is commonly encountered in manufacturing industries. Most of the existing studies are based on optimizing one objective, but in real-world problems, multiple criteria often need to be optimized at once. We propose a Multi-Objective Multi-Agent Reinforcement Learning Algorithm that aims to obtain the non-dominated solutions set for Job Shop scheduling problems. The proposed algorithm is used to solve a set of benchmark problems optimizing makespan and tardiness. The performance of our algorithm is evaluated and compared to other algorithms from the literature using two measures for evaluating the Pareto front. We show that our algorithm is able to find a set of diverse and high quality non-dominated solutions, that significantly and consistently improves upon the results obtained by other state-of-the-art algorithms.

P. Libin and A. Nowé—Contributed equally.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Fayad, C., Petrovic, S.: A fuzzy genetic algorithm for real-world job shop scheduling. In: Ali, M., Esposito, F. (eds.) IEA/AIE 2005. LNCS (LNAI), vol. 3533, pp. 524–533. Springer, Heidelberg (2005). https://doi.org/10.1007/11504894_71

    Chapter  Google Scholar 

  2. Garey, M.-R., Johnson, D.-S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1(2), 117–129 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  3. Rameshkumar, K., Rajendran, C.: 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. 1, p. 012143. IOP Publishing, February 2018

    Google Scholar 

  4. Zhao, F., Qin, S., Yang, G., Ma, W., Zhang, C., Song, H.: A differential-based harmony search algorithm with variable neighborhood search for job shop scheduling problem and its runtime analysis. IEEE Access (2018)

    Google Scholar 

  5. Urlings, T.: Heuristics and Metaheuristics for heavily constrained hybrid Flowshop problems. Ph.D. Universitat Politcnica de Valncia (2010)

    Google Scholar 

  6. Gabel, T., Riedmiller, M.: Adaptive reactive job-shop scheduling with reinforcement learning agents. Int. J. Inf. Technol. Intell. Comput. 24(4) (2008)

    Google Scholar 

  7. Cao, Y., Yang, Y., Wang, H., Yang, L.: Intelligent job shop scheduling based on MAS and integrated routing wasp algorithm and scheduling wasp algorithm. JSW 5(4), 487–494 (2009)

    Google Scholar 

  8. Martinez Jimenez, Y.: A generic multi-agent reinforcement learning approach for scheduling problems. Ph.D., Vrije Universiteit Brussel, p. 128 (2012)

    Google Scholar 

  9. Li, K., Zhou, T., Liu, B.-H., Li, H.: A multi-agent system for sharing distributed manufacturing resources. Expert Syst. Appl. 99, 32–43 (2018)

    Article  Google Scholar 

  10. Roijers, D., Vamplew, P., Whiteson, S., Dazeley, R.: A survey of multi-objective sequential decision-making. J. Artif. Intell. Res. 48, 67–113 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  11. Rey Horn, J., Nafpliotis, N., Goldberg, D.-E.: A niched Pareto genetic algorithm for multiobjective optimization. In: Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, vol. 1, pp. 82–87. IEEE, June 1994

    Google Scholar 

  12. Watanabe, M., Ida, K., Gen, M.: A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Comput. Ind. Eng. 48(4), 743–752 (2005)

    Article  Google Scholar 

  13. Zhang, R., Chiong, R.: Solving the energy-efficient job shop scheduling problem: a multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption. J. Clean. Prod. 112, 3361–3375 (2016)

    Article  Google Scholar 

  14. Nowicki, E., Smutnicki, C.: Some new ideas in TS for job shop scheduling. In: Sharda, R., Voß, S., Rego, C., Alidaee, B. (eds.) Metaheuristic Optimization via Memory and Evolution. Operations Research/Computer Science Interfaces Series, vol. 30, pp. 165–190. Springer, Boston (2005)

    Chapter  Google Scholar 

  15. Weckman, G.-R., Ganduri, C.-V., Koonce, D.-A.: A neural network job-shop scheduler. J. Intell. Manuf. 19(2), 191–201 (2008)

    Article  Google Scholar 

  16. Udomsakdigool, A., Kachitvichyanukul, V.: Two-way scheduling approach in ant algorithm for solving job shop problems. Int. J. Ind. Eng. Manag. Syst. 5(2), 68–75 (2006)

    Google Scholar 

  17. Udomsakdigool, A., Kachitvichyanukul, V.: Multiple colony ant algorithm for job-shop scheduling problem. Int. J. Prod. Res. 46(15), 4155–4175 (2008)

    Article  MATH  Google Scholar 

  18. Wong, L.-P., Puan, C.-Y., Low, M.-Y.-H., Chong, C.-S.: Bee colony optimization algorithm with big valley landscape exploitation for job shop scheduling problems. In: 40th Conference on Winter Simulation on Proceedings, pp. 2050–2058. Winter Simulation Conference (2008)

    Google Scholar 

  19. Surekha, P., Sumathi, S.: Solving fuzzy based job shop scheduling problems using GA and ACO. J. Emerg. Trends Comput. Inf. Sci. (2010)

    Google Scholar 

  20. Pratchayaborirak, T., Kachitvichyanukul, V.: A two-stage PSO algorithm for job shop scheduling problem. Int. J. Manag. Sci. Eng. Manag. 6(2), 83–92 (2011)

    Google Scholar 

  21. Gao, H., Kwong, S., Fan, B., Wang, R.: A hybrid particle-swarm tabu search algorithm for solving job shop scheduling problems. IEEE Trans. Industr. Inf. 10(4), 2044–2054 (2014)

    Article  Google Scholar 

  22. Asadzadeh, L.: A local search genetic algorithm for the job shop scheduling problem with intelligent agents. Comput. Ind. Eng. 85, 376–383 (2015)

    Article  Google Scholar 

  23. Kachitvichyanukul, V., Sitthitham, S.: A two-stage genetic algorithm for multi-objective job shop scheduling problems. J. Intell. Manuf. 22(3), 355–365 (2011)

    Article  Google Scholar 

  24. Yazdani, M., Aleti, A., Khalili, S.-M., Jolai, F.: Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem. Comput. Ind. Eng. 107, 12–24 (2017)

    Article  Google Scholar 

  25. Meng, Q., Zhang, L., Fan, Y.: Research on multi-objective job shop scheduling with dual particle swarm algorithm based on greedy strategy. Wireless Pers. Commun. 103(1), 255–274 (2018)

    Article  Google Scholar 

  26. Sha, D.-Y., Lin, H.-H.: A multi-objective PSO for job-shop scheduling problems. Expert Syst. Appl. 37(2), 1065–1070 (2010)

    Article  Google Scholar 

  27. Ponnambalam, S.G., Ramkumar, V., Jawahar, N.: A multiobjective genetic algorithm for job shop scheduling. Prod. Planning Control 12(8), 764–774 (2001)

    Article  Google Scholar 

  28. Kurdi, M.: An improved island model memetic algorithm with a new cooperation phase for multi-objective job shop scheduling problem. Comput. Ind. Eng. 111, 183–201 (2017)

    Article  Google Scholar 

  29. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.-A.-M.-T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)

    Article  Google Scholar 

  30. Wang, B., Xie, H., Xia, X., Zhang, X.-X.: A NSGA-II algorithm hybridizing local simulated-annealing operators for a bicriteria robust job-shop scheduling problem under scenarios. IEEE Trans. Fuzzy Syst. (2018)

    Google Scholar 

  31. Suresh, R.K., Mohanasundaram, K.M.: Pareto archived simulated annealing for job shop scheduling with multiple objectives. The Int. J. Adv. Manuf. Technol. 29(1–2), 184–196 (2006)

    Article  Google Scholar 

  32. Niu, S.-H., Ong, S.-K., Nee, A.-Y.: An improved intelligent water drops algorithm for solving multi-objective job shop scheduling. Eng. Appl. Artif. Intell. 26(10), 2431–2442 (2013)

    Article  Google Scholar 

  33. Wisittipanich, W., Kachitvichyanukul, V.: An efficient PSO algorithm for finding Pareto-frontier in multi-objective job shop scheduling problems. Ind. Eng. Manag. Syst. 12(2), 151–160 (2013)

    Google Scholar 

  34. Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999)

    Article  Google Scholar 

  35. Lei, D., Wu, Z.: Crowding-measure-based multiobjective evolutionary algorithm for job shop scheduling. Int. J. Adv. Manuf. Technol. 30(1–2), 112–117 (2006)

    Article  Google Scholar 

  36. Lei, D.: A Pareto archive particle swarm optimization for multi-objective job shop scheduling. Comput. Ind. Eng. 54(4), 960–971 (2008)

    Article  Google Scholar 

  37. Hao, X., Gen, M., Lin, L., Suer, G.-A.: Effective multiobjective EDA for bi-criteria stochastic job-shop scheduling problem. J. Intell. Manuf. 28(3), 833–845 (2017)

    Article  Google Scholar 

  38. Watkins, C.-J., Dayan, P.: Q-learning. Mach. Learn. 8(3–4), 279–292 (1992)

    MATH  Google Scholar 

  39. Sutton, R.S., Barto, A.G.: Introduction to Reinforcement Learning, vol. 135. MIT Press, Cambridge (1998)

    MATH  Google Scholar 

  40. Tokic, M.: Adaptive \(\epsilon \)-Greedy exploration in reinforcement learning based on value differences. In: Dillmann, R., Beyerer, J., Hanebeck, U.D., Schultz, T. (eds.) KI 2010. LNCS (LNAI), vol. 6359, pp. 203–210. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16111-7_23

    Chapter  Google Scholar 

  41. Young, P.: Optimal voting rules. J. Econ. Perspect. 9(1), 52–64 (1995)

    Article  MathSciNet  Google Scholar 

  42. Cheng, H.C., Chiang, T.C., Fu, L.C.: Multiobjective job shop scheduling using memetic algorithm and shifting bottleneck procedure. In: Computational Intelligence in Scheduling, CI-Sched 2009, pp. 15–21. IEEE, April 2009

    Google Scholar 

  43. Opricovic, S., Tzeng, G.-H.: Compromise solution by MCDM methods: a comparative analysis of VIKOR and TOPSIS. Eur. J. Oper. Res. 156(2), 445–455 (2004)

    Article  MATH  Google Scholar 

  44. Beasley, J.-E.: OR-Library (2014). http://people.brunel.ac.uk/mastjjb/jeb/info.html

  45. Fisher, H.: Probabilistic learning combinations of local job shop scheduling rules. Ind. Sched., 225–251 (1963)

    Google Scholar 

  46. Adams, J., Balas, E., Zawack, D.: The shifting bottleneck procedure for job shop scheduling. Manage. Sci. 34(3), 391–401 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  47. Applegate, D., Cook, W.: A computational study of the job-shop scheduling problem. ORSA J. Comput. 3(2), 149–156 (1991)

    Article  MATH  Google Scholar 

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

    Google Scholar 

  49. Ruiz-Vanoye, J.A., Diaz-Parra, O., Perez-Ortega, J., Salgado, G.R., Gonzalez-Barbosa, J.J.: Complexity of instances for combinatorial optimization problems. In Computational Intelligence and Modern Heuristics, IntechOpen (2010)

    Google Scholar 

  50. Yamada, T., Nakano, R.: Genetic algorithms for job-shop scheduling problems. In: Proceedings of Modern Heuristic for Decision Support, pp. 67–81 (1997)

    Google Scholar 

  51. Riquelme, N., Von Lücken, C., Baran, B.: Performance metrics in multi-objective optimization. In: Computing Conference (CLEI), Latin American, pp. 1–11. IEEE (2015)

    Google Scholar 

  52. Zitzler, E.: Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications, vol. 63. Shaker, Ithaca (1999)

    Google Scholar 

  53. Tsitsiklis, J.-N.: Asynchronous stochastic approximation and Q-learning. Mach. Learn. 16(3), 185–202 (1994)

    MATH  Google Scholar 

Download references

Acknowledgment

This work was supported by the Vlaamse InterUniversitaire Raad, Flemish InterUniversity Council, Belgium (VLIR) under the UIC program VLIR-UCLV. Pieter Libin was supported by a PhD grant of the FWO (Fonds Wetenschappelijk Onderzoek - Vlaanderen). Erick D. Rodríguez-Bazan was supported by a PhD grant of INRIA. We thank the four anonymous reviewers for their suggestions, that allowed us to improve the manuscript.

Author information

Authors and Affiliations

  1. Universidad Central “Marta Abreu” de Las Villas, Santa Clara, Cuba

    Beatriz M. Méndez-Hernández & Yailen Martinez-Jimenez

  2. Inria Méditerranée Valbonne, Valbonne, France

    Erick D. Rodríguez-Bazan

  3. Vrije Universiteit Brussel, Brussels, Belgium

    Pieter Libin & Ann Nowé

Authors
  1. Beatriz M. Méndez-Hernández
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Erick D. Rodríguez-Bazan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yailen Martinez-Jimenez
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pieter Libin
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ann Nowé
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Beatriz M. Méndez-Hernández .

Editor information

Editors and Affiliations

  1. Helmholtz Zentrum München - Deutsches Forschungszentrum für Gesundheit und Umwelt (GmbH), Neuherberg, Germany

    Igor V. Tetko

  2. Institute of Computer Science, Czech Academy of Sciences, Prague 8, Czech Republic

    Věra Kůrková

  3. Helmholtz Zentrum München - Deutsches Forschungszentrum für Gesundheit und Umwelt (GmbH), Neuherberg, Germany

    Pavel Karpov

  4. Helmholtz Zentrum München - Deutsches Forschungszentrum für Gesundheit und Umwelt (GmbH), Neuherberg, Germany

    Fabian Theis

Appendices

Appendices

A Instance complexity

The instances used were selected according to the complexities proposed by [49, 50], as we show in Table 4.

Table 4. Complexity of the instances used.
Full size table
Table 5. Comparison among SPEA, CMEA, MOPSO and MOMARLA according to Hypevolume for supplementary instances.
Full size table

B Supplementary Instances

We tested the algorithms for other instances but with less complexity. Tables 5 and 6 show the results obtained according to Hypervolume and C-metric respectively. For these instances, our algorithm also shows a better performance.

Table 6. Comparison between SPEA, CMEA, MOPSO and MOMARLA according to C-metric for supplementary instances.
Full size table

C Hypervolume variance

Figure 2 shows the Hypervolume and the variance of the algorithms for the different instances.

Fig. 2.
figure 2

Hypervolume and variance of the algorithms.

Full size image

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Méndez-Hernández, B.M., Rodríguez-Bazan, E.D., Martinez-Jimenez, Y., Libin, P., Nowé, A. (2019). A Multi-objective Reinforcement Learning Algorithm for JSSP. In: Tetko, I., Kůrková, V., Karpov, P., Theis, F. (eds) Artificial Neural Networks and Machine Learning – ICANN 2019: Theoretical Neural Computation. ICANN 2019. Lecture Notes in Computer Science(), vol 11727. Springer, Cham. https://doi.org/10.1007/978-3-030-30487-4_44

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-30487-4_44

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-30486-7

  • Online ISBN: 978-3-030-30487-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation