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

Marek Bazan, Czesław Smutnicki, Maciej E. Marchwiany

Abstract


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. 


Full Text:

PDF

References


S. Martello, F. Soumis, and P. Toth, “Exact and approximation al-

gorithms for makespan minimization on unrelated parallel machines,”

Discrete applied mathematics, vol. 75, no. 2, pp. 169–188, 1997.

N. S. Dey and T. Gunasekhar, “A comprehensive survey of load

balancing strategies using hadoop queue scheduling and virtual machine

migration,” IEEE Access, vol.

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.

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.

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: https:

//www.sciencedirect.com/science/article/pii/S016781911300121X

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.

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.

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.

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.

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.

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.

J. Pempera and C. Smutnicki, “Open shop cyclic scheduling,” European Journal of Operational Research, vol. 269, no. 2, pp. 773–781, 2018. [Online]. Available: https://www.sciencedirect.com/science/article/pii/

S037722171830136X

T. Gonzalez and S. Sahni, “Open shop scheduling to minimize finish time,” J. ACM, vol. 23, no. 4, p. 665–679, oct 1976.

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.

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.

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.

A. Awad, N. El-Hefnawy, and H. Abdel kader, “Enhanced particle

swarm optimization for task scheduling in cloud computing environ-

ments,” Procedia Computer Science, vol. 65, pp. 920–929, 2015.

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.

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.

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.

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.

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.

M. R. Mohamed and M. H. Awadalla, “Hybrid algorithm for multi-

processor task scheduling,” International Journal of Computer Science

Issues (IJCSI), vol. 8, no. 3, p. 79, 2011.

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:

https://www.sciencedirect.com/science/article/pii/S2090447910000055

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.

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.

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.

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.

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.

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.

S. Balin, “Non-identical parallel machine scheduling using genetic

algorithm,” Expert Systems with Applications, vol. 38, p. 6814–6821,

Z. Michalewicz, “Genetic algorithms + data structures = evolution programs,” 1996.

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.

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.

̊Ablad Edvin, S. Ann-Brith, and D. Spensieri, “Exact makespan minimization of unrelated parallel machines,” 2021.

T. Yamada and R. Nakano, “Scheduling by genetic local search with multi-step crossover,” 1996.

D. Goldberg, “Algorytmy genetyczne i ich zastosowania (in polish) [genetic algorithms and their applications],” WNT, Warsaw, 1995.

A. J. Umbarkar and P. D. Sheth, “Crossover operators in genetic

algorithms: a review.” ICTACT journal on soft computing, vol. 6, no. 1, 2015.

E. ̊Ablad, D. Spensieri, R. Bohlin, and J. S. Carlson, “Intersection-free geometrical partitioning of multirobot stations for cycle time optimization,” IEEE Transactions on Automation Science and Engineering, vol. 15, no. 2, pp. 842–851, 2017.


Refbacks

  • There are currently no refbacks.


International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933