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, 201-215
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)
References: Add references at CitEc
Citations: Track citations by RSS feed
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.
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
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
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 ().