Skip navigation

Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance

Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance

Kellerer, Hans, Rustogi, Kabir and Strusevich, Vitaly A. (2012) Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance. Journal of Scheduling, 16 (6). pp. 675-683. ISSN 1094-6136 (Print), 1099-1425 (Online) (doi:https://doi.org/10.1007/s10951-012-0287-8)

[img]
Preview
PDF (AAM)
10164_RUSTOGI_STRUSEVICH__(AAM)_(2013).pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (469kB)

Abstract

We consider a scheduling problem on a single machine to minimize the makespan. The processing conditions are subject to cumulative deterioration, but can be restored by a single maintenance. We link the problem to the Subset-sum problem (if the duration of maintenance is constant) and to the Half-Product Problem (if the duration of maintenance depends on its start time). For both versions of the problem, we adapt the existing fully polynomial-time approximation schemes to our problems by handling the additive constants.

Item Type: Article
Additional Information: [1] The final publication is available at Springer via http://dx.doi.org/10.1007/s10951-012-0287-8.
Uncontrolled Keywords: single machine, deterioration, maintenance, approximation scheme, subset-sum problem, Half-Product Problem.
Subjects: Q Science > QA Mathematics
Pre-2014 Departments: School of Computing & Mathematical Sciences
Related URLs:
Last Modified: 14 Oct 2016 09:24
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
URI: http://gala.gre.ac.uk/id/eprint/10164

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics