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

Rescheduling for New Orders

Department of Management Sciences, Fisher College of Business, The Ohio State University, Columbus, Ohio 43210-1144
School of Mathematics, University of Southampton, Southampton, United Kingdom SO17 1BJ
hall.33{at}osu.edu
c.n.potts{at}maths.soton.ac.uk

This paper considers scheduling problems where a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives and creates a disruption. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. Two classes of models are considered. First, we minimize the scheduling cost of all the jobs, subject to a limit on the disruption caused to the original schedule, where this disruption is measured in various ways. In the second class, a total cost objective, which includes both the original cost measure and the cost of disruption, is minimized. For both classes and various costs based on classical scheduling objectives, and for almost all problems, we provide either an efficient algorithm or a proof that such an algorithm is unlikely to exist. We also show how to extend both classes of models to deal with multiple disruptions in the form of repeated arrivals of new jobs. Our work refocuses the extensive literature on scheduling problems towards issues of rescheduling, which are important because of the frequency with which disruptions occur in manufacturing practice.

Subject classifications: production/scheduling; sequencing; deterministic; single machine.
History: Received August 2002; revision received February 2003; accepted April 2003.

This article has been cited by other articles:

				N. G. Hall, Z. Liu, and C. N. Potts Rescheduling for Multiple New Orders INFORMS Journal on Computing, January 1, 2007; 19(4): 633 - 645. [Abstract] [PDF]