Rescheduling for Job Unavailability

Nicholas G. Hall () and Chris N. Potts ()
Additional contact information
Nicholas G. Hall: Fisher College of Business, The Ohio State University, Columbus, Ohio 43210
Chris N. Potts: School of Mathematics, University of Southampton, Southampton SO17 1BJ, United Kingdom

Operations Research, 2010, vol. 58, issue 3, 746-755

Abstract: This paper considers scheduling problems where the processing of a set of jobs has been scheduled (i.e., planned) to minimize a classical cost objective, under the assumption that the jobs are all available at the start of the planning horizon. Before processing starts, however, the availability of a subset of the jobs is delayed. Therefore, the decision maker needs to adjust the existing schedule to allow for the initial unavailability of those jobs, but without causing excessive disruption to the schedule and expensive resource reallocations. The limit on allowable disruption is measured by the maximum time disruption to any job, between the original and adjusted schedules. For the classical sum of weighted completion times scheduling objective, we provide a computationally efficient optimal algorithm and an intractability proof showing that such an algorithm is the best possible type of result. Also, we provide a linear time approximate solution procedure, show that its worst-case performance ratio is a small constant, and demonstrate computationally that its average performance is very close to optimal. Finally, we provide a fully polynomial time approximation scheme. We also summarize analogous results for three other classical scheduling objectives. Our work is among the first to develop optimal algorithms, heuristics with guaranteed performance bounds, and approximation schemes, for rescheduling problems.

Keywords: production/scheduling; sequencing; deterministic; single machine; manufacturing; performance/productivity (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1090.0751 (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:58:y:2010:i:3:p:746-755

Access Statistics for this article

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