Fuzzy Constraint Relaxation Techniques

for Knowledge-Based Scheduling?

Wolfgang Slany

Christian Doppler Laboratory for Expert Systems

E184/2, TU Wien, A-1040 Vienna, Austria, Europe

Phone: +43{1{58801{6123

Fax: +43{1{5055304

E-Mail: wsi@vexpert.dbai.tuwien.ac.at

Abstract: Mathematical-analytical methods as used in Operations Research approaches are often insufficient for real-world applications. This is due to three reasons: The imprecise informations in the real-world applications, combinatorial complexity of the search space, and conflicting objectives for optimizing. The combination of several knowledge-based techniques, especially approximate reasoning and constraint relaxation, is a promising way to handle these problems.

I attempt to give an overview on existing fuzzy constraint relaxation techniques, focusing on

ffl the type of problems handled,

ffl the techniques used, with examples,

ffl advantages,

and then proceed to compare these techniques with other constraint relaxation techniques.

Special emphasis will be given to the industrial scheduling domain, as this is a very prominent real-world application area for constraint satisfaction methods.

I Introduction

Constraint relaxation is necessary when problems are overconstrained or too difficult to solve completely, but it is acceptable to settle for a good enough" solution. This applies to many problems encountered in practical manufacturing situations. Constraint relaxation as in [4] aims at finding values for a subset of problem describing variables that satisfy a subset of the constraints. Constraints are weakened" to permit additional acceptable value combinations. For practical as well as theoretical reasons, approximate reasoning methods as those examplified by [10] are a very elegant way to weaken these so-called soft" constraints. [3] correctly point out that this method allows to represent in the same framework priorities between the constraints. In this present paper, a small example taken from a real-world application illustrates the easiness and elegance arising from the use of fuzzy constraint relaxation techniques.

?Presented at EUFIT'93, First European Congress on Fuzzy and Intelligent Technologies, Hans-J?urgen Zimmermann (ed.), Sep. 1993, Aachen, Germany, pp. 1124{1127