競売のシミ ュレーションがラグランジュ緩和法
米田 清
Ill………‖‖‖棚‖‖lll‖‖‖‖‖‖‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖＝‖川Illlll‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖川Il…………＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖川Ill州l川‖川Il川‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖＝川！

現象的な意味が書いてある．

1． はじめにラグランジュ緩和法（Lagrangian Relaxation）は

2．定式化

多くのスケジューリング問題で実用になっている．こ2．1ジョブれは一定の型の問題に対しては他の方法よりも有利だ

単純な例でラグランジュ緩和法の原理を説明する．

からである．本稿はその原理を説明する．

仕事ないしジョブは，原料を装置で加工して製品にある問題がラグランジュ緩和法で解ける型にはまっすることである（普通は装置を機械と言う．すると機ているかどうか．ないしは，型にはめることができる会と混同されやすい）．そのジョブがJ＝3個ある．

かどうか．これを直観的に，数式をいじったり数値実験をする前に判断できるようになることを目標に置く．

原料 000→→000 製品

最先端の論文や事例は，素直な型からは外れた問題を

ジョブノ＝1，2，3は各々，原料1，2，3を装置で加工し無理を承知で解いて見せるものが多く，参考になりにて製品1，2，3を作る．
ここで各ジョブには係員が1人ずつ，ついているとくい．
われわれは市場経済の中で生活している．そのため，考える．これは情報用語で言えば，各ジョブをエージ意識しないでも市場経済の仕組みについては理解が備ェントと考えるということである．つまり各ジョブはわっている．ラグランジュ緩和法の算法は競売のシミ個別の意志を持って自律的に行動する．そこでジョブュレーションである．それがわかってしまえば，日常のことを人とみなしたりもする．

的な事をコンピュータ上で実行しているにすぎない．

2．2 時間競売は希少な資源を配分する仕組みであり，端的に多くのスケジューリング技法では時間を（連続な）は競合を価格で解決する．一方，ラグランジュ緩和法実数として扱う．それに対してラグランジュ緩和法では制約の違反を解消する仕組みであり，端的には制約は普通，時間軸を互いに重なり合わない時間区間に区違反をラグランジュ乗数で解決する．

切って，自然数の番号を付けるという扱い方をする

上の2つの文では以下の語句が対応している．
競売 ラグランジュ緩和法（時間を実数として扱っても同様の定式化はできる．
そうすると，うまく解けないことが多い）．
時間fの単位を，この例題では日にとる（実用では希少な資源を配分する 制約の違反を解消する

よく1／10時間を単位にとる）．時間はこの単位の自然

競合 制約違反
価格 ラグランジュ乗数

数で1日，2日，というように数える．例えば「ジョブノ＝1，すなわち原料1を装置で加工して製品1をこのように重要な語句を言い換えれば，概念も働きも作るには，1日かかる」という具合である．1．3日ときれいに対応がついてしまう．

かの整数でない時間単位かかるということは考えない

ラグランジュ乗数と価格との対応は良く知られてい（実用では，計算量を減らすために考えることがある）．

る．数理計画法の教科書にも「ラグランジュ乗数は帰f＝2は，2日目が始まった時刻から2日目が終わるま属価値を表すのでi替在価格とも呼ぶ」くらいの説明がでの時刻に至る，時間の区間についた番号である．

大概は載っており，ミクロ経済学の教科書には，その2．3 納期よねだ きよし 福岡大学経済学部

各ジョブには，各々の納期がある．例えばジョブ1〒814−0180福岡市城南区七隈の納期は今日から4日後で，ジョブ2は7日後だ，と2000年6月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
（3）25丁いう具合である。この例題ではわざと，全てのジョブが同一の納期を持ち，それは今日から4臣】後であるとする。このように意地悪く設定するのは，ラグランジ
ュ緩和法がこの相互に矛盾する要求に，どう折り合いをつけるかを見るためである（もともと納期がうまくぼらけていればヲ 何もエ失しなくてもスケジュールが立っ）。
ジョブが納期に遅れると，顧客に遅延違反金を払わねばならない℡ では早めに済ませておけば良いかと言うと，今度は在庫費用がかかる。早すぎ遅すぎのいずれにしても，納期からずれると納期違反料がかかる。
そこでジョブの完一工田は納期合わせにしたい。

ジョブは2プ3］は加工に各々虹ユタ2］日かかる。
αJ＝ジョブノの加工時間
α＝［qq。

