Paper Info
Title
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.
Year
DOI
Venue
2015
10.1057/jors.2014.132
Journal of the Operational Research Society
Keywords
Field
DocType
scheduling,single machine,lead-time,earliness/tardiness,due-window assignment
Dynamic programming,Numerical tests,Mathematical optimization,Tardiness,Upper and lower bounds,Computer science,Scheduling (computing),Greedy algorithm,Lead time,Operations management
Journal
Volume
Issue
ISSN
66
9
0160-5682
Citations 
PageRank 
References 
1
0.35
8
Authors
2
Name
Order
Citations
PageRank
Enrique Gerstl1637.72
Gur Mosheiov21073105.02