ジョブショップ・スケジューリング選手権 ―― 貪欲・焼きなまし・遺伝的アルゴリズム・厳密解を同じ問題で競わせる

工場やプラントでは、どの仕事をどの設備で、どの順番で流すかをいつも決めています。同じ機械を複数の仕事が取り合うので、順番の付け方ひとつで全体の終わり時刻が変わります。この工程の順番決めは、ジョブショップ・スケジューリングという名前で古くから研究されてきた最適化問題です。

私は産業機器まわりと、Python でのソフト作りの両方に携わってきました。この記事では、その立場から、同じジョブショップ問題を貪欲法・焼きなまし・遺伝的アルゴリズム・厳密解の 4 つで解いて、どれがどれだけ良い段取りを、どれくらいの計算時間で見つけるかを比べてみます。問題も解き方もすべて Python で自作しました。外部のベンチマークデータは使わず、固定シードの乱数で問題を作っているので、同じコードを走らせれば同じ問題と同じ探索を再現できます。ただし、計算時間や、あとで出てくる打ち切り時の探索量は、動かす計算機によって変わります。

結論を先に書いておくと、小さい問題ではどの解き方も同じ最適解に並び、規模が上がると成績に差が出ました。そして、いかにも賢そうな遺伝的アルゴリズムが、いつも上位に来るわけではありませんでした。

ジョブショップとは何か

問題の形はこうです。n 個の仕事（ジョブ）と m 台の機械があります。各ジョブは m 個の工程（オペレーション）の列で、k 番目の工程は決まった機械を、決まった時間だけ占有します。ジョブの中では工程の順番を守らなければならず、機械は一度に一つの工程しか処理できません。目的は、すべての工程が終わる時刻、つまりメイクスパンをできるだけ小さくすることです。

ごく小さな例で、順番が効くことを見ておきます。仕事 A と仕事 B があり、どちらもまず機械 M0、続いて機械 M1 を通るとします。M0 での加工は A が 2、B が 4、M1 では A が 4、B が 2 かかるとします。M0 に A を先に流すと全体は 8 で終わり、B を先にすると 10 かかります。A を先にした場合を追うと、M0 は A を 0 から 2、B を 2 から 6 に流し、M1 は A を 2 から 6、B を 6 から 8 に流せて、8 で終わります。同じ二つの仕事でも、共有する M0 をどちらに先に使わせるかだけで、終わりの時刻が変わります。ここでは短いほうを先に流すと得でしたが、この直感がいつも正しいとは限らないことは、あとで出てきます。

ソフトウェア寄りの言い方に直すと、排他制御が要る共有リソース（機械）を、依存関係（工程の順序）のあるタスク群に割り当てていく問題です。ロックを取り合うタスクの依存グラフ、と言い換えても近いと思います。

言葉だけだと掴みにくいので、6 台 6 ジョブの例をひとつ解いて、スケジュールを図にしてみます。

横軸が時間、縦の各段が一台の機械です。色がジョブ、帯の一つ一つが工程です。どの機械も帯が重なっていないのは、一度に一つしか処理できないからです。どの機械でもかまわないので、いちばん右で終わっている帯を探すと、その右端がメイクスパンにあたります。図では右端の破線がその位置で、この例では 43 でした。段取りを良くするというのは、この破線をできるだけ左に寄せることです。

こうした問題は、機械加工の工程や、塗装や検査のラインなど、設備をまたいで順番に加工していく現場ならどこにでも顔を出します。特別な業種の話ではありません。

解を表す方法と、良さの測り方

解き方を用意する前に、スケジュールの表し方を決めます。ここではオペレーション列という素直な表現を使いました。ジョブ番号を、そのジョブの工程数だけ並べた列です。たとえばジョブ 0 が三回出てくれば、一回目がジョブ 0 の一工程目、二回目が二工程目、という具合です。もう少し具体的に、ジョブが二つでどちらも工程を二つ持つなら、[0, 1, 1, 0] という列は、ジョブ 0 の一工程目、ジョブ 1 の一工程目、ジョブ 1 の二工程目、ジョブ 0 の二工程目、の順に詰めていく、という意味になります。

この列を左から順に読み、各工程を詰めていきます。開始時刻は「そのジョブの前工程が終わる時刻」と「その機械が空く時刻」の遅いほうです。こうすると順序の制約を破らないスケジュールが必ずできるので、途中で壊れた解を気にせずに済みます。

