An efficient local search scheme for minimizing mean absolute deviation of completion times

We present a two phase local search scheme for finding a sequence of n jobs to be performed on a single machine such that mean absolute deviation of completion times from the mean completion time (MADMC) is minimum. By exploiting the structure of the MADMC function, we show that partial dominance exists among the n! feasible sequences. With the help of these dominance relations we are able to show that the complexity of our local search algorithm is a polynomial in the number of jobs. The asymptotic optimality result of Mosheiov apply to our heuristic also since we begin our search from Mosheiov’s heuristic solution, the alternating sequence, and hence improve upon it.