分散スケジューリング問題に対する合意に基づく解法

全文

(1)58. システム制御情報学会論文誌，Vol. 34, No. 2, pp. 58–67, 2021. 論. 文. 分散スケジューリング問題に対する合意に基づく解法* 宮本俊幸 † ・梅田豊裕 ‡ ・高井重昌 †. Consensus-based Approach to Distributed Scheduling Problem*. Toshiyuki Miyamoto† , Toyohiro Umeda‡ and Shigemasa Takai†. In recent years, the development of optimization methods in multi-agent systems has been remarkable. The scheduling problems belong to NP-hard and are not easily solved in a large-scale system. The distributed scheduling method is expected as one of the methods for large-scale systems. In this paper, as the first step of the research, we propose to apply the alternating direction method of multipliers for the consensus problem to the distributed scheduling problem and show that the job shop scheduling problem (JSP) can be formulated by the proposed method. In distributed optimization, the optimization of sub-problems is repeated until the convergence condition is satisfied, but since the scheduling problem is a nonconvex optimization problem, the convergence by the proposed method is not guaranteed. In some cases, a large number of iterations may be required to satisfy the convergence condition. In this paper, we propose two schemes to obtain a feasible solution within a smaller number of iterations. Then, the method is evaluated by computer experiments using benchmark instances of JSP.. 1.. はじめに. 要があり，ローカルな範囲での実行可能化に留まることが多い．結果として，不要なジョブの滞留，ネック設備. 製造コストが膨大になる大規模生産システムにおい. での材料欠損や置場（バッファ）のオーバーフローによ. て，最適化はコスト削減や資源の有効利用などの観点か. る設備停止が発生しやすくなり，納期遅れや生産未達を. ら重要である．しかし，生産システム全体を厳密にスケ. 招く懸念がある．. ジュールするには規模が大きく，計算時間の面で実用上. 一方で，IoT 化により工場内の設備や物流の情報をリ. の問題がある．たとえ生産システム全体の詳細なスケ. アルタイムに取得できる環境が整備されつつある．ま. ジュールが得られたとしても，計算時間とトレードオフ. た，操業や搬送の指示をリアルタイムに直接現場に発信. となるモデルの精度が実態と乖離する点や，実操業では. できる環境も急速に整ってきている．すなわち，大規模. 避けられない種々の変動要素により，スケジュール通りに操業することは極めて難しい．このような理由から，ガイドラインとしての操業計画は立案できても，オペ. モジュールごとの並列的なスケジューリングとモジュー. ながら人の判断で作業スケジュールを作成・修正する必 ∗ †. て一括して作成するのではなく，生産システムを短時間でスケジューリング可能な小さなモジュールに分割し，. レーションレベルでは，操業現場の実際の状況を確認し. ∗. 生産システムにおいて全体のスケジュールを時間をかけ. ル間の協調により，結果的に全体として望ましい生産ス. 原稿受付 2020 年 5 月 15 日第 62 回自動制御連合講演会にて発表（2019 年 11 月）大阪大学大学院工学研究科 Graduate School of Engi-. ケジュールを獲得するための環境が整ってきている．そこで本論文では，自律分散的なアプローチにより，エージェント間の情報交換とエージェント独自のロジックに. neering, Osaka University; 2-1 Yamadaoka, Suita city, Osaka 565-0871, JAPAN ‡ (株) 神戸製鋼所生産システム研究所 Production Systems Research Laboratory, Kobe Steel, Ltd.; 1-5-5, Takatsukadai, Nishi-ku, Kobe, Hyogo 651-2271, JAPAN Key Words : distributed scheduling, consensus, ADMM, optimization.. もとづき，ローカルな制約を満足しつつも全体を望ましい方向に誘導するアプローチを検討する．マルチエージェントシステムにおける重要な問題として合意問題がある．合意問題とは，一部の変数を複数のエージェントで共通の値を持たせながらエージェントが. – 30 –.

