Search Spaceとは？

AutoRosterの左下に表示されている　Search　Spaceは、どのように計算しているのかを、シフトスケジューリング界の重鎮Tim Curtoisさんに聞きました。

Concerning the 10^17367, I imagine that it is possible to assign any shift to any person on every day. This is a relaxation but the value is an approximation so the basic formula is:

(ShiftTypes+1)Days x Employees

e.g. for instance21 = 9182 x 100

But I convert it to a power of 10 using

10Log10(ShiftTypes+1) x Days x Employees

私の計算式でも、(Shifts+OffState)**(26weeks*7days*100Staffs)で、

(8+1)**(26*7*100)=1.635580016513425644305E+17367

確かに、10の17367乗となり一致しています。（この計算結果は、計算サイトによります。）

ここで素晴らしい点は、厳密解であることです。すなわち、21133より良い解がないことが証明できていることです。全宇宙の原子数は、１googol(1e100)以下とされているので、それよりも遥かに大きい探索空間での最適解であります。よく量子アニーリングで現在のコンピュータで計算すると何万年という表現が出てきます。確かに一つ一つの解を地道にチェックしていったらそうなりますが、現実のPCでも上記のような広大な探索空間での最適解が得られることもあります。（数時間のRunで得られていますが、同規模のどんな問題でもいつも得られるということでもありません。）さらに、量子アニーリングで、下界を得ることは難しいと思うので、当面シフトスケジューリングにおける数理的アプローチの地位は揺るがないと思っています。

5800XCPUクーラを変更

CPU温度が92度あったので、安物のCPUクーラを無限五に変更しました。

温度は収まりましたが、今度は、思ったようにマルチスレッドが動いてくれません。

恐らく、大規模では、3次キャッシュも効かなくてDRAMからの到着待ちが多数発生するためと推測しています。Instance22以上の超大規模（期間1年、スタッフ数50人以上）問題には、さらにアプローチの仕方を工夫する必要があることが分かりました。

グラフ圧縮

 Instance23以上では、Graphが重過ぎて64GBあるシステムに載りません。そこで圧縮して一旦Diskに保存し、使用時に伸張展開する方式としました。しかし、LZ4で圧縮してみると、圧縮率が75%程度と思わしくありません。そこで、ZSTDに切り替えてみました。すると50%程度と、2倍程度の圧縮率となりました。

void Roster::decompress_fm_disk()
{
	string s = get_depth_map_filename();
	ifstream fin(s.c_str(), ios::in | ios::binary);
	if (!fin) {
		throw std::runtime_error("can not open compressed file!\n");
	
		return ;
	}
	char* src = new char[compressed_size];
	char* dest = new char[decompressed_size];
	uint64_t elements = decompressed_size / sizeof(uint64_t);
	void* eptr = my_alloc.allocate(sizeof(dd_struct_base_value),elements);
	dd_struct_base_value* zptr = reinterpret_cast(eptr);

	try {
		fin.read(src, compressed_size);
	}
	catch (...) {
		throw std::runtime_error("Read Error while reading compressed file.\n");
	}
	fin.close();
	int dest_size= ZSTD_decompress(dest,decompressed_size,src,compressed_size);
	if (!dest_size) {
		throw std::runtime_error("Read Error while reading compressed file.\n");
	}
	assert(dest_size == decompressed_size);

シーケンシャルRead(６GB/sec)という高速SSDを用意してタスクマネージャで、観測してみると、なんと転送されている様子が観測できません。あっさりキャッシュされているという落ちでした。

なお、プレテストを行ってみたのですが、Instance22/23共、これまでのLBは、更新できました。

しかし、この現象は、メモリに比較的余裕があるInstance23のみの話です。Instance24では、載り切らないはずですので、観測できると思います。

ScheduleNurseⅢ breaks the world record of Instance15 in Scheduling Bechmarks

 ScheduleNurseⅢ has updated the lower bound of Instance 15 from 3829 to 3830. The upper bound is 3831, so only one step is required to reach the exact solution. Unfortunately, it took around 100 hours to get the value due to the enormous branching tree. I think that is the final answer of ScheduleNurseⅢ.

ScheduleNurseⅢ breaks the world record of Instance21 in Scheduling Bechmarks

 

LB=21133 ,UB=21133

Machine :Ryzen5800X 3.8GHz(8cores)

ScheduleNurseⅢ has found the optimum solution in the search space of 10th power of 16367! 

Many researchers have tried to solve the problem for the past seven years, but no one could not have solved it exactly. Then, finally, ScheduleNurseⅢ made it.

ScheduleNurseⅢ breaks the world record of Instance15 in Scheduling Bechmarks

 Applying a new branch algorithm, I found the new record on instance 15 in scheduling benchmarks within 20minutes.

Machine:E3-1226V3 3.3GHz

I ran several hours, but I could not find any better solution beyond 3831.

It looks pretty long-running will be required to update the current lower bound 3829 because the branching tree is enormous. 

Instance20速度改善

 これが一連の改善シリーズ最終版の結果となります。

マシン：E3-1226V3 3.3GHz

改善前：2023sec

改善後：1353sec

Branch方法改善によるものです。Gurobi/Cplexとも比較してみました。

Gurobiは、厳密解に到達しましたが、Cplexは、到達しませんでした。（JobTimeout)　この傾向は、Instance13でも見られました。Gurobiは、計測する度に速度を上げているので、数年後には、追い越されているかもしれません。

