blog

import numpy as np
from mip import Model, OptimizationStatus, maximize, xsum

staffs = ["佐藤", "安藤", "山田", "高橋"]
weeks = 5
days = list(range(7 * weeks))
shifts = ["日", "夜", "休"]

SHIFT_DAY = shifts.index("日")
SHIFT_NIGHT = shifts.index("夜")
SHIFT_OFF = shifts.index("休")

num_staffs = len(staffs)
num_days = len(days)
num_shifts = len(shifts)

model = Model(solver_name="cbc")
shift_table = model.add_var_tensor(
    (num_staffs, num_days, num_shifts),
    "shift_table",
    var_type="B",
)

"""
制約条件
"""

for staff in range(num_staffs):
    # 毎日何れかのシフトに就いている
    for day in range(num_days):
        model += xsum(shift_table[staff, day]) == 1

    for week in [days[i : i + 7] for i in range(0, len(days) - 7 + 1, 1)]:
        # 日勤が4日以下
        model += xsum(shift_table[staff, week, SHIFT_DAY]) <= 4
        # 夜勤が2日以下
        model += xsum(shift_table[staff, week, SHIFT_NIGHT]) <= 2
        # 休日が2日以下
        model += xsum(shift_table[staff, week, SHIFT_OFF]) <= 2

for day in range(num_days):
    # 日勤が2人
    model += xsum(shift_table[:, day, SHIFT_DAY]) == 2
    # 夜勤が1人
    model += xsum(shift_table[:, day, SHIFT_NIGHT]) == 1

# 夜勤のあとは夜勤または休日
for staff in range(num_staffs):
    for today in range(num_days):
        # シフト表作成対象の最終日の場合、その翌日は初日とする
        tomorrow = 0 if today == days[-1] else today + 1
        model += (
            shift_table[staff, today, SHIFT_NIGHT]
            + shift_table[staff, tomorrow, SHIFT_DAY]
            <= 1
        )

"""
目的関数
"""
# 休日の希望
requested_dayoffs = [
    # 佐藤さん
    [2],
    # 安藤さん
    [0, 3],
    # 山田さん
    [5],
    # 高橋さん
    [1, 6],
]

# 休日の希望が最大限叶うようにする
dayoff_satisfactions = []
for staff in range(num_staffs):
    for requested_dayoff in requested_dayoffs[staff]:
        for day in filter(lambda d: d % 7 == requested_dayoff, days):
            dayoff_satisfactions.append(shift_table[staff, day, SHIFT_OFF])

model.objective = maximize(xsum(dayoff_satisfactions))

"""
求解
"""
model.optimize()

if model.status == OptimizationStatus.OPTIMAL:
    print(
        "休日希望の満足度: {}%".format(
            100 * model.objective_value / len(dayoff_satisfactions)
        )
    )
    result_table = shift_table.astype(float, subok=False).round().astype(int)
    shift_index = [0, 1, 2]
    shift = (shift_index * result_table).sum(axis=2)
    for staff in range(num_staffs):
        print(staffs[staff], " ", end="")
        for day in range(num_days):
            if day % 7 == 0:
                print("| ", end="")
            print(shifts[shift[staff, day]], " ", end="")
        print()
else:
    print(model.status)

Welcome to the CBC MILP Solver 
Version: Trunk
Build Date: Oct 24 2021

Starting solution of the Linear programming relaxation problem using Primal Simplex

Coin0506I Presolve 698 (0) rows, 420 (0) columns and 3416 (0) elements
Clp1000I sum of infeasibilities 7.08561e-05 - average 1.01513e-07, 38 fixed columns
Coin0506I Presolve 631 (-67) rows, 344 (-76) columns and 2991 (-425) elements
Clp0029I End of values pass after 344 iterations
Clp0014I Perturbing problem by 0.001% of 1.525588 - largest nonzero change 2.9576128e-05 ( 0.0014788064%) - largest zero change 2.9522154e-05
Clp0000I Optimal - objective value 30
Clp0000I Optimal - objective value 30
Coin0511I After Postsolve, objective 30, infeasibilities - dual 0 (0), primal 0 (0)
Clp0000I Optimal - objective value 30
Clp0000I Optimal - objective value 30
Clp0000I Optimal - objective value 30
Clp0032I Optimal objective 30 - 0 iterations time 0.032, Idiot 0.03

Starting MIP optimization
休日希望の満足度: 100.0%
佐藤  | 日  夜  休  日  休  日  日  | 夜  夜  休  日  日  日  日  | 夜  夜  休  日  日  日  日  | 夜  夜  休  日  休  日  日  | 日  夜  休  日  休  日  日  
安藤  | 休  日  夜  休  日  日  夜  | 休  日  夜  休  日  日  夜  | 休  日  夜  休  日  日  夜  | 休  日  夜  休  日  日  夜  | 休  日  夜  休  日  日  夜  
山田  | 日  日  日  夜  夜  休  日  | 日  日  日  夜  休  休  日  | 日  日  日  夜  休  休  日  | 日  日  日  夜  夜  休  日  | 日  日  日  夜  夜  休  日  
高橋  | 夜  休  日  日  日  夜  休  | 日  休  日  日  夜  夜  休  | 日  休  日  日  夜  夜  休  | 日  休  日  日  日  夜  休  | 夜  休  日  日  日  夜  休