Single-machine scheduling to minimize absolute deviation of completion times from a common due date

The article considers a single-machine n-job scheduling problem to minimize the sum of absolute lateness given a common due date. Two models are defined depending on whether the start time t₀ of schedules is arbitrary or fixed. Conditions are provided when those two models coincide. The developed branch-and-bound procedure is tested on nine known examples from the literature (6 ⩽ n ⩽ 14) and 90 medium-size random problems (15 ⩽ n ⩽ 25) with a fixed t₀.