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.