Approximation schemes for single machine scheduling with non-renewable resource constraints

Györgyi, Péter and Kis, Tamás (2014) Approximation schemes for single machine scheduling with non-renewable resource constraints. Journal of Scheduling, 17 (2). pp. 135-144. ISSN 1094-6136

Preview

Text mat_v1.pdf Download (209kB) | Preview

Abstract

In this paper we discuss exact and approxi- mation algorithms for scheduling a single machine with additional non-renewable resource constraints. Given the initial stock levels of some non-renewable resources (e.g. raw materials, fuel, money), and time points along with replenishment quantities, a set of resource consum- ing jobs has to be scheduled on the machine such that there are enough resources for starting each job, and the makespan is minimized. We show that the prob- lem admits a pseudo polynomial time algorithm when the number of replenishments is not part of the input, and also present an FPTAS when there is only a single resource, and it is replenished only once. We also de- scribe a PTAS for the problem with a constant number of replenishments.

Actions (login required)

Edit Item