2025年10月30日木曜日

シフト勤務表リリース後の修正方法

 未だ、手で何とかしようとしている方がいるので再掲します。


シフト勤務表のリリース後の修正は、機械的な手順で修正が可能です。

ポイントは、ほぼ、予定の変更が付きまとうということです。勿論変更でも人的リソースに余裕があれば、軽微で済む可能性がありますが、大抵は、一人のスタッフのシフト変更が、多数のスタッフに影響を及ぼし、複数の予定の変更がどうしても生じてしまいます。スタッフとの予定変更折衝は、出来るだけ避けたいと思うのは当然です。シフト予定変更が少なければ、少ない程良いのは、言うまでもありません。シフト予定変更を最小にするには、どうしたらよいでしょうか?

その答えが次の動画です。最適化シフトエンジンに、その辺の計算は任せてしまえばよいのです。

https://www.youtube.com/watch?v=U4Bg-8SnHP8


ポイントは、

■過ぎ去った過去は変えられないので、それまでの過去の実績をロックし予定をハード制約にする

■今日以降の決まった変更や、スタッフの当初の休み希望等は、ロックし予定をハード制約にする

■その他は、ソフト制約化を行い予定の変更を許容する

です。

変更したくない予定の重みを大きくすればするほど、予定は変更されにくくなります。あまり、大きくしすぎると重篤な制約にも影響を及ぼしますから、その辺は微調整します。この辺の匙加減は、管理者だけが知っています。どこまでを許せて、どこまでを許せないか?現場を熟知している管理者だけが、医療事故リスクとシフト予定変更インパクトを天秤にかけながら、最適なシフト変更を行える、と考えます。

管理者は、変更してよい箇所とそうでない箇所を自ら指定します。人的リソースは、シフト最適化ソルバを使うことによって物理限界までフルに使うことが出来ます。大切な勤務は、人、管理者が決めることが出来ます。

ソフトウェアやAIが、自分の頭にあることを推し量って決めてくれる筈がありません。管理者自らが、ハード制約とソフト制約を決め、変えてよいところと、変えてはいけない線を指示することが、これからの勤務表作成で求められます。

組織の目標である列制約を満足させつつ、最小の予定変更がクリック操作だけで実現出来ます。

慣れれば、3分で修正が完了します。

2025年10月29日水曜日

Q 年末年始の設定

Ans.特別の日の設定で、ユーザ用独自の年末年始日を定義し、休日に追加してください。


Q.休日の色は変えられないのですか?

Ans.

休日の色は変えられません。祝と振休は、内部で持っているカレンダで決まっており、その日は、色を変えています。


Q.「今月」はユーザ定義できないのですか?

出来ません。今月の定義は、制約開始日から制約終了日のみで決まっており変えることは出来ません。(逆に言えば、制約開始日と制約終了日を変えれば変えられます。)

2025年10月28日火曜日

Q.現在、夜勤専門職員が勤務に入る日の設定では、遅番が3名となっていますが、 11月から遅番を2名に変更していただけますでしょうか

 Ans.

現在の設定箇所は、下記で、ペア制約 AならばBを用いています。


ここを>=2にすれば良いように思いますが、>=2に関しては既に列制約で一般制約として制約済です。

ペア制約では、特殊ケースについて記述しています。今回の変更によって、特殊制約は不要になったのですから、以下のようにペア制約のチェックを外すだけで事足ります。



しかし、求解して確認してみると 解がありません。ソフトの許容範囲エラーです。エラーの数が許容範囲を超えているがために起きているハードエラーです。この手のエラーは許容範囲を拡大することで解消することが出来ます。

赤字●部分をダブルクリックして当該制約に飛びます。

ソフトレベルがどちらもレベル7であることが分かります。

列制約レベル7の許容数を見ると0になっています。

とりあえず、1にしてみます。

