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.

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

ARIGLIANO, ANNA;GHIANI, GIANPAOLO;GRIECO, Antonio Domenico;GUERRIERO, Emanuela
2016-01-01

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11587/412671
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 4
social impact