The dynamic aspects of a production scheduling problem

Abstract

This paper presents a single machine scheduling problem with sequence dependent changeover times. An optimizing solution procedure and various appropriate heuristics are reviewed. We then go on to consider the performance of these and other heuristics in the dynamic situation, as new jobs arrive to be processed and have to be added into the existing schedule at some time. Clearly an ideal solution would be to reschedule as each new job arrived, but as this is not generally practical from a computational viewpoint, it has to be carried out less frequently. The actual frequency of this rescheduling is clearly of importance, and some of the heuristics are more adaptable to this than others. Some results are presented which attempt to quantify this adaptability for the heuristics in question, and it is demonstrated that the best heuristic for the static problem is not necessarily the best heuristic in the dynamic situation.