求解してみると、解はありました。
レベル7のエラーは重篤エラーとして赤でマークされています。
同じレベル7制約である、夜勤数も許容エラー数を1としているがために夜勤数もエラーとなってしまいました。ソルバは、目的関数値UBを最小の結果を求めています。現状の制約状態を変えない限り、このエラー数は必然です。(ただし、エラー箇所は必然ではありません)ソルバは、UB総和をこれ以上小さくする割り当ては存在しない、と言っています。

この解が気にいらず、列制約も変えたくない、ということでしたら予定(ハード制約)をソフトにして、予定変更を認めるしかありません。リソースの限界を使い切ってる、物理限界を超えているので、他に選択肢はありません。以下は、その手順です。

再度レベル7の許容エラー数を0にします。エラー情報を見ると11月16日に集中していることが分かります。



そこで、11月16日の予定を選択して、
ソフト制約にして
レベル7にしてみます。
16日のセルの枠が茶色になりました。



重みを10にして、予定は出来るだけ変えるな!という指示にします。適用は新たなソフト制約なので、チェックが入っていません。チェックして求解してください。
解は、存在します。重み10のエラーが1個なので、予定が1個変更されていることが分かります。

夜勤数、遅番数、早番数は全部満足しています。


しかし、11月16日、誰かの予定が変更されている筈です。予定変更数最小(重み最大)を指示したので、変更数は最小になっています。(この辺は人間業では到底出来ないと思います! 

スタッフ23の予定が休日からC(夜勤専従夜勤入り)に変更されています。
予定で見ると、

休みが夜勤入りに変更されています。

以上の作業を行うのに慣れれば3分です。機械的な手順だけで難しいところは何もありません。



介護士勤務シフト表の最適化の実際は、上のようなちょっと面倒な作業が必要になる場合もあります。リソースの限界を使い切っていることを分かるのは、多分スケジュールナースだけだと思います。その上で対処方法は、上で見たように色々あります。何がベストなのかは、管理者だけが知っています。私も分かりません。

<人的リソースを使い切った場合の対処法まとめ>

■「解がない」のは、ハード制約間に矛盾があるからです。
■エラーメッセージをよく見て当該箇所をソフト制約化します。

<スケジュールナースと他のソフトウェアとの違い>
スケジュールナースでは、ハード制約と、ソフト制約と明確に分かれています。あえて、ユーザさまにその理解を強いている、とも言えます。他のソフトウェアは、この区分がなく、内部的には、全てをソフト制約にして組んでいます。このことの弊害は、ユーザにとって、絶対に落とせない制約とそうでない制約との区分けができなくなることです。そもそもソルバ能力の実力差を指摘したいところではあるのですが、それとは別に根本的な設計思想が違います。一言で言うなら「人的リソースが厳しい」向けのソフトウェアです。

他のソフトウェアでは、どうでしょうか?解はとりあえず出るでしょう。しかし「何故かエラーが沢山出る、でも原因が良く分からない」、で終わってしまうのではないでしょうか?その結果、制御できないエラーだらけの(望んでいない)勤務表になってしまうことでしょう。

スケジュールナースでは、何が絶対か?をユーザさまご自身に委ねています。その結果しばしば、「解がない」事態に陥る結果となります。言い換えると、ユーザさまご自身で限界の線を定めていることになります。「解がない」とは、ユーザさまが定めた絶対線を超えることを意味します。

<許容数0の意味>
上のソルバ設定で許容エラー数が0になっている箇所が散見されます。これは、最大最小制約において、その許容数が0つまり、本来ソフト制約である制約をハード制約化していることを意味しています。私が設定したものではなく、ユーザさまが意図してハード制約化したものと推察されます。


何故、ユーザさまご自身で、ハード制約とソフト制約の区分化を強いるのか?というと、そのユーザにとっても物理限界までリソースを使い切る、ことを主眼にしている、からです。
限界線をユーザさまご自身で決めその物理限界まで使い切るソフトウェアだからこそ、初めて出来る指摘です。スケジュールナースの固有技術です。(特許6364638)

<解がない事態を解消する方法は無数にある>
エラーメッセージに基づいて、指摘箇所をソフト制約化するのですが、実は、上記以外にも方法はあります。数理的には無数にある、と言ってもよいと思います。僅か二つの例を提示したのですが、実は、他の制約を緩める方法は、いくらでもあります。が、大別すれば、上の2方法に分類される、ということです。

<正解を知っているのは管理者だけ>
二つの方法のうちどちらが管理者が求めているものでしょうか?私も分かりません。正解を知っているのは、現場を預かる管理者だけでしょう。たった1個の予定変更を取るか、人が居ない方を取るか、判断するのは管理者です。その職場にもっとも適した緩和方法は、その管理者だけが知っています。この先AIが発達したとしても、私がどちらの案が管理者の求めているものか分からないように、AIも無数にある緩和方法の正解を分かることはないと思います。

大切なことを決めるのは何時でも人、管理者であるべき、がスケジュールナースの設計思想です。




2025年10月27日月曜日

シフト最適化アルゴリズム

 下は、2017年にRAMPで使用したスライドです。

早いもので、これから8年が経ちました。シフト最適化に良いアルゴリズムは何か?というのは、私が、10年以上追い求めているテーマで、この講演時から、SATソルバの限界を感じていてMIPソルバの勉強を始めました。終生の目標として、未解決ナーススケジューリング問題を全問解くという、前人未到の目標を掲げて研究に取り組んできました。

このときは、感触でしかなかったのですが、今は、割に確信に近いイメージを持っています。一つの方式で全てのインスタンスを包含する最適アルゴリズムは存在しない、というイメージです。

<メタヒューリスティクスは無くならない>

ナーススケジューリング問題の黎明期は、メタヒューリスティクス開発の全盛期で、その後次々と、ベンチマーク問題がMIPソルバにより解かれ、メタヒューリスティクスは駆逐されたように思われています。確かに、そうした面はあります。

が、実務問題で厳密解が得られているか?という問いに対して、実は、スケジュールナースでも、最近は凝った制約の塊になることが多く、例えば、5年以上使いこなしているお客さまのプロジェクトを見ても、複雑化した制約が追加され、厳密解が得られることは、多くはない、という傾向が強まった、と思っています。

そして、超大規模のインスタンスに対しては、依然として、現実時間内に現実的な解を得るには、メタヒューリスティクスに頼らざるを得ない、ということではないかと思います。

学生さんがよく取り上げるテーマですが、既にベンチマークセットがあるので、それに対してどうだ?という比較で論じて欲しいと思います。単に実務問題で解けた、では価値がないと思います。

<SATソルバが得意なインスタンス傾向>

SATソルバは、数を数えるのが苦手です。線形制約は、全てブール演算から構成する必要があります。逆に言えば、数を数える場面がない、もしくは少ない場面では、無類の強さを発揮します。例えば、数独もその一つです。100x100の数独問題を解けるのは、今も昔も今後もSATソルバだけだと思います。そのような傾向の強いインスタンス、組み合わせ最適化問題には、SATソルバが最適です。

もう一つの傾向として、

■解空間/探索空間の比率が高いとき

に強さを発揮する傾向にあります。平たく言うとソフトエラーの数が少ないインスタンスは、強いということです。池上ベンチは、全ての制約がソフト制約で、その意味では、探索空間の枝刈りを行うことは出来ません。そのため、探索空間は確かに膨大なのですが、解空間も意外に広い、解の範囲が広範囲に分布しその比率は意外に高いのです。

こうしたインスタンスには探索中の学習が効果を発揮し、高速に求解出来ます。

<MIPソルバが得意なインスタンス傾向>

MIPソルバは、基本線形制約(SATソルバでいう基数制約)で記述します。AND/ORという非線形演算子は備えていないので、そういったオペレータが多いインスタンスは苦手です。で、何が得意かというと、

■数を数える

■解空間が狭い問題

が得意です。SATソルバが苦手な分野を補完しえるということです。Simplexや内点法といったLpソルバのリニア解を近傍探索するアプローチを取っています。基本、数を数えることしか出来ないのですが、それでも人間が作るインスタンスは、リニア解が近い傾向があり、解空間が狭い、地球上の一つの砂粒を探しだすような最適化問題には、LPソルバをベースにした方法しか考えられません。人間が扱うような問題は、リニア解近傍に最適解が存在することが多い、ということを前提としています。SATもMIPもランダムな制約には、全く持って歯が立たないのですが、現実の人間の営みのなかにあるエントロピーがそうさせているのでは?と考えています。

<ナーススケジューリング問題についてあてはめると>

スタッフ一人一人をRosterと言います。スケジュールナース用語では行制約ですが、Roster内演算は、多数のAND/OR演算が主で、僅かに公休数とか夜勤数といった数を数える場面があります。

一方、組織の品質を求める縦制約(列制約)については、ほぼ数を数えるだけです。つまりLPソルバにやらせた方が得策、ということになります。

従い、Rosterをサブ問題として、AND/OR演算を隠ぺいし、列制約を主問題としてLPソルバで扱うのが、一般的ナーススケジューリング問題に対する理にかなったアプローチ、ということが言えます。


<今後の潮流>

MIPでもなくSATでもない、否、MIPでもありSATでもある、新しい形態の数理ソルバが今後の厳密解ソルバの主役になっていきます。

現在、超大規模用にRefineする必要があり、一つ一つの求解部品を丹念に設計し直し組み上げていく作業の途中です。

オープン問題を全問解いたあとに論文化を予定しています。10年の研究成果が出るかどうかは未だ分かりません。

厳密解が分かれば、新しいメタ解法の開発に役立つと期待されます。



2025年10月26日日曜日

重い制約と軽い制約

 重い制約とは、ソルバ負荷が大きい制約のことを指します。軽い制約とは、ソルバ負荷が軽い制約を指します。ソルバ負荷が大きいとは、それを制約するのにメモリを食う制約を言います。メモリを食うというのは、一般に探索空間が大きい制約になります。探索空間とは、探索する状態の数を指します。つまり、ソルバ負荷が大きい制約は、探索するべき状態の数が大きい制約のことです。

およそ最適化シフト勤務表において、何が重い制約かは、ソルバの種類によらず一定の傾向があります。ここでソルバ種類とは、

■MIPソルバ(数理ソルバ)

■SATソルバ(MaxSATソルバ)

■メタヒューリスティクスソルバ

を指しますが、こういった種類によらず普遍的に重い制約を指します。重い制約とは、

1)シフト数が25を超える

