Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 11

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

Efficient selection operators in NSGA-II for Solving Bi-Objective Multi-Skill Resource-Constrained Project Scheduling Problem

, ,

DOI: http://dx.doi.org/10.15439/2017F317

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 8386 ()

Full text

Abstract. This paper presents multiple variances of selection operator used in Non-dominated Sorting Genetic Algorithm II applied to solving Bi-Objective Multi-Skill Resource Constrained Project Scheduling Problem. A hybrid Differential Evolution with Greedy Algorithm is used as a baseline. This comparison is used to determine whether a multi-objective approach can outperform single-objective approaches in finding potential Pareto Fronts. Furthermore, found Pareto Fronts are compared using various measures. A modified selection operators have been introduced along with a clone prevention method. Experiments show the increase in efficiency caused by the use of new selection methods

References

  1. Samà, M., et al. “Lower and upper bound algorithms for the real-time train scheduling and routing problem in a railway network.” IFAC-PapersOnLine 49.3 (2016): 215-220.
  2. Varas, Mauricio, et al. “Scheduling production for a sawmill: A robust optimization approach.“ Inter.l J.l of Prod. Econ.s 150 (2014): 37-51.
  3. Kerzner, Harold. “Project management: a systems approach to planning, scheduling, and controlling.” John Wiley & Sons, 2013.
  4. Blazewicz, J., Lenstra J.K., and AHG Rinnooy Kan. “Scheduling subject to resource constraints: classification and complexity.“ Discrete Applied Mathematics 5.1 (1983): 11-24.
  5. Kolisch R., Sprecher A.m “PSPLIB – A project scheduling problem library“, Eur. J. of Oper. Res. (96), pp. 205–216, 1996.
  6. Luna, Francisco, et al. "The software project scheduling problem: A scalability analysis of multi-objective metaheuristics." Applied Soft Computing 15 (2014): 136-148.
  7. Myszkowski P. B., Skowroński M. E., Sikora K.; “A new benchmark dataset for Multi-Skill Resource-Constrained Project Scheduling Problem”, Proc. of FEDCSIS
  8. Myszkowski P.B., Olech L.P., Laszczyk M. and Skowroński M.E., “Hybrid Differential Evolution and Greedy (DEGR) for Solving Multi–Skill Resource–Constrained Project Scheduling Problem”, Applied Soft Computing in review process, 2017.
  9. Mendes, Jorge Jose de Magalhaes, Goncalves J.F., and Mauricio GC Resende. "A random key based genetic algorithm for the resource constrained project scheduling problem." Compu. & Op. Research 36.1 (2009): 92-109.
  10. Thomas P.R. and Said S.. "A tabu search approach for the resource constrained project scheduling problem." Journal of Heuristics 4.2 (1998): 123-139.
  11. Myszkowski P.B. and Siemieński J.J. "GRASP Applied to Multi–Skill Resource–Constrained Project Scheduling Problem." International Conference on Computational Collective Intelligence. Springer International Publishing, 2016.
  12. Myszkowski P.B., et al. "Hybrid ant colony optimization in solving multi–skill resource–constrained project scheduling problem", Soft Computing 19.12 (2015), pp.3599–3619.
  13. Zhang, Hong, Heng Li, and C. M. Tam. "Particle swarm optimization for resource-constrained project scheduling." International Journal of Project Management 24.1 (2006): 83-92.
  14. Zheng, Huan-yu, Ling Wang, and Xiao-long Zheng. "Teaching–learning-based optimization algorithm for multi-skill resource constrained project scheduling problem." Soft Computing (2015): 1-12.
  15. Abbasi, Babak, Shahram Shadrokh, and Jamal Arkat. "Bi-objective resource-constrained project scheduling with robustness and makespan criteria." Applied mathematics and computation 180.1 (2006): 146-152.
  16. Cowling P., Colledge N., Dahal K., Remde S. “The Trade Off Between Diversity and Quality for Multi-objective Workforce Scheduling” [In:] Gottlieb J., Raidl G.R. (eds) Evolutionary Computation in Combinatorial Optimization. Springer
  17. Deb, Kalyanmoy, et al. "A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II." International Conference on Parallel Problem Solving From Nature. Springer Berlin Heidelberg, 2000.
  18. Deb, Kalyanmoy, Udaya Rao N, and S. Karthik. "Dynamic multi-objective optimization and decision-making using modified NSGA-II: a case study on hydro-thermal power scheduling." Evolutionary Multi-Criterion Optimization. Springer
  19. Rabiee, M., M. Zandieh, and P. Ramezani. "Bi-objective partial flexible job shop scheduling problem: NSGA-II, NRGA, MOGA and PAES approaches.", International Journal of Production Research 50.24 (2012): 7327-7342.
  20. Wang, Shuai, et al. "A practical guide to select quality indicators for assessing Pareto–based search algorithms in search-based software engineering.", Proceedings of the 38th International Conference on Software Engineering. ACM, 2016.
  21. http://imopse.ii.pwr.wroc.pl/