，αJ，…］＝［1，且，2］
1としよう￠1つしかない装置でこれを全てこなすとし

23

45

ら7て，∑αノ＝1＋1＋2＝4日間かかる匂 全てのジョブを納期の4日目から前倒しにしても1日目から始めれば4日目までには終わる。逆に，全てのジョブを後回しにしても4四日から始めれば7日団までには終わる。

だからスケジュールの対象期間は1日白からr＝7日酎までを考えればよい。

ま234567

納期より早すぎたり遅すぎたりするとどれだけの費用がかかるかはジョブ毎に異なる。

ら＝ジョブノの完工日；c＝ト

区＝ ジョブ1，2，3の個別目的関数，CJ，＝中］横軸＝時間f，縦軸＝納期違反料ム（f）￡（cノ）＝ジョブノが完工日cJに完成するときの納期違反料化min／（c）する。

ダ＝［郡と］＝［力（才）］と書く。要するに厨の第ノ行は，ジョブノの納期違反金を完工田毎にならべたものである。具体的な数値は適当な単位（例えば100万円）で測って，

厨「＝2．4 資源制約

全てのジョブノは完工日を納期ら＝4，つまりc＝［4，4，4］にしたいと思っている。これは加工装置がた

5 3 1 0 3 5 7

くさんあれば簡単なことで，各自が作業を実行するま6 4 2 0 3 6 9でのことである。ところが実際は装置が1つしかない由

5 3 1 0 1 3 5

これが目的関数／を最小化する上での制約条件であとしよう。んプ＝1，2，3を上から順に図‖こ示す。
各ジョブは各々の個別目的関数力（cJ）を最小化する
min力（cノ）なる完工ができるように作業を行おうとす
CJる。それでは，全てのジョブからなる全体としては，る。

作業の実行状況は普通，ガントチャート（Ganttchart）で表す。制約条件を数式で表すため，このガントチャートを行列で表しておこう。
0 0 0 1 0 0 0

どのようなスケジュールが望ましいだろうかひ 全体とG（c）＝G［4凍4］＝

しては0 0 11 0 0 0／（c）＝納期違反料の総和＝買カ（cノ）J（例えば′［4，5，3］＝0十3十1＝4）を最小化したい。
′（c）をスケジューリングの目的関数に採用し，最小行がジョブ，列が時間に対応している．1が横に連なっている間が作業を行っている期間で，0は作業なし© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
盈5番（4）

0 0 0 1 0 0 0

オペレーションズ。リサーチ

を表す．例えばジョブノ＝3は才＝3，4日に作業をする．

3．2 ラグランジュ関数

資源制約の違反の程度を装置使用料＝使用権の価格・不足台数＝〟ゐなので，完工日をcとしたとき総費用はゐf（c）＝時間オにおける装置の不足台数／（c，α）＝納期違反料＋装置使用料＝∑C（c）ノ才一1
J＝／（c）＋αゐ（c）

ゐ（c）＝［…，ぁと（c），…］′（′は転置）（2）である．／（c，〟）をラグランジュ関数，〟をラグランで測る．単位は台である．例えばc＝［4，4，4］でガンジュ乗数と呼ぶ．

トチャートが上の場合なら′は金額で測り，ゐは台数で測る．金額と台数とは，

ゐ（c）＝［−1，−1，0，2，−1，−1，剛1］′
負は装置が余っており，0はちょうどで，正は不足を直接は足せない．それに対して上式は「台数で測った表す．つまりゐ≦0なら制約は満たされている．

装置不足ゐに装置を使う権利の価格〟をかけたもの

上のように資源制約を破るスケジュールができるのは，金額で測った納期違反料／に足してもいい」とは，各ジョブが自分が都合の良いときに装置を使える言っている．つまり価格〝は，制約違反の程度ゐをとして予定を立てているからである．

単位変換して，目的関数／と同一の単位に合わせている．

2．5 最適化問題㍑にはもう1つ，納期違反料′と装置不足ぁの相結局，以上のスケジューリング問題を最適化に書き対的な重要度を決めるという機能がある．

直したものはこうして尺度を統一して重要度を決めることによっmin（／（c）lゐ（c）≦0）（1）て定義した，新しい目的関数がラグランジュ関数／でとなる．

ある．′は制約条件を気にしていないのに対して，J3．競売とラグランジュ緩和法数になっている．価格〟をうまく設定してラグラン

