A comparison of evolutionary and simulated annealing algorithms for bi-criteria location-scheduling problem

• Autorzy: Ławrynowicz Mirosław , Filcek Grzegorz

Identyfikatory

DOI

10.15439/2020F91

• Konferencja: Federated Conference on Computer Science and Information Systems (15 ; 06-09.09.2020 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

A comparison of two heuristic algorithms solving a bi-criteria joint location and scheduling (ScheLoc) problem is considered. In this strongly NP-hard problem the sum of job completion times and location investment costs are used to evaluate the solution. The first solution algorithm (EV) uses an evolutionary approach, and the second more time-efficient algorithm (SA) is based on Simulated Annealing.

Słowa kluczowe

EN

computational complexity; evolutionary computation; job shop scheduling; simulated annealing

PL

złożoność obliczeniowa; obliczenia ewolucyjne; harmonogramowanie; symulowane wyżarzanie

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2020
• Tom: Vol. 21
• Strony: 251--255
• Opis fizyczny: Bibliogr. 25 poz., wz., tab.

Twórcy

autor

Ławrynowicz Mirosław

• Wroclaw University of Science and Technology, 27 Wyb. Wyspianskiego St, 50-370 Wroclaw, Poland

autor

Filcek Grzegorz

• Wroclaw University of Science and Technology, 27 Wyb. Wyspianskiego St, 50-370 Wroclaw, Poland

Bibliografia

• 1. J. E. Baker. Reducing bias and inefficiency in the selection algorithm. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application, pages 14–21, Hillsdale, NJ, USA, 1987. L. Erlbaum Associates Inc.
• 2. K. Deb. Multi-objective optimization using evolutionary algorithms, volume 16. John Wiley & Sons, 2001.
• 3. D. Elvikis, H. W. Hamacher, and M. T. Kalsch. Simultaneous scheduling and location (ScheLoc): the planar ScheLoc makespan problem. Journal of Scheduling, 12(4):361–374, 2009.
• 4. J. J. Grefenstette. Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 16(1):122–128, Jan 1986.
• 5. H. Hennes and H. Hamacher. Integrated Scheduling and Location Models: Single Machine Makespan Problems. Report in Wirtschaftsmathematik. Univ., Fachbereich Mathematik, 2002.
• 6. C. Heßler and K. Deghdak. Discrete parallel machine makespan ScheLoc problem. Journal of Combinatorial Optimization, 34(4):1159–1186, 2017.
• 7. J. H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. University of Michigan Press, 1975.
• 8. Y.-C. Hou and Y.-H. Chang. A new efficient encoding mode of genetic algorithms for the generalized plant allocation problem. Journal of Information Science and Engineering, 20:1019–1034, 09 2004.
• 9. D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon. Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. Operations research, 37(6):865–892, 1989.
• 10. M. T. Kalsch. Scheduling-Location (ScheLoc): Models, Theory and Algorithms. Verlag Dr. Hut, 2009.
• 11. M. T. Kalsch and Z. Drezner. Solving scheduling and location problems in the plane simultaneously. Computers & Operations Research, 37(2):256–264, 2010.
• 12. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. science, 220(4598):671–680, 1983.
• 13. J. Krarup and P. M. Pruzan. The simple plant location problem: Survey and synthesis. European Journal of Operational Research, 12(1):36–81, 1983.
• 14. M. Laszczyk and P. B. Myszkowski. Survey of quality measures for multi-objective optimization. Construction of complementary set of multi-objective quality measures. Swarm and Evolutionary Computation, 48:109–133, 2019.
• 15. M. Ławrynowicz and J. Józefczyk. A memetic algorithm for the discrete scheduling-location problem with unrelated executors. In Proc. of 24th Int. Conf. on Models and Methods in Automation and Robotics MMAR, pages 158–163, 2019.
• 16. J. K. Lenstra, A. R. Kan, and P. Brucker. Complexity of machine scheduling problems. In Annals of discrete mathematics, volume 1, pages 343–362. Elsevier, 1977.
• 17. M. Liu, X. Liu, E. Zhang, F. Chu, and C. Chu. Scenario-based heuristic to two-stage stochastic program for the parallel machine ScheLoc problem. International Journal of Production Research, 57(6):1706–1723, 2019.
• 18. Z. Michalewicz and D. B. Fogel. How to solve it: modern heuristics. Springer Science & Business Media, 2013.
• 19. I. M. Oliver, D. Smith, and J. R. Holland. Study of permutation crossover operators on the traveling salesman problem. In Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms at the Massachusetts Institute of Technology, Cambridge, MA. Hillsdale, NJ: L. Erlhaum Associates, 1987.
• 20. B. Piasecki and J. Józefczyk. Evolutionary algorithm for joint task scheduling and deployment of executors. In: Automation of Discrete Processes. Theory and Applications, Silesian University of Technology, 1:169–178, 2018.
• 21. M. Pinedo. Scheduling: theory, algorithms and systems development, volume 29. Springer-Verlag NY, 2012.
• 22. M. Rajabzadeh, M. Ziaee, and A. Bozorgi-Amiri. Integrated approach in solving parallel machine scheduling and location (ScheLoc) problem. International Journal of Industrial Engineering Computations, 7(4):573–584, 2016.
• 23. G. Syswerda. Scheduling optimization using genetic algorithms. Handbook of genetic algorithms, pages 332 – 349, 1991.
• 24. E.-G. Talbi. Metaheuristics: from design to implementation, volume 74. John Wiley & Sons, 2009.
• 25. S. Wesolkowski, N. Francetić, and S. C. Grant. TraDE: Training device selection via multi-objective optimization. In 2014 IEEE Congress on Evolutionary Computation (CEC), pages 2617–2624. IEEE, 2014.

Uwagi

1. Track 1: Artificial Intelligence

2. Technical Session: 13th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).