Scheduling with Multiple Performance Measures: The One-Machine Case

Most scheduling research has considered optimizing a single performance measure (criterion). In this paper we consider the problem of scheduling jobs on a single machine when the desirability of a schedule is evaluated using more than one performance measure. The procedures developed here can be used to construct trade-off curves among selected performance measures. The importance of the trade-off curve is that it provides the complete set of possibly optimal solutions for any objective function (cost function) involving only the selected performance measures. With this information, a manager can concentrate on selecting the most preferred schedule from the set. Algorithms are presented for the three two-criteria problems utilizing mean flow time, maximum tardiness, and number of tardy jobs and the three-criteria problem involving all of these criteria. Computational results for the four algorithms are provided. The most striking result is that the number of efficient solutions is very small in comparison to the number of permutation schedules for all three two-criteria problems and only modestly larger for the three-criteria problem. This has the managerial significance that, irrespective of the individual manager's specific trade-offs between the criteria, the number of possibly optimal schedules that need to be considered is relatively small. Several research directions on heuristic approaches, man-machine interactive approaches, computational efficiency, etc. are possible for the type of problem studied. The work reported here has the potential to stimulate research incorporating multiple performance measures in more complex scheduling models.