(2) 59. 宮本・梅田・高井：分散スケジューリング問題に対する合意に基づく解法. 持つ目的関数の総和の最小化を目的とする最適化問題で. される．本論文では，連結な無向グラフ（通信可能な. ある．スケジューリング問題 [1]，コンピューティングリ. 相手とは双方向で通信できることを意味する）を仮定. ソースの QoS 公平化制御 [2]，カメラセンサネットワー. する．また，エージェント i の隣接エージェントの集合. クによる協調追跡 [3]，拡散現象の初期濃度分布推定 [4]，. を Ni = {i ∈ I | (i,i ) ∈ E} とする．このとき，合意問題. スマートグリッドにおける経済的配分問題 [5] などさま. CP1 は次のように書き換えることができる． (CP2) min fi (xi ). ざまな応用 [6] が報告されている．また，合意問題を含むさまざまな問題に対する分散解. x1 ,x2 ,...,x|I|. 法として交互方向乗数法 (Altenating Direction Method. s.t.. of Multipliers: ADMM)[7,8] がある．ADMM は凸最適化問題に対する解法であり，目的関数の拡張ラグラン. i∈I. (2). x i = x i ,. i ∈ Ni ,i ∈ I. (3). xi ∈ Xi ,. i∈I. (4). ジュ関数を一部の変数ずつ交互に更新することにより求. (3) 式は隣接エージェントと変数の値が一致することを表. 解する手法である．エージェントの変数集合ごとの部分. している．この制約を合意制約という．通信グラフは連. 問題に分解することができれば，分散最適化手法として. 結なので，(3) 式はすべてのエージェントが同じ値を xi. 使うことができる．. に持つことを意味する．よって，問題 CP2 は問題 CP1 と等価になる．. 本論文では大規模生産システムの自律分散的スケジュー施することを目的とする．1) 合意問題に対する ADMM. 交互方向乗数法 (Altenating Direction Method of Multipliers: ADMM)[7] は凸最適化問題に対する解法で. アルゴリズムをスケジューリング問題に適用する方法を. あり，目的関数の拡張ラグランジュ関数を一部の変数ず. 提案する．2) スケジューリング問題の基本的なクラス. つ交互に更新することにより求解する手法である．エー. であるジョブショップスケジューリング問題 (Job-shop. ジェントの変数集合ごとの部分問題に分解することがで. Scheduling Problem: JSP) を提案手法によって定式化. きれば，分散最適化手法として使うことができる．以下. し，計算機実験を通じて提案手法の特性を解析する．分. にグラフ上の合意問題に対する ADMM のアルゴリズム. リング手法構築に向けての第一歩として，次の 2 点を実. 散スケジューリングについての関連研究は 5. にまとめる. を示す [9,10]．ただし，ai はエージェント i が持つパラ. が，ADMM を用いた分散スケジューリング法は著者ら. メータ（ラグランジュ乗数），c はエージェント共通のパ. の知る範囲では存在しない．. ラメータ，右肩の数は繰り返し回数を表す．. 本論文の構成は以下の通りである．2. において合意問題とその分散解法について述べた後，3. においてそのスケジューリング問題への適用を提案する．さらに，ジョブショップスケジューリング問題を提案手法により定式化する．4. では JSP のベンチマーク問題例を用いて計算機実験を実施し，提案手法の特性を解析する．5. では. . i ∈Ni. 関連研究を紹介する．. 2.. ADMM アルゴリズム： (0) (0) Step 1 エージェント i ごとに ai , xi を初期化．k := 0 Step 2 隣接エージェントと xi を交換．k := k + 1． Step 3 エージェント i ごとに ai , xi を更新 (k−1) (k) (k−1) (k−1) ai := ai +c (xi − x i ) (5) (k). xi. 合意問題とその分散解法. := arg min. xi ∈Xi. (k). fi (xi ) + xT i ai. (k−1) (k−1) 2 xi + x i +c xi − 2 . R を実数全体の集合，X を凸集合，I をエージェント集合とし，エージェント i ∈ I の目的関数 fi : X → R を. i ∈Ni. (6). 2. 閉真凸関数とする．合意問題 (consensus problem) は次. Step 4 終了条件を満たすまで Step 2, Step 3 を繰り返す．. 式で表される．. (CP1). min. x∈X. . (0). fi (x). アルゴリズムの Step 1 において，ai. (1). には条件があ. る [10]．条件を満たす簡単な方法は，すべての要素につ. i∈I. いて 0 とすることである．. すなわち，合意問題とは変数 x についてエージェント間の合意を取りながら，エージェントの目的関数の総和を. Step 1, Step 2, Step 3 はエージェントごとに実行可能であり，最適化計算は (6) 式であるため，ADMM ア. 最小化する問題である．. ルゴリズムは分散最適化手法となる．. 分散最適化は，各エージェントによる最適化とエー. アルゴリズムは k → ∞ とすれば最適解へ収束する．実. ジェント間での情報交換を繰り返すことにより達成さ. 際には Step 4 のように終了条件が満たされるまで繰り. れる．エージェント i ∈ I が持つ変数 x のコピーを xi とする．また，定義域を Xi とし，X = ∩i∈I Xi とする．エージェントが通信できる相手に制約がある場合，そ. 返すことになる．終了条件としては次式で与えられる主残差 r (k) と双対残差 s(k) が用いられ，これらの値が十分小さくなれば終了することとする．. の制約構造は通信グラフ G = (I,E),E ⊆ I 2 により表現. – 31 –.

(3) 60. システム制御情報学会論文誌第 34 巻第 2 号 (2021). r(k) =. . (k). (k). xi − xi 22. i∈I i ∈N (k)i (k−1) 2 (k) xi − xi 2 s = i∈I. M1. (7). Fig. 1. (8). Mm. M3. Path graph M1. 提案手法. 3.. B2. M2. Mm. 3.1. 合意に基づく分散スケジューリング本論文では 2. で示した ADMM アルゴリズムをスケ. B0. M3. ジューリング問題に適用することを提案する．なお，スケジューリング問題は非凸最適化問題であるため，提案手法による収束性は保証されない．また，たとえ収束したとしても，最適性は保証されないことに注意されたい． Fig. 2. 提案手法：. X 生産システムをマルチエージェントシステムととら. を満たさなければならない．そこで，機械 i1 ，i2 間に. える．. バッファi3 を挿入する．このとき (9) 式は. X ジョブの開始時刻と終了時刻を変数として合意問題. yi1 ,j = xi3 ,j ≤ yi3 ,j = xi2 ,j. になるようスケジューリング問題を定式化する．. X ジョブの開始時刻と終了時刻について ADMM を用. (10). とすることができ，これは合意制約である．よって，設. いて隣接エージェントと合意をとることにより全体. 備 i の隣接設備集合 Ni をジョブの通過順においての直. スケジュールを作成する．. 前設備と直後設備の集合とすると，スケジューリング問. 提案手法では対象とする生産システムをマルチエー. 題を合意問題 CP2 により定式化することができる．. ジェントシステムととらえる．エージェントは，一つの. 提案手法ではエージェント集合 I および通信グラフ G. 設備，設備群あるいは工場などに対応する．この対応関. を対象システムに応じて決定する必要がある．たとえば，. 係は対象システムに応じて決めればよい．また，設備とは機械やバッファや搬送システムなどである．以下では，エージェントが対応するものを設備とよぶ．. フローショップ型生産システムのようにすべてのジョブが同じ順序で機械により処理されるならば，機械の間にバッファを挿入し，通信グラフを機械とバッファが交互. 本論文では，エージェントのスケジューリング問題に. に現れる道グラフ（Fig. 1）とすればよい．次節以降で. ついて以下の仮定をおく．. 対象とする JSP のようにジョブの処理順に規則性がな. 仮定エージェント i の変数 xi の定義域 Xi が他のエー. いならば，単一のバッファを用意し，通信グラフをバッ. ジェントに依存しない．. ファを中心とする星グラフ（Fig. 2）とすればよい．こ. 仮定が成り立たない（Xi が他のエージェントに依存. こで星グラフの場合でも，機械における処理時間制約な. する）生産システムとしては，有限な共有資源を持つシ. どの制約は機械エージェントの最適化モデルに含まれる. ステムやジョブを処理する設備が選択的に選ばれるシス. ため，バッファエージェントが集中的にスケジューリン. テムがある．たとえば有限な共有資源を持つシステムで. グするようにはならないことに注意されたい．. は，他のエージェントが共有資源を利用している間は処理を始めることができない．このようなシステムでは，他のエージェントの決定が自身の決定に影響を及ぼすた. バッファの数とバッファエージェントにおける最適化モデルの複雑さの間にはトレードオフの関係がある．星グラフではバッファは一つですむが，ジョブの処理順を. め，スケジューリング問題を合意制約だけでは定式化で. バッファエージェントの最適化モデルに制約として与え. きない1 ．仮定が成り立つ場合，設備のスケジュールはエージェントが自律的に決定することができる．ただし，スケ. る必要がある．また，バッファエージェントが持つ変数の数はジョブの数と機械の数の積の関数となる．これに対して，道グラフではジョブの処理順はグラフ構造で表. ジュールが実行可能となるためには隣接エージェントと時刻について整合を取る必要がある．機械 i におけるジョブ j の開始時刻を xi,j ，終了時刻を yi,j とし，ジョブ j. 現されているため，バッファエージェントは処理順に関する制約を持つ必要はない．また，バッファエージェントが持つ変数の数はジョブの数の関数となる．一般に最. が i1 , i2 の順で機械を通過するとすると，. yi1 ,j ≤ xi2 ,j. Star graph. 適化に要する時間は変数や制約の数に対して指数関数的に増加するため，分散最適化における並列度を高めるた. (9). めには，ジョブの処理順をできるだけグラフ構造で表現 1. すべきである．. 合意制約以外の制約を用いれば提案手法を適用可能な場合も存在するが，ADMM アルゴリズムを修正する必要があるため，本論文では対象外とする．. – 32 –.

