2014年3月31日月曜日

連続休みを2回以上、連続休み間隔は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週間--公公
にできればより良い(平準化)、というご要望がありました。
明日実装してみたいと思います。

2014年3月30日日曜日

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

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

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

 
その結果がこちらです。

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

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

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

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

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

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

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

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

<  続く >


2014年3月29日土曜日

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


「土日に連休でその前後には、夜勤がない」
ですから、夜勤の集合をaとすると、そのパターンは、


!axx!a

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

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

最初のxが、今月の最初の日1月1日から効くようにしたいので、
適用は、12月31日からに設定します。そして、パターン最初のaは、金曜日にすれば、xxは、土日になります。最後の日(月)は、夜勤でないになり制約の完成です。
 
下の青部、がその制約になりますが、
昨日作った制約も上の方にありますね。今日作った制約は、昨日作った制約と矛盾するものではないのであってもよいのです。ただし、昨日と今日は、決定的な違いがあります。
昨日の制約は、ハード制約、つまり何が何でも守るべき制約になっています。これが守れない場合、スケジュールナースは、「解がありません。」と言います。
今日の制約は、ソフト制約のレベルを1に設定しています。つまり個々のスタッフについて守らなくてもよいけども、職場全体としては、エラー数(守らない数)が、ある決められた数以下になるような制約にしています。ソフト制約の場合、エラー数を最小にするモードもあるので、それにチェックをして頂くと、最小化した割付を探索します。
下が、その最小化した場合で、エラー数は0になっています。

 


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

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

2014年3月28日金曜日

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

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




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

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

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

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

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

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


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

<明日へ続く>








2014年3月22日土曜日

綺麗な勤務表と将棋名人

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

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

2014年3月20日木曜日

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

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

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

<ペアリング>
スケジュールナースで、ペアリングについては、下記の二つがあります。
  1. ペア禁止
  2. ペア強制
ペア禁止とは、二人の相性が悪い場合、その組み合わせを禁止するものです。従って両方向の特性を持っています。両方向とは、AさんBさんがいたとして、
  1. Aさんから見て、Bさんとは一緒に組まない
  2. Bさんから見て、Aさんとは一緒み組まない
ということです。どちらも同じことですよね。

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

<ペア強制>
  1. Aさんが深夜勤務なら、Bさんは深夜勤務
という風になります。この逆は、必ずしも成立しません。(制約とはなりません。)つまり、Bさんが深夜勤務なら、Aさんは、深夜勤務になる、訳ではありません。

もし、プリセプタ・プリセプティの関係(両方向)にしたいのならば、下のように、二つの制約を記述する必要があります。
スケジュールナースで自動配置した結果です。
中田と渡邊の深夜と準夜が常に同じになっています。
スケジュールナースで、10個の解を出力するのに要した時間は、5秒でした。

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

2014年3月19日水曜日

土日だけ夜勤可能

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

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

土日可能ー>平日不可能ー>不可能は、最大数0

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

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

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

2014年3月18日火曜日

5日連続日勤を回避するには? その2

前回は、ベストエフォットで、5日連続をなるべく回避しましたが、今回は、必ず回避する方法についてです。年休を使ってよい、という前提で制約設計を進めます。

年休といっても、スケジュールとして自動挿入する年休とスタッフ希望で取得する年休とは、違います。スケジュールして挿入する年休は、5日連続を回避するための年休なので、その数は、極小に抑える必要があります。(可能ならば0) 逆にそういう制約がないと年休だらけになってしまいます。

よって、スケジュールで生じる年休のラベルを”す”と表記することにしてラベルを分けます。

制約は、次のように記述しています。
休みxは、公休(Y)または、祝休(H)または、年休(y) または、スケジュールされた休み(h)になります。(一言で休みとは言っても、それぞれに制約式が異なるので、異なる名前をつけざるをえないのです。)
 
5日連続勤務がないことは、この場合MUSTですからソフト制約の列は空欄になります。
代わりにスケジュールされた休みをソフト制約としています。試しに、このソフト制約のチェック5を外して求解すると、下のように”す"でいっぱい入ってしまいます。前月で”す”が入っているのは、制約が効かないからです。
これではいけないので、やはりソフト制約5をEnableしてみると
ちゃんと最小化してくれて、”す”がない勤務表になりました。
今月は、たまたま、必要がありませんでしたが、この制約がないと、スタッフの希望や予定を入れたり、あるいは、休みの少ない月に”解がありません”、とスケジュールナースに言われる可能性があります。そうならないように、しっかり予防的制約を入れました。
ここまで、フレキシブルに対応できるのは、勤務表作成ソフト、スケジュールナースが、制約プログラミングを採用しているためだと思います。

