Approximation schemes for parallel machine scheduling with non-renewable resources

Györgyi, Péter and Kis, Tamás (2017) Approximation schemes for parallel machine scheduling with non-renewable resources. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 258 (1). pp. 113-123. ISSN 0377-2217

Preview	Text pm_ejor.pdf Download (537kB) | Preview
Preview	Text pm_ejor_rev2.pdf Download (630kB) | Preview

Abstract

In this paper the approximability of parallel machine scheduling problems with resource consuming jobs is studied. In these problems, in addition to a parallel machine environment, there are non-renewable resources, like raw materials, energy, or money, consumed by the jobs. Each resource has an initial stock, and some additional supplies at a-priori known moments of times and in known quantities. The schedules must respect the resource constraints as well. The objective is the minimum schedule length or makespan. Polynomial time approximation schemes are provided under various assumptions, and it is shown that the problem becomes APX-hard if the number of machines is part of the input even if there are only two resources.

Item Type:	Article
Subjects:	Q Science / természettudomány > QA Mathematics / matematika
Depositing User:	Dr. Tamás Kis
Date Deposited:	29 Sep 2017 12:19
Last Modified:	05 Apr 2023 06:44
URI:	http://real.mtak.hu/id/eprint/64382

Available Versions of this Item

• Approximation schemes for parallel machine scheduling with non-renewable resources. (deposited 09 Sep 2015 08:48)
  • Approximation schemes for parallel machine scheduling with non-renewable resources. (deposited 26 Oct 2016 08:25)
    • Approximation schemes for parallel machine scheduling with non-renewable resources. (deposited 29 Sep 2017 12:19) [Currently Displayed]

Actions (login required)

Edit Item