2019/11/26 by Kristóf Bérczi, Bérczi, Kristóf, Tamás Király +3
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1911.12138
openalex publication_date 2019/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The paper considers single-machine scheduling problems with a non-renewable resource. In this setting, we are given a set jobs, each of which is characterized by a processing time, a weight, and the job also has some resource requirement. At fixed points in time, a certain amount of the resource is made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that at any time their resource requirement does not exceed the available amounts of resources. The objective that we consider here is the minimization of the sum of weighted completion times. We give polynomial approximation algorithms and complexity results for single scheduling machine problems. In particular, we show strong NP-hardness of the case of unit resource requirements and weights (1|rm=1,aj=1|∑ Cj), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the same problem. We give simple constant factor approximations and a more complicated PTAS for the case of 0 processing times (1|rm=1,pj=0|∑ wjCj). We close the paper by proposing a new variant of the problem in which the resource arrival times are unknown. A 4-approximation is presented for this variant, together with an (4-ε)-inapproximability result.