3．1装置使用価格
時間はr＝7日間と，十分に取ってある．装置のやりくりさえすれば，損失を抑えながら，全てのジョブを片付けられる．それをどう実現するかについては，いろいろな考え方があり，その1つが競売である．
1つのものをたくさんの人が同時に使いたがっているのギから，いちばん欲しがっている人が使う．どれだけ欲しがっているかは，そのジョブ（の担当者）がある時間に装置を使う権利を得るために，いくら払うかによって測る．

ジュ関数／を最小化すれば，制約条件ゐ≦0を満たして，なおかつ目的関数′を最小化するような解が得られるだろう，というもくろみである．
3．3 ラグランジュ緩和
このように制約条件付きの最適化問題（1）を，ラグランジュ乗数を使ってラグランジュ関数の制約なしの最適化問題（2）に置き換えることをラグランジュ緩和と言う．緩和とは，前者が「制約条件を満たせ」という，きつい定式化なのに対して，後者は「制約違反を減らせ」という，緩い定式化になっていることを指す．

㍑≠＝第吉日に装置を使う権利の価格，〟f，・＝］（0≦仇）〟＝トは「制約違反もなるべく少なくしよう」という目的関とする．非負条件0≦〝fは「装置の使用者は金は払っても，金をもらうことはない」という意味である．
この価格をうまく調整すれば，各日′に装置を使うジ

ョブの数∑Gf＝ゐ￡（c）十1を1つり下（0か1）にでJきるだろうという見通しである．

3．4 分解可能性

価格〝が所与なら，完工日cは総費用／を最小化するように決めれば良い．ところでジ

ョブノの完工日Cノを，他のジョブの完工日cf，才≠ノを見ずに装置価格〟だけに依存して決めるとすればG（c）J≠＝G（cJ）ブとと書ける．さらにろノ＝ジョブノの着工日＝∂ノ（cJ）＝CノーαJ＋1

経済モデルでは需要と供給の双方を価格の関数として表す．その場合，一般的には価格が変われば供給量とすればminJ（c，〝）＝′（c）＋αゐ（c）も変わる．しかし，スケジューリングでは装置台数を固定として扱うので，供給が佃格に関して硬直的である．

＝や（写鮎）＋鼻 庚G（ら）ノ才一1］）

したがって，価格で調整するのは装置の需要台数だけであり，供給はどの時間をとっても1台かぎりである．
2000年6月号＝写聖n（鮎）十凰桁）ヰf© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（5）259

＝警min以cJ，祝）∑眺である。

JCJトとなる血 2行田から3行目が肝心である叩 面倒でも例

このガントチャートG［4，4，4］をむりやり実行可能

題をあてはめて確かめると理解しやすい。
上の変形はmin′（c，甜）と警min以cJ，祝）とが最小C

4．2 実行可能化

JCJに直す。それには制約違反を起こしているジョブを後回しにすれば良い。まず9 ジョブ1を1田，後回しす化として同値であると主張している。この主張は分解る。これでジ可能性とか分離可能性と呼ばれ，ラグランジュ緩和法で最も重要な部分である。

ョブ1は実行可能になる。次にジョブ2を2勘 後匝！しする。これでジョブ2と，同時にジョブ3が実行可能になる。こうして実行可能にしたガン

分解可能性の意味は以Fのとおり巾 価格祝が所与

トチャートは00㌻＝／（c＝［5，6，軋祝＝［0，0，0，0，0，0，0］）＝エi5＋エ26＋￡34＝3＋6＋0＝9である。

4．3 双対問題と双対ギャップ

変形前はm五nで，翌を含む複雑な関数である／（c，し、0

まく需要が調整できることを保証する。

1となる。このとき総費用はCに直結するという構造である。この構造が，競売でう＝G［5，6パ］

0 0 1

最適化mimん（cノ，祝）が社会全体の最適化minJ（c，祝）C、ブ0

つまり，分解可能性というのは，各個人の利己的な0ように完Ⅱ田c．7を決めれば良い。

0 0 0nU O

G［4凍4］＝て，利己的に鉦分の費用以cJ，㍑）のみを最小化する

10 0 0ノが価格㍑だけを参照し，他のジョブの都合は無視しnU nU lのとき総費用′を・最小化したい。それには，各ジョブG［4，4，4］は容量制約違反を起こしている甘いスケ．−α）を，ベクトルcを操作して最小化するということジュールであり9 総費用はヱ＝0である。それを実行だった。しかるにmimと軍とが入れ替わった後は可能化したG［5，6，4］は制約を満たしてはいるけれどJ

