A Hybrid Algorithm for Optimized Resource Allocation under Constrained Task Schedule
Mayank Pugalia, Aswin Ashok, Bharat Jayaraman · 2020
We present a novel hybrid algorithm for optimal resource allocation for scheduling tasks that satisfy a variety of diverse constraints. The problem is pitched in geometrical domain and has direct application to several areas including, and not limited to physical resource allocation, crowd sourcing and distributed/cloud computing. The fundamental problem is to complete a set of N tasks at geographically separate locations in a two-dimensional plane where each task takes a fixed duration, requires certain number resources and must be completed within a specified time window. The goal is to maximize the profit by efficient utilization of resources and reducing the cost of movement between locations and waiting at each location. In this paper, we propose multiple strategies with each one progressively better than the previous. The main contribution of the paper is the novel hybrid algorithm that combines the traditional greedy approach with chunk allocation and random tie-breaking scheme to achieve maximal profit by efficient resource allocation.