background

The AI Strategy Office, to which I belong, holds an in-house "AI Trouble Consultation Meeting" to find solutions by combining existing tools and libraries to meet the needs of "Can't you do this?" We also do business.

For example, there is a service called LIFULL HOME'S Living Counter. This is a service that allows you to consult with a dedicated housing search advisor for free regarding house building and housing search.

Is it possible to automate and optimize the mechanism for forming a shift of this housing search advisor? Today, I would like to introduce one of the ways to use Google OR tools that I found there.

example

You have decided to make a shift of 5 home hunting advisors.
Since it is convenient for illustration, I will name it Ichihana, Nino, Sanku, Yotsuba, and May.
To simplify the problem, consider only one store shift.
There are 3 slots per day x 7 days that can be reserved.
Suppose that there is only one counseling room and two people cannot serve customers (receive reservations) at the same time.
Since the consultation work is hard, the advisor can only shift one slot per day.
It is desirable that there is as little time bias as possible among the five people.
It is desirable to make shifts to meet the advisor's desire to work as much as possible.

Solve as a constraint satisfaction problem

Such scheduling problems can sometimes be solved as constraint satisfaction problems (CSPs).

There are some conditions that must be met, but they are big

Conditions that should meet the constraint
Conditions you want to optimize

If you can think of it separately, you can solve it using the solver.

All you have to do is ask the solver to calculate a solution that satisfies the constraints, and then specify the conditions you want to optimize. here,

Two people cannot be in the same shift at the same time
Advisors can only shift one slot per day
Try to avoid time bias as much as possible

As a constraint condition,

Fulfill as many advisors as possible

Let's optimize the value.

Declare the model

First, prepare a model of the solver. Here, we use the CP-SAT model. See https://developers.google.com/optimization/cp/cp_solver for details.

from ortools.sat.python import cp_model

model = cp_model.CpModel()

Prepare variables

Next, prepare a variable to use for the scheduling flag.

For example, if you make a shift of s frame for d days for n advisors, you can make the following shift table.

In order to output the above table as a calculation result, if it is decomposed as follows to make a "three-dimensional array" of n, d, s,

If 1 is included in the element, go to work
If 0 is entered, do not go to work

Can be regarded as.

In other words, the question of where to set the flag in the "three-dimensional array" of n, d, s was reduced.

Let's define a constant according to this example.

    num_advisers = 5
    num_shifts = 3
    days = ["Day", "Month", "fire", "water", "wood", "Money", "soil"]
    num_days = len(days)
    adviser_name = ["May", "Ichihana", "Nino", "Sanku", "Yotsuba"]
    all_advisers = range(num_advisers)
    all_shifts = range(num_shifts)
    all_days = range(num_days)

The variable for setting the 0 or 1 flag and having the solver solve it is created as an instance of the 'ortools.sat.python.cp_model.IntVar' class, so it looks like a pseudo multidimensional array using dict. I will prepare something that can be used.

    shifts = {}
    for n in all_advisers:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

Put constraints

Constraints are entered with model.Add ().

** Two people cannot be in the same shift at the same time: ** Make sure that only one flag is set when the "3D array" diagram is viewed from "top".

    for d in all_days:
        for s in all_shifts:
            model.Add(sum(shifts[(n, d, s)] for n in all_advisers) == 1)

** Advisors can only shift one slot per day: ** Make sure that only one flag is set when the "3D array" diagram is viewed from the "front".

    for n in all_advisers:
        for d in all_days:
            model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 1)

** Avoid time bias as much as possible: ** Since there is a 3 × 7 = 21 frame, with the 21 // 5 = 4 frame as the lower limit, It seems that there will be no bias if the (21 // 5) + 1 = 5 frame is set as the upper limit for each advisor. In the "3D Array" diagram, add all the flags in the plane table for each advisor so that the result is greater than or equal to the lower bound and less than or equal to the upper bound.

    min_shifts_per_adviser = (num_shifts * num_days) // num_advisers
    max_shifts_per_adviser = min_shifts_per_adviser + 1
    for n in all_advisers:
        num_shifts_worked = sum(
            shifts[(n, d, s)] for d in all_days for s in all_shifts)
        model.Add(min_shifts_per_adviser <= num_shifts_worked)
        model.Add(num_shifts_worked <= max_shifts_per_adviser)

Accept time zone requests

Next, quantify the desire to "enter this shift of the day!" This can be a plain 0 or 1 value, so prepare it as a multidimensional array obediently.

If 1 is included in the element, you want to go to work
If the element contains 0, you do not want to go to work

