時間制約の改善

を119Aで行いました。118A 以前では、プロジェクトサンプル特養で、Python記述と時間制約では、4-5倍の差がありましたが、ほぼ同じ時間となりました。これにより、Pythonで記述しなくてもよくなりました。

	１１８A	１１９A
Python制約あり	19sec	19sec
Python制約なし	92sec	24sec

ところで、時間制約のほかに、夜勤回数、日勤回数、半日回数を下記のように
制約しています。

 

夜勤回数は、夜勤回数を6回にしないために必要な記述です。その他は、158.5h-160.25hを保証する意味では、必要がない記述です。

そこで、もし、時間制約以外の制約がないとどうなるかやってみました。

案の定、158.5-160.25hを満たす、夜勤回数、日勤回数、半日回数は、上記に限定されず多くの組み合わせが存在することが分かります。

このとき、時間は、34secかかりました。解空間は広がりますが、探索空間も制約が付加されないので広がることに注意します。Algorithm1の場合、かかる時間は、比＝解空間/探索空間　に

反比例する方向ですので、時間がよりかかったと推測されます。ともあれ、Pythonで気を配る必要がなくなったのは良い方向だと思います。　

 schduling benchmarksからの結果です。目的関数値は、Instance13を除いて、さして改善していません。悪化している場合もあります。しかし、解が出るまでの時間は、例外なく短くなっています。

Note:１）Algorithm1の比較であることに注意してください。Algrorithm4では、時間をかければ、KnownUB値を得ることは可能です。

２）１１９Aでバグがあり１２０Aで修正しました。

 

	Algorithm1
	１１８A		１２０A		Known UB
Instance9	441	141(sec)	539	113(sec)	439
Instance10	4834	213(sec)	4842	170(sec)	4631
Instance13	3944	2109(sec)	3285	(1042sec)	1348
Instance14	1522	235(sec)	1421	209(sec)	1278
Instance15	5249	412(sec)	5135	331(sec)	3225
Instance19	4825	616(sec)	5035	483(sec	3149

 

夜勤専従シフトパターン スニペット

人力解は、下のようになっていました。

これを見ると夜勤の連続があり得るので、通常の2交代パターンを変える必要があります。また、上では、10連続勤務の部分があります。法律上は、4週4回または、1週1回以上の休みが必要ですので法律上は問題ないのですが、7回連続は避けるよう記述しました。

ナースと介護の両方の勤務パターンを見ていると、圧倒的に介護業界は、厳しいものがあります。
例えば、ナースの場合、2交代では、月4回が一般的で、月5回の夜勤を見ることはあまりないのですが、介護の場合は、月5回はざらで、月8回という夜勤専従に近いパターンも珍しくありません。（その点、プロジェクトサンプルに添付した特養サンプルでは、全スタッフのこの上ない平準化を成し遂げていて稀な例であると思います。）


スケジュールナース使用して、人に易しい勤務パターンを実現して欲しいと願うばかりです。日本中の理不尽なシフトを一掃することが、筆者の夢であり責務であるとも思っております。「そこに解があるなら使わない手はない」のです。
人力解とスケジュールナース解の差を見ていただければ、一目瞭然に違いが分かります。夜勤のトータル回数を減らすことは出来ませんが、夜勤のパターンを改善・スタッフ間での平準化を行うことは出来ます。

部分和問題

組み合わせ最適化問題でよく出くわします。解法例は、例えばこちら。

例えば、重み３、５，７があり、目的関数値の暫定値が211だったとして、次のターゲットは何になるかを求めるときに使うことがあります。（大抵は、-1すれば済むので、実際はあまり使わない）　これを解くには、いわずと知れた動的計画法によるのが一般的です。がナーススケジューリングの場合、そこまでは必要なく、単純なループ探索でも支障がないと思います。　　

microsoft開発者登録

Windows7ブラウザでは、うまく登録できませんでした。Chromeで登録できました。個人か法人かで登録料が違います。1847円でした。登録が成功するとWindows デベロッパー センター アカウントの作成が完了しましたのメールが届きます。

次のハードルはデスクトップコンバータです。
 https://developer.microsoft.com/en-us/windows/bridges/desktop

その前に認定キットで様子をみようと思います。認定キットはWindows10SDKに含まれます。
https://developer.microsoft.com/ja-jp/windows/develop/app-certification-kit

スケジュールナースⅢオープンβ版リリース

しました。
β版とはいえ、メインソルバの機能は正式版と変わりません。不完全なのは、以下の通りです。

１）公式チュートリアルが整備されていません。
２）タスク・フェーズについてチュートリアルが整備されていません。
３）Algorithm4が開発中です。

今後の計画としては、Algorithm4の整理、海外ベンチマークテストの移植、英語版含むチュートリアル作成を行います。その後Windowsストアアプリ登録を目指します。来年初頭の予定です。
前にも言及したようにストアアプリ登録後は、無料でのリリースはなくなりますが、ここ1年程度は、使えるはずです。その後は、カレンダが動かないので使用できなくなります。現行有償ユーザへのUpDateおよびサポートは継続します。ただし、ストアアプリライセンスは別となります。よろしくお願いいたします。

Python3制約マニュアルを更新

時間制約は、遅いのですが、場合によっては、Pythonで時間制約を使わずに記述できる場合もあります。そのような例をユーザ様のプロジェクトをそのままお借りして記述しました。
改善前のプロジェクトでは、時間制約だけでもよいのですが、その場合、夜勤6回が出現することがありました。それはまずいということで、夜勤回数も制約化しています。

158.5hと160.25hとなる組み合わせ（夜勤回数、日勤回数、半日回数）は各々一つに限定できるようです。そうするとそれらの条件のAND・ORで制約化すればよいことになります。GUIでは記述できないので、Pythonの出番になる訳です。このプロジェクトで面白いのは、極限的に勤務時間数の平準化を行っていて、休み（公休数）の制約がどこにも入ってこないことです。お聞きしたら、「公休数は決まっているのですが、出来上がった勤務表から「休」を一部手で「公」と変更しております。」　とのことでした。発想が斬新です。
なお、このPython化事例は、以下のような経緯に基づいています。

「夜勤回数を毎月、スタッフ設定から設定し直しています。全員の夜勤回数の総和が日数*4となるようになっております。毎月手で計算しているため、ミスが発生する可能性はあります。
その場合は矛盾でハードエラーが出るわけですが、場合によっては、エラーメッセージからは気づきにくい場合もあります。」

シフト時間が8hまでしか記述できなかったので、そもそも時間制約で記述できなかったのですが、GUIを対応して時間制約で記述してみると、5倍程度時間がかかってしまいました。これは、純粋に技術的な理由により予想されていることです。具体的にはUnitPropagationで記述できないことに起因しています。UnitPropagationするような方法も試してみたのですが、メモリオーバで記述できませんでした。この辺、OR的アプローチでは、むしろ問題なくAlgorithm4では、あまり影響がないはずです。

そこで、Excelで総和一致を確認した後インポートする発想をしていたのですが、ユーザ様プロジェクトの発想をそのままPythonで記述できることに気がつきました。Excelの力を借りることなくPythonでStandAlone的に記述することができました。恐らく、長期休み以外は、この記述で行けると思います。時間も4分の1から5分の1程度になりました。また、各スタッフからみると選択の余地がなかったのが、選択の余地があることになります。解空間は広がりますから、予定が入った場合以前よりも解が得やすくなっている筈です。実際のプロジェクトが入っているので比較してみてください。

いずれにしても、人力でほぼ不可能に思えることを難なくやってのけるのが素晴らしいと思います。ソフトの力を最大限に活用頂いている事例になっていると思います。

特養の記述サンプルとしても価値が高いプロジェクトであると思います。

仙台も冠水

1号配備とかで、土曜日夕方に妻を泉中央駅まで送ってそのまま病院泊まり、今日、日曜、病院まで迎えに行ってきました。広瀬川が決壊寸前までいきましたがなんとか持ちこたえたようです。帰りの道は、すっかり路面が乾いて日常生活に戻っていましたが、途中、道の真ん中で捨て去られた車を何台か見ました。多分AM３：００頃は、市内全域冠水状態だったと思います。

大手の画一的なプログラム

残念ながら、大手企業の大病院に入っているF社やM社のソフトは、画一的で固定の設定しかできません。
M社には、SC2のエンジンが入っているのですが、残念なことにフレキシビリティを生かしたGUI設定になっていません。エンジンがいかに優秀でも、個別病棟ごとに自由な設定ができないのなら、高速ソルバーをもっている意味が半減、否それ以上に価値が下がってしまうと思います。M社には、勿論SC3エンジンへのUpdateを促しますが、そもそもGUIが対応していないので...

解を高速に解くという面において、ここ数年でスケジュールナースが進歩したように今後も高速なソルバーの進歩は未だあるでしょう。しかし、制約プログラムの考え方、ナーススケジューリングDay集合、スタッフ集合、シフト集合（task/phase)の3要素で、欲しい解を記述するスタイルは、いかにソルバーが高速になろうとも変わることのない普遍的なものです。集合演算をGUIでいじくるスタイルは変わりようがないとも言えます。

