Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/309854 
Erscheinungsjahr: 
2023
Quellenangabe: 
[Journal:] Journal of Scheduling [ISSN:] 1099-1425 [Volume:] 26 [Issue:] 4 [Publisher:] Springer US [Place:] New York, NY [Year:] 2023 [Pages:] 369-382
Verlag: 
Springer US, New York, NY
Zusammenfassung: 
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.
Schlagwörter: 
Non-renewable resources
Makespan minimization
Parameterized computational complexity
Fine-grained complexity
Exact algorithms
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.