In depth interpretation of Google or tools' complex scheduling program

stay google or-tools There is a complicated staff scheduling procedure in the official example of (shift_scheduling_sat.py), Because the official did not give the requirements of the problem and the explanation of the code , Therefore, readers may have difficulties in understanding the source code , Today, let's try to interpret this complex scheduling procedure (shift_scheduling_sat.py), Because I am jupyter notebook Run the source code in , In order to better understand the meaning of the source code ,  I adjusted the order of some code snippets in the source code . Readers who first come into contact with the scheduling program can first understand or-tools An official one Simple version of staff scheduling procedure (https://developers.google.com/optimization/scheduling/employee_scheduling)

Basic scheduling requirements

1.   Yes 8 Employees
2.   To row 3 Zhou's class
3.   The daily shift is : [ Rest shift 、 morning shift 、 middle shift 、 The night shift ]

explain ： Employees can only go to 4 One of the shifts , If the employee is on a rest shift, it means that the employee is off the day . Next, we define these basic variables in the code ： Number of employees 、 Shift scheduling weeks 、 shift 、 Total scheduling days 、 Number of shifts .

from ortools.sat.python import cp_model
model = cp_model.CpModel()

#8 Employees 
num_employees = 8

# row 3 Zhou's class 
num_weeks = 3

# The daily shift is divided into :  rest 、 morning shift 、 middle shift 、 evening shift 
shifts = ['O', 'M', 'A', 'N']

# Total scheduling days 
num_days = num_weeks * 7

# Number of shifts 
num_shifts = len(shifts)

Define shift scheduling variables

After defining the basic variables , Next, we need to define a shift scheduling variable to store the shift scheduling results , The shift scheduling variable is the core component of this program , Many of the constraints we will add later must constrain the shift scheduling variable . The shift scheduling variable is a three-dimensional Boolean array work[e, s, d], Its three dimensions are [ staff 、 shift 、 God ], and work The value of the element in can only be 0 or 1, When this work The value of an element in is 1 Tense means that an employee is on a certain day Yes A certain shift , by 0 It means that an employee is on a certain day No on A certain shift . We also need to define 2 Target variable groups and 2 The coefficient array corresponding to the target variables , It is used to store constraint variables and their coefficients of integer and Boolean forms , this 4 Target groups will be used later when making minimization goals . Our three-dimensional scheduling variables work It looks like this ：

# Define shift scheduling variables 
work = {}
for e in range(num_employees):
    for s in range(num_shifts):
        for d in range(num_days):
            work[e, s, d] = model.NewBoolVar('work%i_%i_%i' % (e, s, d))

#  Define linear target variable group and coefficient array , These target variable groups and coefficient arrays are used when minimizing the target 
obj_int_vars = []
obj_int_coeffs = []
obj_bool_vars = []
obj_bool_coeffs = []

 

constraint condition

Here we summarize the constraints in the source code , All in all 7 A constraint , These constraints can be divided into hard constraints and soft constraints , The so-called hard constraint refers to the constraint that must be satisfied and cannot be violated , Soft constraint refers to the constraint that should be satisfied as much as possible but can be violated , When you violate the soft constraint, you will be punished .  Next, we will explain the meaning of these constraints and their implementation methods one by one .

1.   Each employee can only work one shift every day ( hard ).
2. Fix the shift of some employees : Fix some employees to do a certain shift on a certain day ( hard ).
3. Employee needs Request: Some employees want to do a certain shift one day ( soft ).
4. Constraints of continuous days of shift ： The number of consecutive days an employee has worked on a shift ( soft ).
5. The total number of days per week for different shifts is constrained ( soft ).
6. Constraints of interconnection between different shifts ( soft ).
7. Constraints on the number of shifts per day per week ( soft ).

constraint 1: Each employee can only work one shift every day ( hard )

Previously, we defined 4 The shifts are ： Rest shift 、 morning shift 、 middle shift 、 The night shift . Here we stipulate that every employee can only go to 1 A shift , It's a hard constraint , All employees must meet . This constraint is easy to implement ： We just need to make the total number of all shifts of each employee every day equal to 1 That's all right. .

#  Each employee can only do one shift every day 
for e in range(num_employees):
    for d in range(num_days):
        model.Add(sum(work[e, s, d] for s in range(num_shifts)) == 1)

