遺伝的アルゴリズムによる夜勤スケジューリング
夜勤のスケジュール(特に看護師)を作成するのに遺伝的アルゴリズムを使用し、ExcelVBAでシステム製作した。多少計算時間はかかるが、入力データの準備や途中経過の表示など動作確認が容易なシステムとなる。
途中経過が見えるとアルゴリズム改善が容易であり、実用的なシステムも短時間に開発可能となる。
(遺伝的アルゴリズムについては、静岡理工科大学のホームページhttps://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/GA/GA.htm#4.1で分かりやすく説明されているので、参照ください)
夜勤スケジュール2
夜勤スケジュール2では、このような条件を満たすスケジュールを作成する。
1日を日勤、準夜勤、夜勤の3こまに分ける。
項1. それぞれのこまで、必要人数 出勤すること (管理者は1名出勤)
項2. 出勤不可は出勤させないこと(上表の×が出勤不可)。
項3. 3こま連続勤務させないこと。
項4. 目標夜勤数に近づけること。
自動スケジューリング結果は下記となる。
1が出勤を意味する。色が塗られている部分は出勤不可のところである。この結果はすべての条件を満たしている。
遺伝的アルゴリズムでは実行するごとに同じ答えが出る訳ではなく、条件を満たす結果に近いものが作成される。
夜勤スケジュール1で紹介しているように、目標とするスケジュールに近いものを自動作成したのち、各条件に対し〇×判定をするシステムを使い最終調整するのがいいと思う。
遺伝的アルゴリズムでは1つのスケジュール案を1つの生き物(個体)と考える。この例では21こま×10名で210の遺伝子を持つ個体をランダムに400準備する。
完全にランダムなものではなく、縦方向の条件(各こまの出勤人数、出勤不可)を満たすランダムな個体を準備する。
初期値シートに400個体4000行のデータが作成される。
このデータに対し個体の評価(条件を満たさない度合い)、淘汰(優秀なものを中心に残し、個体数を200にする)、交叉(2つの個体から2つの子供を作る)、突然変異(染色体をランダムに変える)の操作を繰り返す。自然に優秀な個体(スケジュール)ができあがる。本例では30世代程度(一回の操作を1世代とよぶ)で完了する。
環境シートに最終的な200個体の集団が作成される。
条件を満たさない点があるごとに減点される。減点の少ない順のリストとなっており、一番上の個体が答えとなる。
緑色部は突然変異が発生した染色体である。
集団の一番下を見ると、減点の多い成績の悪い個体となっている。(201番目より淘汰される)
本システムでの個体の評価、淘汰、交叉、突然変異について説明していく。
個体の評価
スケジューリングの条件を満たさない場合に減点する。減点は看護師、管理者ごとに実施し、個体の減点合計を求め評価に使用する。
項1と項2は守るように個体を作り、かつ交叉、突然変異でもこれを守るので減点は無い。
項3 3こま連続勤務がある場合、1点減点する。
項4 目標夜勤数との差がある場合、差の数×0.5点減点する。
実行例
環境シート
A列に看護師、管理者ごとの減点を表示、B列に個体ごとの減点計を表示している。
環境シートの上部の選択行ポイント計算ボタンを押すと、その行の減点内容が表示される。
淘汰
減点の少ない上位50個体については無条件で選択(生き残る)させる。(エリート選択)
それ以降の個体については、ルーレット選択により150個体が選択される。
ルーレット選択では減点からポイントを算出(1000×0.9の減点乗)し、ポイントが大きい個体が選択される確率を高くし、選択する。
選択されなかった個体は消去される。
交叉
生き残った個体をランダムに分類し、上から2組ずつペアにする。
各ペアから子供を2個体つくる。
親と子供の例
子1は親1の遺伝子を受け継ぐが、色塗り部は親2の遺伝子を受け継ぐ。
子2は親2の遺伝子を受け継ぐが、色塗り部は親1の遺伝子を受け継ぐ。
色塗り部の列の位置、幅はランダムに変える。
この処理ではスケジューリングの条件 項1、項2が壊れることは無い。
突然変異
突然変異前
突然変異後
突然変異確率50%で上のように変化する。(色塗り部)
ランダムに選んだ1列について、スケジューリングの条件 項1、項2を満たすランダムな値に変更する。
生まれたばかりの子供に対しては実施していない。(優秀な子供かもしれないので)
また、減点0の個体に対しても実施していない。
以上で新しい集団ができあがった。個体の評価、淘汰により、選別する。
この作業を繰り返すうちに、優秀な個体(スケジュール)が完成する。
夜勤スケジュール3
夜勤スケジュール3では、このような条件を満たすスケジュールを作成する。
項1 すべての日で日勤2名、夜勤2名とする。
項2 各人の日勤と夜勤のバランスをできるだけ同じにする。
項3 土日の連休を1回以上
項4 連続勤務を4日以下
項5 連続勤務を4日したら、次に休み2日
項6 夜勤の翌日の日勤は不可
項7 夜勤は3連続まで
項8 4連休を避ける
項9 前後の日が休みの間の出勤をできるだけ避ける(困難)
自動スケジューリング結果は下記となる。
「前後の日が休みの間の出勤をできるだけ避ける」以外は条件を満たした。
基本的な処理方法は夜勤スケジュール2と同じ。工夫が必要な点のみ説明する。
個体の評価
スケジューリングの条件を満たさない場合に減点する。減点は看護師ごとに実施し、個体の減点合計を求め評価に使用する。
項1は守るように個体を作り、かつ交叉、突然変異でもこれを守るので減点は無い。
項2 日勤と夜勤の差3日以上のとき減点2、日勤と夜勤の差2日のとき減点1とする。
単純な〇×ではなく、日勤と夜勤のバランスがくずれるほど減点を大きくすることで、収束しやすいと考える。
項3 週末連休無しの場合、減点2とする。
この条件はかなり厳しい。これを実現するための条件を加える。
遺伝的アルゴリズムでは単純に条件のみを評価するのではなく、収束しやするなる条件を加えるべきである。
収束しやするするため、公平性を確保するため、週末連休2回の場合も減点2とする。
また、週末1日のみを休みとすると(もったいない)、週末連休が困難になるため、週末1日のみを休みの場合減点1とする。
項4 連続勤務を6日以上では減点2、連続勤務5日では減点1とする。
項5 連続勤務4日の場合、次に休み2日無ければ減点1とする。
項6 夜勤の翌日の日勤2回以上では減点2、夜勤の翌日の日勤1回で減点1とする。
項7 夜勤5連続以上で減点2、夜勤4連続で減点1とする。
項8 5連休以上で減点2、4連休で減点1とする。
項9 前後の日が休みの間の出勤があるごとに減点0.5加算する。
突然変異
条件が厳しいため突然変異の率を高める。
突然変異を1列だけでなく、最大の場合4列について発生させる。
土日に特別の条件が加えられているため、土日に突然変異が発生する確率を3倍とする。
他の処理は夜勤のスケジュール2と同じである。
すこしの違いで全く別のスケジュールが完成できるのが遺伝的アルゴリズムの魅力である。
Excelを使うことで入力条件の設定、結果の表示、計算式による手作業での調整が容易となる。
ExcelからPythonにデータを渡し、計算させ、結果をExcelが受け取る。
この方法をとることで、Excelの操作性を保ち、計算速度を10倍に早めることができる。
このようなスケジューリングシステムの製作を承っております。
問い合わせは ikanacom@nifty.com まで連絡お願いいたします。