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})
A B C D day required Daily plan Need at night Night plan
Day 1 Closed day night day 2 2 1 1
Day 2 day night Closed day 2 2 1 1
Day 3 day Closed day night 2 2 1 1
Day 4 night day day Closed 2 2 1 1
Day 5 Closed day night day 2 2 1 1
Day 6 day night Closed day 2 2 1 1
Day 7 day Closed day night 2 2 1 1
Day 8 night day day Closed 2 2 1 1

Recommended Posts

Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Combinatorial optimization-typical problems and execution methods