(4) 61. 宮本・梅田・高井：分散スケジューリング問題に対する合意に基づく解法 M1. x1 , y1. x0 [1], y0 [1]. M2. x2 , y2. x0 [2], y0 [2]. Mm. xm , ym. Fig. 3. y ij,1 ,j = xij,1 ,j ≤ xij,1 ,j + pj,1 = yij,1 ,j = xij,1 ,j ≤ y ij,2 ,j = xij,2 ,j ≤ ··· = xij,m ,j B 0. (11). 機械は一つのジョブしか同時には処理できない（同時処理制約）．これは j1 , j2 を任意の異なるジョブとして. x0 [m], y0 [m]. 以下の式によって表現できる．. yi,j1 ≤ xi,j2 ∨ yi,j2 ≤ xi,j1. Job-shop system. (12). ジョブショップスケジューリング問題. なお，(12) 式では論理演算子 (∨) が使われているが，指. 本節では 3.1 で提案した手法により JSP が合意問題と. 示変数（0-1 変数）を 2 個導入することにより一次制約. 3.2. に変換可能である [11]．. して定式化されることを示す．. JSP は，ジョブの処理順序制約，処理時間制約，機械. 以上より，機械 i の目的関数を fi : R2n + → R，バッファ. → R とすると，JSP は以下のよの目的関数を f0 : R2mn +. の同時処理制約を満たしながら所与の目的関数を最小化（もしくは最大化）するスケジュールを求める問題であ. うに定式化される．. る．目的関数としては，メイクスパンや納期遅れが用い. . (JSP) min. られる．. fi (xi ,yi ). (13). i∈I. 非負の実数全体の集合を R+ とする．ジョブショップ. yi,j = xi,j + pj,lj,i ,. s.t.. は m 台の機械と一つのバッファからなり，エージェント. i ∈ M,j ∈ J (14). yi,j1 ≤ xi,j2 ∨ yi,j2 ≤ xi,j1 ,. 構成および通信グラフを Fig. 3 に示す．機械間でジョブ. i ∈ M,j1 ,j2 ∈ J,j1 = j2. を搬送する搬送設備なども含めてバッファとする．また，. xij,l ,j ≤ y ij,l+1 ,j ,. 機械とバッファを合わせて設備とよぶ．Fig. 3 にある設. l ∈ {1,...,m − 1},j ∈ J. 備間のリンクはジョブの移動可能な組を表す．すなわち，機械で処理されたジョブはいったんバッファに置かれてから次の機械に渡される．機械の集合を M = {1,...,m}，機械とバッファを合わせた設備の集合を I = {0,1,...,m}. (15) (16). xi = y0 [i],. i∈M. (17). yi = x0 [i],. i∈M. (18). (14) 式は機械における処理時間制約である．(15) 式は機械における同時処理制約である．(16) 式はバッファにおける時間制約である．(17) 式と (18) 式は機械とバッファ. とする．ここで，設備 0 はバッファを表す．ジョブの集合を J = {1,...,n} とする．ジョブ j ∈ J はすべての機械をあらかじめ定められた順で訪れ，ジョブ. 間の合意制約である．. j が l 番目に訪れる機械を ij,l ∈ M とする．また，機械 i ∈ M がジョブ j の何番目の工程を担当するのかを lj,i で表す．ジョブ j の第 l 工程の処理時間を pj,l ∈ R+ とする．すなわち，ジョブ j の機械 i での処理時間は pj,lj,i で. 上記の制約のうちエージェント i の決定変数の定義域. Xi を与える制約は (14)∼(16) 式である．これらの制約は他のエージェントに依存しないため仮定を満たす．エージェント間にまたがる制約は (17) 式と (18) 式だけであ. ある．. り，これらは合意制約であるため，JSP は合意問題 CP2. 決定変数は各設備での開始時刻と終了時刻である．機. として定式化された．. 械 i でのジョブ j の処理開始時刻を xi,j ∈ R+ ，処理終. 3.3. 了時刻を yi,j ∈ R+ とし，機械 i の決定変数ベクトルを. xi = [xi,1 ,...,xi,n ]T , yi = [yi,1 ,...,yi,n ]T とする．バッファにおける開始時刻はジョブがバッファに配置される時刻，終了時刻はジョブが取り出される時刻である．バッファに機械 i で処理が終わったジョブ j が配置される時刻を. xi,j ∈ R+ ，バッファから機械 i で処理されるためにジョブ j が取り出される時刻を y i,j ∈ R+ とする．また，バッファの決定変数ベクトルを x0 = [x1,1 ,x1,2 ,...,xm,n ]T , y0 = [y 1,1 ,...,y m,n ]T とする．また，x0 と y0 の機械 i に関する部分ベクトルをそれぞれ x0 [i] = [xi,1 ,...,xi,n ]T と y0 [i] = [y i,1 ,...,y i,n ]T とする．ジョブはバッファを出発地点とし，決められた順番（処理順序制約）で，機械への移動・機械での処理（処理時間制約）・バッファへの移動を繰り返す．よって，ジョブ. j に関する時刻に関して以下の関係が成り立つ． – 33 –. 分散スケジューリング JSP は合意問題であるため ADMM アルゴリズムを適用可能である．Step 3 の (5), (6) 式は機械とバッファについて以下のようになる．なお，以下の式においてはメイクスパンの最小化を目的関数としており，Cmax はメイ T T T T T ˆ = [xT ˆ = [y1T ,y2T ,...ym ] でクスパン，x 1 ,x2 ,...xm ] ，y. ある．機械 i：. . (k−1) ai,x := (k−1) ai,y (k−1) − y0 [i](k−1) xi +c (k−1) yi − x0 [i](k−1) (k) T T a(k) xi i,x := arg min xi ,yi (k) (k) xi ,yi yi ai,y (k). ai,x (k) ai,y. . . (19).

