数独でスケジュールナースの使い方を概観する


スケジュールナースが、どんな風に使えるか概観を数独問題を作りながら見ていきます。
世界で一番難しい数独を世界で一番簡単な数独にしてみましょう。

1.数独ルールの制約化
1.1 プロジェクトファイルを開く
プロジェクトサンプルフォルダに9x9数独ファイルが入っています。ファイルをダブルクリックしてファイルを開きます。

1.2 ルールの概観
1.2.1 横方向の数設定
数独は9x9の升目になっています。横方向(行方向)の升目を”日”に割り当てしますので、9日必要になります。スケジュール開始日とスケジュール終了日まで9日間になるようにしてあります。


1.2.2 縦方向(列方向)の数設定
縦方向はスタッフです。スタッフは9人分定義が必要で、次のように定義しています。

 
1.2.3 数独の数字の割り当て
シフトを次のように定義しています。名前の欄が、スケジュールナースの内部で用いる変数名になっています。ラベルがそれに対応する表示名になっています。



1.2.4 行と列の定義

行方向は、各スタッフについての日々になります。通常は、勤務パターンを定義します。
列方向は、その日についての要件が定義されることになります。

1.2.5 行Day制約の記述

1.2.2でスタッフを定義しましたが、行制約->Day制約で呼び出される定義になっています。今回の場合、スタッフ毎にシフトの特性を変える必要はないので、
全スタッフは、以下のDay制約にリンク(毎日制約1として)しています。Day制約というのは、その人の起こりえるシフトを網羅したものです。シフト9種類は全て起こりえるという、定義になります。



1.2.6 行パターン制約の記述
横方向(行方向)の制約です。こちらも、1.2.2で、各スタッフがパターン制約1という名前で、リンクしています。
各シフトは、1回以上という記述です。これで十分な記述ですが、最大、最小を各1に設定してもOKです。



1.2.7 列方向制約

上と同じですが、縦方向の制約になっています。全日(毎日) Aシフトは、最小1個以上という記述です。これも、最大最小1共1としてもよい、記述です。


1.2.8 全日の定義
下のように、平日 または、週末が、全日の定義になっています。


1.2.9 予定入力

数独の問題作成前の全部ブランクの状態になります。


以上、数独のルールが制約として、どのように記述されているかを見てきました。ナーススケジューリング問題も、上で概観したページに制約を追加する形で記述していくことになります。
数独としては、このほかに、小ブロック制約があるのですが、こちらは、スケジューリング問題としては、使う機会があまりないので、別項で記述します。

2.解を得る

下の求解ボタンを押すと、上の制約条件に基づく解が探索されます。



3.解を見る

下のように10解を表示する設定になっています。数独のルールは、制約になり、制約を解く事は、制約を満足するシフトの並びを求めることに等しいことが理解されると思います。(実際、勤務表を作ることはパズルを解く事と同じだ、と感じている師長も多いと思います。)


4 世界一難しい数独を解く

2段目のメニュー、他の予定入力を編集をクリックして、解1をクリックすると下の画面になります。
これは、いわゆる、世界で一番難しい数独 らしいです。



これを求解すると、次の画面になります。メッセージが出ていますが、本プロジェクトでは10解を探す設定になっていて、10解を0,1,2,...と探したときに1番目が見つからなかったという意味です。
言い換えると0番目は解があったことを意味します。OKをクリックすると、




下のように、解が一解だけ表示されます。つまり、下が唯一の解であり、解は他には存在しないということです。


5 世界一簡単な数独問題を作成する

解を編集するには、右クリックで下のようにメニューを出し、予定入力編集に送るを押します。


予定入力編集を見ると
下のように、解を送られています。ここでは、自由に編集が可能です。



CTRLキーを押しながら、全部の1を選択してください。その後に右クリック選択部削除で、削除します。


次の画面となりました。


以上で、世界一難しい数独の答えに辿りつく、世界一簡単な数独の問題作成が終了したので、名前をつけて保存しましょう。

この答えが一つしかないことを、求解して確認してください。

6 解がない数独問題を修正して解を得る

上の問題を修正して、下のような形にしました。左下6x6を削除して、高梨のところに1,2,3,4,5を入力します。
これは、いい加減な問題を作った例です。



当然、下のように求解するとエラーメッセージが出てきます。高梨のところで、なにかおかしいことが分かりますが、よく分かりませんね。
(これは、コメントの部分を省略したために起きる現象です。)
そこで、入力を修正しなければならないのですが、問題は、
最小の変更で、数独ルールを満足させる変更がなにか分からないということです。
これをスケジューリング問題に置き換えると、高梨は、希望シフト1,2,3,4,5を入れたが、希望シフトはできるだけ変えないで、全体の調和を満足させる変更はなにか?ということになります。