constraint 2: Fix the shift of some employees : Fix certain employees to do certain shifts on certain days ( hard ).

The meaning of this constraint is ： Due to work needs, some employees must be fixed to do certain shifts on certain days . This constraint needs to provide a fixed shift table to specify which employees do which shifts on which days . The format of this fixed shift table is ：( staff , shift , God ). Such as (0, 0, 0) Express The first employee rests on the first day .( because python The array subscript of is from 0 Start , therefore 0 Represents the first index position of the array ). This constraint is also very simple to implement , We just need to force the element value of the corresponding position of the fixed shift table in the shift scheduling variable to 1 That's all right. .

#  Fix the shift of some employees : ( staff ,  shift ,  God ).
fixed_assignments = [
        (0, 0, 0),
        (1, 0, 0),
        (2, 1, 0),
        (3, 1, 0),
        (4, 2, 0),
        (5, 2, 0),
        (6, 2, 3),
        (7, 3, 0),
        (0, 1, 1),
        (1, 1, 1),
        (2, 2, 1),
        (3, 2, 1),
        (4, 2, 1),
        (5, 0, 1),
        (6, 0, 1),
        (7, 3, 1),
    ]


#  Implement fixed shift constraints 
for e, s, d in fixed_assignments:
    model.Add(work[e, s, d] == 1)

constraint 3: Employee needs Request: Some employees want to do ( Do not do ) A certain shift ( soft ).

It's a soft constraint , It means to be satisfied as much as possible , Can be violated in case of dissatisfaction , But violation requires a price ( punishment ). The format of this soft constraint is :( staff , shift , God , The weight ), In power, it is important to negative It means that the employee hope Take this flight , When the weight is Comes at a time It means that the employee Don't want to Take this flight . Such as ：(3, 0, 5, -2) Express 3 Employee No. 1 wants to rest on the first Saturday . and (2, 3, 4, 4) said 2 Employee No. 1 doesn't want to work on the night shift on the first Friday .

#  Employee needs Request: ( staff ,  shift ,  God ,  The weight )
# A negative weight means that an employee wants a shift on a certain day , A positive weight means that an employee doesn't want a shift on a certain day 
requests = [
    # 3 Employee No. 1 wants to rest on the first Saturday .
    (3, 0, 5, -2),
    # 5 Employee No. wants to work on the night shift the next Thursday .
    (5, 3, 10, -2),
    # 2 Employee No. 1 doesn't want to be on the night shift on the first Friday .
    (2, 3, 4, 4)
]

#  Constraint implementation : Add employee needs to the target variables 
for e, s, d, w in requests:
    obj_bool_vars.append(work[e, s, d])
    obj_bool_coeffs.append(w)

Here we need to explain how to implement this constraint , After setting all the constraints in the scheduling procedure , We will pass model.Minimize() To optimize all our target variables , As the name suggests, we find the optimal solution by minimizing the value of the target variable . In the specific implementation, we will minimize the product of the target variable and the weight , What we want to achieve is the minimization of this product , When employees want to work on a certain shift on a certain day , Corresponding work[e, s, d] The value could be 1 or 0, And on duty is 1 When multiplied by a negative weight, their product is negative . And on duty is 0 When multiplied by a negative weight, their product is 0, So when minimized (model.Minimize), Negative product will be satisfied preferentially , This is to meet the employees as much as possible hope The desire to go on a certain shift , Similarly, when the weight of power is positive, employees can also be satisfied as much as possible Don't want to The desire to go on a certain shift .

constraint 4: Constraints of continuous days of shift ： The number of consecutive days an employee has worked on a shift ( soft ).

This is also a soft constraint , It is also the most complicated and difficult constraint in this program . The format of this constraint is ：( shift , Minimum days ( hard ), Minimum days ( soft ), Minimum penalty value , Maximum days ( soft ), Maximum days ( hard ), Maximum penalty value ), Such as (0, 1, 1, 0, 2, 2, 0) Indicates the constraints of the rest shift ： Every employee can rest 1 Days or two consecutive days , This is a hard constraint that cannot be violated , and (3, 1, 2, 20, 3, 4, 5) It means the constraints of night shift ： Every employee should be on the night shift continuously 2 Days or 3 God , Just go up 1 Days or continuous 4 Heaven will be punished . However, the source code does not specify the punishment mechanism when the constraint is violated , Here we need to explain the punishment mechanism ：