(5) 62. システム制御情報学会論文誌第 34 巻第 2 号 (2021). ⎛ 2 (k−1) (k−1) + y [i] x 0 i + c ⎝ x i − 2 2 2 ⎞⎫ (k−1) ⎬ + x0 [i](k−1) y ⎠ (20) + yi − i ⎭ 2. M1 M2. 2. s.t. yi,j = xi,j + pj,lj,i ,j ∈ J. (21). (a) k, k + 2, k + 4,···. yi,j1 ≤ xi,j2 ∨ yi,j2 ≤ xi,j1 , j1 ,j2 ∈ J,j1 = j2. バッファ：. . (23). M2. (k−1) (k−1) − yˆ(k−1) a0,x x0 := +c (24) (k−1) (k−1) a0,y y0 −x ˆ(k−1) (k) a(k) x0 T 0,x := arg min Cmax + xT 0 ,y0 (k) (k) x0 ,y0 y0 a0,y ⎛ 2 (k−1) (k−1) + y ˆ x 0 +c ⎝x0 − 2 2 2 ⎞⎫ (k−1) ⎬ (k−1) +x ˆ y ⎠ (25) + y0 − 0 ⎭ 2 (k). a0,x (k) a0,y. . M1. (22). xi ,yi ∈ Rn+ . s.t. xij,l ,j ≤ y ij,l+1 ,j ,. 3.4. t. (b) k + 1, k + 3,··· Fig. 4. t. Gannt charts of a non-converge case. まで多くの繰り返しが必要になることがある．以下に ADMM アルゴリズムを収束させる，あるいは無駄な繰り返しを止めさせるための方策を提案する．方策 1 順序について合意すれば収束とする．無駄に繰り返される場合というのは，ジョブの処理順は隣接エージェントと同じであるが時刻の合意を取るま. 2. でに繰り返しが必要な場合である．そこで，処理順が同. l ∈ {1,...,m − 1},j ∈ J. (26). y ij,J ,j ≤ Cmax ,j ∈ J. (27). x0 ,y0 ∈ Rmn +. (28). じになれば収束と判断することにする．機械 i におけるジョブの処理順ベクトルを wi ∈ {1,...,n}n とし，バッファにおける機械 i のジョブの処理順ベクトルを w0 [i] ∈ {1,...,n}n とすると，処理順に関する残差. 収束性に関する検討. q (k) は次式で与えられる． (k) q (k) = wi − w0 [i]22. JSP は機械の同時処理制約（(15) 式）のため定義域 Xi が非凸となる．そのため，ADMM アルゴリズムは必ずしも収束しない．ADMM アルゴリズムにはパラメータ c があり，この値の選択は収束性や収束値に大きな影. (29). i∈M. 残差 q (k) が 0 になることは，機械群が考えるスケジュー. 響を及ぼす．また，収束するとしても時刻の合意を得る. ルとバッファが考えるスケジュールの間で順序について. まで無駄に多くの繰り返し回数が必要になる場合がある．. は合意が得られたことを意味する．順序の合意が得られ. ADMM が収束しない場合のガントチャートを Fig. 4 に例示する．この例では，繰り返し回数が k のときのガントチャートが Fig. 4(a) であり，k + 1 では Fig. 4(b) のように機械 M1, M2 においてジョブの順序が入れ替わっている．そして，k +2 では再度 Fig. 4(a) の順に戻る．これが永久に繰り返されるため収束しない．この例のよう. れば実行可能スケジュールは多項式オーダの計算で求めることができる．よって，方策 1 では q (k) = 0 となれば収束と判断する．方策 2 パラメータ c を大きくする．凸最適化問題に対する ADMM でも決定変数が振動することがある．文献 [12,13] では受動性に基づいて収束. に周期 2 で繰り返される場合もあれば，もっと長い周期. 性解析がなされている．また，非凸最適化問題である起. でいくつかのスケジュールが繰り返される場合もある．. 動停止問題に対して ADMM を適用している文献 [14] で. 無駄に繰り返されるというのは，Fig. 4 のように順序. も 0-1 変数の振動を抑えるためにパラメータ c を大きく. が入れ替わるのではなく，時刻の合意を得るまでの繰. する手法が紹介されている．. り返しが無駄に多くなることを指す．機械でのジョブの. (6) 式においてパラメータ c は k − 1 回目の解との差への係数である．すなわち，c を大きくすることは前の. 処理順序を固定すると JSP は凸最適化問題となるため. ADMM は収束する．収束の条件は時刻について合意することであり，エージェントはラグランジュ乗数 a にしたがい x, y を更新する．ラグランジュ乗数の更新は (19), (24) 式によって行われる．これらの式は合意に近づけば. 解との差を小さくする働きがあり，結果として非凸最適化問題では ADMM アルゴリズムが局所解へ陥りやすくなる．よって，方策 2 ではパラメータ c を小さな値から始め. 更新量が減るようになっているため，収束条件を満たす. て次第に大きくする：. – 34 –.

