Skip to main content
SpringerLink
Log in

Solving Job Shop Scheduling with Parallel Population-Based Optimization and Apache Spark

  • Conference paper
  • First Online:
Intelligent Decision Technologies (IDT 2020)

Part of the book series: Smart Innovation, Systems and Technologies ((SIST,volume 193))

Included in the following conference series:

  • 479 Accesses

Abstract

The paper proposes an architecture for the population-based optimization in which Apache Spark is used as a platform enabling parallelization of the process of search for the best solution. The suggested architecture, based on the A-Team concept, is used to solve the Job Shop Scheduling Problem (JSP) instances. Computational experiment is carried out to compare the results from solving a benchmark set of the problem instances obtained using the proposed approach with other, recently reported, results.

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
$34.99 /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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover 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. Abdel-Kader, R.F.: An improved pso algorithm with genetic and neighborhood-based diversity operators for the job shop scheduling problem. Appl. Artif. Intell. 32(5), 433–462 (2018). https://doi.org/10.1080/08839514.2018.1481903

  2. Alba, E., Luque, G., Nesmachnow, S.: Parallel metaheuristics: recent advances and new trends. Int. Trans. Oper. Res. 20(1), 1–48 (2013) https://doi.org/10.1111/j.1475-3995.2012.00862.x

  3. Barbucha, D., Czarnowski, I., Jdrzejowicz, P., Ratajczak-Ropel, E., Wierzbowska, I.: JABAT Middleware as a Tool for Solving Optimization Problems, pp. 181–195. Springer, Berlin, Heidelberg, Berlin, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17155-0_10

  4. Boussaid, I., Lepagnot, J., Siarry, P.: A survey on optimization metaheuristics. Inf. Sci. 237, 82 – 117 (2013). Prediction, Control and Diagnosis using Advanced Neural Computations

    Google Scholar 

  5. Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B (Cybernetics) 26(1), 29–41 (1996)

    Google Scholar 

  6. Fogel, D.: Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, vol. 1. IEEE Press piscataway NJ (01 1995)

    Google Scholar 

  7. Geem, Z.W., Kim, J., Loganathan, G.: A new heuristic optimization algorithm: harmony search. Simul. 76, 60–68 (02 2001)

    Google Scholar 

  8. Goldberg, D.E.: Genetic Algorithms in Search Optimization and Machine Learning, 1st edn. Addison-Wesley Longman Publishing Co. Inc., Boston, MA, USA (1989)

    MATH  Google Scholar 

  9. González, P., Pardo Martínez, X., Doallo, R., Banga, J.: Implementing cloud-based parallel metaheuristics: an overview. J. Comput. Sci. Technol. 18(03), e26 (2018). http://journal.info.unlp.edu.ar/JCST/article/view/1109

  10. Hatamlou, A.: Solving travelling salesman problem using black hole algorithm. Soft Comput. 22 (2017)

    Google Scholar 

  11. Jedrzejowicz, P.: Current trends in the population-based optimization. In: Nguyen, N.T., Chbeir, R., Exposito, E., Aniorté, P., Trawiński, B. (eds.) Computational Collective Intelligence, pp. 523–534. Springer International Publishing, Cham (2019)

    Chapter  Google Scholar 

  12. Jedrzejowicz, P., Wierzbowska, I.: Experimental investigation of the synergetic effect produced by agents solving together instances of the euclidean planar travelling salesman problem. In: Jedrzejowicz, P., Nguyen, N.T., Howlet, R.J., Jain, L.C. (eds.) Agent and Multi-Agent Systems: Technologies and Applications, pp. 160–169. Springer, Berlin, Heidelberg (2010)

    Chapter  Google Scholar 

  13. Jedrzejowicz, P., Wierzbowska, I.: Apache spark as a tool for parallel population-based optimization. In: Czarnowski, I., Howlett, R.J., Jain, L.C. (eds.) Intelligent Decision Technologies 2019, pp. 181–190. Springer Singapore, Singapore (2020)

    Chapter  Google Scholar 

  14. Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN’95—International Conference on Neural Networks. vol. 4, pp. 1942–1948 (1995)

    Google Scholar 

  15. Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA (1992)

    MATH  Google Scholar 

  16. Michalewicz, Z.: Genetic Algorithm+Data Structures=Evolution Programs. Springer, Berlin, Heidelberg (1996)

    Book  Google Scholar 

  17. Lawrence, S.R.: Resource constrained project scheduling-a computational comparison of heuristic techniques (1985)

    Google Scholar 

  18. Radenski, A.: Distributed simulated annealing with mapreduce. In: Di Chio, C., Agapitos, A., Cagnoni, S., Cotta, C., de Vega, F.F., Di Caro, G.A., Drechsler, R., Ekárt, A., Esparcia-Alcázar, A.I., Farooq, M., Langdon, W.B., Merelo-Guervós, J.J., Preuss, M., Richter, H., Silva, S., Simões, A., Squillero, G., Tarantino, E., Tettamanzi, A.G.B., Togelius, J., Urquhart, N., Uyar, A.Ş., Yannakakis, G.N. (eds.) Applications of Evolutionary Computation, pp. 466–476. Springer, Berlin, Heidelberg (2012)

    Chapter  Google Scholar 

  19. Sato, T., Hagiwara, M.: Bee system: finding solution by a concentrated search. In: 1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation. vol. 4, pp. 3954–3959 (1997)

    Google Scholar 

  20. Semlali, S., Riffi, M., Chebihi, F.: Memetic chicken swarm algorithm for job shop scheduling problem. Int. J. Electr. Comput. Eng. (IJECE) 9, 2075 (2019)

    Google Scholar 

  21. Silva, M.A.L., de Souza, S.R., Souza, M.J.F., de França Filho, M.F.: Hybrid metaheuristics and multi-agent systems for solving optimization problems: a review of frameworks and a comparative analysis. Appl. Soft Comput. 71, 433–459 (2018). http://www.sciencedirect.com/science/article/pii/S1568494618303867

  22. Sun, L., Lin, L., Lib, H., Genc, M.: Large scale flexible scheduling optimization by a distributed evolutionary algorithm. Comput. Ind. Eng. 128 (2018)

    Google Scholar 

  23. Talukdar, S., Baerentzen, L., Gove, A., De Souza, P.: Asynchronous teams: cooperation schemes for autonomous agents. J. Heuristics 4(4), 295–321 (1998). https://doi.org/10.1023/A:1009669824615

  24. Wu, G., Mallipeddi, R., Suganthan, P.: Ensemble strategies for population-based optimization algorithms—a survey. Swarm Evolut. Comput. 44, 695–711 (2019)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Systems, Gdynia Maritime University, Morska 81-83, 81-225, Gdynia, Poland

    Piotr Jedrzejowicz & Izabela Wierzbowska

Authors
  1. Piotr Jedrzejowicz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Izabela Wierzbowska
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Izabela Wierzbowska .

Editor information

Editors and Affiliations

  1. Gdynia Maritime University, Gdynia, Poland

    Ireneusz Czarnowski

  2. KES International Research, UK

    Robert J. Howlett

  3. Faculty of Engineering and Information Technology, Centre for Artificial Intelligence, University of Technology Sydney, Sydney, NSW, Australia

    Lakhmi C. Jain

Rights and permissions

Reprints and permissions

Copyright information

© 2020 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Jedrzejowicz, P., Wierzbowska, I. (2020). Solving Job Shop Scheduling with Parallel Population-Based Optimization and Apache Spark. In: Czarnowski, I., Howlett, R., Jain, L. (eds) Intelligent Decision Technologies. IDT 2020. Smart Innovation, Systems and Technologies, vol 193. Springer, Singapore. https://doi.org/10.1007/978-981-15-5925-9_1

Download citation

Publish with us

Policies and ethics

Search

Navigation