この記事は、Fusic Advent Calendar 2024 5日目の記事です。
こんにちは！Fusic 機械学習チームの塚本です。
機械学習モデルの開発から運用までなんでもしています。もし、機械学習で困っていることがあれば、気軽にお問い合わせください。
以前、JSPのためのグラフ表現という記事を出しました。
そこでは、キチンと定式化を行ったり、CBCを使って厳密解を求めるなどやっていました。
今回は、定式化や実装部分をおおよそカバーされているFixstars Amplify SE(Scheduling Engine)を使って実装していきます。
実装と言っても、書いた通り、ほとんどがライブラリ内でカバーされていて、我々は変数やデータを準備するだけでいいと言ったものになります。
Fixstars Amplify SEについて
スケジューリング問題をサポートするもので、
実際にこちらのDocumentにも
スケジューリング問題
スケジューリング問題とは、複数のジョブ (Job) とそれらを処理する複数のマシン (Machine) のスケジュールを決定する問題です。 1つのジョブは、指定されたマシンで指定された時間、複数の処理 (Task) を実行し、すべてのタスクが完了するとジョブが完了します。
と記載があります。
最適化問題の中でもジョブショップスケジューリング問題が対象となっています。
今回は問題例として前の記事を参考にするので、別にソルバーとしてCBCを使ってもいいですが、試してみようということでこれを使います。
問題設定
今回は上の記事で書いたもののベンチマークを使って検証していきたいのですが、なぜかアクセスできないようになっています。
自分は手元にあったので使いますが、以下のサンプルなんかを試すのが無難かと思います。
Fixstars Amplify SE(Scheduling Engine)
実装
文字の定義などは前回の記事同様のものを使っていきます。
# Gc: Conjunctive グラフ
# M: マシン
# J: ジョブ
from amplify_sched import Model, Task
token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
model = Model()
for machine in M:
model.machines.add(machine)
for job in J:
model.jobs.add(job)
for operation in O[job]:
machine, _ = Gc.in_edges(operation)
model.jobs[job].append(Task())
model.jobs[job][-1].processing_times[machine] = t(operation)
gantt = model.solve(token=token, timeout=1)
fig = gantt.timeline(machine_view=True)
# pngで出力
fig.write_image("gantt.png")
# htmlで出力
fig.write_html("gantt.html")
前回の記事では、定式化したものをそのままモデリングしています。
そこそこな量を書かないといけなくなったりもするので、こう言ったオーソドックスなものを簡単に得られるのは便利ですね。
計算時間
Timeoutの設定で求解時間の設定はできるようです。
長く計算させれば精度も上がると思います。
実行してみた結果、手元にあるmachine x job = 20 x 20でほんと一瞬で解が出ます。
精度確認などやってみたいですが、ベンチマークサイトが見られないので、比較が難しいので今回はやりませんが、実際に導入する際は試すべきかなと。
JSPは基本的にNP困難なため、ヒューリスティックに解くことが一般的です。
そもそも計算環境に差があったり、ソルバーの仕組みが違ったりで、単純な比較はできませんが、
CBCでは10x10の問題でも解くのが難しいです。
今回は単純なJSPでしたが、他にもdeadlineの設定や、空き時間の設定など結構細かい設定もある見たいです。
目的関数をいじれるようになるといいなあと思いつつ、そこまでしだすと自分で実装した方がいいということなんでしょうね。
全てのマシンの稼働率が均等になるようにみたいな均等にしたいみたいな要望って多かったりするので、オプションで複数目的関数が選べると嬉しいなあと思ったり。。。
地味に嬉しい点として、結果の図が簡単にできるところです。
簡単なデモとしてみやすいですし、バグの確認とかもこういう図とかでみられた方が良かったりもしますしね。
例えば、本番導入はたとえ使わないとしても、データの検証に使ってみたりなどの用途でも使えたりするかもしれません。
Discussion