Rustogi, Kabir and Strusevich, Vitaly A. (2016) Single machine scheduling with a generalized job-dependent cumulative effect. Journal of Scheduling, 20 (6). pp. 583-592. ISSN 1094-6136 (Print), 1099-1425 (Online) (doi:10.1007/s10951-016-0497-6)

Preview

PDF (Author Accepted Manuscript) 20040 STRUSEVICH_Single_Machine_Scheduling_2016.pdf - Accepted Version Download (150kB) | Preview

Abstract

We consider a single machine scheduling problem with changing processing times. The processing conditions are subject to a general cumulative effect, in which the processing time of a job depends on the sum of certain parameters associated with previously scheduled jobs. In previous papers, these parameters are assumed to be equal to the normal processing times of jobs, which seriously limits the practical application of this model. We further generalize this model by allowing every job to respond differently to these cumulative effects. For the introduced model, we solve the problem of minimizing the makespan, with and without precedence constraints. For the problem without precedence constraints, we also consider a situation in which a maintenance activity is included in the schedule, which can improve the processing conditions of the machine, not necessarily to its original state. The resulting problem is reformulated as a variant of a Boolean programming problem with a quadratic objective, known as a half-product, which allows us to develop a fully polynomial-time approximation scheme with the best possible running time.

Item Type:	Article
Uncontrolled Keywords:	Single machine; Deterioration; Precedence constraints; Maintenance; Approximation scheme; 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
Last Modified:	04 Mar 2022 13:07
URI:	http://gala.gre.ac.uk/id/eprint/20040

Actions (login required)

View Item

Downloads