Scheduling of resource tasks

In many applications e.g. from operations research, or areas like operating systems, in particular real-time systems, parallel processing, or production planning systems, optimal strategies for scheduling given sets of activities or tasks in some optimal manner are required. In this paper we deal with the important class of resource constrained scheduling problems. In this kind of problems, tasks may require during their execution specified amounts of various resources, where each resource is available in certain limited amount. In addition, the order of task execution may be restricted by some given precedence constraints. The objective is to construct schedules of minimum makespan for given sets of tasks. Results obtained in this area show that finding an optimal solution is NP-hard in most cases. In this paper an exact method called SIT-graph algorithm is presented. Though this approach is of exponential time complexity in general, it allows to solve interesting and practically important classes of scheduling problems in polynomial time. (C) 1999 Elsevier Science B.V. All rights reserved.