Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/309854 
Year of Publication: 
2023
Citation: 
[Journal:] Journal of Scheduling [ISSN:] 1099-1425 [Volume:] 26 [Issue:] 4 [Publisher:] Springer US [Place:] New York, NY [Year:] 2023 [Pages:] 369-382
Publisher: 
Springer US, New York, NY
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.
Subjects: 
Non-renewable resources
Makespan minimization
Parameterized computational complexity
Fine-grained complexity
Exact algorithms
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.