About Domain-Specific Constraint Patterns

What are Domain-Specific Constraint Patterns?

A pattern describes a recurring problem, gives a solution approach to this problem, and highlights consequences of choosing this approach. The solution approach describes the best practice or expert knowledge of how to model the problem. By making the patterns domain-specific, problem specific modelling ideas can be included, including specific global constraints and search strategies that are known for the problem, into the pattern description. This allows for a simplification of the modelling process, as well as making high-quality models easier to obtain.

Describing Domain-Specific Constraint Patterns

The current pattern description includes several attributes that are listed and explained here:

Intent	What does the constraint pattern do?
Motivation	What is the motivation behind the pattern?
Applicability	What are the situations in which the pattern can be applied? What are Conditions (e.g. on the event log) under which the pattern can be applied?
Participants	The objects participating in the pattern.
Collaborations	How do the participants collaborate in the pattern?
Diagram	A graphical representation of the pattern, e.g. a Gantt chart.
Consequences	What are the trade-offs and results of using the pattern? What aspects does it allow to be varied and which are fixed?
Modelling variants	What are variants of the best-practice modelling of this pattern (depending on the availability of specific variable or constraint types)?
Forces	Which other patterns must hold if this pattern holds.
Enables	Which other patterns have this pattern as a prerequisite?
Incompatible with	Which other patterns can not be applied with this pattern?
Compatible with	Which patterns can be applied with this pattern?
Search Strategies	Which search strategies work well in the setting of this pattern?

Using domain-specific Constraint Patterns

We show how a constraint model can be assembled for example in IBM Cplex from the pattern implementations of variables and constraints available on this website on the example of the following problem:

Problem Description
A set of products are to be processed in a Flow Shop environment. A set of workers exist with one worker present for the processing of each operation. Further, each worker takes a certain amount of time to walk between machines.

Occurring domain-specific Constraint Patterns
– Flow Shop Pattern (Products in Flow Shop)
– Distinguishable Resources Pattern (Workers)
– Resource Setup Times Pattern (Worker walking times)

The Applicability Entry

As part of the description of patterns, we give information about the applicability of the pattern, so the situation in which the pattern can be applied. We describe these conditions as necessary and sufficient conditions on an event log. To formally state these, we make some definitions for event logs below using the formalisation by Wil van der Aalst in his book Data Science in Action. We will closely follow some of the definitions relating to event logs he made in this book.

Definition: Event Attribute
Let $\mathcal{E}$ be the event universe. Events may be characterized by various attributes. Let $AN$ be the set of attribute names. For any event $e\in\mathcal{E}$ and name $n\in AN$ , $\texttt{\#}_n(e)$ is the value of attribute $n$ for event $e$ . If event $e$ does not have an attribute named $n$ , then $\texttt{\#}_n(e) = \bot$ (null value).

We can now define an event log. An event log contains data related to a single process and consists of events. Each event refers to a single process instance, also referred to as case. For a set $A$ , let $A^*$ denote the set of finite sequences over $A$ .

Definition: Event Log $E$
Let $\mathcal{C}$ be the case universe. For any case $c\in \mathcal{C}$ and name $n\in AN$ , define $\texttt{\#}_n(c)$ to be the value of attribute $n$ for case $c$ ( $\texttt{\#}_n(c) = \bot$ if case $c$ has no attribute $n$ ). Each case has a special attribute trace, where $\texttt{\#}_{\mbox{trace}}(c) \in \mathcal{E}^*$ . A trace is a finite sequence of events such that each event appears only once. An event log is then a set of cases $E\subseteq \mathcal{C}$ such that each event appears at most once in the entire log.

Events that belong to the same activity instance, for example the start processing and complete processing event of one activity, may be identified as belonging together through the activity instance attribute or the activity name. We also call an activity instance an operation.

Note that the same process might be described by different event logs. For the example of scheduling problems, an event log might be using the jobs as cases, or the machines as cases. While some events will occur in both logs, other events such as machine setup will only occur in one of the logs. From an event log, we can obtain, by matching all events of the same activity instance, a sequence of events for each job and each machine. If a pattern has sufficient conditions stated over for example the machine sequences, but they are empty in this case, the pattern is clearly not satisfied. These sequences can be obtained even if the log looks different, for example if it contains start time and duration information of each operation instead of start and completion time. In these cases, a suitable adapter needs to be implemented for the given event log structure.

Definition: Job operations sequence $ops(j)$
For each job $j \in J_E$ in the event log $E$ , the job operation sequence $ops(j) = \langle op_1(j), \dots, op_{|ops(j)|}(j)\rangle$ is the sequence of operations corresponding to grouped events of the trace of the job ordered by ascending start times (if these exist), where each operation $op_{i}(j)$ may have any number of attributes. Attributes can for example be the following: the activity $\texttt{\#}_{\mbox{activity}}(op_i(j))$ , the start time $\texttt{\#}_{\mbox{start}}(op_i(j))$ , the completion time $\texttt{\#}_{\mbox{end}}(op_i(j))$ and the machine $\texttt{\#}_{\mbox{machine}}(op_i(j))$ of the operation.

We define operation sequences for machines analogously to the operation sequences for jobs.

Definition: Machine operation sequence $\mathfrak{ops}(m)$
For each machine $m \in M_E$ , the machine operation sequence $\mathfrak{ops}(m) = \langle \mathfrak{op}_1(m), \dots, \mathfrak{op}_{|\mathfrak{ops}(m)|}(m)\rangle$ is the sequence of operations corresponding to grouped events of the trace of $m$ ordered by ascending start times (if these exist), where each operation $\mathfrak{op}_{i}(m)$ may have any number of attributes. Attributes can for example be the following: the activity $\texttt{\#}_{\mbox{activity}}(\mathfrak{op}_i(m))$ , the start time $\texttt{\#}_{\mbox{start}}(\mathfrak{op}_i(m))$ , the completion time $\texttt{\#}_{\mbox{end}}(\mathfrak{op}_i(m))$ , and the job $\texttt{\#}_{\mbox{job}}(\mathfrak{op}_i(m))$ of the operation.

In some cases one or several resources exist in the problem and we may need to consider the resource operation sequence, which is defined analogously to the job and machine operation sequences. For $r \in \mathcal{R}$ the resource operation sequence is denoted by $\mbox{ops}(r) = \langle \mbox{op}_1(r), \dots, \mbox{op}_{|\mbox{ops}(m)|}(m)\rangle$ .

Note that, as for events and cases, we use the notation $\bot$ to denote that an operation does not have an attribute. Further, we may restrict these operation sequences to events of a certain type, such as processing events, where the transaction type is either start processing and end processing, also called filtering. We denote the processing subsequences of $ops(j)$ and $\mathfrak{ops}(m)$ by $ops^p(j)$ and $\mathfrak{ops}^p(m)$ respectively.