良さの物差しはメイクスパンですが、比べるための床も用意しておきます。どの機械も、その機械に載る全工程の合計時間はかならずかかります。どのジョブも、その全工程を合計しただけの時間はかならずかかります。この二つの最大が下界で、どんな並べ方でもこれ未満にはなりません。どんなに運よく待ち時間ゼロで流せたとしても、絶対にこれより早くは終わらない、という床です。今回の三つの問題では、下界はそれぞれ 23、35、59 でした。この床は、あとでヒューリスティクスの答えがどこまで良いのかを測る物差しとして効いてきます。

出場する 4 つの解き方

出場するのは次の四つです。考え方だけ先に並べておきます。

貪欲法は、その場その場で次に流す工程を、あらかじめ決めた規則で選ぶやり方です。短い工程を先に回す規則（SPT、最短加工時間の頭文字）や、残り仕事量が多いジョブを先に片づける規則（MWKR、最大残作業量の頭文字）など、こうした次の一手をその場で決める規則を、まとめてディスパッチ規則と呼びます。いくつかの規則を試して、いちばん良かったものを採用しました。計算は一瞬で終わります。

焼きなましは局所探索の一種です。名前は、金属を高い温度からゆっくり冷ますとひずみが抜けて安定する、あの処理から来ています。その温度にあたる値を内側に持っていて、熱いうちほど悪くなる変更も受け入れやすく、冷えるにつれて良くなる変更だけを選ぶようになります。実際には、いまの並びの二か所を入れ替えて少し変え、良くなれば受け入れ、悪くなっても最初のうちはある確率で受け入れます。少し入れ替えたくらいでは良くならない行き止まりに、はまり込むのを避けるためです。

遺伝的アルゴリズムは、並びを染色体に見立てます。交叉は二つの親の並びを混ぜて子を作る操作、突然変異は子の一部を入れ替える操作です。成績の良い個体を選んで交叉と突然変異で子を作り、集団を世代交代させていきます。ジョブショップでは、単純に混ぜると工程の順番が壊れてしまうので、順番を保ったまま混ぜる交叉（POX）を使いました。

厳密解は分枝限定法です。意味のあるスケジュールだけを枝分かれでたどり、先ほどの下界を使って、いまの暫定解（その時点でいちばん良い完成解）より良くなる見込みのない枝は丸ごと切り捨てます。ここでいう枝とは、組みかけのスケジュールに次の工程を一つ加えてみる、その試みの一つ一つです。プログラムでいう枝刈り探索です。原理的にはかならず最適を出せますが、たどる枝の数が問題サイズとともに急激に増えます。

この四つのうち、貪欲法と焼きなましと遺伝的アルゴリズムは、最適である保証はないものの、良い解を現実的な時間で探しにいく手法です。ここではまとめてヒューリスティクスと呼びます。厳密解だけが、最適だという保証を持ちます。

焼きなましと遺伝的アルゴリズムは、公平のために、スケジュールを評価できる回数、つまり列をスケジュールに直して（復号して）メイクスパンを測る呼び出しの回数の予算を、同じ値に揃えました。焼きなましは貪欲解から探索を始めます。でたらめな並びから登り直す手間を省いて、決めた評価回数をまるごと磨き込みに使えます。私の実装では最初の温度を出発点のメイクスパンに比例させているので、問題の大きさに合わせて、はじめにどれだけ悪化を許すかが自動で決まります。遺伝的アルゴリズムのほうは、最初の集団の一個体だけを貪欲解にして、残りは無作為に散らしました。以下では、この同じ条件で、小さい問題から大きい問題へと三つの規模を順に走らせていきます。

三つの問題の内訳は次のとおりです。

問題	規模（ジョブ×機械）	総作業時間	下界	評価回数の予算
小	3×3	42	23	3,000
中	6×6	167	35	12,000
大	10×8	382	59	20,000

小さい問題では差がつかない

まず 3 ジョブ 3 機械の小さな問題です。ここでは四つとも、同じ 23 に並びました。貪欲法の SPT が一瞬で 23 を出し、厳密解も、分枝限定法だけを単独で走らせると 13 個の枝をたどるだけで、0.1 ミリ秒ほどで最適が 23 だと示しました。

この問題では、最適の 23 が下界の 23 とちょうど一致していました。下界を計算した時点で 23 より小さくはできないと分かっているので、23 を出す並びが一つ見つかれば、あとは探すまでもなく、それが最適だと決まります。小さいうちは、解き方の選択で差がつきません。それどころか、厳密解が一瞬で本当の答えをくれるので、凝った手法を持ち出す理由がありません。中くらいの問題からは、下界と最適がずれてきて、その隙間を埋めるために探索がいるようになります。

中くらいの問題で差が出はじめる

