シフトを自動で組むプログラムをPythonで書いた

Python シフトスケジューリング

アルバイトのシフトを組むのって大変らしいですね。

調べてみると「ナーススケジューリング問題はNP困難」などと出てきます。

ただ、頭のなかで考えていた問題は労働者ごとの職能に差がないものだったので、ナーススケジューリング問題よりは簡単かもしれない。……どうせ人間が目視で確認するし、何パターンか出力すれば良くね？ 表にする部分の作業をやるだけでも楽になるのでは？と思い、最適化とか考えずに可能なシフトをいくつか出力してみました。

問題設定

入力

  • 労働者の希望勤務枠が与えられる。労働者が希望していない労働枠での勤務は不可。
  • 労働枠に対して必要人数が与えられる。必要人数以上の勤務は不可。不足の場合はダミー労働者を配置する。
  • 労働枠の重なりが与えられる。重なりのある労働枠を同一労働者が勤務することは不可。

出力

  • シフト案100個
  • 各シフト案に対して
    • 勤務枠ごとの勤務労働者
    • (シフト案を評価する目安として)勤務労働者内における勤務回数の標準偏差
import copy
import random
import collections
import string


def is_legal(plan, required, possible, group):
    for cell, workers in plan.items():
        if len(workers) != required[cell]:
            return False
        for worker in workers:
            if cell not in possible[worker]:
                return False
    for g in group:
        worked = []
        for cell in g:
            for worker in plan[cell]:
                if worker in worked:
                    return False
                worked.append(worker)
    return True


def evaluate(plan):
    total_work = 0
    worked = {}
    for cell, workers in plan.items():
        total_work += len(workers)
        for worker in workers:
            if 'dummy' in worker:
                pass
            elif worker in worked:
                worked[worker] += 1
            else:
                worked[worker] = 1
    total_work /= len(worked)
    score = sum(v * v for k, v in worked.items()) / len(worked)
    if score - total_work**2 < 0:
        return total_work + (total_work**2 - score)**0.5
    return (score - total_work * total_work)**0.5


def solver(required, possible, group):
    cells = [k for k, v in required.items()]
    workers = [k for k, v in possible.items()]
    timetable = {}
    for cell in cells:
        timetable[cell] = []
        for worker in workers:
            if cell in possible[worker]:
                timetable[cell].append(worker)
    generation = 0
    plan = {cell: [] for cell in cells}
    plans = list()
    for i in range(100):
        if is_legal(plan, required, possible, group):
            for cell in cells:
                plan[cell].sort()
            score = evaluate(plan)
            plans.append(
                (score, str(list(sorted(plan.items(), key=lambda t: t[0])))))
        for cell in cells:
            while len(timetable[cell]) < required[cell]:
                suffix = random.sample(string.ascii_uppercase, 4)
                dummy = 'dummy' + ''.join(suffix)
                timetable[cell].append(dummy)
                if dummy not in possible:
                    possible[dummy] = []
                possible[dummy].append(cell)
            plan[cell] = random.sample(timetable[cell], required[cell])

    return list(plans)


def generate_sampledate():
    eachday = {'A': 2, 'B': 1, 'C': 2, 'D': 1, 'E': 3, 'F': 1}
    not_same_member = [('A', 'B'), ('C', 'D'), ('E', 'F')]
    required = {}
    group = []
    for day in range(1, 31):
        d = ('0' + str(day))[-2:]
        for k, v in eachday.items():
            required[d + k] = v
        for g in not_same_member:
            group.append((d + e for e in g))

    workers = ['Amy', 'Basil', 'Clara', 'Desmond', 'Ernest', 'Fanny', 'George',
               'Hector', 'Ida', 'James', 'Kate', 'Leo', 'Maud', 'Neville',
               'Olive', 'Prue', 'Quentin', 'Rhoda', 'Susan', 'Titus', 'Una',
               'Victor', 'Winnie', 'Xerxes', 'Yorick', 'Zillah']
    possible = {}
    for w in workers:
        possible[w] = []
        for k in required:
            if random.random() > 0.78:
                possible[w].append(k)
    return required, possible, group


if __name__ == '__main__':
    plans = solver(*generate_sampledate())
    plans.sort()
    print(*plans, sep='\n')

感想