Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929383117160448 |
|---|---|
| author | Bendotti, Pascale Indrigo, Luca Brunod Chrétienne, Philippe Escoffier, Bruno |
| author_facet | Bendotti, Pascale Indrigo, Luca Brunod Chrétienne, Philippe Escoffier, Bruno |
| contents | This paper mainly focuses on a resource leveling variant of a two-processor scheduling problem. The latter problem is to schedule a set of dependent UET jobs on two identical processors with minimum makespan. It is known to be polynomial-time solvable.
In the variant we consider, the resource constraint on processors is relaxed and the objective is no longer to minimize makespan. Instead, a deadline is imposed on the makespan and the objective is to minimize the total resource use exceeding a threshold resource level of two. This resource leveling criterion is known as the total overload cost. Sophisticated matching arguments allow us to provide a polynomial algorithm computing the optimal solution as a function of the makespan deadline. It extends a solving method from the literature for the two-processor scheduling problem.
Moreover, the complexity of related resource leveling problems sharing the same objective is studied. These results lead to polynomial or pseudo-polynomial algorithms or NP-hardness proofs, allowing for an interesting comparison with classical machine scheduling problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_08104 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems Bendotti, Pascale Indrigo, Luca Brunod Chrétienne, Philippe Escoffier, Bruno Computational Complexity Data Structures and Algorithms This paper mainly focuses on a resource leveling variant of a two-processor scheduling problem. The latter problem is to schedule a set of dependent UET jobs on two identical processors with minimum makespan. It is known to be polynomial-time solvable. In the variant we consider, the resource constraint on processors is relaxed and the objective is no longer to minimize makespan. Instead, a deadline is imposed on the makespan and the objective is to minimize the total resource use exceeding a threshold resource level of two. This resource leveling criterion is known as the total overload cost. Sophisticated matching arguments allow us to provide a polynomial algorithm computing the optimal solution as a function of the makespan deadline. It extends a solving method from the literature for the two-processor scheduling problem. Moreover, the complexity of related resource leveling problems sharing the same objective is studied. These results lead to polynomial or pseudo-polynomial algorithms or NP-hardness proofs, allowing for an interesting comparison with classical machine scheduling problems. |
| title | Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.08104 |