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)

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 / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
Related URLs:	Organisation
Last Modified:	04 Mar 2022 13:08
URI:	http://gala.gre.ac.uk/id/eprint/10164

Actions (login required)

View Item

Downloads