Earliness-Tardiness Scheduling Around Almost Equal Due Dates

The just-in-time concept in manufacturing has aroused interest in machine scheduling problems with earliness-tardiness penalties. In particular, common due date problems, which are structurally less complicated than problems with general due dates, have emerged as an interesting and fruitful field of research. We prove that so-called almost common due date problems, in which the due date d_j and processing time p_j of each job J_j(j = 1, …, n) are such that d_j ∈ [D, D + p_j] for some constant D, are structurally less complicated also. Our main contribution is an O(n²) time dynamic programming algorithm for the almost common due date problem with large D. The dynamic programming algorithm is interesting in its own right, since the optimality principle behind it applies to other common due date and almost common due date problems as well.