5.283. shift
| DESCRIPTION | LINKS | GRAPH |
- Origin
N. Beldiceanu
- Constraint
shift(MIN_BREAK,MAX_RANGE,TASKS)
- Argument(s)
-
MIN_BREAK int MAX_RANGE int TASKS collection(origin−dvar,end−dvar) - Restriction(s)
-
MIN_BREAK>0 MAX_RANGE>0 required(TASKS,[origin,end]) TASKS.origin<TASKS.end - Purpose
The difference between the end of the last task of a shift and the origin of the first task of a shift should not exceed the quantity MAX_RANGE. Two tasks t1 and t2 belong to the same shift if at least one of the following conditions is true:
- Example
-
(
)6,8,〈
〉origin−17 end−20, origin−7 end−10, origin−2 end−4, origin−21 end−22, origin−5 end−6 Figure 5.283.1 represents the different tasks of the example. Each task is drawn as a rectangle with its corresponding id attribute in the middle. We indicate the distance between two consecutive tasks of a same shift and observe that it is less than or equal to MIN_BREAK=6. Since each shift has a range that is less than or equal to MAX_RANGE=8, the shift constraint holds (the range of a shift is the difference between the end of the last task of the shift and the origin of the first task of the shift).
Figure 5.283.1. The two shifts of the example
- Usage
The shift constraint can be used in machine scheduling problems where one has to shut down a machine for maintenance purpose after a given maximum utilisation of that machine. In this case the MAX_RANGE parameter indicates the maximum possible utilisation of the machine before maintenance, while the MIN_BREAK parameter gives the minimum time needed for maintenance.
The shift constraint can also be used for timetabling problems where the rest period of a person can move in time. In this case MAX_RANGE indicates the maximum possible working time for a person, while MIN_BREAK specifies the minimum length of the break that follows a working time period.
- See also
- Key words
constraint type: scheduling constraint, timetabling constraint, temporal constraint.
- Arc input(s)
TASKS
- Arc generator
-
SELF↦collection(tasks) - Arc arity
-
1 - Arc constraint(s)
-
• tasks.end≥tasks.origin • tasks.end−tasks.origin≤MAX_RANGE - Graph property(ies)
-
NARC=|TASKS|
- Arc input(s)
TASKS
- Arc generator
-
CLIQUE↦collection(tasks1,tasks2) - Arc arity
-
2 - Arc constraint(s)
-
⋁(
)tasks2.origin≥tasks1.end∧tasks2.origin−tasks1.end≤MIN_BREAK, tasks1.origin≥tasks2.end∧tasks1.origin−tasks2.end≤MIN_BREAK, tasks2.origin<tasks1.end∧tasks1.origin<tasks2.end - Sets
-
CC↦ [
]variables−col(
)VARIABLES−collection(var−dvar), item(var−TASKS.origin),item(var−TASKS.end)] - Constraint(s) on sets
-
range_ctr(variables,≤,MAX_RANGE)
- Graph model
The first graph constraint enforces the following two constraints between the attributes of each task:
The end of a task should not be situated before its start,
The duration of a task should not be greater than the MAX_RANGE parameter.
The second graph constraint decomposes the final graph in connected components where each component corresponds to a given shift. Finally, the Constraint(s) on sets slot restricts the stretch of each shift.
Parts (A) and (B) of Figure 5.283.2 respectively show the initial and final graph associated with the second graph constraint of the Example slot. Since we use the set generator CC we show the two connected components of the final graph. They respectively correspond to the two shifts that are displayed in Figure 5.283.1.
Figure 5.283.2. Initial and final graph of the shift constraint
(a) (b) - Signature
Consider the first graph constraint. Since we use the SELF arc generator on the TASKS collection the maximum number of arcs of the final graph is equal to |TASKS|. Therefore we can rewrite the graph property NARC=|TASKS| to NARC≥|TASKS| and simplify to .