結果です。横軸はスレッド数1-32,縦軸は、求解時間です。純粋にSAT SOLVERとしての評価です。CPUは、Ryzen5950X 128GBです。
全般的には、スレッド数16が極小となることが分かります。DPSは、Synchronoizationに関わる時間ロスが十分に小さいことを示しています。
全般的に、期待通りの結果となっています。DPSの場合、マシンが決まれば、例えばこのグラフは何回試行しても同じ結果となります。別な環境では別なグラフになります。今の求解に対して再現性がある、ということです。
山梨大学鍋島先生のDPSに最新版KISSATをWindowsに移植しようとしたのですが、失敗しました。原因は良くわからず、断念しました。
DPSは、パラレル版のソルバで、Determisticという特徴がありながら、性能劣化を極小にしているところが素晴らしいです。
DFS: A Framework for Deterministic Parallel SAT Solvers
最新版のKissatは、長い時間でみるとあまり性能向上はないのですが、短い時間でみると効果があるようです。なので、是非組み込みたかったのですが、何か見落としがあるのだと思いますがパラレルにするとクラッシュしてしまう問題が発生しました。
とりあえず、sc2021時点のkissatでのWindowsポートは出来たので、これから評価してみたいと思います。上手く組み込みできれば、求解毎のバラつきを抑えることが出来る筈です。勿論、そのままでは組み込み出来ないので、色々やることはあるのですが、基本性能は、SAT能力で決まり、機械的な手順でスケジュールナースのメインソルバとして使うことは出来る筈です。今後の予定としては、Algorithm５として実装予定で、リノベーション後のAlgorithm3/4でも使用予定です。
スケジュールナースは、勤怠時間管理ソフトではなくシフト最適化ソフトです。その目的と機能は、あくまでシフトを最適化することです。世界最高のソルバではありますが、正しい使いをしないとその性能を発揮することはできません。
正しい使い方とは、コンピュータが解きやすいように、問題を簡単化することです。数理ソルバでモデリングと言えば、制約を数式に置き換える作業を言います。池上先生のモデリングにしても、他のモデリングの書籍には書いていませんが、皆、その数式化するときに、簡単なモデルを採用しています。例えば、2交代職場において、その勤務時間は、５分単位、10分単位、15分単位で細かく見ると違いますが、それらを大雑把にまとめて、一つの夜勤や日勤という形で表現します。基本的には２交代なら２＋１（休み),３交代なら３＋１（休み）という風に、勤怠時間管理における時間が異なる勤務をそのままシフトにすることはしていません。
なぜそのようなモデリングが必要になるかというと、「そうしないと解けないから」に着きます。このことは常識で皆さん理解している、と思っていたのですが、どうやらそうでない方もいるようです。
シフトとは何か？ 一回でもシフト勤務表を手で作ったことがあるならば、その大変さを身に染みていると思います。まずは、頭の中の勤務表ソフトという得体の知れないブラックボックスを1回リセットして、ご自分の「手」で勤務表を作られることをお勧めします。皆さん、下の動画内にある手書き勤務表を書いて（あるいはExcelで）やってみてください。
そしてその経験が自然なモデリングを生むと思います。出来る限り状態削減しないと、まともに組めないということが実感として分かって頂けると思います。そして今、手で行って頂いた作業と同じことをさせるのが自動化勤務表ソフトです。
しかし、その経験がなく、頭だけで考えていると、勤務規定マニュアルに沿った形（何十種～何百種も規定があるのが普通です）をそのままシフトにすればよい、という間違った発想になってしまうかもしれません。どうもお話していて話が嚙み合わないのは、その辺の経験の差ではないか？という思いに至りました。私自身は、手で作成したことはないのですが、勤務シフトのソフトウェアを書こうという人は、まず簡単なモデル上で発想を巡らせることになるので、やはり同じ経験を積んでいると言えると思います。
ナーススケジューリング問題は、適切なモデリングなしには、まともに解が出ない世界です。それは、スケジュールナースによらずどのソフトウェアについても同じです。状態変数の数を削減しない限り、小規模な問題も大規模問題になってしまいます。本来なら、物理限界まで求められる最適シフトが、求めることが出来なくなってしまいます。
https://www.nurse-scheduling-software.com/japanese/publications/lecture_notes_for_basic_modeling.pdf
勤怠時間管理は、実態に合わせることは必要でしょう。給料計算には。ですが、それはシフト勤務をした結果です。未来のシフト勤務を予測し必要な加算のための夜勤者を割り当てることとは別物なのです。
事務屋さんにとっては、事務的な負担を削減するが目的でしょう。しかし、私が意図しているナーススケジューリングは、事務的な負担削減が目的ではありません。シフト管理者から見た、組織の目標である看護品質の確保とスタッフのQOL向上にあります。
その目的の為には、何を置いてもモデリングが必要なのです。例えば、組織として加算要件を満足できなかったり、理不尽なシフトを強いられたりしたら、（事務負荷削減を達成したとしても）意味がない、本末転倒ではないでしょうか？
もしも簡単に厳密解が得られるような人的リソース十分の職場だったとしたら、簡単に目的関数値０に到達できるかもしれません。この状態以下に良い状態はあり得ないので事務的なことも目を向けられる余裕が出てきますが、今までそのような簡単な職場は見たことがありません。皆、例外なくリソースギリギリのなかでやり繰りしています。だからこそ、そこをなんとかしたい方々の為にスケジュールナースという高性能ソフトウェアが必要であり、高性能イコールそれだけ助けになるのだ、と信じています。