Then, the shift wishes for 5 people can be quantified as the following 3D array.

    shift_requests = [
            [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
            [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],   #Ichihana
            [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
            [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
            [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]
            ]

Here, when shifts contains a value, if the calculation of shift_requests [n] [d] [s] * shifts [(n, d, s)] is performed for each element, The calculation result will be 1 only when "the element meets the advisor's wishes". By passing this to a function called model.Maximize, you can instruct the solver on the optimization conditions.

    model.Maximize(
        sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_advisers
            for d in all_days for s in all_shifts))

https://developers.google.com/optimization/scheduling/employee_scheduling

Whole program

from ortools.sat.python import cp_model


def main():
    # This program tries to find an optimal assignment of advisers to shifts
    # (3 shifts per day, for 7 days), subject to some constraints (see below).
    # Each adviser can request to be assigned to specific shifts.
    # The optimal assignment maximizes the number of fulfilled shift requests.
    num_advisers = 5
    num_shifts = 3
    days = ["Day", "Month", "fire", "water", "wood", "Money", "soil"]
    num_days = len(days)
    adviser_name = ["May", "Ichihana", "Nino", "Sanku", "Yotsuba"]
    all_advisers = range(num_advisers)
    all_shifts = range(num_shifts)
    all_days = range(num_days)
    shift_requests = [
            [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
            [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],
            [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
            [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
            [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]
            ]
    # Creates the model.
    model = cp_model.CpModel()

    # Creates shift variables.
    # shifts[(n, d, s)]: adviser 'n' works shift 's' on day 'd'.
    shifts = {}
    for n in all_advisers:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

    # Each shift is assigned to exactly one adviser in .
    for d in all_days:
        for s in all_shifts:
            model.Add(sum(shifts[(n, d, s)] for n in all_advisers) == 1)

    # Each adviser works at most one shift per day.
    for n in all_advisers:
        for d in all_days:
            model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 1)

    # min_shifts_assigned is the largest integer such that every adviser can be
    # assigned at least that number of shifts.
    min_shifts_per_adviser = (num_shifts * num_days) // num_advisers
    max_shifts_per_adviser = min_shifts_per_adviser + 1
    for n in all_advisers:
        num_shifts_worked = sum(
            shifts[(n, d, s)] for d in all_days for s in all_shifts)
        model.Add(min_shifts_per_adviser <= num_shifts_worked)
        model.Add(num_shifts_worked <= max_shifts_per_adviser)

    model.Maximize(
        sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_advisers
            for d in all_days for s in all_shifts))
    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    solver.Solve(model)
    for d in all_days:
        print(days[d] + "Day of the week:")
        for s in all_shifts:
            for n in all_advisers:
                if solver.Value(shifts[(n, d, s)]) == 1:
                    if shift_requests[n][d][s] == 1:
                        print('Adviser', adviser_name[n], 'works shift', s, '(requested).')
                    else:
                        print('Adviser', adviser_name[n], 'works shift', s, '(not requested).')
        print()

    # Statistics.
    print()
    print('Statistics')
    print('  - Number of shift requests met = %i' % solver.ObjectiveValue(), '(out of', num_advisers * min_shifts_per_adviser, ')')
    print('  - wall time       : %f s' % solver.WallTime())


if __name__ == '__main__':
    main()

Output result:

Sunday:
Adviser Yotsuba works shift 0(not requested).
Adviser Nino works shift 1(requested).
Adviser Sanku works shift 2(requested).

Monday:
Adviser Ichihana works shift 0(not requested).
Adviser Nino works shift 1(requested).
Adviser Yotsuba works shift 2(requested).

Tuesday:
Adviser Sanku works shift 0(requested).
Adviser Ichihana works shift 1(requested).
Adviser Yotsuba works shift 2(not requested).

Wednesday:
Adviser Nino works shift 0(requested).
Adviser Ichihana works shift 1(requested).
Adviser May works shift 2(not requested).

Thursday:
Adviser Yotsuba works shift 0(requested).
Adviser Sanku works shift 1(not requested).
Adviser May works shift 2(requested).

Friday:
Adviser Sanku works shift 0(requested).
Adviser May works shift 1(requested).
Adviser Ichihana works shift 2(not requested).

Saturday:
Adviser Nino works shift 0(not requested).
Adviser Yotsuba works shift 1(not requested).
Adviser May works shift 2(requested).


Statistics
  - Number of shift requests met = 13 (out of 20 )
  - wall time       : 0.007237 s

We were able to output the solution that most satisfied the advisor's shift wishes.

Enjoy!

[PYTHON] Fill in 5 equal shifts