IP-based Local Searchによるナーススケジューリング問題の近似解法(アルゴリズム理論)

概要

論文の詳細を見る
ナーススケジューリング問題は,勤務表上で日々の業務に必要な要員確保に関する条件(縦の条件)と,各スタッフの勤務や休みの回数や労働時間,勤務の並びなどの労務上の条件(横の条件)を考慮しつつ各スタッフに日別のシフトを割り当てる問題である.本論文では,勤務表中のある数日分の区間(割付窓)に対するシフトの更新を,勤務表全体に対して反復して行うことで,一定レベルの解を短時間で得るアルゴリズムを提案する.割付窓の更新は,縦の条件を制約式,横の条件を目的関数に対応させた整数計画問題(IP:Integer Programming)を解くことで行うが,この操作は局所探索における近傍操作に対応することから,本論文ではこのアルゴリズムをIP-based Local Searchと名づけた.典型的な病院の勤務表(3交代,25名,1か月)を例題としたベンチマーク問題でシミュレーションを行った結果,横方向の条件にはやや違反が残ったものの,縦の条件を完全に満足した勤務表を数十秒程度で得ることができた.このアルゴリズムは,シフトに関する先見的知識に依存しないため,2交代,3交代のみならずより細分化されたシフト体系の勤務表に対しても適用が可能である.
2006-10-01