2)パターン制約においてパターン長が長い

3)最大ー最小制約において最大値が大きい

になります。具体的には、パターン長で1週間を超えるような制約は避けるべきです。最大ー最小については、10個を超えると負担になってくるようなイメージを持っています。

勿論必要な制約であれば、使って構わないのですが、不要な負担は出来るだけ避けて頂くのが求解速度の関係で吉となります。

1)シフト数

シフトの割り当ては、1日に1個です。シフト数が2個なら 2状態しかありませんから全く負担にはなりません。シフトが32個あったとすると、32シフトのなかから1個を選ぶ必要があります。言い換えると1個以上かつ1個以下である必要があります。つまり、1個以上のORと取って、かつ全ての2個の組み合わせを禁止する必要があります。そうなると32C2の組み合わせを禁止する必要があり、32C2=32*31/2個分の組み合わせを禁止しなくてはいけません。2状態に対して指数関数的に状態空間が増えます。Days*Staff分で効いてきます。これが、最適化シフト勤務表においてシフト数は出来るだけ少なくしてください、と言っている理由です。

2)最大-最小制約

例えば、一カ月のうち、1日だけ働くを制約してみましょう。その組み合わせ状態数は、31C1で、31通りです。これに対して、16日働くことにすると31C16で601080390通りの組み合わせが存在します。これは、大変そうだな、というイメージになると思います。でも一カ月のうち30日働くは、31C30=31に過ぎません。なので、必ず大きな数程負担という訳ではないということになります。