(6) 63. 宮本・梅田・高井：分散スケジューリング問題に対する合意に基づく解法. c = c1 + c2 k. (30). Table 1. ここで，c1 は c の初期値，c2 は増加量である．. 3.5. メッセージ複雑度. 分散アルゴリズムの評価指標の一つに通信複雑度がある．通信複雑度とは分散アルゴリズムが終了するまでに必要な通信量であり，メッセージ複雑度とはアルゴリズムが終了するまでに送信される定数サイズのメッセージの個数である．. ADMM アルゴリズムの Step 2 において，機械エージェントはバッファエージェントに 2n 個のメッセージを送信する．バッファエージェントは各機械エージェントに 2n 個のメッセージを送信する．したがって，1 回の繰り返しにおいて送信されるメッセージの数は 4mn 個となる．繰り返し回数を K 回とすると，メッセージ複雑度は O(mnK) となる．なお，1 回の繰り返しにおいて送信されるメッセージの数は不変なので，メッセージ複雑度は通信グラフのトポロジによらず同じである．. 計算機実験. 4. 4.1. 実験条件 JSP のベンチマーク問題例を利用し提案手法の収束性を調べる．ベンチマーク問題例は JSPLIB1 から取得した．ソルバーには IBM ILOG CPLEX ver.12.8 を用いた．使用した計算機は CPU: Intel Core i7-2700, Memory: 32 Gbyte, OS: Linux ver.3.6.11 である． ADMM アルゴリズムを以下の三つの手法で実行した． S0 方策 1, 2 を使わない． S1 方策 1 を使う． S2 方策 2 を使う． ADMM アルゴリズムの終了条件は，繰り返し回数 k が 200 を超えるか，主残差 r (k) と双対残差 s(k) がともに 0.1 より小さくなるまでとした．手法 S1 では，処理順に関する残差 q (k) が 0 となることを終了条件に追加した．手法 S0, S1 においてパラメータ c は 0.1 で固定し，手法 S2 において c1 = 0.1, c2 = 0.01 とした．パラメータ c, c1 , c2 の選定は収束させるうえで重要であるが，問題. inst. abz5 abz6 abz8 la10 la11 la12 la13 la18 la27 la28 la29 la35 orb04 orb05 orb06 swv02 swv13 swv19 ta08 ta09 ta16 ta25 ta26 ta33 ta42 ta50 ta60 ta61 ta67 ta76 ta77 ta78. m 10 10 15 5 5 5 5 10 10 10 10 10 10 10 10 10 10 10 15 15 15 10 20 15 20 20 15 20 20 20 20 20. n 10 10 20 15 20 20 20 10 20 20 20 30 10 10 10 20 50 50 15 15 20 20 20 30 30 30 50 50 50 100 100 100. 繰り返し回数. S0 > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 t.o. t.o. > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 t.o. t.o. t.o. t.o. t.o. t.o.. S1 > 200 58 89 33 33 > 200 > 200 56 > 200 61 74 > 200 71 70 78 > 200 t.o. t.o. 93 88 92 166 134 > 200 > 200 > 200 t.o. t.o. t.o. t.o. t.o. t.o.. S2 161 160 > 200 65 105 > 200 113 150 > 200 > 200 > 200 > 200 157 161 > 200 173 t.o. t.o. > 200 > 200 > 200 > 200 > 200 > 200 > 200 > 200 t.o. t.o. t.o. t.o. t.o. t.o.. 返し回数が 200 に達したことを，t.o. はあるエージェン. 例ごとに調整することは困難である．そのため，問題例. トにおいてタイムアウトした（制限時間（300 秒）内に. la10 を使った予備実験の結果より上記の値に設定した．. 実行可能解を見つけられなかった）ことを意味する．. 制限時間を設けた．予備実験の結果より制限時間を 300. (1) 繰り返し回数について手法 S0 ではいずれの問題例でも繰り返し回数の上限までに収束しなかったが，手法 S1 や S2 では収束した問題例も存在する．タイムアウトしなかった問題例（24 例）中，手法 S1 では 15 例で，手法 S2 では 9 例で収束. 秒とした．. した．. また，エージェントが解く最適化問題は元の問題に比べて小規模となるが，組合せ最適化問題であるため最適解を得るには膨大な時間が必要な場合がある．そのため，エージェントの 1 回の最適化（(6) 式の実行）においても. 4.2. タイムアウトしなかった問題例において大きく分ける. 結果. 繰り返し回数を Table 1 に示す．inst. は問題例の名前，. m は機械数，n はジョブ数である．表中の > 200 は繰り 1. と，1) 手法 S1 でのみ収束した，2) 手法 S2 でのみ収束した，3) 手法 S1 と S2 でのみ収束した，4) いずれの手法でも収束しなかった場合の 4 通りに分けることができる．手法 S1 でのみ収束した 9 例のうち abz8 と la29 につ. https://github.com/tamy0612/JSPLIB. – 35 –.

