連続休みを2回以上、連続休み間隔は2週間程度で平準化 その２

下は、連続休み2回以上の制約です。

パターンのところが新しいです。ひとつひとつ見ていきます。
まず、$S関数ですが、パターンの加算に関する制約です。
$S(min, max, type, pattern...)
これ自体は、今までの最大、最小と同じ意味で、
type 0:  min<= X <=max
type 1:  X>=min
type 2:             X<=max

という制約になります。上の
$S(2,0,1..)
は、最小2以上 という制約になります。

$P(n, パターン）
nは、パターン開始日n　のnです。
$P(1, xx)は、パターン開始日1のところの日をxのスタートとする
という意味です。ここでは、スケジュール開始日の第一日目がxで
第2日目もxであるならマッチして、$P(1,xx)の結果は1を返します。
マッチしなければ、0を返します。

$P(2,!xxx)は、パターン開始日2のところの日をxのスタートとするという
意味になります。パターン開始日2がスケジュール日(1月1日から1月29)の間
マッチするする部分を$Sで加算することになります。

まとめると、
最初の日のxxと、最初の日から1月29日まで!xxxにマッチする部分を
加算して、2以上という制約になります。

面倒ですが、「連続休みを2回以上」という制約にしたい場合は、
この行をコピペすればよいです。

勿論、xの定義、第一日の定義、スケジュール日の定義は各々の環境で違ってくるでしょうが、
単に置き換えればよいだけです。

なお、日の定義は左のようになっています。









これで平準化前の「連続休みを2回以上」制約が記述できました。
この結果は、勤務表自動作成ソフト　スケジュールナースで、14秒かかりました。

今回は、前回と違って、分離した2回以上連続休みしか数えないので、公公公を　2連続休み2回とカウントする不具合はありません。




できれば、休み間隔は、公公-- 2週間--公公
にできればより良い(平準化）、というご要望がありました。
明日実装してみたいと思います。

連続休みを2回以上、連続休み間隔は2週間程度で平準化

という、ご要望を頂きました。平準化の部分は、できればということで、弱い制約でよい、とのことでした。最初は、まずい制約の例です。

＜まずい制約例＞
連続休みが2回以上制約ですが、簡単に下の青部のように記述しました。

 

その結果がこちらです。



まずい点がお分かりでしょうか？
3回連続の休みを
公公公
2回の連続休みとしている点が、意図していないのです。

これを回避するために、公公公を2回にカウントしないための制約について考えてみましょう。
!xxx
をカウントすれば、良さそうですが、これも厳密ではありません。初日に前月からの公が続いている場合、カウントしなくなってしまうのです。

31　 １　 2
公　公　公--->!xxxにマッチしないので、カウントしない　xxなら1日2日でマッチする

1  　 2     3    4
日   公　公　公 --->!xxxに2日でマッチ　　　

ですから、初日と、それ以外で制約を分ける必要があります。つまり、

Σ　初日の場合は、xxを、スケジュール日は、!xxxを

をカウントすればよいです。

これを記述するために、Version111から、パターン記述の拡張を行っています。

<  続く >

土日の連休を一回は、つけてあげたい その２



「土日に連休でその前後には、夜勤がない」

ですから、夜勤の集合をaとすると、そのパターンは、



!axx!a

になります。その意味は、

夜勤でない、休み、休み、夜勤でない
になります。

最初のxが、今月の最初の日1月1日から効くようにしたいので、

適用は、12月31日からに設定します。そして、パターン最初のaは、金曜日にすれば、xxは、土日になります。最後の日（月）は、夜勤でないになり制約の完成です。
 

下の青部、がその制約になりますが、

昨日作った制約も上の方にありますね。今日作った制約は、昨日作った制約と矛盾するものではないのであってもよいのです。ただし、昨日と今日は、決定的な違いがあります。

昨日の制約は、ハード制約、つまり何が何でも守るべき制約になっています。これが守れない場合、スケジュールナースは、「解がありません。」と言います。

今日の制約は、ソフト制約のレベルを１に設定しています。つまり個々のスタッフについて守らなくてもよいけども、職場全体としては、エラー数（守らない数）が、ある決められた数以下になるような制約にしています。ソフト制約の場合、エラー数を最小にするモードもあるので、それにチェックをして頂くと、最小化した割付を探索します。

下が、その最小化した場合で、エラー数は0になっています。



 

勤務表自動作成ソフト、スケジュールナースでの求解時間は、7秒でした。

すくなくとも一つという制約ではありますが、二つ入っている人は一人しかいませんね。
中々厳しい制約のようで、これを自動化ソフトなしで割り付ける看護師長さんは、凄いと思います。
とりあえず、前後に夜勤のない土日連休、フリー連休とも言うのでしょうか？看護協会のガイドラインのひとつは、こういう制約で満たすことができます。

土日の連休を一回は、つけてあげたい

という制約は、どう書けばよいでしょうか？




一般的な休みの集合をxとすると、
連続した休みは、xx　になります。

最初のxが土曜日であればよいので、下図の青ラインの制約を入れればOKです。

この制約で割り当てたのが下の勤務計画表です。

勤務表ソフト、スケジュールナースで、求解時間は5秒でした。看護師全員に土日休みが入りました。

ところで看護協会のガイドラインにこんなのがあります。

少なくとも１カ月に１回以上は
土曜・日曜ともに前後に夜勤のない休日をつくる。

上の制約よりも、さらに難易度が上がりますね。

＜明日へ続く＞

綺麗な勤務表と将棋名人

昨日も、看護師長とお話させて頂いて、「綺麗な勤務表」　という言葉が看護師長からでてきました。　「あの看護師長が作る勤務表は綺麗だったよね..」　、やはり看護師長である妻が坦懐したことを思い出しました。どうも、看護師長の中でも、勤務表作成名人が存在しているようなのです。その人が作る勤務表は、基準の理想パターンが、各スタッフで一日づつずれていって、図形パターンとして、ｘに近いようようなパターンが現れるらしいのです。　
　コンピュータの側（ソフトウェア作成）から見ると、綺麗という概念は勿論、制約プログラミングの概念からは、基準パターンというものさえありません。単に制約というフィルタで探索空間から解をろ過するだけです。一方、看護師長達は、長年の経験から、複雑に込み入った勤務表を作り上げる能力を獲得しています。それは、素人の私から見ると、本当に驚嘆すべき能力です。
　
　
　今日のコンピュータ技術は、勤務表を完全に解けるところまで着ています。完全に解けるとは、解の有無（SAT/UNSAT）を判定できることを言います。　問題の複雑度にもよりますが、大体の問題は、数秒程度で解けます。殆どの問題は、1分以内程度で解けるでしょう。勿論、完全には解けない問題も未だ存在しますが、実用的はかなりの割合で解けるようになってきました。解があるとは、将棋で言えば、詰める手順が分かったようなものです。昨今、コンピュータと人間の対戦でコンピュータが勝利する場面が増えてきましたが、NSP（ナーススケジューリング問題）の探索空間は、10の80乗から10の200乗程度で、解の個数も10の10乗程度（感覚です）は、存在することが分かってきました。このような規模が解けるようになったのは、ハードウェアの進歩(x100)とソフトウェアの進歩(x1000)=x100000 によるものです。将棋ほど、探索空間は大きくないにせよ、それは、数年前までは不可能と思われていました。技術の進歩がこれほど、急速に伸びるとは思われていなかったのは、やはり将棋ソフトと同様の世界です。
　
 　昨日の話に戻しますが、スケジュールナースが出力した勤務表の画面には、一部、ｘパターンが現れていました。師長と画面を眺めながら、ｘパターンの話を師長はしてくださいました。
　
　
　人間が美しいと感じるパターンが、実は、究極の制約上の解になっているというのは、偶然なのか偶然でないのかは分かりません。勤務表作成名人は、解の存在は知らなかったことは確かです。数年前までは、*完全には解けませんでしたから。しかし勤務表作成名人は、複雑に込み入った制約のなかでも美しいパターンが究極解に最も近いことを知っていたのです。

*注
　　”完全には”　の意味は、厳密解を指します。近似解の算法は、数年前以前にもありましたが、
厳密解の算出は、この3-4年で可能になりました。

プリセプター プリセプティ ペア設定の仕方

これも、一昨日の看護師長との打ち合わせで、出てきた話です。
もうすぐ、新人ナースが入ってきますね。

先輩ナースと新人ナースの設定についてです。まずは、ペアリング設定についてです。

＜ペアリング＞
スケジュールナースで、ペアリングについては、下記の二つがあります。

1. ペア禁止
2. ペア強制

ペア禁止とは、二人の相性が悪い場合、その組み合わせを禁止するものです。従って両方向の特性を持っています。両方向とは、AさんBさんがいたとして、

1. Aさんから見て、Bさんとは一緒に組まない
2. Bさんから見て、Aさんとは一緒み組まない

ということです。どちらも同じことですよね。

でも、ぺア強制は、上とは、違い片方向の性質です。

＜ペア強制＞

1. Aさんが深夜勤務なら、Bさんは深夜勤務

という風になります。この逆は、必ずしも成立しません。（制約とはなりません。）つまり、Bさんが深夜勤務なら、Aさんは、深夜勤務になる、訳ではありません。

もし、プリセプタ・プリセプティの関係（両方向）にしたいのならば、下のように、二つの制約を記述する必要があります。

スケジュールナースで自動配置した結果です。

中田と渡邊の深夜と準夜が常に同じになっています。

スケジュールナースで、10個の解を出力するのに要した時間は、5秒でした。

ただし、この制約は、他の制約との矛盾が起きる可能性が高いです。よくよく考えて、他の制約が機能することを確認した後の、最後にトライすることをお勧めします。

土日だけ夜勤可能

昨日、ある看護師長さんと打ち合わせしていて、上記のご要望を頂きました。

家庭の事情で、中にはそういう方もおられるでしょう。土日だけでMAX4回の夜勤という条件でしたので、次のように制約しました。考え方は、

土日可能ー＞平日不可能ー＞不可能は、最大数０

です。

で、平日の定義は、次のように、月火水木金のORになります。

 

後は、このパターンをスタッフ定義の中でリンクすればよいだけです。このプログラミングは、
3分くらいでした。スケジュールナースでは、これくらいの制約は平気です。

もうひとつご要望がありまして、長期休みの方がいて、当然夜勤の回数が限られるというものです。
これは、上で作ったパターンをコピーして修正したほうが早そうですね。上とほぼ同じ制約で
土日の制約がないだけです。