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
Uncontrolled Keywords: single machine, deterioration, maintenance, approximation scheme, subset-sum problem, Half-Product Problem
Subjects: Q Science > QA Mathematics
Faculty / Department / Research Group: Faculty of Liberal Arts & Sciences
Faculty of Liberal Arts & Sciences > School of Computing & Mathematical Sciences (CAM)
Related URLs:
Last Modified: 17 Feb 2020 12:46
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
Selected for REF2021: 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