Scheduling with a due-window for acceptable lead-times

Abstract

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.

Keywords:

• scheduling
• single machine
• lead-time
• earliness/tardiness
• due-window assignment

Acknowledgements

This research was supported by the Israel Science Foundation (Grant No. 1286/14). The second author was supported in part by The Charles Rosen Chair of Management and the Recanati Fund of The School of Business Administration, The Hebrew University, Jerusalem, Israel.