2014年3月17日月曜日

5日連続日勤を回避するには?

5日連続勤務(特に日勤)は、夜勤ナースにとってかなりきついらしいです。
そこで、
  1. 勤務は最大で4日連続
という制約について、物理的に配置可能かスケジュールナースを使って調べてみました。結論的には、ご提示頂いた条件で、殆どの月は初期割り当てなしという条件化で配置可能でしたが、一部配置不可能な月がありました。(公休日が少ない6月が難しい、ただし、毎年配置不能という訳ではなさそう。)

スケジュールナースで、タイムアウトが出ていないときは、厳密解です。この場合タイムアウトは出ていませんでしたので物理的に配置不可能な場合が存在する、という結論です。

解決案としては、二つあり
  1. 最大の努力をし配置不能のときは諦める(最大5日も可とする。配置不能の数を最小にするソフト制約)
  2. 年休を割り当てる(配置できないときは、年休を割り当て最大4日連続をKeepする)
があります。スケジュールナースでは、どちらも制約プログラミング可能です。

まず、1からプログラムしましょう。

5日連続勤務を不可とし、それをソフト制約とすればよさそうです。

”不可”=最大でその数が0

であるので、xを休みとすると、なんらかの勤務はその否定!xになります。
5日連続勤務は、

!x!x!x!x!x 最大数 0

という制約になります。これをソフト制約とすればよいのです。
(勤務表ソフト、スケジュールナースは、制約プログラミングでスケジュール制約を記述します。)

職場は、ICUです。
結構、スタッフ希望と予定を入れても組めるようですね。

勤務表ソフト、スケジュールナースで自動作成した結果は下図です。

ちゃんと4日MAXになっています。この求解に要した時間は3秒でした。





2014年3月16日日曜日

ガイドラインシミュレーション その4

初期条件として、休み希望1日/Person、日勤は、2日/Dayまで追加してみました。
これでも、配置は可能でした。

 
しかし、このままでは、休み希望2日/personは、満たせませんね。
許容可能な初期休み数を増やすにはどうしたらよいのでしょうか?
色々な考え方や影響がありますが。。
 
追記:正循環勤務表については、こちらで詳しく検討しました。

2014年3月15日土曜日

ガイドラインシミュレーションその3

何が問題かと言いますと、スタッフ個人の希望を入れると途端に作成できなくなるのです。

上記は、スタッフ毎にランダムに休み希望を入れたものですが、
前回の設定では、スケジュールナースは、タイムアウトではなく「解がありません」と言ってきました。(厳密解なので、あらゆる組み合わせを試行してもなかった、物理的に無理、ということを意味します。厳密解でないソルバは、解が見つかりませんから、タイムアウトです。)

これは、制約に無理があるということを意味します。前回どういう制約を入れたかというと、

準準休深深パターンが各スタッフで2回以上

という制約です。

<勤務計画表のロバスト性とは?>

スタッフの休み希望の許容最大値は、月2回までのところが多く、月3回、4回、5回になるに従ってその割合が減少するようです。勤務計画表は、スタッフの希望に対してロバスト(頑強な、屈強な)性がないといけません。具体的には、「月2回まで可能」にするためには、少なくとも月2回までは、月を変えてシミュレーションを繰り返しても大丈夫であることを確認しておく必要があるということです。

上記の制約のどこに無理があったのでしょうか?
原因は、準準休深深パターンというのは、長周期パターンであることが考えられます。スタッフ希望
休みがなければ、自由に配置できますが、分断され長周期パターンを押し込めなくなるのではないかと推測しています。

ですので、多少条件を緩和し、
準準休深深パターンが各スタッフで1回以上
にすると、
<つづく>

2014年3月14日金曜日

ガイドラインシミュレーションその2

準休深 パターンは、正循環を実施しようとすると必ず出現します。準の後は休でなければならず、深の前は休みでないといけないので、このパターンはある意味都合がよいのです。このパターンをガイドラインの範囲でできるだけ少なくしたいという場合は、
準準休深深 パターンをできるだけ多くする下図の勤務計画表にするかもしれません。

しかしながら、この勤務計画表は、致命的な問題があります。


続く

2014年3月13日木曜日

看護協会ガイドラインのシミュレーション

とりあえず様子見のところが大半かと思いますが、もし、検討する事になったらどのように考えたらよいでしょうか?

よい方法があります。シミュレーションです。シミュレーションは、現在の職場の環境とほぼ同じ条件をつくり、ガイドラインを遵守した場合、しない場合について様々な勤務パターンを実際に作ってみます。これを紙と鉛筆でやるのは大変ですので、その辺はPCを使おうという訳です。

