Optimization of a task schedule for teams with members having various skills

• Autorzy: Bazan Marek , Smutnicki Czesław , Marchwiany Maciej E.

Identyfikatory

DOI

10.24425/ijet.2024.149515

• Języki publikacji: EN

Abstrakty

EN

We consider the real-life problem of planning tasks for teams in a corporation, in conditions of some restrictions. The problem takes into account various constraints, such as for instance flexible working hours, common meeting periods, time set aside for self-learning, lunchtimes and periodic performance of tasks. Additionally, only a part of the team may participate in meetings, and each team member may have their own periodic tasks such as self-development. We propose an algorithm that is an extension of the algorithm dedicated for scheduling on parallel unrelated processors with the makespan criterion. Our approach assumes that each task can be defined by a subset of employees or an entire team. However, each worker is of a different efficiency, so task completion times may differ. Moreover, the tasks are prioritized. The problem is NP-hard. Numerical experiments cover benchmarks with 10 instances of 100 tasks assigned to a 5-person team. For all instances, various algorithms such as branch-and-bound, genetic and tabu search have been tested.

Słowa kluczowe

EN

unrelated parallel machine scheduling problem; task scheduling for corporation teams; genetic algorithms; tabu search; branch and bound

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2024
• Tom: Vol. 70, No. 1
• Strony: 59--69
• Opis fizyczny: Bibliogr. 39 poz., rys., tab.

Twórcy

autor

Bazan Marek

• Wroclaw University of Scienceand Technology, Department of Computer Engineering, Wrocław, Poland; JT Weston sp. z o.o. Warszawa, Poland

autor

Smutnicki Czesław

• Wroclaw University of Scienceand Technology, Department of Computer Engineering, Wrocław, Poland

autor

Marchwiany Maciej E.

• JT Weston sp. z o.o. Warszawa, Poland

Bibliografia

