Algorithms for minimizing maximum lateness with unit length tasks and resource constraints

Algorithms for minimizing maximum lateness with unit length tasks and resource constraints

0.00 Avg rating0 Votes
Article ID: iaor1995115
Country: Netherlands
Volume: 42
Issue: 2/3
Start Page Number: 123
End Page Number: 138
Publication Date: Apr 1993
Journal: Discrete Applied Mathematics
Authors: , ,
Abstract:

The problem the authors consider is that of scheduling n unit length tasks on identical processors in the presence of additional scarce resources. The objective is to minimize maximum lateness. It has been known for some time that the problem is NP-hard even for two processors and one resource type. In the present paper the authors show that the problem can be solved in O(nlogn) time, even for an arbitrary number of resources if the instance of the problem has the saturation property (i.e., no resource unit is idle in an optimal schedule). For the more general problem without saturation, two heuristic algorithms and a branch and bound approach are proposed. The results of computational tests of the above methods are also reported.

Reviews

Required fields are marked *. Your email address will not be published.