Scheduling a single machine with multiple due dates per job

Abstract In this paper, we consider single-machine scheduling with multiple due dates per job. This is motivated by several industrial applications, where it is not important by how much we miss a due date. Instead the relevant objective is to minimize the number of missed due dates. Typically, this situation emerges whenever fixed delivery appointments are chosen in advance, such as in the production of individualized pharmaceuticals or when customers can only receive goods at certain days in the week, due to constraints in their warehouse operation. We compare this previously unexplored problem with classical due date scheduling, for which it is a generalization. We show that single-machine scheduling with multiple due dates is NP-hard in the strong sense if processing times are job dependent. If processing times are equal for all jobs, then single-machine scheduling with multiple due dates is at least as hard as the long-standing open problem of weighted tardiness with equal processing times and release dates $$1 \mid r_j, p_j = p \mid \sum w_j T_j$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>∣</mml:mo> <mml:msub> <mml:mi>r</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> <mml:mo>∣</mml:mo> <mml:mo>∑</mml:mo> <mml:msub> <mml:mi>w</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:mrow> </mml:math> . Finally, we focus on the case of equal processing times and provide several polynomially solvable special cases as well as an exact branch-and-bound algorithm and heuristics for the general case. Experiments show that our branch-and-bound algorithm compares well to modern exact methods to solve problem $$1 \mid r_j, p_j = p \mid \sum w_{j} T_{j}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>∣</mml:mo> <mml:msub> <mml:mi>r</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> <mml:mo>∣</mml:mo> <mml:mo>∑</mml:mo> <mml:msub> <mml:mi>w</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:mrow> </mml:math> .