Scheduling with a due-window for acceptable lead-times |
| |
Authors: | Enrique Gerstl Gur Mosheiov |
| |
Institution: | 1.Jerusalem College of Technology,Jerusalem,Israel;2.The Hebrew University,Jerusalem,Israel |
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|