Every real-life task imposes constraints of different kinds and different importances that should not be violated to achieve viable solutions. Typical constraints that have to be dealt with in schedulingsystems include deadlines or the exchange of machine parts before they wear out. As it is not possible to know beforehand if all constraints can be satisfied in any given system the notion of importance of a given constraint is a very important measure that can help as a guideline if constraint violations are inevitable.
It is easy to see that constraints can come in two ways that can be identified as crisp constraints (e.g. a timeline that has to be met) on the one hand and fuzzy constraints (e.g. a chemical compatibility has to be a member of a specified set in a membership function) on the other hand.
For any given system at hand all constraints are specified in the ConFlip++ module by the means of simple constraints (also called compare constraints) and composed constraints (also called concatenated constraints).
This is an atomic type of constraint that can be used as a stand-aloneconstraint or to compose a more complex concatenated constraint. In the following the parameters of this constraint together with a short description are given:
| Parameter | Description |
|---|---|
| name | specifies the unique name of a constraint |
| importance | a real number in the range of [0..1] denoting the relative importance of a constraint. |
| dilatation | denotes if the constraint (more exact: the variable of the constraint) is of the type fuzzy, crisp or mixed (though a mixed constraints is fuzzy in essence) |
| comment | this optional parameter can be used for a short description by the user |
| variable | the unique name of the variable a constrained is designed for |
| compare_operator | any operator out of the operator set {=;;<;>} |
| compare_value | the value to which the variable is compared to |
| Parameter | Real-World Instance |
|---|---|
| name | lu-c1 |
| importance | 0.9 |
| dilation | fuzzy |
| comment | 'Aluminum constraint 1' |
| variable | alu (has to be defined already in FLIP++) |
| compare_operator | < |
| compare_value | 0.01 |
Composed constraints are the combination of either two compare constraints, one compare constraint and one composed constraint or two composed constraints. They are useful to create constraint trees by the means of aggregating constraints as well as for modeling antagonistic criteria. The complexity and type of the constraintsin a system to be modeled depends solely on the user. In the following the parameters of this constraint together with a short description are given:
| Parameter | Description |
|---|---|
| name | specifies the unique name of the constraint |
| importance | a real number in the range of [0..1] denoting the relative importance of a constraint. |
| dilatation | denotes if the constraint (more exact: the variables of the constraint) is of the type fuzzy, crisp or mixed (though a mixed constraints is fuzzy in essence) |
| comment | this optional parameter can be used for a short description by the use |
| constraint_1 | name of the 1st-component constraint |
| constraint_2 | name of the 2nd-component constraint |
| concat_operator | a conjunction operator out of the operator set {and; or} |
Note that as usual the meaning of the concat_operator can be defined by what the user finds meaningful - the default operators are fuzzy and and fuzzy or.
Suppose for the example that we have two compare constraints alu-c1 (the one of the example above) and another compare constraint called ni-c1 (that would look something like the alu-c1 costraint though that is not really importance). The concatenation constraint could look like this:
| Parameter | Real-World Instance |
|---|---|
| name | alu-c1-ni-c1 | importance | 0.8 | dilatation | fuzzy | comment | combined aluminum-nickel constraint |
| constraint_1 | alu-c1 |
| constraint_2 | ni-c1 |
| concat_operator | and |
Of course the question arises about a ruleset for any concatenated constraints. The answer is that whenever one creates a concatenated constraint Conflip++ automatically creates a new ruleset out of default or user-defined values. This automatically created ruleset can of course be fine-tuned by the human expert.
Another very important notion about ConFlip++ is SetofConstraints. Each SetofConstraints consists of a name and a list of constraints (that can either be of type compare or concat). Furthermore it has a ruleset-object, tables for concatenating and comparing constraints with the appropriate operators defined in the OperatorSet, and a parameter set describing fuzzy linguistic variables. This makes it obviously easy to group and administer constraints that belong together.
A typical constraint-tree that is in fact part of a real-world steelmaking-scheduling system using StarFlip++ is shown in picture 1:
Besides of being the place for declaring and defining the constrains that are inherent in the system to be modelled ConFlip++ is as well the place where the evaluation of a constraint takes place. The three steps of constraint evaluation are as follows:
All free linguistic variables are assigned numbers that are either defuzzified real numbers or possibility distributions.
The evaluation functon returns a value (by default a defuzzified real number) that describes the degree of satisfaction of a constraint with its assigned number(s).
Evaluated constraints are retained in a SetOfEvalConstraints for further operations.
Of course there can be more than one SetOfEvalConstraints with the same idea of grouping constraints that somehow belong together as we have seen above for SetOfConstraints.
 |
 |
 |
(c)1996 Andreas RAGGL, Mazen YOUNES, Markus BONNER, Wolfgang SLANY
Last modified: Tue Jun 24 15:36:37 MET-DST 1997
by StarFLIP Team