REAL

Approximability of scheduling problems with resource consuming jobs

Györgyi, Péter and Kis, Tamás (2015) Approximability of scheduling problems with resource consuming jobs. Annals of Operations Research, 235. pp. 319-336. ISSN 0254-5330

This is the latest version of this item.

[img]
Preview
Text
anor_ptas rev1.pdf

Download (366kB) | Preview

Abstract

The paper presents new approximability results for single machine scheduling problems with jobs requiring some non-renewable resources (like raw materials, energy, or money) beside the machine. Each resource has an initial stock and additional supplies over time. A feasible schedule specifies a starting time for each job such that no two jobs overlap in time, and when a job is started, enough resources are available to cover its requirements. The goal is to find a feasible schedule of minimum makespan. This problem is strongly NP-hard. Recently, the authors of this paper have proposed a PTAS for the special case with a single non-renewable resource and with a constant number of supply dates, as well as an FPTAS for the special case with two supply dates and one resource only. In this paper we prove APX-hardness of the problem when the number of resources is part of the input, and new polynomial time approximation schemes are devised for some variants, including (1) job release dates, and more than one, but constant number of resources and resource supply dates, and (2) only one resource, arbitrary number of supply dates and job release dates, but with resource requirements proportional to job processing times.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: Dr. Tamás Kis
Date Deposited: 26 Dec 2015 16:33
Last Modified: 04 Apr 2023 11:19
URI: http://real.mtak.hu/id/eprint/31337

Available Versions of this Item

Actions (login required)

Edit Item Edit Item