presented at the 14th Workshop of the UK Planning and Scheduling Special Interest Group

1

CBR in Scheduling:

Reusing Solution Components

P?draig Cunningham
Department of Computer Science
Trinity College Dublin
College Green Dublin 2
Ireland
Padraig.Cunningham@cs.tcd.ie

Barry Smyth
Hitachi Dublin Laboratory
Trinity College Dublin
College Green Dublin 2
Ireland
Barry.Smyth@hdl.ie

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.

1 Introduction

There is a lot of optimism at the moment about the usefulness of case-based reasoning (CBR) in the development of knowledge based systems. The view is that cases can represent good quality solutions that may be reused in new situations. Typically, cases represent compiled knowledge in weak theory domains (CAPLAN/CBC as described in (Mu?oz, Paulokat & Wess, 1994) is a typical example of this idea.). There are other situations where solution reuse may be advantageous; for instance in optimisation problems where cases can represent highly optimised structures in the problem space. In this paper we explore this type of reuse in job scheduling problems.

Two distinct approaches to case-based scheduling can be identified from the literature. The first one is used in Koton's SMARTplan (1989). Cases are used to propose preliminary schedules which are then adapted (refined and repaired) to satisfy the target schedule requirements. The second approach does not uses cases to propose schedules, but instead to adapt schedules proposed by other methods (for example, Sycara & Miyashita, 1994). In other words cases can encode actual schedules (the first approach) or they can encode repair procedures (the second approach).

In this work we examine the first approach and look at two different modes of reuse -- (1) the reuse of single cases as skeletal solutions, and (2) the reuse of multiple cases as the building blocks of the desired target solution.

We are interested in the use of CBR in scheduling problems in general but we start here with a single machine problem where job setup time is schedule dependent. We consider two CBR solutions to this problem and we compare these with two standard solution techniques. The first is Simulated Annealing; this produces good quality solutions but is computationally expensive. The second is a na?ve search mechanism that selects the nearest job next. This is referred to as the Myopic solution; it produces poorer solutions but is fast.

An extensive evaluation comparing these techniques is presented. Our conclusion is that the CBR techniques produce fairly good quality solutions quickly. The details of the scheduling problem are presented in the next section before the CBR solutions are introduced in section