[PYTHON] Lösen von Planungsproblemen für Krankenschwestern mit Kombinationsoptimierung

Was ist das

"Lösen des Krankenschwester-Planungsproblems (Schichtoptimierung) mit einem genetischen Algorithmus" bis Kombinationsoptimierung Ich habe versucht, es mit SaitoTsutomu / items / bfbf4c185ed7004b5721) zu lösen.

Lesen Sie die Tabelle (Schichtanforderung usw.)

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("""\
Tag\t Monat\t Monat\t Monat\t Feuer\t Feuer\t Feuer\t Wasser\t Wasser\t Wasser\t Baum\t Baum\t Baum\t Gold\t Gold\t Gold\t Boden\t Boden\t Boden\t Tag\t Tag\t Tag
Zeitzone\t Morgen\t Mittag\t Nacht\t Morgen\t Mittag\t Nacht\t Morgen\t Mittag\t Nacht\t Morgen\t Mittag\t Nacht\t Morgen\t Mittag\t Nacht\t Morgen\t Mittag\t Nacht\t Morgen\t Mittag\t Nacht
Erforderliche Anzahl von Personen\t2\t3\t3\t2\t3\t3\t2\t3\t3\t1\t2\t2\t2\t3\t3\t2\t4\t4\t2\t4\t4
Mitarbeiter 0\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t
Mitarbeiter 1\t○\t○\t○\t\t\t\t○\t○\t○\t\t\t\t○\t○\t○\t\t\t\t\t\t
Mitarbeiter 2\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t○\t○\t○\t○\t○\t○
Mitarbeiter 3\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○
Mitarbeiter 4\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○
Mitarbeiter 5\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t\t\t\t\t\t
Mitarbeiter 6\t\t\t\t\t\t\t\t\t\t\t\t\t○\t○\t○\t○\t○\t○\t○\t○\t○
Mitarbeiter 7\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t
Mitarbeiter 8\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○
Mitarbeiter 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.Erforderliche Anzahl von Personen= a.Erforderliche Anzahl von Personen.astype(int)
a.iloc[:,2:] = ~a.iloc[:,2:].isnull()
a.insert(0, 'Tag', 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]) #Die ersten 3 Zeilen werden angezeigt

Löse mit Python

"V ..." wie die V-Zuordnung ist eine Variable.

python

N Rahmen,N Mitarbeiter= a.shape[0],a.shape[1]-3
L Mitarbeiter= list(range(N Mitarbeiter))
L Administrator= [3,5,9] #Manager ist Mitarbeiter 3, 5, 9
C Erforderliche Anzahl von Personen Unterschied= 10
C nicht erwünscht= 100
C Mindestanzahl von Frames= 1
C Mangel an Administratoren= 100
C 1 Tag 2 Frames= 10
m = LpProblem() #Mathematisches Modell
V-Zuordnung= np.array(addbinvars(N Rahmen,N Mitarbeiter))
a['V Erforderliche Anzahl von Personen Unterschied'] = addvars(N Rahmen)
V Mindestanzahl von Frames= addvars(N Mitarbeiter)
a['V Administratormangel'] = addvars(N Rahmen)
V 1 Tag 2 Frames= addvars(N Mitarbeiter)
m += (C Erforderliche Anzahl von Personen Unterschied* lpSum(a.V Erforderliche Anzahl von Personen Unterschied)
    +C nicht erwünscht* lpSum(a.apply(lambda r: lpDot(1-r[L Mitarbeiter],V-Zuordnung[r.name]), 1))
    +C Mindestanzahl von Frames* lpSum(V Mindestanzahl von Frames)
    +C Mangel an Administratoren* lpSum(a.V Administratormangel)
    +C 1 Tag 2 Frames* lpSum(V 1 Tag 2 Frames)) #Zielfunktion
for _,r in a.iterrows():
    m += r.V Erforderliche Anzahl von Personen Unterschied>=  (lpSum(V-Zuordnung[r.name]) - r.Erforderliche Anzahl von Personen)
    m += r.V Erforderliche Anzahl von Personen Unterschied>= -(lpSum(V-Zuordnung[r.name]) - r.Erforderliche Anzahl von Personen)
    m += lpSum(V-Zuordnung[r.name,L Administrator]) + r.V Administratormangel>= 1
for j,n in enumerate((a.iloc[:,L Mitarbeiter].sum(0)+1)//2):
    m += lpSum(V-Zuordnung[:,j]) +V Mindestanzahl von Frames[j] >= n #Mehr als die Hälfte der Hoffnung
for _,v in a.groupby('Tag'):
    for j in range(N Mitarbeiter):
        m += lpSum(V-Zuordnung[v.index,j]) -V 1 Tag 2 Frames[j] <= 2 #Bis zu 2 Frames pro Tag
%time m.solve()
R Ergebnis= np.vectorize(value)(V-Zuordnung).astype(int)
a['Ergebnis'] = [''.join(i*j for i,j in zip(r,a.columns)) for r in RErgebnis]
print('Zielfunktion', value(m.objective))
print(a[['Tag','Zeitzone','Ergebnis']])

Ausgabe

CPU times: user 7.45 ms, sys: 4.23 ms, total: 11.7 ms
Wall time: 22.8 ms
Zielfunktion 0.0
Ergebnis der Tageszeitzone
0 Monat Morgen Mitarbeiter 1 Mitarbeiter 5
Januar Mittag Mitarbeiter 3 Mitarbeiter 5 Mitarbeiter 7
Februar Nacht Mitarbeiter 1 Mitarbeiter 3 Mitarbeiter 4
3 Di Morgen Mitarbeiter 0 Mitarbeiter 3
4 Di Mittag Mitarbeiter 3 Mitarbeiter 5 Mitarbeiter 7
5 Di Nacht Mitarbeiter 4 Mitarbeiter 5 Mitarbeiter 8
6 Mi Morgen Mitarbeiter 0 Mitarbeiter 5
7 Mi Mittagessen Mitarbeiter 1 Mitarbeiter 3 Mitarbeiter 5
8 Mittwoch Nacht Mitarbeiter 3 Mitarbeiter 4 Mitarbeiter 8
9 Do Morgen Mitarbeiter 3
10 Do Mittag Mitarbeiter 5 Mitarbeiter 7
11 Do Nacht Mitarbeiter 8 Mitarbeiter 9
12 Fr Morgen Mitarbeiter 1 Mitarbeiter 5
13 Fr Mittagessen Mitarbeiter 1 Mitarbeiter 7 Mitarbeiter 9
14 Fr Nacht Mitarbeiter 5 Mitarbeiter 6 Mitarbeiter 8
15 Sa Morgen Mitarbeiter 0 Mitarbeiter 3
16 Sa Mittag Mitarbeiter 2 Mitarbeiter 6 Mitarbeiter 7 Mitarbeiter 9
17 Sat Night Mitarbeiter 3 Mitarbeiter 4 Mitarbeiter 6 Mitarbeiter 9
18. Morgen Mitarbeiter 0 Mitarbeiter 9
19. Mittag Mitarbeiter 2 Mitarbeiter 3 Mitarbeiter 6 Mitarbeiter 9
20. Nacht Mitarbeiter 2 Mitarbeiter 3 Mitarbeiter 4 Mitarbeiter 6

――Die Berechnungszeit betrug 23 Millisekunden, und es wurde die exakt optimale Lösung erhalten.

• Die Zielfunktion (Summe der Strafen) ist $ 0 $, sodass alle Bedingungen erfüllt sind.

das ist alles

Referenz

• Kombinationsoptimierung - Typisches Problem - Arbeitsplanungsproblem