Branching Treeの可視化

 Algorithm4のデバッグをしていて必要になったので作りました。定番のGraphVizで可視化しています。このツールは、Verilog　Simulatorでもお世話になっていて使うのは10年振りくらいです。

Instance8のBranching　Treeです。このインスタンスの厳密解はLB=UB＝1300が知られています。Branchingを行うのは、最適解、すなわち目的関数値が最小になる整数解を得るためです。連続変数での緩和解は、ROOT　Nodeの値1296.57として得られています。

で、Branchingを行って、それまで得られた最小の整数解以上の目的関数値だった場合、そのノード以下は調べる必要がないという状況が生まれます。これをPruneすると言います。PruneしたNodeでは、子Nodeがありません。たとえば、So Far　UB=1300が得られている状況で、連続緩和解1299.1が得られたとします。重みの種類は1,2３,100であるとすると、整数解の目的関数値は1300が有りえる値です。その値は既に得られているので、もはやそのNode以下は見る必要がない、ということになります。

そう風に、ありえる全てのノードを調べて最適解を探します。一般にNodeを下降していくと、LBは上がって行きます。あるレベル（段）では、もうこれより小さなLB値は有り得ないということが分かります。そうすると全体のLBも上げることが出来ます。また、Prune効果によって、調べるべきNode数も減少していき、ついに調べるNodeがない(Empty)状態になったとき、LB==UBの証明、となる訳です。

組み合わせ最適化で爆発するのは、このBranching　Treeが調べても調べてもNodeが増え続ける一方という状況です。こうなると有限の時間内に最適解を見つけることができないので、LBとUBの間にGapが生じたままになります。よく論文でGAPが何％以下になった、という記述がありますが、これは、調べるべきNodeをEmptyに出来なかったという裏返しでもあります。

LBに近いLBが最初から分かっていれば、PruneできるNodeが増えて、結果的に調べるNode数を減らせるので嬉しい状況です。その目的の為、ヒューリスティクス解を使うのも良くやる手法です。また、出来る限り早期にLBに近いUBを得たいので、最初はDFS(Depth　First　Search)を行うのも常道手段です。

こういった手順を踏むので、最初の実行可能解が得られる時間が長いのがAl4の特徴です。また得られる整数解は、離散的にしか得られません。(AL1みたいに一個一個減りません)

しかし、Al1では難しいインスタンスでも、時間をかければ厳密解に到達する可能性が高いのが特徴です。今回のRefactoringは、昨今のManyCore環境を生かしたコンセプトになっており、コア数が多ければ多いほど高い能力を発揮します。コア数が増え続けるのは今後も変わることのないトレンドでしょう。主体はAL1で変わらないとは思いますが、AL4を使う場面も多くなってくると予想しています。

