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

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