There are both hard and soft constraints , You will not be punished if you meet the soft constraint , When the hard constraint is satisfied but the soft constraint is not satisfied, it will be punished , It usually falls on [1,2) perhaps (3,4] The values of these two semi closed intervals will be punished . And as long as the number of consecutive days of the shift is equal to the boundary value of the hard constraint (1 or 4) Metropolis Be punished . As long as the continuous number of days of the shift is equal to the boundary value of the soft constraint (2 or 4) all Can't Be punished . Next, let's look at the pattern of continuous working days in these two semi closed intervals ：

Yes [1,2) Mode of continuous working days in the interval

There is only one integer value falling in this interval 1, That is to say, employees are n There are only 1 You will be punished during the first night shift , If n=7 when , stay 7 There are only 1 There are several situations of night shift ：

In other words, here 7 In the case of only one night shift in the day , Then this night shift can take place in 7 Any day of the day , So there will be 7 Patterns .

Yes (3,4] Mode of continuous working days in the interval

There is only one integer value falling in this interval 4, That is to say, employees are n It's been going on for days 4 You will be punished during the first night shift , If n=7 when , stay 7 It's been going on for days 4 There are several situations of night shift ：

In other words, here 4 Consecutive night shifts can occur in 7 In heaven d0,d1,d2,d3 God , So there will be 4 Patterns . Now let's see how to use code to realize the constraint of continuous days ：

#  Constraint of consecutive days  :
# (shift, hard_min, soft_min, min_penalty,soft_max, hard_max, max_penalty)
shift_constraints = [
    # Can rest continuously 1 Days or two , Will not be punished .
    (0, 1, 1, 0, 2, 2, 0),
    # The night shift goes on continuously 2 Days or 3 God ,  Just go up 1 Days or continuous 4 Heaven will be punished .
    (3, 1, 2, 20, 3, 4, 5),
]

# Generate a fixed pattern sequence of consecutive working days 
def negated_bounded_span(works, start, length):
    sequence = []
    #  Process the left boundary of the sequence  
    if start > 0:
        sequence.append(works[start - 1])
    for i in range(length):
        sequence.append(works[start + i].Not())
    #  Process the right boundary of the sequence 
    if start + length < len(works):
        sequence.append(works[start + length])
    return sequence


def add_soft_sequence_constraint(model, works, hard_min, soft_min, min_cost,
                                 soft_max, hard_max, max_cost, prefix):
    cost_literals = []
    cost_coefficients = []

    #  It is forbidden to be less than hard_min Day class 
    for length in range(1, hard_min):
        #for start in range(len(works) - length - 1) # Existing in the source code bug
        for start in range(len(works) - length + 1):
            model.AddBoolOr(negated_bounded_span(works, start, length))

    #  Punishment for continuous working days falling in the range [hard_min,soft_min) Situation in 
    if min_cost > 0:
        for length in range(hard_min, soft_min):
            #for start in range(len(works) - length - 1) # Existing in the source code bug
            for start in range(len(works) - length + 1): 
                span = negated_bounded_span(works, start, length)
                name = ': under_span(start=%i, length=%i)' % (start, length)
                lit = model.NewBoolVar(prefix + name)
                span.append(lit)
                model.AddBoolOr(span)
                cost_literals.append(lit)
                # We filter exactly the sequence with a short length.
                # The penalty is proportional to the delta with soft_min.
                cost_coefficients.append(min_cost * (soft_min - length))

    #  Punishment for continuous working days falling in the range (soft_max ,soft_min] Situation in .
    if max_cost > 0:
        for length in range(soft_max + 1, hard_max + 1):
            #for start in range(len(works) - length - 1) # Existing in the source code bug
            for start in range(len(works) - length + 1): 
                span = negated_bounded_span(works, start, length)
                name = ': over_span(start=%i, length=%i)' % (start, length)
                lit = model.NewBoolVar(prefix + name)
                span.append(lit)
                model.AddBoolOr(span)
                cost_literals.append(lit)
                # Cost paid is max_cost * excess length.
                cost_coefficients.append(max_cost * (length - soft_max))

    #  Prohibit continuous >hard_max Day class 
    for start in range(len(works) - hard_max - 1):
        model.AddBoolOr([works[i].Not() for i in range(start, start + hard_max + 1)])
    return cost_literals, cost_coefficients


