[PYTHON] Combinatorial optimization-typical problem-work scheduling problem

Typical problem and execution method

Work scheduling problem

Given the number of staff, the number of days scheduled, the number of shift types, the patterns of shifts to avoid, and the required number of shifts per day, find a schedule that meets these requirements. There are many variations of objective functions and constraints.

Execution method

usage

Signature: shift_scheduling(ndy, nst, shift, proh, need)
Docstring:
Work scheduling problem
input
    ndy:Days
    nst:Number of staff
    shift:shift(One character)List of
    proh:Prohibition pattern(Shift string)List of
    need:List of required number of people for each shift(Each day)
output
A table of shift numbers by day and staff

python

from ortoolpy import shift_scheduling
ndy, nst = 8, 4
shift = 'Holiday night'
proh = ['Night after night', 'Night sun', 'Akira']
need = {'Day':[2] * 8, 'Night':[1] * 8}
r = shift_scheduling(ndy, nst, shift, proh, need)
print(r)

import numpy as np, pandas as pd
a = pd.DataFrame(np.vectorize(lambda i: shift[i])(r),
    columns=[chr(65+i) for i in range(nst)],
    index=['%Day d'%i for i in range(1,ndy+1)])
for sft,lst in need.items():
    a['%s required'%sft] = lst
    a['%s plan'%sft] = (a.iloc[:,:4]==sft).sum(1)
print(a)

result

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

A B C D day required day plan night required night plan
Day 1 Holiday Night Day 2 2 1 1
Day 2 Day Night Holiday 2 2 1 1
Day 3 Day Holiday Night 2 2 1 1
Day 4 Night Day Closed 2 2 1 1
Day 5 Holiday Night Day 2 2 1 1
Day 6 Day Night Holiday 2 2 1 1
Day 7 Day Closed Night 2 2 1 1
Day 8 Night Day Closed 2 2 1 1

python

# pandas.DataFrame
from ortoolpy.optimization import ShiftScheduling
ShiftScheduling(8, 4, 'Holiday night', ['Night after night','Night sun','Akira'], {'Day':[2]*8, 'Night':[1]*8})