(7) 64. システム制御情報学会論文誌第 34 巻第 2 号 (2021) SULPDO GXDO. SULPDO GXDO. . . UHVLGXH. UHVLGXH. . . . . Fig. 5. . . . N. . . . . . Change of primal and dual residues for abz8 by S0. . Fig. 7. . . . N. . . . . Change of primal and dual residues for la35 by S0. SULPDO GXDO. . WLPH>V@. UHVLGXH. . . . . . . Fig. 6. . . . N. . . . . . . . Fig. 8. N. . . . . Change of computation time for abz8 by S0. Change of primal and dual residues for la29 by S0. いて，手法 S0 での主残差と双対残差の変化を Fig. 5 と. あることが確認できた．手法 S1 と S2 でのみ収束した 6 例のうち，la18 では手. . WLPH>V@. Fig. 6 に示す．問題例 abz8 については順調に主残差が減少しており，手法 S0 でもさらに繰り返すことにより収束すると考えられる．これに対し，問題例 la29 については k = 90 あたりから主残差と双対残差の減少が止まっている．この例では Fig. 4 のような振動が起こっており，手法 S0 では収束しない．手法 S1 でのみ収束した 9 例のうち la29, ta16, ta26 の 3 例は la29 と同様の振る舞いをしており，残りの 6 例（abz8, la28, orb06, ta08, ta09, ta25）は abz8 と同様の振る舞いをしていた．方策 1 を適用することにより，abz8 と同様の 6 例については無駄な繰り返しを止めさせることに成功していた．la29 と同様の 3 例については実行可能解を導くことに成功していた．手法 S2 でのみ収束した 3 例（abz5, la13, swv02）について残差の変化の様子を調べた．手法 S0 と S1 では Fig. 6 と同様の変化をしていた．すなわち，Fig. 4 のような振動が起こっており収束しなかった．手法 S2 では収束したため，パラメータ c を増加させることは効果が. . . Fig. 9. . . . N. . . . . Change of computation time for la35 by S0. あった．いずれの手法でも収束しなかった 6 例のうち la35 について手法 S0 での主残差と双対残差の変化を Fig. 7 に示す．la12 と la27 についてはいずれの手法でも Fig. 6 のようにある程度収束してから振動していたが，その他の 4 例（la35, ta33, ta42, ta50）ではいずれの手法でも. Fig. 7 のように大きく振動していた．大きく振動していた 4 例はいずれもジョブ数が 30 であり，ある程度収束していた例よりジョブ数が多い．ま. 法 S0 において振動が起こっており，繰り返し回数を増. た，ジョブ数が 50 以上の例ではすべてタイムアウトし. やしても収束が見込めなかった．その他の 5 例（abz6,. la10, la11, orb04, orb05）では残差が減少していたため，繰り返し回数を増やすと手法 S0 でも収束する見込みは – 36 –. ていた．したがって，300 秒という制限時間がこれらの問題例に対しては短すぎることが大きく振動した理由として考えられる．.

(8) 宮本・梅田・高井：分散スケジューリング問題に対する合意に基づく解法. 65. 化計算することが可能である．しかし，ジョブ数が 30. (2) 計算時間について問題例 abz8 と la35 について手法 S0 での計算時間の変化の様子を Fig. 8 と Fig. 9 に示す．計算時間は各エージェントでの最適化時間（(6) 式の実行時間）の総和である．2 例とも機械数は 10 なのでエージェント数は 11 となり，最適化時間の総和の最大値は 3300 秒である．問題例 abz8 では初期の数回はいくつかのエージェン. 個程度の例題でもエージェントでの最適化計算が制限時間までかかっている．今回の実験では数理計画ソルバを使って最適化計算を行ったが，大規模システムへの適用のためにはスケジューリングに関する既存手法との融合について検討する必要がある．これらについては今後の課題としたい．. トで制限時間まで最適化計算しているが，繰り返し回数の増加にともない最適化時間は短くなっていた．そして，. 関連研究. 5.. 本論文ではマルチエージェントにもとづくスケジュー. 途中からはすべてのエージェントで制限時間内に最適化が終了していた．ガントチャートの変化の様子を見ると，. リング問題について検討した．マルチエージェントにも. 初期では作業順が大幅に変更されるのに対し，途中から. とづくスケジューリングという考え方自体は新しいも. は作業順はあまり変わらず作業開始時刻の微調整となっ. のではない．Intelligent Manufacturing System (IMS). ていた．手法 S1 や S2 で収束した問題例ではいずれの手. プログラム1 は米国，欧州そして日本の 3 地域間の共同. 法でも計算時間について同様の傾向が見られた．すなわ. 研究プロジェクトとして 1995 年に始まった．IMS に. ち ADMM アルゴリズムでは，スケジュールの概形が決. おける初期のプロジェクトの中にエージェントにもと. まるまではエージェントの最適化には時間を要するが，. づく生産システムに関するものを見つけることができ. 概形が決まってからは作業開始時刻の微調整となるため. る．たとえば，次世代生産システム (Next Generation. Manufacturing Systems)[15,16]，ホロニック生産シス. 毎回の最適化における時間は短くなる．. テム (Holonic Manufacturing Systems)[17] がある.. 問題例 la35 のように残差が大きく振動して収束しなかった 4 例については，繰り返し回数が増加しても最適. マルチエージェントにもとづくスケジューリング方法. 化時間は制限時間までかかっていた．これらの例ではス. は三つの種類に分けることができる：ヒューリスティッ. ケジュールの概形が定まらないため最適化時間が減少し. ク法，メタヒューリスティック法，最適化法．ヒューリスティック法では，エージェントが機械やジョ. なかったと考えられる．. ブに対して存在し，エージェントは古典的なディスパッ. 4.3. 考察本論文では ADMM アルゴリズムを収束させるための. チングルールにより判断を下す．Miyamoto らは状況依. 二つの方策を示した．実験結果は両方策とも効果がある. 存エージェントを JSP に適用している [18]．ここでは，. ことを示していた．. エージェントは機械に対して存在し，ルールの集合から. 方策 1 はスケジュールの振動が発生しない場合に無駄. 生産システムの状況に応じてルールを選択し，次の操作. な繰り返しをなくすのに有効である．しかし，方策 1 に. をルールにより決定している．Lee らはエージェントが. は振動を抑える効果はない．問題例 la29 を含む 3 例のよ. ジョブに対して存在し，つぎに処理される機械をルール. うに方策 1 を使わない場合に振動する例題において実行. にもとづき選択する分散スケジューリング法を示してい. 可能解を見つけることができたが，これは振動中に処理. る [19]．メタヒューリスティック法ではマルチエージェントシ. 順に関する残差が 0 になっただけである．方策 2 には振動を抑える効果があると考えられるが，. ステムがメタヒューリスティックにより JSP を解く．文. 問題例に対して適切にパラメータを選択する必要があり，. 献 [20] ではタブーサーチが使われ，文献 [21] では免疫ア. その選択は容易ではない．. ルゴリズムが使われている．. また，今回の実験ではジョブ数が 30 以上の問題例に. 最適化法では分散最適化手法が使われる．文献 [22–24]. ついては残差が大きく振動してしまった．ジョブ数が 20. ではラグランジュ分解法（Lagrangian Decomposition;. 以下の問題例では振動が発生しても全体スケジュールのうち一部について合意が取れず振動しているだけでス. LD，ラグランジュの分解調整法や双対分解法ともいわれる）[25] を JSP に適用している．LD は JSP 以外の問. ケジュールの概形は定まっていた．しかし，ジョブ数が. 題への適用も報告されている．たとえば，ビークルスケ. 30 以上の問題例ではスケジュール全体が大きく変化して. ジューリング [26] や割り当て問題 [27] がある．. LD と ADMM の違いは，エージェント間にまたがる. いた．実験の結果は，スケジュールの振動を抑えたり，スケ. 制約を緩和するときにラグランジュ関数を使うか拡張ラ. ジュールの概形を定めたりする仕組みのさらなる検討が. グランジュ関数を使うかである．ADMM アルゴリズム. 必要であることを示している．. の (6) 式において，パラメータ c を 0 とすると LD アルゴリズムとなる．LD と比べると ADMM は収束性が良い. 実験では逐次的に最適化を行ったが，提案手法は分散最適化手法であるためエージェントごとに並行的に最適. 1. – 37 –. https://www.ims.org/.

