V-SHAPED AND LAMBDA-SHAPED PROPERTIES FOR OPTIMAL SINGLE-MACHINE SCHEDULES FOR A CLASS OF NONSEPARABLE PENALTY-FUNCTIONS

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.