• [1] S. Martello, F. Soumis, and P. Toth, “Exact and approximation algorithms for makespan minimization on unrelated parallel machines,” Discrete applied mathematics, vol. 75, no. 2, pp. 169-188, 1997.
• [2] N. S. Dey and T. Gunasekhar, “A comprehensive survey of load balancing strategies using hadoop queue scheduling and virtual machine migration,” IEEE Access, vol. 7, pp. 92 259-92 284, 2019. [Online]. Available: doi:10.1109/ACCESS.2019.2927076
• [3] M. S. Qureshi, M. B. Qureshi, M. Fayaz, W. K. Mashwani, S. B. Belhaouari, S. Hassan, and A. Shah, “A comparative analysis of resource allocation schemes for real-time services in high-performance computing systems,” International Journal of Distributed Sensor Networks, vol. 16, no. 8, p. 1550147720932750, 2020. [Online]. Available: doi:10.1177/1550147720932750
• [4] A. Keivani, F. Ghayoor, and J.-R. Tapamo, “A review of recent methods of task scheduling in cloud computing,” in 2018 19th IEEE Mediterranean Electrotechnical Conference (MELECON), 2018, pp. 104-109. [Online]. Available: doi:10.1109/MELCON.2018.8379076
• [5] H. Hussain, S. U. R. Malik, A. Hameed, S. U. Khan, G. Bickler, N. Min-Allah, M. B. Qureshi, L. Zhang, W. Yongji, N. Ghani, J. Kolodziej, A. Y. Zomaya, C.-Z. Xu, P. Balaji, A. Vishnu, F. Pinel, J. E. Pecero, D. Kliazovich, P. Bouvry, H. Li, L. Wang, D. Chen, and A. Rayes, “A survey on resource allocation in high performance distributed computing systems,” Parallel Computing, vol. 39, no. 11, pp. 709-736, 2013. [Online]. Available: doi:10.1016/j.parco.2013.09.009
• [6] R. Zabolotnyi, P. Leitner, and S. Dustdar, “Profiling-based task scheduling for factory-worker applications in infrastructure-as-a-service clouds,” in 2014 40th EUROMICRO Conference on Software Engineering and Advanced Applications, 2014, pp. 119-126. [Online]. Available: doi:10.1109/SEAA.2014.42
• [7] V. C. Kalempa, L. Piardi, M. Limeira, and A. S. de Oliveira, “Multi-robot preemptive task scheduling with fault recovery: A novel approach to automatic logistics of smart factories,” Sensors, vol. 21, no. 19, 2021. [Online]. Available: doi:10.3390/s21196536
• [8] O. Berman, R. C. Larson, and E. Pinker, “Scheduling workforce and workflow in a high volume factory,” Management Science, vol. 43, no. 2, pp. 158-172, 1997.
• [9] S. Hasg¨ul, I. Saricicek, M. Ozkan, and O. Parlaktuna, “Project-oriented task scheduling for mobile robot team,” Journal of Intelligent Manufacturing, vol. 20, pp. 151-158, 2009.
• [10] B. Fu, W. Smith, D. M. Rizzo, M. Castanier, M. Ghaffari, and K. Barton, “Robust task scheduling for heterogeneous robot teams under capability uncertainty,” IEEE Transactions on Robotics, vol. 39, no. 2, pp. 1087-1105, 2022.
• [11] H. Fei, C. Combes, N. Meskens, and C. Chu, “Endoscopies scheduling problem: A case study,” IFAC Proceedings Volumes, vol. 39, no. 3, pp. 635-640, 2006, 12th IFAC Symposium on Information Control Problems in Manufacturing. [Online]. Available: doi:10.3182/20060517-3-FR-2903.00323
• [12] J. Pempera and C. Smutnicki, “Open shop cyclic scheduling,” European Journal of Operational Research, vol. 269, no. 2, pp. 773-781, 2018. [Online]. Available: doi:10.1016/j.ejor.2018.02.021
• [13] T. Gonzalez and S. Sahni, “Open shop scheduling to minimize finish time,” J. ACM, vol. 23, no. 4, p. 665-679, oct 1976. [Online]. Available: doi:10.1145/321978.321985
• [14] S. H. Jang, T. Y. Kim, J. K. Kim, and J. S. Lee, “The study of genetic algorithm-based task scheduling for cloud computing,” International Journal of Control and Automation, vol. 5, no. 4, pp. 157-162, 2012.
• [15] F. A. Omara and M. M. Arafa, “Genetic algorithms for task scheduling problem,” Journal of Parallel and Distributed Computing, vol. 70, no. 1, pp. 13-22, 2010.
• [16] P. Pirozmand, A. A. R. Hosseinabadi, M. Farrokhzad, M. Sadeghilalimi, S. Mirkamali, and A. Slowik, “Multi-objective hybrid genetic algorithm for task scheduling problem in cloud computing,” Neural computing and applications, vol. 33, pp. 13 075-13 088, 2021.
• [17] A. Awad, N. El-Hefnawy, and H. Abdel kader, “Enhanced particle swarm optimization for task scheduling in cloud computing environments,” Procedia Computer Science, vol. 65, pp. 920-929, 2015.
• [18] H. Izakian, B. T. Ladani, A. Abraham, V. Snasel et al., “A discrete particle swarm optimization approach for grid job scheduling,” International Journal of Innovative Computing, Information and Control, vol. 6, no. 9, pp. 1-15, 2010.
• [19] T. Chen, B. Zhang, X. Hao, and Y. Dai, “Task scheduling in grid based on particle swarm optimization,” in 2006 Fifth International Symposium on Parallel and Distributed Computing. IEEE, 2006, pp. 238-245.
• [20] J. P. B. Mapetu, Z. Chen, and L. Kong, “Low-time complexity and low-cost binary particle swarm optimization algorithm for task scheduling and load balancing in cloud computing,” Applied Intelligence, vol. 49, pp. 3308-3330, 2019.
• [21] X. Wei, “Task scheduling optimization strategy using improved ant colony optimization algorithm in cloud computing,” Journal of Ambient Intelligence and Humanized Computing, pp. 1-12, 2020.
• [22] M. A. Tawfeek, A. El-Sisi, A. E. Keshk, and F. A. Torkey, “Cloud task scheduling based on ant colony optimization,” in 2013 8th international conference on computer engineering & systems (ICCES). IEEE, 2013, pp. 64-69.
• [23] M. R. Mohamed and M. H. Awadalla, “Hybrid algorithm for multiprocessor task scheduling,” International Journal of Computer Science Issues (IJCSI), vol. 8, no. 3, p. 79, 2011.
• [24] M. Fahmy, “A fuzzy algorithm for scheduling non-periodic jobs on soft real-time single processor system,” Ain Shams Engineering Journal, vol. 1, no. 1, pp. 31-38, 2010. [Online]. Available: doi:10.1016/j.asej.2010.09.004
• [25] X. Kong, C. Lin, Y. Jiang, W. Yan, and X. Chu, “Efficient dynamic task scheduling in virtualized data centers with fuzzy prediction,” Journal of network and Computer Applications, vol. 34, no. 4, pp. 1068-1077, 2011.
• [26] N. Mansouri and M. M. Javidi, “Cost-based job scheduling strategy in cloud computing environments,” Distributed and Parallel Databases, vol. 38, pp. 365-400, 2020.
• [27] M. M. Syslo, N. Deo, and J. S. Kowalik, Algorytmy optymalizacji dyskretnej: z programami w jezyku Pascal ang: (Algorithms for discrete optimization: with programs in Pascal). Wydawnictwo Naukowe PWN, 1999.
• [28] F. A. Potra and S. J. Wright, “Interior-point methods,” Journal of computational and applied mathematics, vol. 124, no. 1-2, pp. 281-302, 2000.
• [29] Y. Guo, A. Lim, B. Rodrigues, and L. Yang, “Minimizing the makespan for unrelated parallel machines,” International Journal on Artificial Intelligence Tools, vol. 16, no. 03, pp. 399-415, 2007.
• [30] K. Jansen and L. Porkolab, “Improved approximation schemes for scheduling unrelated parallel machines,” in Proceedings of the thirty-first annual ACM Symposium on Theory of Computing, 1999, pp. 408-417.
• [31] S. Balin, “Non-identical parallel machine scheduling using genetic algorithm,” Expert Systems with Applications, vol. 38, p. 6814-6821, 2011.
• [32] Z. Michalewicz, “Genetic algorithms + data structures = evolution programs,” 1996.
• [33] O. Ramos-Figueroa, M. Quiroz-Castellanos, E. Mezura-Montes, and N. Cruz-Ramirez, “An experimental study of grouping mutation operators for the unrelated parallel-machine scheduling problem,” Mathematical and Computational Applications, vol. 28, no. 1, 2023. [Online]. Available: doi:10.3390/mca28010006
• [34] V. Sels and A. M. D. M. V. Jos´e Coelho, “Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem,” pp. 107-117, 2015.
• [35] Åblad Edvin, S. Ann-Brith, and D. Spensieri, “Exact makespan minimization of unrelated parallel machines,” 2021.
• [36] T. Yamada and R. Nakano, “Scheduling by genetic local search with multi-step crossover,” 1996. [Online]. Available: doi:10.1007/3-540-61723-X 1059
• [37] D. Goldberg, “Algorytmy genetyczne i ich zastosowania (in polish) [genetic algorithms and their applications],” WNT, Warsaw, 1995.
• [38] A. J. Umbarkar and P. D. Sheth, “Crossover operators in genetic algorithms: a review.” ICTACT journal on soft computing, vol. 6, no. 1, 2015.
• [39] E. Åblad, D. Spensieri, R. Bohlin, and J. S. Carlson, “Intersectionfree geometrical partitioning of multirobot stations for cycle time optimization,” IEEE Transactions on Automation Science and Engineering, vol. 15, no. 2, pp. 842-851, 2017.

Uwagi

1. Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).

2. This work was financed with European Union funds from the Smart Growth Operational Programme 2014-2020, Measure 1.1.: R&D projects of enterprises. Sub-measure 1.1.1.: Industrial research and development carried out by enterprises.This work was financed with European Union funds from the Smart Growth Operational Programme 2014-2020, Measure 1.1.: R&D projects of enterprises. Sub-measure 1.1.1.: Industrial research and development carried out by enterprises.