Adaptive scheduling for high-volume shops

Abstract

A conceptual algorithm for NP-hard scheduling problems that gives accurate reactive scheduling for high-volume shops is presented. The heuristic algorithm provides classical dispatch scheduling with an embedded optimization procedure. It delivers successive updates of the initially generated schedule by extending in an unconventional way the horizon of applicability. An adaptive mechanism is implemented. The successive schedule updates are generated using beam search. The conceptual algorithm is applied to problems where a periodic production pattern is assumed. Analysis of the algorithm's behavior reveals that the performance measure converges to the calculated lower bounds and that the computational time can be polynomial, for each problem, in the number of parts to process.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>