Benchmark 評価

http://www.schedulingbenchmarks.org/

のうち最初の8題をやってみました。
最後の1題を除いてOptimum値が一致しました。

最後の1題、Instance8は、ベルギー、ルーヴェン・カトリック大学 Pieter Smetさんによる新しい解がOptimumとされています。　（CPLEXでも最適値は求まっていません。）

それまでは、長らくノッティンガムの1308という解がBestでした。私の解(開発中エンジン）は1301で、下記値と一致していません。サイトには、解のファイルも置いていますが、残念ながら、最新の結果を反映したものではありません。

そこで、Pieter Smetさんにお願いして、解を頂いて解析することにしました。
→頂きました。なおPieter Smetさんの論文は、レビュー中であり未だオープンになっていないそうです。

下記インスタンスは、去年のRAMP講演でも発表しましたが、SATにとって苦手なインスタンス郡です。厳密解が得られたのは、Instance1のみで、その他は、近似解で、規模が大きくなるに従い乖離
が大きくなる傾向にありました。

Instance	Weeks	Employees	Shift types	Best known lower bound	Best known solution
Instance1	2	8	1	607	607
Instance2	2	14	2	828	828
Instance3	2	20	3	1001	1001
Instance4	4	10	2	1716	1716
Instance5	4	16	2	1143	1143
Instance6	4	18	3	1950	1950
Instance7	4	20	3	1056	1056
Instance8	4	30	4	1300	1300