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

[img] Text
Restricted to Repository staff only

Download (481kB) | Request a copy


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. © 2015 Springer Science+Business Media New York

Item Type: Article
Uncontrolled Keywords: Vertex cover problem; Single machine scheduling; non-renewable resources; approximation schemes
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA76 Computer software / programozás
Depositing User: MTMT SWORD
Date Deposited: 15 Feb 2016 13:08
Last Modified: 15 Feb 2016 13:08

Actions (login required)

Edit Item Edit Item