Algorithms for minimizing maximum lateness with unit length tasks and resource constraints (Q1803669)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Algorithms for minimizing maximum lateness with unit length tasks and resource constraints |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms for minimizing maximum lateness with unit length tasks and resource constraints |
scientific article |
Statements
Algorithms for minimizing maximum lateness with unit length tasks and resource constraints (English)
0 references
29 June 1993
0 references
The paper presents the algorithms for deterministic scheduling \(n\) unit length tasks on identical processors in the presence of additional resource constraints. The objective is to minimize maximum lateness. The paper shows that the problem can be solved in \(O(n\log n)\) 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 for the exact solution of the problem a branch and bound algorithm are proposed. The results of computational tests of these algorithms are also included.
0 references
deterministic scheduling
0 references