Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems

Abstract

In this paper, we consider bicriterion scheduling problems involving job completion times and job waiting times in a nonpreemptive single machine environment. As an example, we seek to determine a schedule that yields both a low mean and a low variation of completion time. Such a schedule is attractive when the system has the dual objectives of minimizing in-process inventory and providing different jobs the same quality of service. Similarly, we seek a schedule that performs well on both the mean and variation of waiting time. As the measure of variation, we use the sum of absolute pairwise differences. We present an efficient algorithm for minimizing the variation of waiting time. Next, we assume that the total scheduling cost is a function of the mean and variation of completion time alone, and is linear. We give an efficient algorithm for minimizing this total cost. Finally, we consider parametric analysis of this cost function and present simple procedures for generating all or some of the optimal schedules. All the results are extended to the case where job waiting times are substituted for job completion times.