Minimizing mean absolute deviation of job completion times from the mean completion time

In many scheduling environments it is recommended to control the balance of the performance of individual jobs, e.g., the variability of the job completion or waiting times. In service systems, for example, it may be important to provide customers with an identical or similar service quality, as measured by their time in system or waiting time. Several measures of variation have been studied in scheduling literature in this context; our paper considers the measure of Mean Absolute Deviation of job completion times from the Mean Completion time (MADMC). Recently, Aneja et al. proved that minimizing MADMC on a single-machine is NP-hard. We introduce a simple heuristic and an easily obtained lower bound on the optimal MADMC value. We prove that the worst case optimality gap of the heuristic is bounded by the constant 2, and that this bound is tight. Better worst case bounds can be achieved in special cases. Both the heuristic and the lower bound are shown to be asymptotically accurate under very general conditions. Both the heuristic and lower bound are extended to parallel identical machines. In our extensive numerical study we show that the heuristic produces, both in the single-machine and in the multi-machine case, extremely close-to-optimal schedules.