塾時間割りGithub

一連のプロジェクトファイルをUploadしました。

 Schedule_Nurse3_Gallery/Japanese/プロジェクトサンプル/タスク勤務表/塾時間割 at main · sugawara-system/Schedule_Nurse3_Gallery · GitHub

にOriginalを含めてExcelファイルも同封しています。

プロジェクトファイルだけでしたら、スケジュールナースⅢでもダウンロード可能です。

    ファイル⇒Githubプロジェクトを開く

で、下記画面となります。塾時間割フォルダにあるファイルを選択してダブルクリックです。

プロジェクトファイルをロードした状態では、プロジェクトファイル名がついておりません。求解する前に名前を付けて保存してください。

今後、ユーザContributionプロジェクトファイルを拡充していこうと思います。

塾の時間割作成問題その３

 求解して、下記のように、右クリック、全て挿入で、1限、2限..毎、国語、数学、英語の講師数が表示されます。

＜シフトとフェーズの関係＞

設定⇒フェーズ定義、シフト定義、予定入力をクリックすると下の状態になっています。

シフトWorkの定義は、1限から4限までフルに働くパターンを表しています。

PH1３は、１限から３限まで、PH24は、2限から４限までの3単位の連続時間業務を表しています。

PH12,PH23,PH34は、2単位の連続時間業務を表現しています。４個のあらゆる組み合わせを考えると4C4, 4C3,4C2,4C1のパターンが考えられます。必要ならここでパターンを増やしてもよいし、不必要ならパターンを削除すればよいです。とりあえず、defaultのまま話を進めます。

Workシフト(ラベルW)には、必ず4個のタスクで埋める必要があります。（必ず埋める必要があるので、空きタスクを前に定義しました。）また、PH12シフトでは、1限から3限まで3個のタスクで満たされる必要があります。

＜予定は未だ入力されていない＞

元のExcelでは、

となっていますが、未だ入力されていないことに注意してください。ソルバは、入力がフリーであるとして、解を求めています。つまり、上記予定が入っていないので、真の欲しい解にはなっていません。

＜上を入力しただけでは不十分＞

安藤さんは、すべてフルタイムだからWで埋めればよい、朱沢さんは、月水金に、３４限だけなので.. という風に手で変換しながら入力したのが下です。

これで求めた解が下です。

確かに、予定が入っているシフトには、全て何らかのタスクが割りあてられていますが、それ以外にもシフトが入っているところがあります。スケジュールナース上の予定は、予定固定の意味です。入っていないところは、フリーです。ですので、上のExcelに対応させるには、休みシフトを定義して入力　求解して、

とすることが必要です。

ようやく、これで、所望の解を得ることが出来ました。

塾の時間割作成問題その４

 ＜ハード制約とソフト制約＞

必ず実現するべき制約をハード制約といいます。一方出来れば、かなえたい制約をソフト制約と言います。ハード制約を満足できる解が発見できないときは、解そのものが出ません。ですので、ハード制約は必ず実現できなけれいけない制約でもあります。

今回の塾問題の場合、何があっても、受講者には必ず講師が割り当てられないと考えると、各時限の講師者数はハード制約となります。一方で、講師側のシフト希望も現状ではハード制約なので、容易に解がない状況が考えられます。スケジュールナースの場合、予定も含めて殆ど全ての制約がソフト制約化が可能になっていて、求解での様子を見ながら変えることができます。とりあえず、列制約をハード制約化したのが、下です。Defaultでは、ソフトレベルが定義されていますが、それをクリアするとハード制約になります。

＜空き時間を最小化する＞

行制約の空きタスクをパターン禁止にします。これがハード制約だと、当然解が無くなってしまうので、必ずソフト制約にする必要があります。ソフトレベルは、インデックスであり、重みではありません。インデックスに対応した重みは、求解時に指定します。

＜求解結果＞

画面左上行制約１が、上のインデックス1に対応します。チェックがブランクになっていると思いますので、チェックを入れます。重みは1のままで結構です。

