Single-machine time-dependent scheduling problems with fixed rate-modifying activities and resumable jobs

Anna Arigliano (), Gianpaolo Ghiani (), Antonio Grieco () and Emanuela Guerriero ()
Additional contact information
Anna Arigliano: Università del Salento
Gianpaolo Ghiani: Università del Salento
Antonio Grieco: Università del Salento
Emanuela Guerriero: Università del Salento

4OR, 2017, vol. 15, issue 2, No 5, 215 pages

Abstract: Abstract In this paper, we deal with single machine scheduling problems subject to time dependent effects. The main point in our models is that we do not assume a constant processing rate during job processing time. Rather, processing rate changes according to a fixed schedule of activities, such as replacing a human operator by a less skilled operator. The contribution of this paper is threefold. First, we devise a time-dependent piecewise constant processing rate model and show how to compute processing time for a resumable job. Second, we prove that any time-dependent continuous piecewise linear processing time model can be generated by the proposed rate model. Finally, we propose polynomial-time algorithms for some single machine problems with job independent rate function. In these procedures the job-independent rate effect does not imply any restriction on the number of breakpoints for the corresponding continuous piecewise linear processing time model. This is a clear element of novelty with respect to the polynomial-time algorithms proposed in previous contributions for time-dependent scheduling problems.

Keywords: Scheduling; Single machine; Learning effect; Deteriorating jobs; Time dependent scheduling; Rate modifying activity; 90B35 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10288-016-0333-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:15:y:2017:i:2:d:10.1007_s10288-016-0333-z

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-016-0333-z

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().