This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Hall, N. G. Articles by Potts, C. N. Search for Related Content

Scheduling with Fixed Delivery Dates

Department of Management Sciences, Fisher College of Business, The Ohio State University, Columbus, Ohio 43210-1144
Labour Market Information & Statistics, Department of Labour, Private Bag X117, Pretoria, South Africa 0001
Faculty of Mathematical Studies, University of Southampton, Highfield, Southampton, United Kingdom, SO9 5N4
hall.33{at}osu.edu
maseka.Lesaoana{at}labour.gov.za
c.n.potts{at}maths.soton.ac.uk

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.

Subject classifications: Production/scheduling: scheduling with fixed delivery dates; Sequencing, deterministic: algorithms and complexity results.
History: Received January 1997; revision received September 1998; revision received August 1999; accepted September 1999.

This article has been cited by other articles:

				K. E. Stecke and X. Zhao Production and Transportation Integration for a Make-to-Order Manufacturing Company with a Commit-to-Delivery Business Mode MSOM, January 1, 2007; 9(2): 206 - 224. [Abstract] [PDF]

				Z.-L. Chen and G. Pundoor Order Assignment and Scheduling in a Supply Chain Operations Research, May 1, 2006; 54(3): 555 - 572. [Abstract] [PDF]

				Z.-L. Chen and G. L. Vairaktarakis Integrated Scheduling of Production and Distribution Operations Management Science, April 1, 2005; 51(4): 614 - 628. [Abstract] [PDF]

				N. G. Hall and C. N. Potts Supply chain scheduling: Batching and delivery Operations Research, July 1, 2003; 51(4): 566 - 584. [Abstract] [PDF]