結果、Errorsが29、Cost(目的関数値)が29となりました。結果か出方から見て、これは、厳密解で、これを下回る解は存在しません。

＜行制約:1の適用を外してみる＞

チェックを外すとそのソフト制約は、制約そのものがない、として扱われます。そうして、求解すると、目的関数値はソフト項がないので出てきません。で、空き時間を地道に目で数えていくと、同じ29個ありました。

＜結果の解釈＞

ソフト制約化によって、パターンを禁止したのですから、目的関数値が最小になる方向に作用するはずです。その効果がなかったということは、恐らく、シフトを固定にしているために、改善の余地が殆どない、ということではないかと思います。

＜改善の余地　シフトor休み入力＞

シフトは、何らかのタスクが埋め込まれる必要がありました。現状の予定では、シフトが空きタスクで埋まってしまうことがあります。そこで、予定の入力の仕方を変更し、予定自体は、ハード制約のままですが、例えばWまたは休みという入力の仕方に変更します。こうすれば、空きタスク最小化の効果により、休みシフトになる場合も出て来るでしょう。

上がその結果で、目的関数値は、21まで減少させることが出来ました。また、行成約:1のチェックを外して、制約を無効化すると、空き時間は、25程度となりました。よって最小化の効果が出ていることが確認できました。なお、結果から見てこれも厳密解だと思われます。

以上でこれが、空き時間最小化の解です。（同じ目的関数値の別解も容易に得られます。）

塾の時間割作成問題その５

予定入力付きのシフトの最小化は、前回でその答えは出ています。

そのままでは、自由度が少ないので、全くフリーの状態では、どのような解になるか、興味があったのでやってみました。

やり方は、簡単で、予定入力をクリアすればよいだけです。

さすがに、空き時間は5個と少なくなりました。しかし、決して0にはならないということが分かりました。

＜なるべく連続シフトで＞

空きタスクをなるべく挟まない形を記述追加しました。

業務は、英数国の集合です。

結果は、

たまたまなのかは、分かりませんが上記解はありました。（本来はソフト制約とすべきでしょう。）

