Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines

Abstract

As a measure of variation, total absolute deviation of job completion times (TADC) has received relatively little attention in scheduling literature. Minimizing TADC on a single machine was shown to have a polynomial time solution. In this note, we extend TADC in two directions: (i) we allow position-dependent processing times and (ii) we consider parallel identical machines. We show that each of these two more general problems, and TADC with both extensions remain polynomially solvable.

Keywords:

• scheduling
• single machine
• parallel identical machines
• measures of variation
• position-dependent processing times