Simple and integrated heuristic algorithms for scheduling tasks with time and resource constraints

Abstract

We consider the problem of scheduling a set of n tasks in a system having r resources. Each task has an arbitrary, but known, processing time and a deadline, and may request use of a number of resources. A resource can be used either in shared mode or exclusive mode. In this article, we study algorithms used for determining whether or not a set of tasks is schedulable in such a system, and if so, determining a schedule for it. This scheduling problem is known to be NP-complete and hence we methodically study a set of heuristics that can be used by such an algorithm. Due to the complexity of the problem, simple heuristics do not perform satisfactorily. However, an algorithm that uses combinations of these simple heuristics works very well compared to an optimal algorithm that takes exponential time complexity. For the combination that performs the best, we also determine the scheduling costs as a function of the size of the task set scheduled.