Minimizing the sum of absolute deviations under a common due date for a single-machine scheduling problem with availability constraints

This paper investigates a single-machine scheduling problem with a planned maintenance period. The objective is to minimize the sum of absolute deviations (SAD) of job completion times under a common due date. It appears to be the first attempt to schedule jointly the SAD criterion and machine availability constraints. The problem is first mathematically formulated as a mixed integer linear programming model and is then solved optimally. Subsequently, we present some optimality conditions and describe the special cases of the problem which are polynomially solvable. As the computational complexity associated with the formulation makes it difficult for standard solvers address large-sized problems in reasonable solution time, we propose an ant colony optimization algorithm based on the results of our analysis. Computational results for different problem sizes demonstrate that our application of the suggested algorithm is efficient in obtaining near-optimal solutions.