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:
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 be the event universe. Events may be characterized by various attributes. Let be the set of attribute names. For any event and name , is the value of attribute for event . If event does not have an attribute named , then (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 , let denote the set of finite sequences over .
Definition: Event Log
Let be the case universe. For any case and name , define to be the value of attribute for case ( if case has no attribute ). Each case has a special attribute trace, where . A trace is a finite sequence of events such that each event appears only once. An event log is then a set of cases 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
For each job in the event log , the job operation sequence 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 may have any number of attributes. Attributes can for example be the following: the activity , the start time , the completion time and the machine of the operation.
We define operation sequences for machines analogously to the operation sequences for jobs.
Definition: Machine operation sequence
For each machine , the machine operation sequence is the sequence of operations corresponding to grouped events of the trace of ordered by ascending start times (if these exist), where each operation may have any number of attributes. Attributes can for example be the following: the activity , the start time , the completion time , and the job 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 the resource operation sequence is denoted by .
Note that, as for events and cases, we use the notation 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 and by and respectively.