"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).
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 |
"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