Scheduling with non-renewable resources: Minimizing the sum of completion times

Bérczi, Kristóf and Király, Tamás and Omlor, S. (2020) Scheduling with non-renewable resources: Minimizing the sum of completion times. LECTURE NOTES IN COMPUTER SCIENCE, 12176. pp. 167-178. ISSN 0302-9743

Preview

Text 1911.12138.pdf Available under License Creative Commons Attribution. Download (549kB) | Preview

Abstract

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 schedul- ing machine problems. In particular, we show strong NP-hardness of the case of unit re- source requirements and weights (1|rm = 1, aj = 1| ∑ Cj ), thus answering an open question of Gy¨orgyi and Kis. We also prove that the schedule corresponding to the Shortest Process- ing 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| ∑ wj Cj ). 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.

Actions (login required)

Edit Item