#  Shift constraints 
for ct in shift_constraints:
    shift, hard_min, soft_min, min_cost, soft_max, hard_max, max_cost = ct
    for e in range(num_employees):
        works = [work[e, shift, d] for d in range(num_days)]
        variables, coeffs = add_soft_sequence_constraint(
            model, works, hard_min, soft_min, min_cost, soft_max, hard_max,
            max_cost,
            'shift_constraint(employee %i, shift %i)' % (e, shift))
        obj_bool_vars.extend(variables)
        obj_bool_coeffs.extend(coeffs)

Here we will use two custom functions ：negated_bounded_span and add_soft_sequence_constraint , among negated_bounded_span The function of is to generate a fixed pattern of a continuous shift , It accepts 3 Parameters ：works, start, length. among works yes work A line of ,start Indicates the starting position of the fixed mode ,length Indicates the number of consecutive working days .negated_bounded_span The return result of is :  stay works In sequence , With start Is the continuity of the starting position length A fixed pattern of days . Such as ： hypothesis works Is the length of the 4,length by 2 be ：

When start by 0 When to return to [ v0.Not(), v1.Not(), v2 ]
When start by 1 Will return [ v0,  v1.Not(),  v2.Not(), v3 ]
When start by 2 When to return to  [ v1,  v2.Not(),  v3.Not() ]

Different start Position will get One Different continuity length The fixed pattern of days , As for why to use Not(), We will explain later AddBoolOr() Methods will be explained .add_soft_sequence_constraint Function acceptance 9 Parameters , It contains the boundary values of hard constraints and soft constraints ,add_soft_sequence_constraint The function of is to limit the number of consecutive working days to the boundary value range of the hard constraint, and punish the cases outside the boundary range of the soft constraint , Finally, the number of days outside the hard constraint boundary is forbidden to be continuous ( Less than hard_min And greater than hard_max), such as ： Assume that the total number of working days is 7 At this time of day, if hard_min=2,soft_min=3,soft_max=4,hard_max=5, Then the number of consecutive days of a shift is 2 God ,3 God ,4 God ,5 God The number of days that cannot be continued is 1 God ,6 God ,7 God . As shown in the figure below ：

How to judge consecutive days

There are three cases to deal with continuous working days :1. Prohibit continuous n Day shift ,2. It can be continuously n Day shift , 3. Prohibit continuous n Classes of more than days , We need to discuss these three situations separately .

1. Prohibit continuous n Day shift

When the number of consecutive working days is less than the minimum boundary value of the hard constraint (hard_min) It needs to be forbidden , If When hard_min=2, Just forbid a certain shift to work only 1 God , When hard_min=3 when , You need to prohibit a certain shift from going on 1 Days and continuity 2 God . As we said before, if there is a total of 7 Day shift , A certain shift will only work for one day 7 Kind of ( happen 7 Any day of the day ), Therefore, we should prohibit this 7 The occurrence of , We will use the following 7 strip AddBoolOr Statement to prohibit this 7 The occurrence of ：

