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 Google Scholar Google Scholar Articles by Hall, N. G. Articles by Potts, C. N. Search for Related Content

Rescheduling for Multiple New Orders

Department of Management Sciences, Fisher College of Business, The Ohio State University, Columbus, Ohio 43210
Department of Management Studies, School of Management, University of Michigan–Dearborn, Dearborn, Michigan 48126
School of Mathematics, University of Southampton, Southampton, SO17 1BJ, United Kingdom
hall.33{at}osu.edu
zhixin{at}umd.umich.edu
c.n.potts{at}soton.ac.uk

Aset of original jobs has been scheduled on a single machine, but not processed, when a set of new jobs arrives. The decision maker needs to insert the new jobs into the existing schedule without excessively changing it. The objective is minimization of the maximum lateness of the jobs, subject to a customer service requirement modeled by a limit on the maximum time change of the original jobs. Because the schedule of the original jobs can be arbitrary, this problem models multiple disruptions from repeated new job arrivals. We show that this scheduling problem is intractable, even if no new jobs arrive. We describe several approximation algorithms and analyze their worst-case performance. Next, we develop a branch and bound algorithm that uses a variable neighborhood descent algorithm to obtain an initial upper bound, several dominance properties that we establish, and a lower bounding scheme based on a preemptive relaxation of the problem. The branch and bound algorithm solves 99.9% of randomly generated instances with up to 1,000 jobs within 60 CPU seconds. Our work demonstrates for the first time that optimization of large scale, intractable rescheduling problems is possible. More generally, it refocuses the literature on scheduling problems towards rescheduling issues.

Key words: deterministic scheduling; rescheduling for new job disruptions; heuristic worst-case analysis; branch and bound algorithm
History: received March 2005; revised August 2006; accepted August 2006.