This article

I tried to solve the optimization problem called the nurse scheduling problem with a genetic algorithm, and it was a record because it was fairly accurate.
I'm using a library called deap in python

Premise

Nurse scheduling problem

There is a Nurse Scheduling Problem

This is a problem of determining the work schedule of nurses working in medical facilities such as hospitals, and is a typical example of the shift scheduling problem. Due to complicated shift work such as day shift, evening shift, night shift, and consideration of various restrictions, it is a difficult task that requires manual labor to actually obtain a schedule ...

In short, it automatically schedules shift work optimally.
There are various restrictions, from basic things that meet the required number of people, fairness, essential qualifications / roles, these two people (because they are not close?) Can not be put together, etc. It feels like a problem, and it is difficult to make a perfect answer, so it seems to be a field that seeks an approximate solution.

Genetic algorithm

There seem to be various ways to solve the above problem, but [Genetic Algorithm](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84 % E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0) seems to be a relatively major method.
The genetic algorithm generally optimizes by the following methods.
Create a lot of "individuals" that contain data (usually one-dimensional sequences or tuples like genes)
The data of the individual created at the beginning is random
Progressing generations while changing individuals by combining two individuals (crossing), mutating randomly (mutation), etc.
Individual scores are based on how well the individual's data meet the predefined constraints.
Adjust so that individuals with better scores will survive generations
After a certain generation, the individual with the highest score as a whole is obtained as an approximate solution.
It is a method that can be used for general combination optimization to find discrete solutions even in optimization.
For details, it is easy to understand that it is here.
In particular, the "One Max problem" with the constraint that the higher the score is, the simpler and easier to understand.

So how to apply

How can the above genetic algorithm be applied to solve the nurse scheduling problem? However, it is an image that the data given to the individual is used as a shift frame.
Example) For example, suppose you try to make a shift of 3 people as follows (1 is the frame to be assigned).

Day of the week	Month	Month	Month	fire	fire	fire	water	water	water	wood	wood	wood	Money	Money	Money	soil	soil	soil	Day	Day	Day
Time zone	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night
Employee 0	0	0	0	1	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	0	0
Employee 1	1	1	0	0	0	0	0	1	1	0	0	0	0	0	1	0	0	0	0	0	0
Employee 2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	1	0

Here, the data of the individual is obtained by connecting zeros from employee 0 to employee 2 into one array.
In other words, in the above case, it has the following one-dimensional array data.

[0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,
 1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0]

We will properly build scoring logic to calculate how much this individual meets various constraints, and advance the generation according to the rules of the genetic algorithm.
Then, a better individual will remain (= a more optimal combination will be obtained).

Implemented in Python / deap

Let's proceed with the implementation concretely.

Use of deap

Implementation used python, which is strong in machine learning
A rich library of genetic algorithms called deap
Install with pip normally (details omitted)

pip install deap

How to use is easy to understand the example of OneMax problem of here

Sample specifications

The specifications of this sample are as follows.

Employees and shift wishes

The number of employees is 10, and the following shift requests are made.

Day of the week	Month	Month	Month	fire	fire	fire	water	water	water	wood	wood	wood	Money	Money	Money	soil	soil	soil	Day	Day	Day
Time zone	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night
Required number of people	2	3	3	2	3	3	2	3	3	1	2	2	2	3	3	2	4	4	2	4	4
Employee 0	○			○			○			○			○			○			○
Employee 1	○	○	○				○	○	○				○	○	○
Employee 2																○	○	○	○	○	○
Employee 3	○	○	○	○	○	○	○	○	○	○	○	○	○	○	○	○	○	○	○	○	○
Employee 4			○			○			○			○			○			○			○
Employee 5	○	○	○	○	○	○	○	○	○	○	○	○	○	○	○
Employee 6													○	○	○	○	○	○	○	○	○
Employee 7		○			○			○			○			○			○			○
Employee 8			○			○			○			○			○			○			○
Employee 9										○	○	○	○	○	○	○	○	○	○	○	○

The required number of employees is the number of employees required for this piece.

Constraint

Make sure your score goes up enough to meet the following constraints. The numbers in parentheses are weights and represent the priority of the constraint.

The required number of employees and the number of assigned employees must match (10)
Do not assign to frames that the employee does not want (100)
Assign at least 1/2 of the number of frames desired by each employee (1)
The intention is to include as much as possible because he requested it.
Be sure to assign one administrator (100)
Administrators are employees 3, 5, 9
The same employee should be assigned up to 2 frames per day (10)

Code overview

The entire program is here
I referred to the code of This One Max problem quite a bit (≒ copy).

point

I will explain only the points modified from the above OneMax problem for the nurse scheduling problem.

Employee definition

First, we define employee classes in an object-oriented way.

class Employee(object):
  def __init__(self, no, name, age, manager, wills):
    self.no = no
    self.name = name
    self.age = age
    self.manager = manager

    #will is the day of the week_Time zone. 1 is morning, 2 is noon, 3 is night.
    #Example) mon_1 is monday morning
    self.wills = wills
...

The place where the instance is created is as follows