特に、SAT系ソルバは、この制約がネックになることが多いです。

3)パターン長

何故長いパターンは負担なのでしょうか?シフトが2状態しかないABというパターンは、2状態のTreeで表現出来ます。



これが、4パターン長(16組み合わせ)では、


5パターン長(32組み合わせ)と増えていくと以下のようなイメージとなります。


7パターンは、以下です。



これが、1週間のパターン長での話です。指数関数的に組み合わせ状態数が増えて大変そうだな、ということを分かって頂けると思います。たった2シフトでのグラフですが、最初の1)シフト数が大きいと、さらに複雑なグラフとなります。シフト数が2)線形制約、3)パターン長、全てに効いてきます。


例えば、スケジューリングベンチマークinstance15では、

とありますが、これらは2パターンに過ぎず、ソルバの負担は軽いです。

しかし、以下のNo1.時間制約と、E6のシフトパターン制約は、重い制約の部類となります。



この中で最も軽い制約は、E7/E8 次いで、E5<E4<E3の順となります。



2025年10月25日土曜日

法政大学 野々部先生の講演

いつの間にか、久保先生とMOAIという会社を立ち上げられたようで、拝聴しました。

組合せ最適化問題に対する実用的アプローチ(第5回 MOAI研究部会 8月5日) - YouTube

