Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
<|reference_start|>Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems: 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.<|reference_end|>
@article{bendotti2024resource,
    title={Resource Leveling: Complexity of a UET two-processor scheduling variant
  and related problems},
    author={Pascale Bendotti, Luca Brunod Indrigo, Philippe Chr'etienne, Bruno
  Escoffier},
    journal={arXiv preprint arXiv:2406.08104},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.08104},
    primaryClass={cs.CC cs.DS}
}