2019年10月31日木曜日

時間制約の改善

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

 118A119A
Python制約あり19sec19sec
Python制約なし92sec24sec

ところで、時間制約のほかに、夜勤回数、日勤回数、半日回数を下記のように
制約しています。
 
夜勤回数は、夜勤回数を6回にしないために必要な記述です。その他は、158.5h-160.25hを保証する意味では、必要がない記述です。
そこで、もし、時間制約以外の制約がないとどうなるかやってみました。
案の定、158.5-160.25hを満たす、夜勤回数、日勤回数、半日回数は、上記に限定されず多くの組み合わせが存在することが分かります。
このとき、時間は、34secかかりました。解空間は広がりますが、探索空間も制約が付加されないので広がることに注意します。Algorithm1の場合、かかる時間は、比=解空間/探索空間 に
反比例する方向ですので、時間がよりかかったと推測されます。ともあれ、Pythonで気を配る必要がなくなったのは良い方向だと思います。 
 schduling benchmarksからの結果です。目的関数値は、Instance13を除いて、さして改善していません。悪化している場合もあります。しかし、解が出るまでの時間は、例外なく短くなっています。
Note:1)Algorithm1の比較であることに注意してください。Algrorithm4では、時間をかければ、KnownUB値を得ることは可能です。
2)119Aでバグがあり120Aで修正しました。
 

 Algorithm1
 118A 120A Known UB
Instance9441141(sec)539113(sec)439
Instance104834213(sec)4842170(sec)4631
Instance1339442109(sec)3285(1042sec)1348
Instance141522235(sec)1421209(sec)1278
Instance155249412(sec)5135331(sec)3225
Instance194825616(sec)5035483(sec3149

 

0 件のコメント:

コメントを投稿