Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 21

Proceedings of the 2020 Federated Conference on Computer Science and Information Systems

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

,

DOI: http://dx.doi.org/10.15439/2020F91

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 251–255 ()

Full text

Abstract. 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.

References

  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.