(9) 66. システム制御情報学会論文誌第 34 巻第 2 号 (2021). ことが知られている．凸最適化において，LD は目的関数に対して狭義の凸性を要求するのに対して，ADMM は 2 乗のペナルティ項を持つため目的関数に狭義の凸性までは要求しない [8]．すなわち，ADMM の方がより広範囲の問題に適用することができる．なお，本論文で扱った JSP は連続緩和すると線形制約になるため，LD を適用するにはエージェントごとの目的関数 fi () を狭義凸関数にしなければならない．. 6.. おわりに. 本論文ではスケジューリング問題に対する分散解法として合意問題に対する ADMM アルゴリズムを用いる方法を提案した．合意問題に対する ADMM アルゴリズムは凸最適化問題に対する解法であるため，非凸最適化問題であるスケジューリング問題では最適性や収束性は保証されないが，計算機実験により例題によっては収束することを確認できた．また，提案した収束させるための方策も効果があることを確認できた．本論文では提案手法の収束性について評価することを目的としたため，解の質については評価しなかった．大規模システムでは多種多様な評価項目があり，解の質は総合的に判断される．解の質についての評価は，提案手. proach; IEEE Trans. Smart Grid, Vol. 9, No. 5, pp. 4964–4974 (2018) [6] W. Ren, R. W. Beard and E. M. Atkins: A survey of consensus problems in multi-agent coordination; Proc. of ACC, pp. 1859–1864 (2005) [7] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein: Distributed optimization and statistical learning via the alternating direction method of multipliers; Foundations and Trends in Optimization, Vol. 3, No. 1, pp. 1–122 (2010) [8] 宮本，北村，森，泉井：交互方向乗数法を用いた分散最適化—エネルギー管理システムへの応用；システム／制御／情報, Vol. 60, No. 6, pp. 219–224 (2016) [9] G. Mateos, J. A. X. S. Bazerque and G. B. Giannakis: Distributed sparse linear regression; IEEE Trans. Signal Process., Vol. 58, No. 10, pp. 5262– 5276 (2010) [10] T.-H. Chang, M. Hong and X. Wang: Multiagent distributed optimization via inexact consensus ADMM; IEEE Trans. Signal Process., Vol. 63, No. 2, pp. 482–497 (2015) [11] H. P. Williams: Model Building in Mathematical Programming, 5-th ed., Wiley (2013) [12] 宮野，山下，畑中，柴田，神保，藤田：連続時間 ADMM の提案と受動性に基づく収束性解析；計測自動制御学会論文集，Vol. 55, No. 4, pp. 286–293 (2019). 法を今後より現実的な問題に適用するうえで実施したいと考えている．. [13] S. Yamashita, T. Hatanaka, J. Yamauchi and M. Fujita: Passivity-based generalization of primal–dual dynamics for non-strictly convex cost functions; Automatica, Vol. 112, p. 108712 (2020) [14] M. J. Feizollahi, M. Costley and S. Grijalva: Largescale decentralized unit commitment; Intl. J. of Elect. Power and Energy Syst., Vol. 73, pp. 97–106 (2015) [15] T. Okabe, P. Bunce and R. Limoges: Next generation manufacturing systems (NGMS) in the IMS program; Advances in Production Management Systems, pp. 43–54, Springer (1998) [16] P. Bunce, R. Limoges and T. Okabe: NGMS — Next Generation Manufacturing Systems (IMS Project); Enterprise Engineering and Integration, pp. 274–283, Springer (1997) [17] H. Van Brussel, P. Valckenaers and J. Wyns: HMS — Holonic Manufacturing Systems test case (IMS Project); Enterprise Engineering and Integration, pp. 284–292, Springer (1997) [18] T. Miyamoto, B. Krogh and S. Kumagai: Contextdependent agents for real-time scheduling in manufacturing systems; IEICE Trans. on Fundamentals, Vol. E85-A, No. 11, pp. 2407–2413 (2002) [19] K. Lee, J. Y. T. Leung and M. L. Pinedo: Coordination mechanisms for parallel machine scheduling; European Journal of Operational Research, Vol. 220, No. 2, pp. 305–313 (2012) [20] M. Ennigrou and K. Ghédira: New local diversification techniques for flexible job shop scheduling. 本論文により，大規模システムに対する分散スケジューリング手法の一つとしての提案手法の可能性を確認することができた．今後は，実行可能解を現実的な時間で求解するための検討，解の最適性について検討，現実的なシステムへの適用により提案手法のさらなる評価・改善を行いたい．. 参考文献 [1] K. L. Moore and D. Lucarelli: Decentralized adaptive scheduling using consensus variables; Int. J. Robust Nonlinear Control, Vol. 17, No. 10, pp. 921–940 (2007) [2] N. Hayashi, T. Ushio and T. Kanazawa: Adaptive arbitration of fair QoS based resource allocation in multi-tier computing systems; IEICE Trans. Fundamentals, Vol. 93, No. 9, pp. 1678–1683 (2010) [3] K. Segawa, K. Hamada, N. Hayashi and S. Takai: Cooperative target tracking by 2-level hierarchical PTZ camera sensor networks; Proc. of IEEE CDC, pp. 2975–2980 (2015) [4] N. Hayashi and S. Takai: Distributed source identification by two-hop consensus dynamics with uniform time-varying communication time-delays; SICE J. on Cont., Measurement, and Syst. Integration, Vol. 10, No. 2, pp. 70–76 (2017) [5] D. H. Nguyen, T. Narikiyo and M. Kawanishi: Optimal demand response and real-time pricing by a sequential distributed consensus-based ADMM ap-. – 38 –.

