2021/02/26 by Matthias Bentert, Bentert, Matthias, Robert Bredereck +7 · 1 citation
Engineering · #Advanced Manufacturing and Logistics Optimization #Computer Science and Game Theory (cs.GT) #F.2.2 #FOS: Computer and information sciences #G.2.1 #I.1.2 #I.2.8 #Optimization and Packing Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2102.13642
openalex publication_date 2021/02/26 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
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.