以上、スケジュールナースⅢによるハードおよびソフト制約化について見てきました。勤務表の観点は、雇用者側と、スタッフ側の要求と相反するものがあり、どの辺にバランスを取るかというのは、管理者次第です。制約化も千差万別であって、ある職場にとっての正解が必ず別の職場でも正解になるものでもありません。また組み合わせ問題の最適化という性質上、やってみないと(RUN）してみないとどんな具合か分からない、予想がつかない、という厄介な性質もあります。

スケジュールナースでは、このトレードオフ問題に関して、予定制約のソフトレベル化（予定に優先度をつける）あるいは、禁止化(希望を書くのではなく禁止を書く）、という提案を行っています。なるべく広い解空間で、なるべく良い解を探す、という発想です。

以上勤務表ソフトを使った塾の時間割作成の紹介でした。

塾の時間割作成問題その２

 前回Import用のExcelシートを作成しました。今回は、そのExcelファイルをインポートして、プロジェクトファイルを作成するところまでを行います。

タスク勤務表スキル付きプロジェクトを立ち上げます。

前回、整形したExcelファイルをインポートします。

ウィンドウの設定⇒Excel取り込み出力設定⇒Excel取り込み設定⇒ファイルパス

で、前回整形したExcelファイルMyタスク勤務表4phaseを指定⇒取り込みボタンをクリックします。

予定入力をクリックすると(隠れている場合は、ウィンドウズの設定⇒カスケード等で表示させる）次のように国数英の予定が表示されます。

なお、上のように数値部分が上手く読み取れない場合があります。その場合は、Excelからコピペしてください。

その他のプロジェクト設定変更点は、以下の青部です。

■ハード列基数制約のソフト化をオフ

■最終タイムアウトを 30⇒1

にしています。

求解ボタンを押すと1秒未満で、下記画面になります。

ファイル⇒名前をつけて保存

でプロジェクトの完成です。

塾の時間割作成問題その１

 https://qiita.com/e-yudana/items/dab6bc76d9ff41d551f5

を解いてみます。

スケジュールナースⅢにこの問題をどのようにマッピングさせるかが、まず最初の問題です。

講師の勤務希望は下のようになっています。1日を４Phaseに分けると良さそうだという

ことが分かります。

また、担当科目は、

となっています。ということで、フェーズ-タスクタイプの勤務表にすれば良さそうだ、ということが分かりました。

ゴールがあった方が分かりやすいと思います。

下記が実装したプロジェクトの様子です。

イメージし易くなったのではないでしょうか？

月から土まで、1限から4限まで、必要な人数を過不足なく確保すればよい、という問題です。

ただし、国語とか数学のスキルが必要なので、スキルを持った人を確保する必要があります。また、その人数は、各日、各限で違います。

この問題は、たまたま、受講生と講師が1-1でマッピングされるので、この形式にマッピングできました。（受験生と講師のマッピングは、ほぼ自明扱いとしています。。受験生の名前は、入力不要です。）

　現スケジュールナースⅢのユーザは、大半がシフトタイプタイプですので、少し奇異に感じる方もいるかもしれません。フェーズタスクタイプ型というのは、1日のうちで、複数の仕事を行う場合に適した勤務表です。予定が、タスクと、シフトと二つあるのが特徴です。マニュアルはこちら

Pythonは、全く使っていません。GUIのみで解くことは可能です。

問題は、

どのようにしてExcelから上記プロジェクトにマッピングするか？

です。最も近いExcelは、タスク勤務表4Phaseとタスク勤務表2Phaseスキル付きです。

これらを作業フォルダにコピーしておきます。下記はインストールしたスケジュールナースⅢで、ファイルを開くで、全てのファイルで、Excelファイルを表示させています。

タスク勤務表4Phaseを編集します。最初は、スタッフ名です。

次に稼働日です。月曜から土曜なので、2021年11月1日-11月6日に設定しました。

表示開始日は制約開始日にしました。不要な予定はクリアします。

＜タスクスキル属性>

このシートは、タスク勤務表4Phaseにはありません。タスク勤務表2Phaseスキル付きからコピーして、次のように編集します。空き時間は、その名の通り空き時間です。通常の、業務形態の場合、なんらかのタスクで埋められるのが普通ですが、このプロジェクトの場合、空きタスクを定義しないと、解がない状態になってしまいます。全てのスタッフがこのスキルを持つ必要があります。

＜工程人数＞

編集して以下のような表にします。

手で行うのも大変なので、受講管理表データをExcel内で合算して、それをコピーするようにしています。

以上で、整形したExcelをインポートする準備が完了しました。

＊その２からその５まで解説はあります。

GithubにオリジナルのExcelファイル、使用したExcelファイル、プロジェクトファイルを置いています。

時間割り作成問題

 池上先生のチュートリアル論文が参考になります。

untitled (orsj.or.jp)

現状では、CPLEX/Gurobi等の数理的ソルバーを使って解くことは難しく、ヒューリスティクスが主体みたいです。また、時間割について競技会(Timetabling Competition)も過去5回行われています。(NurseSchedulingCompetitionは過去2回）

PATAT - International Conference on the Practice and Theory of Automated Timetabling (patatconference.org)

スケジュールナースは、時間割のソルバーではありませんが、タスクや、Pythonを用いることで、簡単なモデルでしたらモデル化できるかもしれません。前回もそうでしたが、スケジュールナースは、単純な勤務表のみに留まらず、既に、工場の生産計画、人材派遣業務、放送局のシフト割、等でも使われています。数独も応用のうちの一つですが、時間割もその一つになるかもしれません。

Qiitaで、面白そうな問題があったので、解こうと思っていたのですが、世界記録更新の方に眼がいってしまい手付かずになっていました。Algorithm３ソルバーは、基本アルゴリズムが完成しつつあり、検証のための時間待ちが多くなってきました。空いた時間で、この問題を解いてみたいと思います。