A multivariate complexity analysis of the material consumption scheduling problem - Matthias Bentert; Robert Bredereck; Péter Györgyi; Andrzej Kaczmarczyk; Rolf Niedermeier (Journal of Scheduling, 2023)
The NP-hard problem Material Consumption Scheduling and related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with scheduling jobs that consume non-renewable resources—each job has individual resource demands. The goal is to minimize the makespan. We focus on the single-machine case without preemption: from time to time, the resources of the machine are (partially) replenished, thus allowing for meeting a necessary precondition for processing further jobs. We initiate a systematic exploration of the parameterized computational complexity landscape of Material Consumption Scheduling , providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the problem's computational complexity. This leads to a deepened understanding of this fundamental scheduling problem.
Keywords: 650; Non-renewable resources; Makespan minimization; Parameterized computational complexity; Fine-grained complexity; Exact algorithms