Approximation schemes for parallel machine scheduling with non-renewable resources
Péter Györgyi and
European Journal of Operational Research, 2017, vol. 258, issue 1, 113-123
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 in time and in known quantities. The schedules must respect the resource constraints as well. The optimization objective is either the makespan, or the maximum lateness. Polynomial time approximation schemes are provided under various assumptions, and it is shown that the makespan minimization problem is APX-complete if the number of machines is part of the input even if there are only two resources.
Keywords: Scheduling; Parallel machines; Non-renewable resources; Approximation schemes (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed
Downloads: (external link)
Full text for ScienceDirect subscribers only
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:258:y:2017:i:1:p:113-123
Access Statistics for this article
European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati
More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().