スケジュールナースのブログ: 時間制約の改善

2019年10月31日木曜日

を119Aで行いました。118A 以前では、プロジェクトサンプル特養で、Python記述と時間制約では、4-5倍の差がありましたが、ほぼ同じ時間となりました。これにより、Pythonで記述しなくてもよくなりました。

ところで、時間制約のほかに、夜勤回数、日勤回数、半日回数を下記のように
制約しています。

夜勤回数は、夜勤回数を6回にしないために必要な記述です。その他は、158.5h-160.25hを保証する意味では、必要がない記述です。

そこで、もし、時間制約以外の制約がないとどうなるかやってみました。

案の定、158.5-160.25hを満たす、夜勤回数、日勤回数、半日回数は、上記に限定されず多くの組み合わせが存在することが分かります。

このとき、時間は、34secかかりました。解空間は広がりますが、探索空間も制約が付加されないので広がることに注意します。Algorithm1の場合、かかる時間は、比＝解空間/探索空間　に

反比例する方向ですので、時間がよりかかったと推測されます。ともあれ、Pythonで気を配る必要がなくなったのは良い方向だと思います。　

schduling benchmarksからの結果です。目的関数値は、Instance13を除いて、さして改善していません。悪化している場合もあります。しかし、解が出るまでの時間は、例外なく短くなっています。

Note:１）Algorithm1の比較であることに注意してください。Algrorithm4では、時間をかければ、KnownUB値を得ることは可能です。

２）１１９Aでバグがあり１２０Aで修正しました。

スケジュールナースのブログ