Resource Allocation and Task Scheduling with Skill Level and Time Bound Constraints

Authors: Salam Saudagar, Ankit Kamboj, Niraj Mohan, Satgounda Patil, Nilesh Powar

Abstract:

Task Assignment and Scheduling is a challenging Operations Research problem when there is a limited number of resources and comparatively higher number of tasks. The Cost Management team at Cummins needs to assign tasks based on a deadline and must prioritize some of the tasks as per business requirements. Moreover, there is a constraint on the resources that assignment of tasks should be done based on an individual skill level, that may vary for different tasks. Another constraint is for scheduling the tasks that should be evenly distributed in terms of number of working hours, which adds further complexity to this problem. The proposed greedy approach to solve assignment and scheduling problem first assigns the task based on management priority and then by the closest deadline. This is followed by an iterative selection of an available resource with the least allocated total working hours for a task, i.e. finding the local optimal choice for each task with the goal of determining the global optimum. The greedy approach task allocation is compared with a variant of Hungarian Algorithm, and it is observed that the proposed approach gives an equal allocation of working hours among the resources. The comparative study of the proposed approach is also done with manual task allocation and it is noted that the visibility of the task timeline has increased from 2 months to 6 months. An interactive dashboard app is created for the greedy assignment and scheduling approach and the tasks with more than 2 months horizon that were waiting in a queue without a delivery date initially are now analyzed effectively by the business with expected timelines for completion.

Keywords: Assignment, deadline, greedy approach, hungarian algorithm, operations research, scheduling.

References:

[1] R. Aboudi and K. Jornsten, Resource Constrained Assignment Problems: Discrete Applied Mathematics 26) 175-191 North-Holland (1990) https://core.ac.uk/download/pdf/82253919.pdf
[2] G. Georgiadis, A. Elekidis, Optimization-Based Scheduling for the Process Industries: From Theory to Real-Life Industrial Applications, Processes 2019, 7, 438. https://doi.org/10.3390/pr7070438
[3] S. Dhall, C. Liu, On a Real-Time Scheduling Problem, Operations Research Journal Vol. 26, No. 1, (Feb 1978) https://doi.org/10.1287/opre.26.1.127
[4] T. Nehzati, N. Ismail, Application of Artificial Intelligent in Production Scheduling: a critical evaluation and comparison of key approaches, International Conference on Industrial Engineering and Operations Management Kuala Lumpur, Malaysia, (January 22 – 24, 2011) http://ieomsociety.org/ieom2011/pdfs/IEOM007.pdf
[5] H.S. Stone, “Multiprocessor Scheduling with the Aid of Network Flow Algorithms” IEEE Trans. Software Eng., vol. 3, no. 1, pp. 85-93, (Jan. 1977) https://ieeexplore.ieee.org/document/1702405
[6] W. Kuhn, The Hungarian Method for the Assignment Problem, Bryn Yaw College https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf
[7] G. Korsah, M. Dias, A. Stentz, A Comprehensive Taxonomy for Multi-Robot Task Allocation, International Journal of Robotics Research 32. 1495-1512. 10.1177/0278364913496484. (2013) http://www.cs.cmu.edu/afs/cs/Web/People/gertrude/documents/Korsah_IJRR_Taxonomy.pdf
[8] A. Malik, A. Sharma, V. Saroha. International Journal of Scientific and Research Publications. Greedy Algorithm. Volume 3, Issue 8, ISSN 2250-3153, (August 2013) https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.642.4368&rep=rep1&type=pdf
[9] Z. Dong, N. Liu, R.Cessa, Greedy scheduling of tasks with time constraints for energy-efficient cloud-computing data centers. Journal of Cloud Computing. 4. 10.1186/s13677-015-0031-y, (2015). https://www.researchgate.net/publication/276886824_Greedy_scheduling_of_tasks_with_time_constraints_for_energy-efficient_cloud-computing_data_centers/link/5612c21608aea34aa9299a9f/download
[10] R. Mohan, N.Gopalan, Task Assignment for Heterogeneous Computing Problems using Improved Iterated Greedy Algorithm. International Journal of Computer Network and Information Security. 6. 50-55. 10.5815/ijcnis.2014.07.07, (2014). https://www.researchgate.net/publication/276230469_Task_Assignment_for_Heterogeneous_Computing_Problems_using_Improved_Iterated_Greedy_Algorithm/link/589becd3a6fdcc75417435e0/download
[11] V. Adlakha and H. Arsham, Managing Cost Uncertainties in Transportation and Assignment, Journal of Applied Mathematics Decision Science, 2(1), 65-104 (1998) http://www.kurims.kyoto-u.ac.jp/EMIS/journals/HOA/JAMDS/Volume2_1/104.pdf
[12] C. Zorlu, Project Overview of Breast Cancer Treatment, Hult Business School (2020) https://www.academia.edu/42775787/PROJECT_OVERVIEW_OF_BREAST_CANCER_TREATMENT