page 1  (6 pages)
2to next section

Constraint-Based Scheduling in Oz

J?org W?urtz, DFKI GmbH, Saarbr?ucken

Abstract

It is discussed, how scheduling problems can be solved in the concurrent constraint programming language Oz. Oz is the first high-level constraint language, which offers an interface to invent new constraints in an efficient way using C++. Its multi-paradigm features including programmable search are unique in the field of constraint programming. Through the interface, algorithms from Operations Research and related fields can be incorporated. The algorithms can be combined through encapsulation into constraints and can communicate via shared variables. This is exemplified by the integration of new techniques based on edge-finding for job-shop and multi-capacitated scheduling. The viability of Oz as a platform for problem solving is also exemplified by a graphical scheduling workbench. The performance for job-shop problems is comparable to state-of-the-art scheduling tools.

1 Introduction

Since many years, Operations Research (OR) is successfull in solving application problems. Often, tailored algorithms are developped, which tackle the problem under investigation very efficiently. But difficulties may arise, if the tailored algorithm has to be adapted to changes of the problem formulation. The special-purpose program may have to be restated in a time-consuming way.

On the other hand, constraint programming was invented with the aim to combine declarativeness and expressiveness with efficiency [7]. This works well for several application domains like scheduling, configuration, or resource allocation. But for larger and especially hard problems, the used constraint-techniques were not sufficient. Hence, techniques from OR were incorporated into constraint systems, pioneered by CHIP [4]. Changes of the problem formulation can be modeled by stating different constraints. But CHIP lacks flexibility to allow the user to invent new kinds of constraints.

We propose Oz [11, 12] as a platform to integrate algorithms from OR to achieve an amalgamation of a high-level constraint language with efficient OR techniques. Oz is a concurrent constraint language providing for functional, object-oriented, and constraint programming. The unique advantages of Oz, which can be offered to the OR community are:

ffl Expressiveness. Different language paradigms allow a natural and high-level modelling of the problem. Concurrent constraints provide for rapid testing of different models.

ffl Programmable Search. Besides predefined search strategies like depth-first one solution search or branch & bound, the user can program his own strategies [10]. Search is completely separated from the reduction of the search space achieved by constraint propagation.

ffl Modularity. Through the encapsulation of different algorithms into constraints, they can be combined and interact in one environment. In combination with search and objects, collaborating problem solvers can be programmed.

ffl Openness. Through the use of a C++ interface [9], new constraints can be implemented efficiently by the programmer and used like any Oz procedure.