We consider the problem of scheduling n jobs on a single machine to minimize a non-separable, linear combination of three functions of job completion times: (i) the sum of the squares, (ii) the square of the mean, 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 functions, are particular cases of this general objective function. Our paper unifies many results on the nature of optimal schedules and gives a complete characterization of optimal schedules. We establish SPT, LPT, V-shaped and Λ-shaped characterizations of the optimal sequence for this objective function depending on the coefficients of the components of the linear combination.