mimで，スカラーCJを操作して簡単な関数以cJ，祝）CJを最小化しておいて，後で足せば良いことになってい最適には遠く，総費用は㌻＝9である。したがって，最適スケジュールの総費用は0から9までの，どこかにある。

る。ベクトルcを操作する最小化より9 スカラーCノ

このようにして，実行不可能なガントチャートと9を操作する最小化の方が，格段に易しい。社会全体のそれを後回しによって実行可能化したガントチャート

都合を考えて行動するより，利己的に行動する方が，とが与えられたら，総費用の下界ヱと上界㌻とが計格段に易しい。

算でき，最適なガントチャ｝トに対応する総費用はその間にある。

梯。競売の実行上界と下界の差ト」を双対ギャップと言う。これ4。且 第0価格案が大きければ実行可能スケジュール否そ∂は最適解に価格の初期値として遠く㍑＝［0，0，0，0，0タ0，0］，小さければ近いことがわかるので，重要な情報である。

を採る◎ いつ装置を使っても無料である印 すると／（c，ここまでは，装置を使うと費用が発生する，ジョブ祝）＝／（c）だから，各ジョブは納期違反料だけを払えの立場で問題を考えて来た。ここで，各ジョブから納ば良い。

期違反料と装置使用料，すなわちん（cJ，㍑）を集める

且＝［且Jf］

集金エージェントを作ろう。すなわち今までの金を払且ノと＝ジョブノが才＝CJとしたときのん＝以才，㍑）

う立場から翻って9 逆の受け取る立場で問題を考える⑳

集金者は利己的に自分の収入を最大化するように行動とする。この場合は且31＝∞（ジョブ3は加工にα3＝する。集金者に操作できるのは価格視である。これ2巨ヨかかるから）以外は且ノ才＝香子となる。よって最は数学的には最適化で主問題nJ（c，朗）に対して双適な完工削まc［4，4，4］で，対応するガントチャートは先にも示したG［4，4，吐 このとき総費用は
ヱ＝7（c＝［4，4，軋祝＝［0，0，0，0，0，0，0］）＝且14十且24＋￡34＝昂4＋ダら4十厨も4＝0

選6㊥（6）

対問題mⅩJ（cタ㍑）を考えることに当たる8

集金者は需要と供給の差を見て，収入が増えるように価格を設定する貯 もし，ある時間に装置を使いたい© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズロリサーチ

0 0 01 0 0＝G［4，5，3］000

し，只より安くはしない（0≦〟）．

00 10なければ，その時間の装置使用料を値下げする．ただ10 01する．逆に，もしある時間に装置を使いたいジョブが00 00

ジョブが複数あれば，その時間の装置使用料を値上げ

で，［∠，㌻］＝［1，4］となり，〟＝［0，0，0，0，0，0，0］の時価格がうまく設定された状態では，装置に対する競よりも良いスケジュールが得られている．

合が解消されている．つまり，ある時間に装置を使う

4．5 第2価格案

ジョブの数が0か1に絞られている．

第0価格案ではf＝4だった競合日が第1価格案で装置を使うジョブの数が0なら，装置をその時間に使用する権利の価格は0である．誰も使いたくないもはf＝3に移った．そこで集金者は，今度はf＝3に価格を立てる．例えばのの値段は只なので．

㍑＝［0，0，2，3，0，0，0］

装置を使うジョブの数が1のとき，その時間に装置とすると，を使用する権利の佃格は適正である．なぜなら，価格

5 3 3 3 3 5 7を上げれば，その時聞からジョブが逃げてしまう．逆

エ＝に価格を下げれば，その時間に装置を使いたいジョブが複数になってしまう．

6 4 4 3 3 6 9CO 3 3 5 4 3 5である．こうなると費用が等しくなる完工日がたくさ

再び双対ギャップ㌻−｛の意味を考えよう．現在のんあって，この価格のもとでの最適完工日は一意に定価格設定における主問題の現状値が上界㌻，双対問

まらない．c＝［2，4，2］でもc＝［3，4，5］でも総費用J題の現状値が下界∠である．上界㌻は需要者であるは同じである．早い完工日を優先するなら，解はc＝ジョブたちが，現状の価格のもとで総費用をどれだけ［2，4，2］で，01000000010000000011

は供給者，すなわち集金者が，そのうちのどれだけを0払ってもしかたがないと思っているかを表す．下界ヱ＝G［3，4，2］