ナーススケジューリング問題は、一般に過制約です。全てを満足させる解は一般にはありません。満足させる解がないのなら、それでおしまい。ではなくて、どうしたら満足させることができるか? そのための最小の変更は何か? ということが問題なのです。過制約の中で、最もその頻度が高いのが、個人の希望シフトです。(賢いナースは、あえて休み希望をダイレクトにださずに、ここに深夜を入れると、休みがより取れるとか、狙ってきます。)  希望は、多いところで、5日、少ないところで、2日が一般的だと思いますが、そのほかにも、会議や、リーダ等、研修等で、予定として入ってくる分が意外に多いものです。

そのためには、変更可能なスケジュール部をソフト制約にすることが必要です。下図で、高梨の1,2,3,4,5を選択し、右クリックで、選択部をソフト制約化、を押します。


レベルが出てくるので、適当なレベルを選択します。今回の場合、他のソフト制約がないので、どれを選択しても同じです。
レベル7が最高レベル、レベル1が最低レベルで、レベルが高いほど、優先的に配置されます。



次に求解部分で、
行ソフト予定入力制約1の適用をチェック、各スタッフの許容エラー数を1、ソフトセラー数の最小化を1に設定します。



しかし、求解してみると、下のように解がありません。



許容エラー数を2にしてみても解がありません。


許容エラー数を3にすると、やっと、下のように10個の解が出ました。下図で、高梨の5,7,9が予定とは異なる部分です。




解が沢山でましたが、それは、左下6x6の部分の変更解です。高梨の予定変更は、最小3個が必要であることは分かりましたが、5,7,9以外の選択肢がないかどうか分かりずらいのですね。
そこで、下のように、予定エラーの再掲を禁止をチェックして再求解します。


すると、今度は、2解しかでてきませんでした。(解1と解2だけは、同じ可能性があるので、右クリック予定入力と比較で実際にチェックしてみてください)


確かに、2解は、異なります。よって、数独仕様を満たす最小の変更数は3で、その変更部解は、5,2,3,7,6と下の9,2,3,5,7の2解のみであることが分かります。高梨さんには、申し訳ないけれども、5日のシフト希望のうち、3日は諦めてもらうしかありません。(ソフトの能力の問題ではなく、物理的に入らないのです。)




それでは、高梨さんばかりに押し付けるのは不公平なので、下のように全体をソフト制約としてみましょう。



この場合、スタッフの許容エラーは2個で解がありました。


確かに、高梨さんの変更は3から2に減らすことはできましたが、依然として2個の変更は強いられます。下図が変更部パターン解の全てです。








このように、ソフト制約を使いこなすことによって、解が存在しない場合でも、解が存在する最小の変更を求めることができます。
また、エラーが出てきた場合でも、どこに原因があるか、最小の解から原因部を特定することができます。
また、決まってしまったスケジュールに対する変更(インフルエンザや切迫等で長期に休みになった場合)についても、同様に最小の変更部を求めることができます。

16x16,25x25,36x36数独ソルバ
プロジェクトサンプルフォルダに入っています。

36x36ソルバの解の一部です。10解の出力に18sec 

36x36ソルバの解出力全体



参考http://schedule-nurse.blogspot.jp/2014/06/36x36.html


8. まとめ −従来のシフト表自動生成ソフトとの違い

以上、数独を題材として、スケジュールナースの機能を見てきましたが、従来のシフト作りと大分様子が変わることに気づかれたと思います。
ここで、まとめておきます。

機能 スケジュールナース 従来のシフト表自動生成ソフト 備考
複数の解提示 スケジュールナースは、連続的に出力可能
UNSAT証明 x UNSAT証明がないと終わりがない(探索し続けるしかないので、例えば数独の解が一解しかないことが分かりません)
柔軟な制約記述 スケジュールナースは、数独も制約プログラム可能、外部制約スクリプトにより、短い記述で複雑な制約が書けます。
検証も充実 書いた制約が正しく動作しているかを言語でチェックする機能です。PC版では、検証のためのPythonライブラリソースコードをプロジェクト単位で出力するので簡単にチェックスクリプトを書くことが出来ます。
ポスト処理 Excelで読み込めるCSVフォーマットをサポートしています。Excel等に独自集計をまとめたい、プロジェクト毎に、Excelに出力するためのpythonソースコードを出力します。ユーザは、それを利用して直接にExcelを操作するプログラムを書くことが出来ます。
探索能力 多くの場合、厳密解提示(物理限界まで探索可能)可能
探索速度 スケジュールナースは、特許取得済みの新技術により圧倒的な探索速度を誇ります
過制約対応 制約を満足する最小の予定変更の提示が可能。
エラーの原因表示 x 解がない場合のエラー原因の表示が可能
新しく制約を書く場合には、必須の機能です。

[Prev] [Next] [Index] [Home]