面白く聴かせて頂きました。メタヒューリスティクスの実装の中身をここまで詳しく解説されているのは、見たことがありません。メタヒューリスティクスは、古くて新しい潮流があると思います。新しい潮流部分、戦略的摂動等について述べられているのが興味深いと思いました。「feasibilityの境界付近に最適解は存在する」は、確かに私も似たような経験をしたことがあったと思います。

野々部先生は、ナーススケジューリングコンペティションⅠで入賞されています。野々部先生のアルゴリズムは、Nuoptにも搭載され我が国におけるメタヒューリスティクスの第一人者です。

muc15_CR6_2.pdf



2025年10月24日金曜日

Highs Hypo

 A factorisation-based regularised interior point method using the augmented system

Highsの新しいIPMソルバの実装論文が出ました。

インスタンスによっては、10倍程度の向上もあったようですが、平均的には、期待したほどではありません。Leading SolverのCOPTとかの比較が論ぜられていないので、性能の相対位置が分からないのですが、トップとは未だ相当の性能差があると思います。監修者のJacek Gondzio氏は、IPM業界の重鎮でありIPMに関する論文を数多く出していて、期待していたのですが残念な結果となりました。

IPMは、旧新両方残るようです。旧IPMは、CROSSOVERなしにBasicSolutionを得ることが出来ます。(通常のIPMがCROSSVOERで時間を食ってしまうことを回避できるメリットがあります。)

一方、CuoptのBarrierは、GPUによる実装です。以下に記述があるのですが、GH200は、F1仕様のGPUで

NVIDIA GH200搭載のサーバのお値段 - Vengineerの妄想

であり、市井のGPUでどうなるか良くわかりません。

Solve Linear Programs Using the GPU-Accelerated Barrier Method in NVIDIA cuOpt | NVIDIA Technical Blog


いずれにしても、Cuoptは、高速化したPDLPX、IPMにしてもGPUによるDirect factoring が魅力であり、WSL2で試してみる必要があると考えます。(欲しいのは業界最高性能のLpソルバです。)

課題がまた増えてしまいました。

■整数化課題

■開発ソースをGCC化

■VisualStudio2022 WSL2で、Cuoptを評価、実装

これでは、年内かかってしまうと思います。しかし、業界最速のLpソルバであることは、間違いないと思います。これで時間さえかければ、最後に残った超大規模のオープンナーススケジューリング問題(探索空間10の82911乗,宇宙の素粒子の数は10の100乗程度)を解ける筈です。なんとか年内に解決したいと思います。こんなにも早く実装して頂いたNVIDIAのChristopher Maesさんに感謝したいと思います。