出力されるのは、勤務計画表なので、今までの勤務計画表と比べてみれば、パターンの違いや問題になりそうな所が浮かび上がってくるので、それについてさらに検討を進めればよいだろう、という考えです。

それでは、スケジュールナースでも、色々な条件を絡めて作ってみようと思います。

 
 
あくまでシミュレーションなので、そんなに怒らないでください。ガイドライン11項目のうちスケジュールに係わる下記8項目を満足します。
  • ガイドライン1勤務と勤務の間隔は11時間以上あける。
  • 勤務の拘束時間は13時間以内とする。
  • 夜勤回数は、3交代制勤務は月8回以内を基本
  • 夜勤の連続回数は、2連続(2回)までとする
  • 連続勤務日数は5日以内とする。
  • 夜勤後の休息について、2回連続夜勤後には
    おおむね48時間以上を確保する。1回の夜勤後についても
    おおむね24時間以上を確保することが望ましい。
  • 週末の連続休日
    少なくとも1カ月に1回以上は
    土曜・日曜ともに前後に夜勤のない休日をつくる。
  • 交代の方向は正循環の交代周期とする。


     

 すべての勤務が日->準->休->深-> 方向になっているのは、正循環だからです。日日日日日は、あってもよいのですが、準や深は、準準、深深までです。

全ての勤務が11時間以上あけるになっているので、日深や、準日はありません。準夜のあとは、必ず休みになるし、深夜の前も休みになります。実は、上の結果は、気づいた方もおられると思いますが、次の制約をプラスで入れてあります。

  1. 日勤の連続日数を3日
  2. 深深の数を最小化
  3. 準準の数を最小化
  4. 深-深間隔は5日以上
  5. 準-準間隔は4日以上
この制約は、極めて厳しい制約で、数あるソルバのなかでも、現実的な時間内にこの解を出せるソルバはスケジュールナースだけでしょう。




 
追記:正循環勤務表については、こちらで詳しく検討しました。
 

2014年3月11日火曜日

特許出願

スケジュールナースは、特許を出願しています。

内容は、スケジュールのソフト制約に関する求解の高速化に関するものです。ナーススケジューリング問題というのは、スケジューリング問題でも難しい問題であることが知られていまして、この半年の開発で暖めたアイデアを具現化しました。

個人で出願するのは、初めてだったので、手続きに大分手間取りました。

大まかな流れは、

1)電子認証のための申請->区役所
2)電子認証のためのICカード購入
3)インターネット出願のソフトインストール
4)簡単願書作成のインストール

5)出願料の納付(PayEasy) 15000円
6)出願 インターネット出願ソフトによる

です。それから、審査請求しないといけないのですが、これは、私のような者には、救済制度があり、平均で6-7年かかる特許審査も早期ににできる制度があります。

会社員時代には、専門の弁理士さんがいて、資料数枚と口頭説明だけで全部やってくれたのですが、弁理士さんに頼まずに全部自分でやるとなると大変です。でも、そのときの経験が大分役に立ちました。

ちなみに、あのとき書いた特許の殆どは、審査請求されずに埋もれてしまったようです。

震災から3年

あの日から3年経ちました。

私の家の近くでも土砂崩れがあり通りがかった人が巻き込まれ亡くなりました。
また、付近で半壊した家が数件あり、現在は更地になっている所もあります。

電気、ガス、水道もない一週間でした。妻は、震災から二日後に帰ってきました。家族の無事を涙して確認した後、またすぐに病院に戻らなければいけない、というので、看護師長である妻を車で送っていきました。

闇の中を街に向かいました。車中から見る街は、いつもの喧騒はなく、人気がなく静まりかえっていました。光のない街というのを初めて見ました。多分、これからも見ることはないでしょう。それは、深い虚無のようでもあり、僅かに非常電源で灯る微かな光だけが、心細さを癒してくれるようでした。



2014年3月9日日曜日

はじめまして。

http://www.nurse-scheduling-software.com/

で、勤務計画表の自動作成ソフトウェアを始めました。

看護職は24 時間365 日、日夜、夜勤・交代制勤務を行って患者の健康と生命を守っています。一方で、夜勤・交代制勤務と生活の両立の難しさは離職の原因ともなり、過度な負担は心身への影響や医療事故のリスクを高めるという研究結果もあります。

看護師長からみれば人事管理上の複雑で高度な判断を要する集積が勤務表ですし、
スタッフからみれば、一ヶ月の生活のすべてがそこにある「永遠のベストセラー」です。
看護師長とスタッフの立場で違いはあるのですが、両面で力になりたいと思いました。

よろしくお願いします。