A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem
Abstract
The NP-hard Material Consumption Scheduling Problem and closely related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with minimizing the makespan when scheduling jobs that consume non-renewable resources. 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 pre-condition for processing further jobs, each of which having individual resource demands. We initiate a systematic exploration of the parameterized computational complexity landscape of the problem, providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the computational complexity. Thereby, we get a deepened understanding of this fundamental scheduling problem.
Cite
Text
Bentert et al. "A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I13.17397Markdown
[Bentert et al. "A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/bentert2021aaai-multivariate/) doi:10.1609/AAAI.V35I13.17397BibTeX
@inproceedings{bentert2021aaai-multivariate,
title = {{A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem}},
author = {Bentert, Matthias and Bredereck, Robert and Györgyi, Péter and Kaczmarczyk, Andrzej and Niedermeier, Rolf},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2021},
pages = {11755-11763},
doi = {10.1609/AAAI.V35I13.17397},
url = {https://mlanthology.org/aaai/2021/bentert2021aaai-multivariate/}
}