Scheduling with a due-window for acceptable lead-times

Due‐dates are often determined during sales negotiations in two stages: (i) in the pre‐sale stage, the customer provides a time interval (due‐window) of his acceptable due‐dates, (ii) in the second stage, the parties agree on the delivery penalties. Thus, the contract reflects penalties of both parts of the sales negotiations: earliness/tardiness penalties of the due‐dates (as a function of the deviation from the agreed upon due‐window), and earliness/tardiness penalties of the actual delivery times (as a function of the deviation from the due‐dates). We model this setting of a two‐stage negotiation on a single machine, and reduce the problem to a well‐known setting of minimizing the weighted earliness/tardiness with a given (fixed) due‐window. We adopt (and correct) a pseudo‐polynomial dynamic programming algorithm for this NP‐hard problem. The algorithm is extended to a setting of parallel identical machines, verifying that this case remains NP‐hard in the ordinary sense. Moreover, an efficient greedy heuristic and a tight lower bound are introduced and tested. Extremely small optimality gaps are obtained in our numerical tests.