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 (exact) 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 solvability. Thereby, we get a deepened understanding of the algorithmic complexity of this fundamental scheduling problem.

翻译：自1980年代以来,对NP-硬材料消化问题和密切相关的问题进行了彻底研究。大致上说,问题涉及在安排消耗不可再生资源的工作时尽量缩小抽取量。我们重点处理单机案,而没有先发制人:机器的资源有时(部分)得到补充,从而可以满足处理进一步工作的必要先决条件,每个工作都有个别的资源需求。我们开始系统探讨这一问题的参数化(具体)复杂面貌,提供参数化的可移动性和易移动性结果。我们这样做主要是调查与资源供应有关的参数如何影响计算溶解性。因此,我们加深了对这一基本时间安排问题的算法复杂性的理解。