次は 6 ジョブ 6 機械です。貪欲法は、この問題では MWKR がいちばん良く、それでもメイクスパンは 55 でした。あとで示すいちばん良い解より、三割近く大きい値です。一方、焼きなましと遺伝的アルゴリズムはどちらも 43 に届きました。

この 43 が最適かどうかは、厳密解が答えてくれます。分枝限定法は 0.2 秒ほどでそれを示しました。焼きなましと遺伝的アルゴリズムも、同じ 43 に届いていたことになります。じつは、この記事のはじめにガントチャートで見たメイクスパン 43 のスケジュールは、この 6 ジョブ 6 機械の最適解でした。

少し補っておくと、この厳密解は白紙から 43 を探し当てたわけではありません。先に走らせた焼きなましと遺伝的アルゴリズムの 43 を暫定解として渡してあり、分枝限定法はそれより良い枝だけを探して、結局それを超える並びが無いことを確かめて終わりました。厳密解の仕事の大半は、新しい解を見つけることではなく、ヒューリスティクスの答えに間違いがないと保証することでした。速いヒューリスティクスで良い暫定解を用意しておくほど、枝刈りが早く効いて、厳密解も楽になります。

もう一つ面白かったのは、ディスパッチ規則の良し悪しが問題で入れ替わることでした。3 ジョブ 3 機械では最良の 23 を出した SPT が、6 ジョブ 6 機械では 119 で、この問題でいちばん良かった MWKR の 55 の倍以上に膨らみました。短い工程を先に、という直感は、いつも通じるわけではありません。

大きい問題で厳密解が失速する

最後は 10 ジョブ 8 機械です。ここで厳密解が失速しました。8 秒の予算を使い切り、数十万から百万にのぼる枝をたどっても、最適だと証明できません。

分枝限定法がたどっているのは、能動スケジュールと呼ばれる並べ方だけです。言いかえると、どの工程も、ほかの工程を後ろにずらさないかぎりは、もう前に詰める余地がないところまで前詰めしたスケジュールです。無駄な空きをできるだけ左へ寄せた形、と読んでもかまいません。最適な段取りはかならずこの形にできるので、ここだけを探せば最適を取りこぼしません。ヒューリスティクスがオペレーション列から作る解のほうは、もう少しゆるい詰め方まで含んだ広い集合ですが、その中にも最適は入っているので、こちらも不利にはなりません。つまり厳密解のほうが、探索する並べ方の範囲はむしろ狭いことになります。

その狭い範囲に絞ってもなお、数え上げる枝は規模とともに急に増えます。たどった枝の数で見ると、3 ジョブ 3 機械は 13 個、6 ジョブ 6 機械は約 2 万 6 千個で終わりますが、10 ジョブ 8 機械は 8 秒でそれをはるかに超える枝をたどっても終わりません。工程の数、つまり枝の深さが 9、36、80 と増えるにつれ、枝の総数が急に膨らむ、これが組み合わせ爆発です。ジョブショップ・スケジューリングは、規模が大きくなると厳密に解くのが急激に難しくなることが知られていて、計算量の分類では NP 困難（規模が増えると、最適を必ず見つける計算が急に重くなる種類の問題）に当たります。

ヒューリスティクス同士では、焼きなましが 70、遺伝的アルゴリズムが 72、貪欲法が 98 でした。厳密解が最適を証明できなくても、下界は役に立ちます。この問題の下界は 59 ですから、どんな並べ方でも 59 より短くはできません。真の最適は、その 59 以上、見つかっている 70 以下のどこかにあります。焼きなましの 70 は、真の最適より大きくても、(70 - 59) ÷ 59、つまり 18.6 パーセントの隔たりに収まります。証明が間に合わないときでも、答えがどこまで悪くなりうるかの上限は、こうして下界から見積もれます。

途中経過を図にすると、二つの性格の違いが見えます。

遺伝的アルゴリズムは、序盤で速く 73 あたりまで下げます。ただ、そこから頭打ちになりやすい傾向がありました。私の実装では、交叉が二つの親から並びを受け継ぐので、親どうしが似てくると子も遠くへは行きません。新しさを持ち込むのは二割の確率でかかる一点の入れ替えだけで、これだけでは、一度狭まった集団を広げ直すのが追いつきません。選択も 3 個体から一番良いものを採るので、良い個体へ寄る力が強く、序盤の速い改善と引き換えに、早い頭打ちを招きやすいのだと思います。焼きなましは階段状にゆっくりで、途中は遺伝的アルゴリズムに離されていますが、最後に 70 まで届いて上位に来ました。図のいちばん下の水平線が下界の 59 です。どの曲線もそこまでは届いておらず、10 ジョブ 8 機械では、真の最適が分からないまま、まだ縮む余地を残して終わったことになります。

