Scheduling independent tasks on heterogeneous processors using heuristics and Column Pricing

摘要

Efficiently scheduling a set of independent tasks on a virtual supercomputer formed by many heterogeneous components has great practical importance, since such systems are commonly used nowadays. Scheduling efficiency can be seen as the problem of minimizing the overall execution time (makespan) of the set of tasks under question. This problem is known to be NP-hard and is currently addressed using heuristics, evolutionary algorithms and other optimization methods. In this paper, firstly, two novel fast executing heuristics, called LSufferage and TPB, are introduced. L(ist)Sufferage is based on the known heuristic Sufferage and can achieve in general better results than it for most of the cases. T(enacious)PB is also based on another heuristic (Penalty Based) and incorporates new ideas that significantly improve the quality of the resulted schedule. Secondly, a mathematical model of the problem is presented alongside with an associated approach based on the Linear Programming method of Column Pricing. This approach, which is called Column Pricing with Restarts (CPR), can be categorized as a hybrid mathematical programming and heuristic approach and is capable of solving in reasonable time problem instances of practically any size. Experiments show that CPR achieves superior results improving over published results on problem instances of various sizes. Moreover, hardware requirements of CPR are minimal.