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で得られていますが、同規模のどんな問題でもいつも得られるということでもありません。）さらに、量子アニーリングで、下界を得ることは難しいと思うので、当面シフトスケジューリングにおける数理的アプローチの地位は揺るがないと思っています。