REAL

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

[img]
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.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: Dr. Tamás Kis
Date Deposited: 09 Sep 2015 08:53
Last Modified: 03 Apr 2023 08:30
URI: http://real.mtak.hu/id/eprint/26101

Actions (login required)

Edit Item Edit Item