成績と計算時間を並べてみる

三つの問題での成績を、それぞれの問題で見つかった最良解からの差でまとめると、こうなります。

3 ジョブ 3 機械では、三つの手法がどれも同じ 23 に届きました。この 23 は厳密解が最適だと確かめた値でもあるので、最良からの差はそろって 0 パーセントです。全員が最適に達したので、そもそも差のつけようがありません。差が開くのは、問題が大きくなってからでした。貪欲法は速い代わりに、規模が上がると最良解から離れていきます。6 ジョブ 6 機械で二割八分、10 ジョブ 8 機械で四割ほどの差でした。焼きなましと遺伝的アルゴリズムは、その差を時間をかけて詰めていきます。ここで一つ注意しておきたいのは、3 ジョブ 3 機械と 6 ジョブ 6 機械の最良解は厳密解で最適だと確かめた値ですが、10 ジョブ 8 機械の最良解 70 は、本当の最適かどうか分かっていないという点です。図の 10 ジョブ 8 機械で焼きなましが 0 パーセントに見えるのは、真の最適との差ではなく、今回見つかった最良解との差として読んでください。

計算時間の側も見ておくと、貪欲法はどの問題でもおおむねミリ秒級、焼きなましと遺伝的アルゴリズムはこの実行では数十ミリ秒から一、二秒でした。厳密解は小さい問題では一瞬でも、大きい問題では予算を使い切っても終わりません。速さと解の質はおおむね引き換えで、今回の三つの問題では、それが数字にそのまま出ました。

この実験から見えたこと

ここでいちばん確かめたかったのは、名前が派手な手法が本当にいつも上位に来るのか、という点でした。結果は、少なくともこの実験では、素朴な焼きなましのほうが、同じ評価回数で遺伝的アルゴリズムより良い解に届く、というものでした。

ただし、これを焼きなましは遺伝的アルゴリズムより優れている、と一般化はできません。近傍の作り方、交叉や突然変異のやり方、集団の大きさ、そして問題の構造を変えれば、順位は簡単に入れ替わります。今回はたまたま、この問題とこの設定で焼きなましが上位に来た、というだけです。同じ入れ替わりは、ディスパッチ規則でも見えていました。3 ジョブ 3 機械で最良だった SPT が、6 ジョブ 6 機械では大きく外しています。今回は近傍も交叉も集団の大きさも変えず、三つの問題を同じ道具立てで走らせました。それでも順位が動くということは、どこでも通じる万能の設定は無く、問題ごとに測り直すしかない、ということです。

一つ断っておくと、評価回数を揃えても、まったく同じ条件になるわけではありません。遺伝的アルゴリズムには集団の管理や交叉の処理があり、焼きなましとは一回の評価あたりの周辺の手間が違います。ここで揃えたのは、あくまでスケジュールを復号して良さを測る回数です。

私が言いたいのは、手法の名前の印象で決め打ちせず、自分の問題で実際に走らせて測るのが確実だ、ということです。今回のように、小さい部分問題を厳密解で解いて真の最適を押さえ、それを物差しにヒューリスティクスの取りこぼしを見る、という組み合わせは手堅いと感じました。実務でも、貪欲法の即席スケジュールをたたき台にして、局所探索で磨くだけで、かなり縮められます。

まとめと次に試すこと

同じ選手権の枠組みは、詰め込み（ビンパッキング）や巡回路（配送や配線の順番）にもそのまま作れます。目的関数と近傍の作り方を差し替えれば、同じ 4 つの解き方を別の問題で競わせられます。問題が変わると上位の顔ぶれも変わるはずで、そこを次に確かめてみるつもりです。

現場に近づけるときも、足す先はだいたい決まっています。前の品種によって変わる段取り替えの時間は、機械が空く時刻への上乗せとして、スケジュールの組み立て部分に入ります。納期を守りたいなら、物差しをメイクスパンから、遅れの合計や最大の遅れに差し替えます。この工程はこの機械でしかできない、といった適合の制約は、問題の側に書き込みます。今回のラボは、その手前にある一番小さなジョブショップとして作りました。目的関数か、制約か、組み立て方か、足したいものがどこに効くのかが見えていれば、今回の 4 つの解き方をそのまま使い回せます。

工程の順番決めは、設備を共有して順番に流す現場ならどこにでもある、身近な最適化です。手を動かして測ってみると、どの解き方をどこで使うかの感覚が少しずつ掴めてきます。使ったコード（問題の生成、四つの解法、図の描画）はすべて自作で、GitHub に置きました（logicia32/jobshop-lab）。