実際に収入として得ているかを表す．よって双対ギャップは，需要者が価格設定の変更によって支出を減らす余地の，限度額を示している．同様に双対ギャップである．
ここで上下界を調べると［ヱ，㌻］＝［4，4］となり，実は，僕給者が価格設定の変更によって収入を増やす余行可能なスケジュールの品質は第1価格案と同じで，地の，限度額を示している。

改善されていない．しかし，双対ギャップが㌻一旦＝結局，双対ギャップは，価格設定の不適切さに由来する需給の承離を測っている．

0であることがわかった．つまり，これで最適なスケジュールが得られていることが判明した．よって問題

4．4 第1価格案は解けた．上のG［3，4，2］が最通解の1つである．

ここで装置不足台数ゐを調べると，≠＝4で競合が起こっている．そこで，集金者は例えば〟。＝3に設定5．おわりにする．

価格の調整だけでは実行可能解が得られていない．
〟＝［0，0，0，3，0，0，0］

良い線までは行くものの，最後の所はガントチャート

今度は装置価格が0ではない日があるので，んf＝をむりやり実行可能に直すヒューリステイクスに頼っん（f，〟）を計算して並べると，ている．実行可能解の存在は，実行できなかった作業

5 3 1 3 3 5 7はいくらでも後回しにできる，という逃げ道で保証し′．＝

6 4 2 3 3 6 9ている．

∝）3 1 3 4 3 5

このヒューリステイクスの良し悲しが，得られるスとなる。ジョブノ＝3のf＝1日目がエ31＝∞となってケジュールの質に影響する．あまり複雑なことはせずいるのは，作業が2日かかって1日では終わらないたに，バグがないことと，実行時間がジョブ数Jのオめ，Cl＝1にできないからである．

ーダー0（J）と短いことを主眼にするとまちがいが少

これによると最適な完工日はc＝［3，3，3］で，今度は3日に集中してしまう．

2000年6月号

ない．

最通解は一意でなかった．最適解の周辺は鍋底にな© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（7）261

っていてヲ どの解を採っても同じような品質である。

えばメタヒューリステイクスでは主問題だけを扱い，解の品質は双対ギャップで見当がつく。実用的には最利用するのは目的関数の値だけである〃

どんな問題でうまく行くかについては，分解可能性適性にこだわらないで良い。

例題では価格を2回，値上げしただけで最適解に到が鍵であるり 個人が利己的に行動すると社会が良くな達した。実は1園だけの値上げで，既に最通解に到達るという構図が成り立てば良い。そのための条件の1していたのだけれど，それが判明しなかった小 神経質

つは，各人が個性を持っていることである。全ての人に価格を最適化しないでも，実用的な解が得られる場が同じように行動すれば，競合は解消しない。諦める合は多いu

人があり執着する人があって，初めて競売が機能する。

価格を適正に設定するのは難しい。大きい問題では個性は個別目的関数￡の違いである。もしも多く価格を上げたり下げたり，いろいろな探索をする必要の個別関数が同一になるような問題を扱う必要があるが焦じる。ラグランジュ緩和法の論文の多くは，このなら，無理にも僅かな違いを導入する中探索法に関する二工夫を扱っている。
参考文献

価格改訂をどのようにするべきかの最大の手がかり
はト，∂J（c，㍑）／∂〟f，…］′＝ゐ（c）すなわち装置の不足台［1］Zhang，Y．，LJuhP．B．，Yoneda，K．，Kano，TリK
Y∴数だった。これを勾配でなく劣勾配と言う。関数J［c（祝），祝］は価格祝の関数として多面体でヮ 一般には微分可能でないからである。劣勾配を辛がかりに価

Mixed−mOdelAssembly Line Scheduiing Using

the Lagrangian Relaxation Technique，ⅠIETransacM

tioms32（2）：125¶134，（2000）（分解口†能件の満たし九価格の新しい設定法，ジョブに格を改訂する算法を劣勾配法と呼ぶ。

脚性を与一える方法など．）

ラグランジュ緩和法が高速なのは，双対問題で勾配情報を使うからであるひ 主問題は組み合わせ最適化の問題なので，勾配の概念はない。しかし双対問題では，［2］米田 清：ラグランジュ緩和法によるスケジューリン
グ；システム／制御／情報41（4）；130−138，（1996）．
（本稿より多少，詳しい解説∴細かい誤りが多い。）

曲がりなりにも勾配情報が使える。それに対して，例26望（8）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ⑳リサーチ