看護師長が、個人で使えるように、ソフト自体の価格は、300円/月程度にするつもりです。来年のリリースを目指します。後は、初期設定を行うサービス、サポート体制と教育・啓蒙活動が重要であると考えます。

離散系と連続系

連続系での最適化ソルバーには、Simplexや内点法があります。連続線形領域では、NP困難の世界から脱することができます。連続系の解は、2.5人とか、1.3人とかになります。人を、そんな風に分割することはできないので、整数化した解が欲しい訳です。組み合わせ最適化の世界は、整数の世界です。ところが、整数の世界の最適値と、連続系の最適値は、似て非なるものです。難しいのは、整数化です。連続系からなんとかしようというのがOR的アプローチAlgorithm4になります。一方で、最初から、整数の世界でなんとかしようというのが、AI的アプローチでAlgorithm1です。
最適化解は、時間をかければ、Algorithm4の方が得やすいです。一方、Algorithm1は、短い時間で近似解を得るのが得意です。現在行っているのは、Algorithm4で、近似解でよいから短い時間オーダで解を得るものです。整数化解をいつどのタイミングで得るかということが問題です。INRC2の８Weeksの１インスタンスデータを得るのに数日かかっていますが、これに近い解を１０数分程度内に得ることが目標です。とても不可思議な世界で、整数化世界とは、全く異なる様相です。多分、機械学習させれば、なんらかの法則性や相関性が見出せるのではないかと思いますが、そこまでは行わずに、アイデアをCut＆Tryするということを行っています。

SC3導入2

導入の問い合わせがあったので、SC3ベースで新たにつくりました。Excelベースの方が導入前後の品質がVisualに比較できます。現実のルール（脳内）を可視化・計数化するとどうなるのか、をベースに置いて、そこからこれだけ改善できる、という方が説得力があります。