J. Mittenthal et al., V-SHAPED AND LAMBDA-SHAPED PROPERTIES FOR OPTIMAL SINGLE-MACHINE SCHEDULES FOR A CLASS OF NONSEPARABLE PENALTY-FUNCTIONS, European journal of operational research, 86(2), 1995, pp. 262-269
Citations number
12
Categorie Soggetti
Management,"Operatione Research & Management Science
We consider the problem of scheduling n jobs on a single machine to mi
nimize a non-separable, linear combination of three functions of job c
ompletion times: (i) the sum of the squares, (ii) the square of the me
an, and (iii) the mean. Many regular and non-regular penalty functions
, e.g., the mean completion time, variance of the completion times, a
linear combination of the variance and the mean, and certain other fun
ctions, are particular cases of this general objective function. Our p
aper unifies many results on the nature of optimal schedules and gives
a complete characterization of optimal schedules. We establish SPT, L
PT, V-shaped and h-shaped characterizations of the optimal sequence fo
r this objective function depending on the coefficients of the compone
nts of the linear combination.