Scheduling problems with non-regular penalty functions - a review (Q1106097)

The problem of scheduling n jobs on a single or several machines so as to minimize certain non-regular objectives is discussed. Such criteria include the variance of completion times, absolute deviations of the completion times from a common due date, piecewise linear functions imposing penalty on early and late completion times and quadratic loss functions. These problems include both the case when the due date is given as well as the case when the due date is to be determined. This paper presents a review of research done in these areas of scheduling. The review also considers the situations when the processing times are not known deterministically but are random variables with known probability distributions.