5.289. shift

DESCRIPTIONLINKSGRAPH
Origin

N.Β Beldiceanu

Constraint

πšœπš‘πš’πšπš(𝙼𝙸𝙽_π™±πšπ™΄π™°π™Ί,π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄,πšƒπ™°πš‚π™Ίπš‚)

Arguments
𝙼𝙸𝙽_π™±πšπ™΄π™°π™Ίπš’πš—πš
π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄πš’πš—πš
πšƒπ™°πš‚π™Ίπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πš’πšπš’πš—-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›)
Restrictions
𝙼𝙸𝙽_π™±πšπ™΄π™°π™Ί>0
π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄>0
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°πš‚π™Ίπš‚,[πš˜πš›πš’πšπš’πš—,πšŽπš—πš])
πšƒπ™°πš‚π™Ίπš‚.πš˜πš›πš’πšπš’πš—<πšƒπ™°πš‚π™Ίπš‚.πšŽπš—πš
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 π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄. Two tasks t 1 and t 2 belong to the same shift if at least one of the following conditions is true:

  • Task t 2 starts after the end of task t 1 at a distance that is less than or equal to the quantity 𝙼𝙸𝙽_π™±πšπ™΄π™°π™Ί,

  • Task t 1 starts after the end of task t 2 at a distance that is less than or equal to the quantity 𝙼𝙸𝙽_π™±πšπ™΄π™°π™Ί.

  • Task t 1 overlaps task t 2 .

Example
6,8,πš˜πš›πš’πšπš’πš—-17πšŽπš—πš-20,πš˜πš›πš’πšπš’πš—-7πšŽπš—πš-10,πš˜πš›πš’πšπš’πš—-2πšŽπš—πš-4,πš˜πš›πš’πšπš’πš—-21πšŽπš—πš-22,πš˜πš›πš’πšπš’πš—-5πšŽπš—πš-6

FigureΒ 5.289.1 represents the different tasks of the example. Each task is drawn as a rectangle with its corresponding πš’πš attribute in the middle. We indicate the distance between two consecutive tasks of a same shift and note that it is less than or equal to 𝙼𝙸𝙽_π™±πšπ™΄π™°π™Ί=6. Since each shift has a range that is less than or equal to π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄=8, the πšœπš‘πš’πšπš 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.289.1. The two shifts of the example
ctrs/shift1
Symmetries
  • Items of πšƒπ™°πš‚π™Ίπš‚ are permutable.

  • One and the same constant can be added to the πš˜πš›πš’πšπš’πš— attribute of all items of πšƒπ™°πš‚π™Ίπš‚.

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 π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄ parameter indicates the maximum possible utilisation of the machine before maintenance, while the 𝙼𝙸𝙽_π™±πšπ™΄π™°π™Ί 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 π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄ indicates the maximum possible working time for a person, while 𝙼𝙸𝙽_π™±πšπ™΄π™°π™Ί specifies the minimum length of the break that follows a working time period.

See also

common keyword: πšœπš•πš’πšπš’πš—πš_πšπš’πš–πšŽ_πš πš’πš—πšπš˜πš Β (temporal constraint).

used in graph description: πš›πšŠπš—πšπšŽ_πšŒπšπš›.

Keywords

constraint type: scheduling constraint, timetabling constraint, temporal constraint.

Arc input(s)

πšƒπ™°πš‚π™Ίπš‚

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŠπšœπš”πšœ)

Arc arity
Arc constraint(s)
β€’ πšπšŠπšœπš”πšœ.πšŽπš—πšβ‰₯πšπšŠπšœπš”πšœ.πš˜πš›πš’πšπš’πš—
β€’ πšπšŠπšœπš”πšœ.πšŽπš—πš-πšπšŠπšœπš”πšœ.πš˜πš›πš’πšπš’πš—β‰€π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄
Graph property(ies)
𝐍𝐀𝐑𝐂=|πšƒπ™°πš‚π™Ίπš‚|

Arc input(s)

πšƒπ™°πš‚π™Ίπš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŠπšœπš”πšœ1,πšπšŠπšœπš”πšœ2)

Arc arity
Arc constraint(s)
β‹β‹€πšπšŠπšœπš”πšœ2.πš˜πš›πš’πšπš’πš—β‰₯πšπšŠπšœπš”πšœ1.πšŽπš—πš,πšπšŠπšœπš”πšœ2.πš˜πš›πš’πšπš’πš—-πšπšŠπšœπš”πšœ1.πšŽπš—πšβ‰€π™Όπ™Έπ™½_π™±πšπ™΄π™°π™Ί,β‹€πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—β‰₯πšπšŠπšœπš”πšœ2.πšŽπš—πš,πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—-πšπšŠπšœπš”πšœ2.πšŽπš—πšβ‰€π™Όπ™Έπ™½_π™±πšπ™΄π™°π™Ί,πšπšŠπšœπš”πšœ2.πš˜πš›πš’πšπš’πš—<πšπšŠπšœπš”πšœ1.πšŽπš—πšβˆ§πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—<πšπšŠπšœπš”πšœ2.πšŽπš—πš
Sets
π–’π–’β†¦πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ-πšŒπš˜πš•πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšŸπšŠπš›-πšƒπ™°πš‚π™Ίπš‚.πš˜πš›πš’πšπš’πš—),πš’πšπšŽπš–(πšŸπšŠπš›-πšƒπ™°πš‚π™Ίπš‚.πšŽπš—πš)

Constraint(s) on sets
πš›πšŠπš—πšπšŽ_πšŒπšπš›(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,≀,π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄)
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 π™Όπ™°πš‡_πšπ™°π™½π™Άπ™΄ 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.289.2 respectively show the initial and final graph associated with the second graph constraint of the Example slot. Since we use the set generator 𝖒𝖒 we show the two connected components of the final graph. They respectively correspond to the two shifts that are displayed in FigureΒ 5.289.1.

Figure 5.289.2. Initial and final graph of the πšœπš‘πš’πšπš constraint
ctrs/shiftActrs/shiftB
(a) (b)
Signature

Consider the first graph constraint. Since we use the 𝑆𝐸𝐿𝐹 arc generator on the πšƒπ™°πš‚π™Ίπš‚ collection the maximum number of arcs of the final graph is equal to |πšƒπ™°πš‚π™Ίπš‚|. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂=|πšƒπ™°πš‚π™Ίπš‚| to 𝐍𝐀𝐑𝐂β‰₯|πšƒπ™°πš‚π™Ίπš‚| and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.