Solving nurse scheduling problems with combinatorial optimization

what is this

"Solving the nurse scheduling problem (shift optimization) with a genetic algorithm" is now [combinatorial optimization](http://qiita.com/ I tried to solve it with SaitoTsutomu / items / bfbf4c185ed7004b5721).

Read the table (shift request, etc.)

python


import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
from io import StringIO

a = pd.read_table(StringIO("""\
Day of the week\t month\t month\t month\t fire\t fire\t fire\t water\t water\t water\t-tree\t-tree\t-tree\t gold\t gold\t gold\t soil\t soil\t soil\t day\t day\t day
Time zone\t morning\t noon\t night\t morning\t noon\t night\t morning\t noon\t night\t morning\t noon\t night\t morning\t noon\t night\t morning\t noon\t night\t morning\t noon\t night
Required number of people\t2\t3\t3\t2\t3\t3\t2\t3\t3\t1\t2\t2\t2\t3\t3\t2\t4\t4\t2\t4\t4
Employee 0\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t
Employee 1\t○\t○\t○\t\t\t\t○\t○\t○\t\t\t\t○\t○\t○\t\t\t\t\t\t
Employee 2\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t○\t○\t○\t○\t○\t○
Employee 3\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○
Employee 4\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○
Employee 5\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t\t\t\t\t\t
Employee 6\t\t\t\t\t\t\t\t\t\t\t\t\t○\t○\t○\t○\t○\t○\t○\t○\t○
Employee 7\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t
Employee 8\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○
Employee 9\t\t\t\t\t\t\t\t\t\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○""")).T
a,a.columns = a.iloc[1:],a.iloc[0].tolist()
a.Required number of people= a.Required number of people.astype(int)
a.iloc[:,2:] = ~a.iloc[:,2:].isnull()
a.insert(0, 'Day of the week', a.index.str[0])
a.reset_index(drop=True, inplace=True)
a = a.iloc[:,list(range(3,a.shape[1]))+[0,1,2]]
print(a[:3]) #First 3 lines display
Employee 0 Employee 1 Employee 2 Employee 3 Employee 4 Employee 5 Employee 6 Employee 7 Employee 8 Employee 9 day of the week Time zone Required number of people
0 True True False True False True False False False False month morning 2
1 False True False True False True False True False False month noon 3
2 False True False True True True False False True False month night 3

Solve with Python

"V ..." such as V allocation is a variable.

python


N frames,N employee= a.shape[0],a.shape[1]-3
L employee= list(range(N employee))
L administrator= [3,5,9] #Manager is employee 3, 5, 9
C Required number of people difference= 10
C not desired= 100
C Minimum number of frames= 1
C shortage of administrators= 100
C 1 day 2 frames= 10
m = LpProblem() #Mathematical model
V allocation= np.array(addbinvars(N frames,N employee))
a['V Required number of people difference'] = addvars(N frames)
V Minimum number of frames= addvars(N employee)
a['V administrator shortage'] = addvars(N frames)
V 1 day 2 frames= addvars(N employee)
m += (C Required number of people difference* lpSum(a.V Required number of people difference)
    +C not desired* lpSum(a.apply(lambda r: lpDot(1-r[L employee],V allocation[r.name]), 1))
    +C Minimum number of frames* lpSum(V Minimum number of frames)
    +C shortage of administrators* lpSum(a.V administrator shortage)
    +C 1 day 2 frames* lpSum(V 1 day 2 frames)) #Objective function
for _,r in a.iterrows():
    m += r.V Required number of people difference>=  (lpSum(V allocation[r.name]) - r.Required number of people)
    m += r.V Required number of people difference>= -(lpSum(V allocation[r.name]) - r.Required number of people)
    m += lpSum(V allocation[r.name,L administrator]) + r.V administrator shortage>= 1
for j,n in enumerate((a.iloc[:,L employee].sum(0)+1)//2):
    m += lpSum(V allocation[:,j]) +V Minimum number of frames[j] >= n #More than half of hope
for _,v in a.groupby('Day of the week'):
    for j in range(N employee):
        m += lpSum(V allocation[v.index,j]) -V 1 day 2 frames[j] <= 2 #Up to 2 frames on each day
%time m.solve()
R result= np.vectorize(value)(V allocation).astype(int)
a['result'] = [''.join(i*j for i,j in zip(r,a.columns)) for r in Rresult]
print('Objective function', value(m.objective))
print(a[['Day of the week','Time zone','result']])

output


CPU times: user 7.45 ms, sys: 4.23 ms, total: 11.7 ms
Wall time: 22.8 ms
Objective function 0.0
Day of the week time zone result
0 month morning employee 1 employee 5
January noon Employee 3 Employee 5 Employee 7
February Night Employee 1 Employee 3 Employee 4
3 Tue Morning Employee 0 Employee 3
4 Tue Noon Employee 3 Employee 5 Employee 7
5 Tue Night Employee 4 Employee 5 Employee 8
6 Wed Morning Employee 0 Employee 5
7 Wed Lunch Employee 1 Employee 3 Employee 5
8 Water Night Employee 3 Employee 4 Employee 8
9 Thu Morning Employee 3
10 Thu Noon Employee 5 Employee 7
11 Thu Night Employee 8 Employee 9
12 Fri Morning Employee 1 Employee 5
13 Friday Lunch Employee 1 Employee 7 Employee 9
14 Fri Night Employee 5 Employee 6 Employee 8
15 Sat Morning Employee 0 Employee 3
16 Sat noon Employee 2 Employee 6 Employee 7 Employee 9
17 Sat Night Employee 3 Employee 4 Employee 6 Employee 9
18th morning employee 0 employee 9
19th noon Employee 2 Employee 3 Employee 6 Employee 9
20th night Employee 2 Employee 3 Employee 4 Employee 6

――The calculation time was 23 milliseconds, and the exact optimum solution was obtained. --The objective function (sum of penalties) is $ 0 $, so all the conditions are met.

that's all


reference

-Combinatorial optimization-Typical problem-Work scheduling problem

Recommended Posts

Solving nurse scheduling problems with combinatorial optimization
Solving 4-color problems with combinatorial optimization
Solving school district organization problems with combinatorial optimization
Solving game theory with combinatorial optimization
Solving the nurse scheduling problem (shift optimization) with a genetic algorithm
Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
Grouping games with combinatorial optimization
Solving Mathematical Optimization Model Exercises with Google's OR-Tools (3) Production Optimization Problems
Solving "cubes in cubes" by combinatorial optimization
Maximize restaurant sales with combinatorial optimization
Go see whales with combinatorial optimization
Pave the road with combinatorial optimization
Let's stack books flat with combinatorial optimization
Precautions when solving DP problems with Python
Solve combinatorial optimization problems with Google's OR-Tools (5) Decide on a date course
Create an academic society program with combinatorial optimization
Introduction to Python Mathematical Optimization Solving junior high school math problems with pulp
Use combinatorial optimization
○○ Solving problems in the Department of Mathematics by optimization
Solving knapsack problems with genetic algorithms and MGG models
Road installation with optimization
Grouping by combinatorial optimization
Getting Started with Optimization
Problems with installing Scrapy
Problems with webpay cooperation
How to write offline real-time Solving E05 problems with Python