SIMULTANEOUS-OPTIMIZATION OF EFFICIENCY AND PERFORMANCE BALANCE MEASURES IN SINGLE-MACHINE SCHEDULING PROBLEMS

Manufacturing and service organizations routinely face the challenge o f scheduling jobs, orders, or individual customers in a schedule that optimizes either (i) an aggregate efficiency measure, (ii) a measure o f performance balance, or (iii) some combination of these two objectiv es. We address these questions for single machine job scheduling syste ms with fixed or controllable due dates. We show that a large class of such problems can be optimized by solving either a single instance or a finite sequence of instances of the so-called (SQC) problem, in whi ch the sum of general quasiconvex functions of the jobs' completion ti mes is to be minimized. To solve a single instance of (SQC), we develo p an efficient, though pseudopolynomial algorithm, based on dynamic pr ogramming. The algorithm generates a solution that is optimal among al l schedules whose starting time is restricted to the points of a presp ecified (arbitrary) grid. The algorithm is embedded in an iterative pr ocedure, where in each iteration a specific instance of (SQC) is solve d. Special attention is given to the simultaneous minimization of the mean and variance of completion times. (C) 1993 John Wiley & Sons, Inc .