#Only in the morning
e0 = Employee(0, "Yamada", 40, False, ['mon_1', 'tue_1', 'wed_1', 'thu_1', 'fri_1', 'sat_1', 'sun_1'])

#Mon / Wed / Fri
e1 = Employee(1, "Suzuki", 21, False, ['mon_1', 'mon_2', 'mon_3', 'wed_1', 'wed_2', 'wed_3','fri_1', 'fri_2', 'fri_3'])

#Only on weekends
e2 = Employee(2, "Sato", 18, False, ['sat_1', 'sat_2', 'sat_3', 'sun_1', 'sun_2', 'sun_3'])

#OK anywhere
e3 = Employee(3, "Tanaka", 35, True, ['mon_1', 'mon_2', 'mon_3',
                                     'tue_1', 'tue_2', 'tue_3',
                                     'wed_1', 'wed_2', 'wed_3',
                                     'thu_1', 'thu_2', 'thu_3',
                                     'fri_1', 'fri_2', 'fri_3',
                                     'sat_1', 'sat_2', 'sat_3',
                                     'sun_1', 'sun_2', 'sun_3'
                                    ])

...

employees = [e0, e1, e2, e3, e4, e5, e6, e7, e8, e9]

Definition of shift (frame)

Defines a class of shifts or a set of frames
The tuple "list" in this class is the "individual" of the genetic algorithm.

#Class representing shift
#Internally 3(Morning day and night) *The 7th*10 people=Consists of 210-dimensional tuples
class Shift(object):
  #Definition of top
  SHIFT_BOXES = [
    'mon_1', 'mon_2', 'mon_3',
    'tue_1', 'tue_2', 'tue_3',
    'wed_1', 'wed_2', 'wed_3',
    'thu_1', 'thu_2', 'thu_3',
    'fri_1', 'fri_2', 'fri_3',
    'sat_1', 'sat_2', 'sat_3',
    'sun_1', 'sun_2', 'sun_3']

  #Estimated number of people in each frame
  NEED_PEOPLE = [
    2,3,3,
    2,3,3,
    2,3,3,
    1,2,2,
    2,3,3,
    2,4,4,
    2,4,4]

  def __init__(self, list):
    if list == None:
      self.make_sample()
    else:
      self.list = list
    self.employees = []

  #Generate random data
  def make_sample(self):
    sample_list = []
    for num in range(210):
      sample_list.append(random.randint(0, 1))
    self.list = tuple(sample_list)
...

As mentioned above, at first we are making individuals with random data
The Shift class is longer, but it's just a data manipulation method that gets the frames and users that meet the conditions endlessly.

Scoring and weighting

Individual scoring is weighted using the deap function

creator.create("FitnessPeopleCount", base.Fitness, weights=(-10.0, -100.0, -1.0, -100.0, -10.0))
creator.create("Individual", list, fitness=creator.FitnessPeopleCount)

...

def evalShift(individual):
  s = Shift(individual)
  s.employees = employees

  #Difference between expected number of people and assigned number of people
  people_count_sub_sum = sum(s.abs_people_between_need_and_actual()) / 210.0
  #Number of assignments to times when you are not applying
  not_applicated_count = s.not_applicated_assign() / 210.0
  #Number of employees with less than half the number of assignments
  few_work_user = len(s.few_work_user()) / 10.0
  #Number of frames with no administrator
  no_manager_box = len(s.no_manager_box()) / 21.0
  #Assigned to all morning, noon, and night
  three_box_per_day = len(s.three_box_per_day()) / 70.0
  return (not_applicated_count, people_count_sub_sum, few_work_user, no_manager_box, three_box_per_day)

toolbox.register("evaluate", evalShift)

