Iterative Improvement Methods for Knowledge-Based Scheduling

Article type: Research Article

Authors: Dorn, Jürgen

Affiliations: Christian Doppler Laboratory for Expert Systems, Vienna, University of Technology, Paniglgasse 16, A-1040 Vienna, Austria. Email: dorn@vexpert.dbai.tuwien.ac.at

Abstract: For large industrial applications the constraint-based formulation of scheduling problems fits better than mathematical representations from Operational Research, because the constraint approach is more flexible and can be adapted more easily to organizational changes in the production. However, the search for a good solution for realistic applications can be very expensive and furthermore, in scheduling one is not only interested in a feasible solution but also in an optimized solution. In this paper I present iterative improvement methods that can be used to optimize a schedule that is represented by constraints. These methods start with any schedule and try to optimize it by iterative modifications. The goal of the optimization method may be a minimization of the number of constraint violations or a maximization of a function that aggregates the satisfaction degrees of all involved soft constraints. Additionally, consistency techniques for constraints can be used to check a schedule after each modification. These problem solving methods have several benefits for realistic industrial applications. Since they can start with any preliminary schedule and can be interrupted anytime, they can be applied easily to reactive and cooperative scheduling. Further, they produce often better solutions in less time than other methods as was shown in several experiments. The paper gives an overview on important design decisions for iterative improvement methods, presents some of these methods in more detail and shows some results of our experiments made in applications of the steel-making industry.

DOI: 10.3233/AIC-1995-8102

Journal: AI Communications, vol. 8, no. 1, pp. 20-34, 1995