(10) 宮本・梅田・高井：分散スケジューリング問題に対する合意に基づく解法. [21]. [22]. [23]. [24]. [25]. [26]. [27]. 67. 著者略歴. problem with a multi-agent approach; Autonomous Agents and Multi-Agent Systems, Vol. 17, No. 2, pp. 270–287 (2008) W. Xiong and D. Fu: A new immune multi-agent system for the flexible job shop scheduling problem; Journal of Intelligent Manufacturing, Vol. 29, No. 4, pp. 857–873 (2015) L. Gou, T. Hasegawa, P. B. Luh, S. Tamura and J. M. Oblak: Holonic planning and scheduling for a robotic assembly testbed; Proc. of the 4th Intl. Conf. on Computer Integrated Manufacturing and Automation Technology, pp. 142–149 (1994) N. Liu, M. A. Abdelrahman and S. Ramaswamy: A complete multiagent framework for robust and adaptable dynamic job shop scheduling; IEEE Trans. on SMC Part C-Applications and Reviews, Vol. 37, No. 5, pp. 904–916 (2007) C. Xu, G. Sand, I. Harjunkoski and S. Engell: A new heuristic for plant-wide schedule coordination problems: The intersection coordination heuristic; Computers and Chemical Engineering, Vol. 42, pp. 152– 167 (2012) M. Guignard and S. Kim: Lagrangean decomposition: A model yielding stronger lagrangean bounds; Mathematical Programming, Vol. 39, No. 2, pp. 215– 228 (1987) T. Nishi and Y. Tanaka: Petri net decomposition approach for dispatching and conflict-free routing of bidirectional automated guided vehicle systems; IEEE Trans. on SMC - Part A: Systems and Humans, Vol. 42, No. 5, pp. 1230–1243 (2012) K. Hanada and K. Hirayama: Distributed Lagrangian relaxation protocol for the over-constrained generalized mutual assignment problem; Proc. of Intl. Conf. on Principles and Practice of Multi-Agent Systems, pp. 174–186 (2011). みやもと. としゆき. 宮本俊幸 (正会員) 1997 年 3 月大阪大学大学院工学研究科博士後期課程修了．同年 4 月同大学工学部助手，2003 年同大学院工学研究科講師， 2006 年同助教授，2007 年同准教授となり現在に至る．その間，2000 年 10 月より 2001 年 9 月まで文部省在外研究員として. カーネギーメロン大学にて客員研究員．離散事象システム，自律分散システム，マルチエージェントシステムなどの研究に従事．博士（工学）．IEEE，電子情報通信学会，計測自動制御学会などの会員．うめ. だ. とよひろ. 梅田豊裕. 1991 年 3 月大阪大学大学院基礎工学研究科制御工学専攻修士課程修了．同年 4 月（株）神戸製鋼所入社．2001 年 3 月神戸大学大学院自然科学研究科情報メディア科学専攻博士後期課程修了．現在，同社生産システム研究所に所属し，現実の生産システムを対象にした最適化やスケジューリング技術の応用研究に従事．博士（工学）．日本 OR 学会，日本鉄鋼協会，日本経営工学会などの会員．たか. い. しげまさ. 高井重昌 (正会員) 1991 年 3 月神戸大学大学院工学研究科システム工学専攻修士課程修了．1992 年 6 月大阪大学工学部助手，1998 年 4 月和歌山大学システム工学部講師，1999 年 10 月同助教授，2004 年 10 月京都工芸繊維大学工芸学部助教授，2007 年 4 月同大学大学院工芸科学研究科准教授，2009 年 4 月大阪大学大学院工学研究科教授となり現在に至る．離散事象システムの制御，診断などの研究に従事．博士（工学）．電子情報通信学会，計測自動制御学会，IEEE の会員．. – 39 –.

(11)