next up previous
Next: Using OR-data as Up: A comparison between Operations Previous: OR models and

WIZARD: A knowledge-based tool for real world scheduling

Since the early 1980's research done in Artificial Intelligence has struggled to overcome the limitations of mathematical models. Heuristic models and systems try to exploit the knowledge lying in the data to be considered or used by human planners. Among the best-known systems are ISIS [10]), OPIS [21]), and Micro-Boss ([20]). Other systems presented in the literature are SONIA ([8]), OPAL ([6]) and TOSCA ([3], [4]).

We view scheduling as an assignment problem which is stated by [19] as a subtype of construction. Assignment problems are characterized by two sets of objects, demands and supplies, where each element of one set must be assigned to one element from the other set satisfying given requirements. Requirements may be incompatibilities and there may be preferences for single assignments or even constellations of assignments. Problem domains include assignment of courses to room/time combinations for school time tables, of jobs to time-units and machines for productions schedules, of employees to working places, airport gates to aeroplanes and others.

The set of demands in scheduling problems are the tasks of the jobs to be processed in the time horizon considered; the supplies are the machines, tools, devices, and personnel available over time.

We have developed the knowledge-based tool WIZARD (This acronym can be resolved only in German; its translation means ``Knowledge-based allocation in an assisting system for resource scheduling''; [17]) which can be classified according to [12] as knowledge-intensive in contrast to search-intensive approaches.

WIZARD's basic problem-solving strategy is propose-and-exchange ([18]). It is a sort of branch-and-bound-algorithm and mainly consists of four steps:

  1. Select an operation to be scheduled next.
    This step can integrate several strategies; it is, e.g., possible to concentrate first on heavily loaded resources postponing the remaining operations on other resources.
  2. Select the required resources (if there are any alternatives) and possible times for the operations and assign these values.
  3. Test the constraints.
    In WIZARD hard and soft constraints are distinguished. They implement the restrictions mentioned above. By assigning a weight to every constraint and minimizing the sum of penalties the constraints also implement the objective to be reached by a solution.
  4. If constraints are violated the operations involved in the violations are identified and a limited number of local repairs are tried.

Instead of chronological or dependency directed backtracking in case of constraint violations a variant of iterative repair ([25]) --- although developed independently --- is applied. The main differences from the propose-and-exchange method to iterative repair are first that WIZARD explicitly looks for multi-step repairs and may perform an A-search in the space of possible repairs, and second that WIZARD uses an anytime variant ([7]). The differences between the methods are discussed in greater detail in [16].

All steps except for the third one can extensively use human problem solving knowledge.

The selection of the next operation to be scheduled can involve so-called external priorities, e.g. when a customer is promised to be served preferentially, or heuristical knowledge, e.g. when a scheduler has made the experience that certain tasks are more critical than others and should thus be given more attention.

More important is step two. Especially the selection among different members of the staff to be in charge of specific operations can take into account even such esoteric knowledge as preferences for certain personnel or the fact that a worker may be less reliable on certain days of the week.

The same applies to step four. Some operations can be transferred to different machinery or even to external processing while others should be processed in-house. In many cases the scheduler can come to an informal arrangement with the foremen or other responsible persons in order to meet late due-dates etc. thus making many constraints obsolete which otherwise would result in severe problems.

These examples show that a system for real world scheduling must be able to deal with various aspects, preferences and demands that are not considered in most mathematical models.

The requirements mentioned above are met by WIZARD by the following means:

To sum up, one can say that WIZARD is designed to implement a great variety of aspects playing a vital role in real world production scheduling.

next up previous
Next: Using OR-data as Up: A comparison between Operations Previous: OR models and

Christian Hestermann
Fri Dec 6 16:28:54 MET 1996