New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints

Györgyi, Péter and Kis, Tamás (2022) New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints. DISCRETE APPLIED MATHEMATICS, 311. pp. 97-109. ISSN 0166-218X

Preview

Text 1-s2.0-S0166218X22000117-main.pdf Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (488kB) | Preview

Abstract

We consider single machine scheduling problems with additional non-renewable resource constraints. Examples for non-renewable resources include raw materials, energy, or money. Usually they have an initial stock and replenishments arrive over time at a-priori known time points and quantities. The jobs have some requirements from the resources and a job can only be started if the available quantity from each of the required resources exceeds the requirements of the job. Upon starting a job, it consumes its requirements which decreases the available quantities of the respective non-renewable resources. There is a broad background for this class of problems. Most of the literature concentrate on the makespan, and the maximum lateness objectives. This paper focuses on the total weighted completion time objective for which the list of the approximation algorithms is very short. We extend that list by considering new special cases and obtain new complexity results and approximation algorithms.

Actions (login required)

Edit Item