CBR in Scheduling: Reusing Solution Components

Abstract

In this paper we explore the reuse of components of known good schedules in new scheduling problems. This involves accumulating a case-base of good quality schedules, retrieving a case (or cases) similar to a new scheduling problem and building a new schedule from components of the retrieved cases. Two CBR solutions to a single machine scheduling problem with schedule dependent setup times are described. These are evaluated by comparing them with two more conventional alternative techniques – simulated annealing and myopic search. Both CBR techniques are shown to provide good quality solutions and significant time improvements over simulated annealing.