Return (not_applicated_count, people_count_sub_sum, few_work_user, no_manager_box, three_box_per_day)` `` weights = (-10.0, -100.0, -1.0, -100.0, -10.0) (Specify in order)
By the way, it seems that the smaller the score, the better, so the weight must be negative.

Specify the number of evolutions, etc.

As shown below, let's calculate up to about 500 generations with 300 individuals.

    pop = toolbox.population(n=300)
    CXPB, MUTPB, NGEN = 0.6, 0.5, 500 #Crossing probability, mutation probability, evolutionary computation loop count

Run

When executed, the learning process will be output as shown below.

$ python nurse_scheduling_by_ga.py 
Evolution started
Evaluate 300 individuals
--0 generation--
Evaluate 245 individuals
*Parameter 1
  Min 0.242857142857
  Max 0.242857142857
  Avg 0.242857142857
  Std 2.2660056242e-08
*Parameter 2
  Min 0.247619047619
  Max 0.247619047619
  Avg 0.247619047619
  Std 9.49766396283e-09
*Parameter 3
  Min 0.0
  Max 0.0
  Avg 0.0
  Std 0.0
*Parameter 4
  Min 0.142857142857
  Max 0.142857142857
  Avg 0.142857142857
  Std 1.66600046866e-08
*Parameter 5
  Min 0.114285714286
  Max 0.114285714286
  Avg 0.114285714286
  Std 1.19267483008e-08
--1 generation--
Evaluate 235 individuals
*Parameter 1
  Min 0.238095238095
  Max 0.238095238095
  Avg 0.238095238095
  Std 2.45699769971e-08
*Parameter 2
  Min 0.228571428571
  Max 0.228571428571
  Avg 0.228571428571
  Std 2.38534966016e-08
*Parameter 3
  Min 0.1
  Max 0.1
  Avg 0.1
  Std 1.31048702444e-08
*Parameter 4
  Min 0.047619047619
  Max 0.047619047619
  Avg 0.047619047619
  Std 4.46646616171e-09
*Parameter 5
  Min 0.1
  Max 0.1
  Avg 0.1
  Std 1.31048702444e-08

(snip)

--499 generations--
Evaluate 219 individuals
*Parameter 1
  Min 0.0333333333333
  Max 0.0333333333333
  Avg 0.0333333333333
  Std 2.98168707519e-09
*Parameter 2
  Min 0.0714285714286
  Max 0.0714285714286
  Avg 0.0714285714286
  Std 8.33000234328e-09
*Parameter 3
  Min 0.1
  Max 0.1
  Avg 0.1
  Std 1.31048702444e-08
*Parameter 4
  Min 0.0952380952381
  Max 0.0952380952381
  Avg 0.0952380952381
  Std 8.93293232343e-09
*Parameter 5
  Min 0.0428571428571
  Max 0.0428571428571
  Avg 0.0428571428571
  Std 4.56253018749e-09
--End of evolution--
The best individual: [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1], (0.0, 0.0, 0.2, 0.047619047619047616, 0.1)
0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0
0,1,0,0,0,0,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1
1,0,1,0,1,1,0,0,1,0,1,0,1,0,1,0,1,1,0,0,1
0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0
1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1
0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,1
0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	1	0	0
0	1	0	0	0	0	1	1	0	0	0	0	1	1	1	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
1	0	1	0	1	1	0	0	1	0	1	0	1	0	1	0	1	1
0	0	0	0	0	1	0	0	1	0	0	1	0	0	1	0	0	0
1	1	1	1	1	1	1	1	1	0	0	1	0	1	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	1
0	1	0	0	1	0	0	1	0	0	1	0	0	0	0	0	1	0
0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	1	1

It is a cut-out specification that the result is output as standard in array format, CSV format, TSV format.
Process it appropriately and paste it on Excel for use.
By the way, the execution time was less than 2 minutes

result

So, I tried somehow and the result was as follows
(The data is different from the result of the above implementation, but don't worry)

Day of the week	Month	Month	Month	fire	fire	fire	water	water	water	wood	wood	wood	Money	Money	Money	soil	soil	soil	Day	Day	Day	Number of assignments	Desired number	Assignment rate
Time zone	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night	Morning	Noon	Night
Required number of people	2	3	3	2	3	3	2	3	3	1	2	2	2	3	3	2	4	4	2	4	4
Approved number	2	3	3	2	3	3	2	3	3	1	2	2	2	3	3	2	4	4	2	4	4
Difference	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Employee 0	1	0	0	1	0	0	1	0	0	0	0	0	0	0	0	1	0	0	1	0	0	5	7	71.4%
Employee 1	0	1	1	0	0	0	0	1	1	0	0	0	0	1	1	0	0	0	0	0	0	6	9	66.7%
Employee 2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	1	1	4	6	66.7%
[tube]Employee 3	0	1	0	0	1	0	0	1	0	1	1	0	1	0	0	0	0	0	0	1	0	7	21	33.3%
Employee 4	0	0	1	0	0	1	0	0	1	0	0	0	0	0	0	0	0	1	0	0	1	5	7	71.4%
[tube]Employee 5	1	0	1	1	1	1	1	0	0	0	0	1	0	0	1	0	0	0	0	0	0	8	15	53.3%
Employee 6	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	1	1	1	0	0	0	5	9	55.6%
Employee 7	0	1	0	0	1	0	0	1	0	0	1	0	0	0	0	0	1	0	0	1	0	6	7	85.7%
Employee 8	0	0	0	0	0	1	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	4	7	57.1%
[tube]Employee 9	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	0	1	1	1	1	1	7	12	58.3%

Number of administrators	1	1	1	1	2	1	1	1	0	1	1	2	1	1	1	0	1	1	1	2	1

Bold is where the conditions were not met
It's mostly working for the fairly complicated conditions

At the end

If you can do it so far, it seems that you can make a shift immediately by making fine adjustments manually.
However, I thought that less than 2 minutes would take too much time.
I tried to speed up some things by distributing it with scoop, but it ended up becoming a CPU bottleneck and it didn't get much faster.
It may be faster if you use GPU like Deep Learning
It appeared in Paper level, but no implementation was found. .. It's hard to make your own using cuda. ..
By the way, as for me, my sister is a nurse, and she seems to be staring at the schedule for about a week to make shifts, so I thought it would be quite useful if I seriously created constraints.

[PYTHON] Solving the nurse scheduling problem (shift optimization) with a genetic algorithm