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

► Partial dominance exists due to which our local search algorithm has polynomial time complexity in the number of jobs. ► For n less than or equal to 25, for 80% of the problems our algorithm ADJACENT got the exact solutions. ► For problems of sizes 30-400, ratios of output of ADJACENT and the lower bound did not exceed 1.13. ► We provide exact solution of 75 problems which can be used as benchmarks.