アルバイトのシフトを組むのって大変らしいですね。
調べてみると「ナーススケジューリング問題は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')
感想
- Google フォーム - アンケートを作成、分析できる無料サービスなどでシフトの希望を集めれば、案外使えるかもしれない。
- フォームを作るのも自動化できるし、自動で調査して、自動でシフトを組んで、自動で人間が働く時代も近い！
- 労働者数×労働を希望する確率 < 必要労働数だと絶望的にシフトが埋まらない。予備人員が大切。
- 労働者の名前はギャシュリークラムのちびっ子たち―または遠出のあとで
から取りました。
