Scheduling with Fixed Delivery Dates

Nicholas G. Hall (), 'Maseka Lesaoana () and Chris N. Potts ()
Additional contact information
Nicholas G. Hall: Department of Management Sciences, Fisher College of Business, The Ohio State University, Columbus, Ohio 43210-1144
'Maseka Lesaoana: Labour Market Information & Statistics, Department of Labour, Private Bag X117, Pretoria, South Africa 0001
Chris N. Potts: Faculty of Mathematical Studies, University of Southampton, Highfield, Southampton, United Kingdom, SO9 5N4

Operations Research, 2001, vol. 49, issue 1, 134-144

Abstract: In most classical scheduling models, it is assumed that a job is dispatched to a customer immediately after its processing completes. In many practical situations, however, a set of delivery dates may be fixed before any jobs are processed. This is particularly relevant where delivery is an expensive or complicated operation, for example, as with heavy machinery. A similar situation arises where customers find deliveries disruptive and thus require them to be made within a limited time interval that repeats periodically. A third possibility is that a periodic business function, for example, the supplier's billing cycle, effectively defines a delivery date, and includes all jobs that have been completed since the previous billing cycle. These situations are not adequately represented by classical scheduling models. We consider a variety of deterministic scheduling problems in which a job is dispatched to a customer at the earliest fixed delivery date that is no earlier than the completion time of its processing. Problems where the number of delivery dates is constant, and others where it is specified as part of data input, are studied. For almost all problems considered, we either provide an efficient algorithm or establish that such an algorithm is unlikely to exist. By doing so, we permit comparisons between the solvability of these fixed delivery date problems and of the corresponding classical scheduling problems.

Keywords: Production/scheduling: scheduling with fixed delivery dates; Sequencing; deterministic: algorithms and complexity results (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.1.134.11192 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:1:p:134-144

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().