A multivariate complexity analysis of the material consumption scheduling problem

Matthias Bentert (), Robert Bredereck (), Péter Györgyi (), Andrzej Kaczmarczyk () and Rolf Niedermeier ()
Additional contact information
Matthias Bentert: Technische Universität Berlin
Robert Bredereck: Technische Universität Berlin
Péter Györgyi: Eötvös Loránd Research Network
Andrzej Kaczmarczyk: Technische Universität Berlin
Rolf Niedermeier: Technische Universität Berlin

Journal of Scheduling, 2023, vol. 26, issue 4, No 3, 369-382

Abstract: Abstract 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: Non-renewable resources; Makespan minimization; Parameterized computational complexity; Fine-grained complexity; Exact algorithms (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00771-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:26:y:2023:i:4:d:10.1007_s10951-022-00771-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00771-5

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().