AddBoolOr([ v0.Not(), v1 ]）
AddBoolOr([ v0, v1.Not(), v2 ]）
AddBoolOr([ v1, v2.Not(), v3 ]）
AddBoolOr([ v2, v3.Not(), v4]）
AddBoolOr([ v3, v4.Not(), v5 ]）
AddBoolOr([ v4, v5.Not(), v6 ]）
AddBoolOr([ v5, v6.Not() ]）

because AddBoolOr The result is Ture, And its parameters (list The elements in ) Must do or operation , To ensure that the result is True, Will exclude some combination , As the first above AddBoolOr Statement will exclude [1 , 0] This combination , Second AddBoolOr Statement will exclude [ 0, 1, 0 ], Because these combinations will make AddBoolOr As the result of the False, But this is not allowed to happen . The following is to prohibit a continuous shift 2 Day shift AddBoolOr sentence ：

AddBoolOr([ v0.Not(), v1.Not(), v2 ]）
AddBoolOr([ v0, v1.Not(), v2.Not(), v3 ]）
AddBoolOr([ v1, v2.Not(), v3.Not(), v4 ]）
AddBoolOr([ v2, v3.Not(), v4.Not(), v5 ]）
AddBoolOr([ v3, v4.Not(), v5.Not(), v6 ]）
AddBoolOr([ v4, v5.Not(), v6.Not() ]）

If you want to know more AddBoolOr Principle , Please refer to my other blog :  Linear programming Google OR-Tools Introduction and actual combat Examples in .

2. It can be continuously n Day shift

If the number of consecutive working days occurs in the range of hard constraints , Will not be banned , Then we can achieve continuous n The restriction of day shift only needs to be on the original prohibition n Day shift AddBoolOr Add a new... To the parameter sequence of the statement bool Variable bits , Because the addition of a new one breaks the original prohibition . If you can work for two consecutive days AddBoolOr by ：

AddBoolOr([ v0.Not(), v1.Not(), v2, v_new ]）
AddBoolOr([ v0, v1.Not(), v2.Not(), v3, v_new  ]）
AddBoolOr([ v1, v2.Not(), v3.Not(), v4, v_new  ]）
AddBoolOr([ v2, v3.Not(), v4.Not(), v5, v_new  ]）
AddBoolOr([ v3, v4.Not(), v5.Not(), v6, v_new  ]）
AddBoolOr([ v4, v5.Not(), v6.Not(), v_new  ]）

3. Prohibit continuous n Classes of more than days

When the number of consecutive working days is greater than the maximum boundary value of the hard constraint (hard_max) It needs to be forbidden . Because it is greater than hard_max The number of days may be many , Each is greater than hard_max Of days AddBoolOr There will be many sentences , If you traverse all greater than hard_max Days of , Will generate many AddBoolOr The sentence of , This seems to be a very inefficient approach , The right thing to do is , We just need to prohibit continuous hard_max+1 Days of work can be achieved “ Prohibit continuous n Classes of more than days ”. If you need a total of 7 Day shift ,hard_max=5 when , We need to prohibit continuous 6 Days and 7 Day class , At this time, we only need to continue to prohibit 6 Day shift AddBoolOr The statement can be modified slightly to meet the prohibition 6 Days and 7 God's demand ：

AddBoolOr([ v0.Not(), v1.Not() , v2.Not(), v3.Not(), v4.Not(), v5.Not() ]）
AddBoolOr([ v0, v1.Not() , v2.Not(), v3.Not(), v4.Not(), v5.Not(), v6.Not() ]）

Please pay attention “ Prohibit continuous n Day shift ” And “ Prohibit continuous n Classes of more than days ” their AddBoolOr The difference between the statement and the last element in the parameter list , The last of the latter is all Not().

Punishment mechanism

Continuous working days outside the soft constraint interval and within the hard constraint interval will be punished , The so-called penalty is to use the minimum penalty value (min_cost) Or the maximum penalty value (max_cost) Multiply by the difference between the continuous working days and the soft constraint boundary value , Doing so will result in a larger product of the number of consecutive working days that are farther away from the boundary value of the soft constraint , The closer to the soft constraint boundary value, the smaller the product of continuous working days , Finally, we are making optimization goals (model.Minimize) when , The continuous working days can be very close to the boundary value of the soft constraint , So as to achieve a reasonable optimization goal .

In the source code Bug

Observe carefully or-tools Official website source code  add_soft_sequence_constraint Function seems to have a pair start Index position judgment bug:

 

So let's assume that len(works)=4,length=1, that start Index position of ( first Not Position of appearance ) Can only be (0,1,2,3), So it should be range(4-1+1) = range(len(works) - length + 1) :

Length =1
[ v0.Not(), v1 ]
[ v0, v1.Not(), v2]
[ v1, v2.Not(), v3 ]
[ v2, v3.Not() ]

And when length=2 yes start Index position of ( first Not Position of appearance ) Can only be (0,1,2), So it should be range(4-2+1) = range(len(works) - length + 1):

Length = 2
[ v0.Not(), v1.Not(), v2 ]
[ v0, v1.Not(), v2.Not(), v3 ]
[ v1,v2.Not(), v3.Not() ]

  constraint 5: The total number of days per week for different shifts is constrained ( soft )

The requirement of this constraint is to stipulate the weekly rest days and night shift days of each employee , For rest days, each employee should try to rest every week 2 God , Below or above 2 Heaven will be punished , For the night shift, every employee should at least 1 Day and night shift , You can only go up 4 Day and night shift , For not working the night shift , Or more than 4 Those who work day and night will be punished . also , The total days of weekly rest or night shift must be within the range of hard constraints .

#  The shift is constrained by the number of days per week :
#( shift , Minimum days ( hard ),  Minimum days ( soft ),  Minimum penalty value , Maximum days ( soft ),  Maximum days ( hard ),  Maximum penalty value )
weekly_sum_constraints = [
    #  Constraints on the number of days off per week .
    (0, 1, 2, 7, 2, 3, 4),
    #  least 1 Night shift , most 4 Night shift , Not up or over 4 Night shift will be punished .
    (3, 0, 1, 3, 4, 4, 0),
]


def add_soft_sum_constraint(model, works, hard_min, soft_min, min_cost,
                            soft_max, hard_max, max_cost, prefix):
    cost_variables = []
    cost_coefficients = []
    sum_var = model.NewIntVar(hard_min, hard_max, '')
    #  Calculate the actual working days .
    model.Add(sum_var == sum(works))

    #  The total number of days of punishment is less than soft_min Total number of days .
    if soft_min > hard_min and min_cost > 0:
        delta = model.NewIntVar(-len(works), len(works), '')
        model.Add(delta == soft_min - sum_var)
        # TODO(user): Compare efficiency with only excess >= soft_min - sum_var.
        excess = model.NewIntVar(0, 7, prefix + ': under_sum')
        model.AddMaxEquality(excess, [delta, 0])
        cost_variables.append(excess)
        cost_coefficients.append(min_cost)

    #  The total number of days of punishment exceeds soft_max Total number of days .
    if soft_max < hard_max and max_cost > 0:
        delta = model.NewIntVar(-7, 7, '')
        model.Add(delta == sum_var - soft_max)
        excess = model.NewIntVar(0, 7, prefix + ': over_sum')
        model.AddMaxEquality(excess, [delta, 0])
        cost_variables.append(excess)
        cost_coefficients.append(max_cost)

    return cost_variables, cost_coefficients

#  Constraints on the total number of days off and night shifts per week 
for ct in weekly_sum_constraints:
    shift, hard_min, soft_min, min_cost, soft_max, hard_max, max_cost = ct
    for e in range(num_employees):
        for w in range(num_weeks):
            works = [work[e, shift, d + w * 7] for d in range(7)]
            variables, coeffs = add_soft_sum_constraint(
                model, works, hard_min, soft_min, min_cost, soft_max,
                hard_max, max_cost,
                'weekly_sum_constraint(employee %i, shift %i, week %i)' %
                (e, shift, w))
            obj_int_vars.extend(variables)
            obj_int_coeffs.extend(coeffs)

We use a user-defined function to constrain the total number of days off and night shifts per week add_soft_sum_constraint, The function is to 1. Calculate the actual working days ,2. The total number of days of punishment is less than soft_min Total number of days ,3. The number of days of punishment for technical cooperation exceeds soft_max Total number of days . Now we will explain these three functions one by one ：

Calculate the actual working days

Here, the total number of days on rest shift and night shift must be within the range of hard constraints , That is, it should be greater than hard_min, Less than or equal to hard_max. Here we want to explain ,or-tools Don't suggest Use it directly “>= constant 1” and “<= constant 2” This expression , Instead, it is suggested to first define an integer variable within a certain interval in this case (NewIntVar()), And then use “==” To replace “>=” and “<=”, As we can see in the code, before calculating the actual working days, define an in (hard_min,hard_max) Integer variable of interval sum_var To express Actual working days , And then used model.Add(sum_var == sum(works))  Statement to calculate the actual rest days and night shift days , This avoids the use of “>=” and “<=”.

The total number of days of punishment is less than soft_min Total number of days

When the total number of days of rest and night shift is less than the minimum soft constraint boundary value (soft_min) when , Would be right soft_min And sum_var The difference between them is punished , That is to say, leave soft_min The farther away sum_var( Less than soft_min The direction of ), The greater the punishment , Here we use AddMaxEquality Method to identify less than soft_min The direction of soft_min And sum_var The difference between , Then punish ,  The punishment mechanism is similar to that of the previous consecutive days of the shift , No more explanation here .

The total number of days of punishment exceeds soft_max Total number of days .

When the total number of days of rest and night shift is greater than the maximum soft constraint boundary value (soft_max) when , Would be right sum_var And soft_min The difference between them is punished , That is to say, leave soft_max The farther away sum_var( Greater than soft_max The direction of ), The greater the punishment , Here we use AddMaxEquality Method to identify greater than soft_max The direction of sum_var On soft_ma The difference between , Then punish , The punishment mechanism is similar to that of the previous consecutive days of the shift , No more explanation here .

constraint 6: Constraints of interconnection between different shifts ( soft ).

Here we have made provisions for the interconnection between different shifts ： The middle shift and night shift will be punished , That is to say, if the middle shift of the previous day , The night shift the next day will be punished , It's a soft constraint ; Night shift and even morning shift are forbidden , That is, if the night shift the previous day , Then it is forbidden to work in the morning the next day , It's a hard constraint , The format of this constraint is ：( The previous shift , The next shift , Penalty value (0 signify Forbidden )), Now let's look at the code :

#  Constraints on the interconnection of different shifts :
# ( The previous shift ,  The next shift ,  Penalty value  (0  signify   Forbidden ))
penalized_transitions = [
    #  The middle shift is connected with the evening shift , The penalty value is 4.
    (2, 3, 4),
    #  The night shift is connected with the morning shift , Forbidden .
    (3, 1, 0),
]


#  Punish and prohibit illegal shift connections 
for previous_shift, next_shift, cost in penalized_transitions:
    for e in range(num_employees):
        for d in range(num_days - 1):
            transition = [
                work[e, previous_shift, d].Not(), work[e, next_shift,
                                                       d + 1].Not()
            ]
            if cost == 0:
                model.AddBoolOr(transition)
            else:
                trans_var = model.NewBoolVar(
                    'transition (employee=%i, day=%i)' % (e, d))
                transition.append(trans_var)
                model.AddBoolOr(transition)
                obj_bool_vars.append(trans_var)
                obj_bool_coeffs.append(cost)

Prohibit the realization of night shift and morning shift

This constraint is relatively easy to implement , We just need to find out the shift variables of each employee work The first one is the night shift and the second one is the morning shift , If it exists, it will appear [1,1] This combination , And then we use AddBoolOr() Reverse them , In this way, we can avoid [1,1] This group , Thus, the situation of banning night shift and even morning shift can be realized .

The realization of the punishment of the middle shift and the night shift

This constraint is relatively easy to implement , We just need to find out the shift variables of each employee work The first one is the middle shift and the second one is the night shift , If it exists, it will appear [1,1] This combination , Because this combination is not forbidden , Is allowed to exist , Because only AddBoolOr() To reverse them would be to prohibit this combination , This is not what we want , So what we have to do is , Add a new one to this combination while negating bool Variable , In this way, we can break the constraint that is forbidden after negation , This is similar to the previous constraint 4 Medium It can be continuously n Day shift The operation of .

 

constraint 7: Constraints on the number of shifts per day per week ( soft ).

The requirement of this constraint is the morning shift every day of the week 、 middle shift 、 The total number of three night shifts must not be less than the specified number , Punishment will be given for the excess quantity , Now let's look at the code ：

#  The number of shifts per day per week is limited : Every day of the week ( From Monday ) The minimum number of each shift （ morning shift , middle shift , evening shift ）.
weekly_cover_demands = [
    (2, 3, 1),  #  Monday ：2 Morning shift ,3 A middle class ,1 An evening shift 
    (2, 3, 1),  #  Tuesday ：2 Morning shift ,3 A middle class ,1 An evening shift 
    (2, 2, 2),  #  Wednesday ：2 Morning shift ,2 A middle class ,2 An evening shift 
    (2, 3, 1),  #  Thursday ：2 Morning shift ,3 A middle class ,1 An evening shift 
    (2, 2, 2),  #  Friday ：2 Morning shift ,2 A middle class ,2 An evening shift 
    (1, 2, 3),  #  Saturday ：1 Morning shift ,2 A middle class ,2 An evening shift 
    (1, 3, 1),  #  Sunday ：1 Morning shift ,3 A middle class ,1 An evening shift 
]


#  The punishment exceeds   The number of shifts per week per day 
excess_cover_penalties = (2, 2, 5)

# Cover constraints
for s in range(1, num_shifts):
    for w in range(num_weeks):
        for d in range(7):
            works = [work[e, s, w * 7 + d] for e in range(num_employees)]
            # Ignore Off shift.
            min_demand = weekly_cover_demands[d][s - 1]
            worked = model.NewIntVar(min_demand, num_employees, '')
            model.Add(worked == sum(works))
            over_penalty = excess_cover_penalties[s - 1]
            if over_penalty > 0:
                name = 'excess_demand(shift=%i, week=%i, day=%i)' % (s, w,
                                                                     d)
                excess = model.NewIntVar(0, num_employees - min_demand,
                                         name)
                model.Add(excess == worked - min_demand)
                obj_int_vars.append(excess)
                obj_int_coeffs.append(over_penalty)

Here we are on a weekly basis ( Monday to Sunday ) Every morning shift 、 middle shift 、 The total number of night shifts is stipulated :

A specified quantity <= Actual morning shift , middle shift , Total number of night shifts <= The total number of

It's a hard constraint , It limits the total number of actual shifts to a certain range , This is achieved through the following code ：

worked = model.NewIntVar(min_demand, num_employees, '')
model.Add(worked == sum(works))

Next, the actual number of shifts exceeding the specified number will be punished , The purpose of punishment is to make the actual number of shifts as close as possible to the specified number . The realization and restriction of punishment 5 The method in is similar to , I won't repeat it here .

Minimize the goal

After setting all constraint codes , We can set optimization goals , Here we are using model.Minimize(), We want to multiply all the target variables by all the coefficients , Finally, minimize the product , The purpose of minimization is to make the value of each constraint as close as possible to the boundary of the soft constraint . Now let's look at the code ：

#  Minimize the goal 
model.Minimize(
    sum(obj_bool_vars[i] * obj_bool_coeffs[i]
        for i in range(len(obj_bool_vars))) +
    sum(obj_int_vars[i] * obj_int_coeffs[i]
        for i in range(len(obj_int_vars))))

solver = cp_model.CpSolver()

# Set the program execution time 
solver.parameters.max_time_in_seconds = 10

solution_printer = cp_model.ObjectiveSolutionPrinter()
status = solver.SolveWithSolutionCallback(model, solution_printer)



#  Promise the scheduling results 
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print()
    header = '          '
    for w in range(num_weeks):
        header += 'M T W T F S S '
    print(header)
    for e in range(num_employees):
        schedule = ''
        for d in range(num_days):
            for s in range(num_shifts):
                if solver.BooleanValue(work[e, s, d]):
                    schedule += shifts[s] + ' '
        print('worker %i: %s' % (e, schedule))
    print()
    print('Penalties:')
    for i, var in enumerate(obj_bool_vars):
        if solver.BooleanValue(var):
            penalty = obj_bool_coeffs[i]
            if penalty > 0:
                print('  %s violated, penalty=%i' % (var.Name(), penalty))
            else:
                print('  %s fulfilled, gain=%i' % (var.Name(), -penalty))

    for i, var in enumerate(obj_int_vars):
        if solver.Value(var) > 0:
            print('  %s violated by %i, linear penalty=%i' %
                  (var.Name(), solver.Value(var), obj_int_coeffs[i]))

    print()
    print('Statistics')
    print('  - status          : %s' % solver.StatusName(status))
    print('  - conflicts       : %i' % solver.NumConflicts())
    print('  - branches        : %i' % solver.NumBranches())
    print('  - wall time       : %f s' % solver.WallTime())

Here we set a very important parameter max_time_in_seconds , The function of this parameter is to limit the execution time of the program , Here we set it to 10 second , We let the program only execute 10 second , If it comes to 10 Seconds later, the program did not find the optimal solution (OPTIMAL), Then exit and output the feasible solution (FEASIBLE). The reason for this is that , Optimization problems in real life , The scale and business complexity are often high , For example, in the scheduling problem, if the number of employees increases to dozens or even hundreds , The number of shifts will be increased to dozens , Add dozens of constraints , Then the algorithm may not find the optimal solution in a short time , At this time, it is also a good choice for us to limit the program execution time and output feasible solutions .

summary

Today we learned how to use cp_model Arrange shifts for employees , And the methods of implementation in various constraints , Especially the judgment method of continuous days and AddBoolOr()、AddMaxEquality() I have learned how to use , At the same time, we also seem to have found bug. And it is modified . I hope this blog can help you learn or-tools Help .

Reference material

Linear programming Google OR-Tools Introduction and actual combat

or-tools Official website

Official website scheduling algorithm source code (shift_scheduling_sat.py)