統合スケジューリングに関する研究

(1)

ハイブリッド型遺伝的アルゴリズムを用いた生産・物流情報システムのための

統合スケジューリングに関する研究

Study on Integrated Scheduling for Manufacturing and Logistics Information System using Hybrid Genetic Algorithm

2007 年 4 月

岡本東

(2)

ハイブリッド型遺伝的アルゴリズムを用いた生産・物流情報システムのための

統合スケジューリングに関する研究

Study on Integrated Scheduling for Manufacturing and Logistics Information System using Hybrid Genetic Algorithm

2007 年 4 月

早稲田大学大学院情報生産システム研究科

情報生産システム工学専攻ソフトコンピューティング研究

岡本東

(3)

第 1 章緒言

1.1 研究の背景と目的

生産スケジューリングにサプライチェーンの視点を取り入れて考案された先進的スケジューリング

（Advanced Planning and Scheduling; APS）は，生産管理，生産スケジューリング，供給・在庫計画，物流・輸送計画，工程計画，製品設計，さらにはMES（Manufacturing Execution System）をはじめとする実行系をも統合した形態に発展している。APS の実現のために，製造業における情報システムの基幹となるデータ交換形式，オブジェクトモデル，データベース・スキーマなど，また，それらすべての基礎となるオントロジも含め標準規格の制定，それに基づく実装が進められている（PSLX, 2003）

（Nishioka & Wada, 2006 (1)-(3)）。

生産スケジューリングをはじめとするAPSに含まれる個々の問題においても，NP（Non-deterministic Polynomial）困難な組合せ問題となっているものが多く，従来はそれぞれの問題の特性に合わせた最適解法が研究されてきた。しかし，APS の実現の上で，問題を統合して取り扱う場合においては，複数の問題の解が互いに制約となるなど複雑な構造を持ち，従来の手法での最適なスケジュール作成は困難である。

このような，構造を明らかにすることが困難な問題に対しては，探索的な手法が有効となる場合が多い。中でも，遺伝的アルゴリズム（Genetic Algorithm; GA），シミュレーテッド・アニーリング法

（Simulated Annealing; SA），タブー探索法（Tabu Search; TS）などをはじめとするメタ戦略による最適化は近年注目され研究が盛んに行われている。これらの手法は，従来の解析に基づく近似解法解と比較して頑健性が高く，現実の問題に含まれる複合問題や制約の変更・追加のように時間と共に構造が変化する問題にも適応することができる。しかし，従来のメタ戦略に関する研究の多くは，シンプルにモデル化されたスケジューリング問題や配送問題を対象としていた。

また，今日の製造業における計画やスケジューリングにおいては，単一の企業内だけでなく，複数の企業をまたがったサプライチェーン全体の枠組で問題を捉える必要があり，このためには，情報システム間のデータ交換に用いる，標準化されたデータ・フォーマットの策定が必要となる。一方，個々の企業や企業群に蓄積されたノウハウや特色を活かした情報システムの構築のためには，一般的な情報を取り扱うだけでなく，特定の企業や企業群に固有の情報も柔軟に取り扱う必要がある。このため，

一般的な項目を整理し標準化する一方で，拡張性についても考慮する必要がある。

本研究の目的は，設備保守等によって変化するスケジューリング問題や，生産スケジューリングと輸送計画といった複合問題に対して，柔軟に対応可能なデータ・フォーマットと，それらを処理し効率的に最適化を行う遺伝的アルゴリズムを用いたスケジューラを中心とした生産・物流システムの研究開発を行う。まず，既存の生産スケジューリングおよび輸送計画に関する研究の成果を明らかにし，

(7)

研究対象となるスケジューリング問題へ従来手法を適用した場合の問題点を明らかにする。また，生産と輸送の統合スケジューリング問題について数学モデルを定式化し，このモデルに適した効率的な最適化手法を提案する。

1.2 本論文の構成

本論文は以下の7章から構成されている。

第 2 章では，従来研究されてきたスケジューリング問題について述べ，本研究で提案するモデルとの違いを明らかにする。また，遺伝的アルゴリズムによるスケジューリング手法の開発の必要性について述べる。

第3章と第4章ではAPSシステムを実現するためのスケジューラの実現について述べる。

第3 章では，APS システムにおけるスケジューリングの重要性を示し，遺伝的アルゴリズムを用いたスケジューリング・エージェントとそこで用いるデータ構造の提案を行う，更に，設備保守の追加を例として，システム構築時に想定していなかった要素を追加する際にも，最小限の変更で要素を追加することができることを検証し，本手法の柔軟性を示す。

第4 章では，APS システムにおける生産スケジューリングと配送計画を担うスケジューリング・エージェントと輸送管理エージェントの連携方法について述べ，その一手法として，生産と配送のそれぞれの最適化を考慮した多目的最適化を行い，複数の妥協解を求め，その中から適切なものを選択する方法について示す。

第5章と第6章では，生産・輸送の統合スケジューリングを行うためのモデルについて述べる。

第 5 章では，生産工程と輸送作業を作業として統一的に取り扱い，また，生産設備である機械と車輌を資源として統合的に取り扱うことによって，生産と輸送のスケジューリングを統一的に実現するモデルを提案する。この統合モデルによって生産スケジューリングのための手法を大幅に変更することなく，生産・輸送の統合スケジューリングを可能としている。

第 6 章では生産工程とピックアップ‐デリバリのサービスを作業として取り扱うことによって，異なる種類の資材，半製品，製品の混載輸送を考慮したスケジューリングのためのモデルを示す。これにより，従来のモデルを用いた場合より現実的かつ効率的なスケジュール生成を可能とする。これらのモデルを基に，生産のための GA スケジューラの処理の一部を変更することによって，生産と輸送の多目的スケジューリングを実現する。

第7章で，本論文から得られた知見についてのまとめを行い，今後の課題について述べる。

本研究で用いるスケジューリング・サブシステムと周辺システムの基本構成を図1.1に示す。顧客からの要求に基づくオーダ情報と製造BOM（Bill of Manufacturing）がXML（Extensible Markup Language）文書として与えられ，これを元にプリプロセッサが必要な染色体のサイズなどのGAのパラメータや，

先行制約などの制約を決定する。GAスケジューラの出力した最適解はポストプロセッサから出力される。輸送および配送に関する要素がある場合には輸送管理サブシステムとの間で調整を行う。製造指示サブシステムによって作業指示書をXML文書として出力する。さらに，この作業指示書をXSL（XML

(8)

Stylesheet Language）によって書かれた変換規則を元にXSLT（XSL Transformations）（W3C, 1999）を用いて変形することによって，SVG（Scalable Vector Graphics）（W3C, 2003）によるガントチャートを出力することができる。

ポストプロセッサ GAスケジューラプリプロセッサ

生産オーダ顧客からの BOM管理注文情報

製造指示書製造BOM

輸送管理製造指示

XSLT プロセッサ

生産能力・

生産ルール

ガントチャート

ポストプロセッサ GAスケジューラプリプロセッサ

生産オーダ顧客からの BOM管理注文情報

作業指示書製造BOM

輸送管理製造指示

XSLT プロセッサ

生産能力・

生産ルール

ガントチャート

XML XML

XML

XML SVG

設備保守設備保守

XML

図1.1 生産・物流情報システムのスケジューリング・サブシステム構成図

(9)

第 2 章スケジューリング問題と遺伝的アルゴリズム

2.1 はじめに

従来，スケジューリング問題および配送問題は，組合せ最適化問題として数多くの研究が行われ，

解法が開発されてきた。規模の大きな問題においては，厳密解を求めることが困難であることから，

問題の理論的な解析に基づく近似解法や，発見的（ヒューリスティック）解法に関する研究が大部分を占める。前者は短い時間で良好な解を得ることができ，解の下界が保障されるなどの利点を有するものも多いが，問題の構造の変化に対応できないといった欠点がある。一方，発見的手法はこれらとは相反する性質を持ったものが多い。本章では，従来のスケジューリング問題および配送問題について述べ，第 3 章以降で提案するモデルとの違いを明らかにする。また，発見的手法の中でもメタ戦略に属する遺伝的アルゴリズムによるスケジューリング手法の開発の必要性について述べる。

2.2 生産と物流に関する問題の分類

2.2.1 スケジューリング問題

生産工程を対象としたスケジューリング問題として最も盛んに研究されているのは，ジョブショップ・スケジューリング問題（Job-shop Scheduling Problem; JSP）であり，製品をつくるために必要な作業群（ジョブ）とその作業順序，作業と機械の対応関係が与えられ，主にメークスパンの最小化を目的関数とした最適化を行う。また，作業に割り当て可能な機械が複数存在するフレキシブル・ジョブショップ・スケジューリング問題（Flexible Job-shop Scheduling Problem; fJSP）（Brucker & Schlie, 1990）

（Kacem et al., 2002），作業順序が自由なオープンショップ・スケジューリング問題（Open-shop Scheduling Problem; OSP），作業順序や機械の割当がすべてのジョブで共通なフローショップ・スケジューリング問題（Flowshop Scheduling Problem; FSP）などのバリエーションがある。これらのスケジューリング問題を一般化した数学モデルを以下に示す。

インデックス

i, j: 作業番号, i, j = 1, 2, …, J_k k, l: ジョブ番号, k, l = 1, 2, …, K m, n: 機械番号, m, n = 1, 2, …, N

パラメータおよび決定変数

K: ジョブ総数 N: 機械総数

(10)

Jk: オーダkにおける作業数 oki: オーダkにおけるi番目の作業 Mm : m番目の機械

p_kim: 作業o_kiの機械M_mにおける工程時間 c_M: メークスパン

c_ki: 作業o_kiの終了時刻

1, , 0, .

ki m

kim

o M

x =⎧⎪⎨

⎪⎩

作業において資源が選択された場合それ以外の場合

1, , 0, .

ki lj

kilj

o o

y ⎧

=⎨

⎩

をより先に実行する場合それ以外の場合　　　　　

ここでは，目的関数としてメークスパンを最小化する場合について述べる。

min ^c^M⁼^max_{i k}_,

{ }

^c^ki (2.1)

s. t.

(

c^lj−p^ljm−c x x y^ki

)

kim ljm kilj ≥⁰ ∀( , ),( , ),k i l j m (2.2)

(

c^kj−p^kjn−c^ki

)

x x ykim kjn kikj ≥⁰ ∀i j k m n, , , , (2.3)

kij kjki 0

r y = ∀i j k, , ^(2.4)

kiki 0

y = ∀i k, (2.5)

kilj ljki 1

y +y = ∀( , ),( , ),( , ) ( , )k i l j k i ≠ l j ^(2.6)

1 N 1

kim m

x

=

∑

= ^∀^{i k}^, ^(2.7)

(

^c^ki⁻^p^kim

)

^x^kim^≥⁰ ^∀^{i k m}^{, ,} ^(2.8)

ki 0

c ≥ ∀i k, (2.9)

{ }

^0,1

xkim∈ ∀i k m, , ^(2.10)

{ }

^0,1

ykilj∈ ∀( , ),( , )k i l j ^(2.11)

式_(2.1)はメークスパンを最小化する目的関数である。式_(2.2)は₁つの機械を複数の作業へ同時に割当できないことを示す。式_(2.3)はジョブにおける先行作業がある場合，それらが終了した後に作業が開始できることを示す。式(2.4)は先行作業より先に作業を開始できないことを示す。式(2.5), (2.6)は作業順序の整合に関する制約を示す。式(2.7)はすべての作業はいずれか 1 つの機械に割当されることを示す。式(2.8)はすべての作業が基準時刻(0)以降に開始することを示す。式(2.9), (2.10), (2.11)は非負条件である。なお，これらの制約条件は説明のため冗長に記述しており，実際の各問題においては不要なものも含まれている。

JSP, fJSPおよび_FSPにおいては，先行関係_r_kijについて式_(2.12)が成り立つ。

1, 1 ,

0, .

kij

r ⎧ j i= +

=⎨

⎩

の場合

それ以外の場合 ^(2.12)

(11)

一方OSPの場合にはrkijは，常に0である。

また，_fJSPにおいて資源割当_x_kimは決定変数であるが，JSP, OSP, FSP においてはパラメータとして与えられる。_FSPにおいては，多くの場合，ジョブ_kに関わらず式_(2.13)が成り立つ。

1, ,

0, .

kim

i m

x ⎧ =

=⎨

⎩

の場合

それ以外の場合 ^(2.13)

これらのスケジューリング問題を更に発展させた，_iRS/OS（Integrated Resource Selection and Operation Sequence）及び_APS（Advanced Process Planning and Scheduling）（_{Moon, 2004}）が提案されている。これらの問題では，先行関係_r_kijはパラメータとして与えられ，資源割当_x_kimは_fJSPと同様に決定変数となっている他，段取りや輸送など，一般的なスケジューリング問題には含まれない要素が追加されている。しかし，これらの問題における輸送では，車輌（資源）の台数や積載量に関する制約は考慮されていない。

2.2.2 配送問題

配送問題は，巡回セールスマン問題（Traveling Salesman Problem; TSP）を基本とし，複数の車輌による巡回を行う車輌配送問題（Vehicle Routing Problem; VRP），またピックアップ‐デリバリを考慮した VRP-pd（VRP with Pickup and Delivery）（Mosheiov，1994）などの派生問題がある。配送問題を一般化した数学モデルを以下に示す。

インデックス

i, j, k: ロケーション番号, i, j, k = 0, 1, 2, …_{, J (0:}配送拠点₎ m: 車輌番号, m = 1, 2, …, N

パラメータおよび決定変数

J: ロケーション総数 N: 車輌総数

P_i : i番目のロケーション M_m : m番目の車輌 dij: Pi, Pj間の距離 rij: Pi, Pjの巡回順序制約 T: 総走行距離

1, , ,

0, .

i j m

ijm

P P M

x =⎧⎪⎨

⎪⎩

間の輸送に車輌が割り当てられた場合それ以外の場合

( )

1, 0 ,

0, .

m i j

ijm

M P i P

y ⎧⎪ ≠

=⎨

⎪⎩

車輌がを出発した後にに到着する場合それ以外の場合

一般に目的関数として総走行距離（または時間）の最小化が用いられる。以下も同様の目的関数に

(12)

基づくモデルを示す。

min

1 1 1

N J J

ij ijm

m i j

T d x

= = =

=

∑∑∑

^(2.14)

s. t.

1 0 1 0

1

N J N J

ijm jim

m j m j

x x

= = = =

= =

∑∑ ∑∑

^{∀ ≥}ⁱ ¹ ^(2.15)

0

1 1 1

0

J J J

im ijm

i i j

Jx x

= = =

− ≥

∑ ∑∑

^∀^m ^(2.16)

0 0

1 1

1

J J

im i m

i i

x x

= =

= ≤

∑ ∑

^∀^m ^(2.17)

ijm ikm kjm 0

y −y x ≥ ∀i j k m, , , (2.18)

1 N 0

ijm ij m

y r

=

∑

− ≥ ^∀^{i j}^, ^(2.19)

{ }

^0,1

xijm∈ ∀i j m, , (2.20)

{ }

^0,1

yijm∈ ∀i j m, , (2.21)

式(2.14)は総走行距離を最小化する目的関数である。式(2.15)は配送拠点を除くすべてのロケーションについていずれかの車輌1台が配送のために到着し，出発することを示す。式(2.16)は配送拠点を出発していない車輌は他のロケーションに配送を行うことができないことを示す。式(2.17)は配送拠点を出発した車輌は必ず配送拠点に戻り，かつ配送拠点を出入りする回数は 1 回までであることを示す。式 (2.18)は巡回順序の整合に関する制約である。式(2.19)は巡回順序に制約がある場合，同じ車輌で指定の順序で巡回することを示す。式(2.20), (2.21)は非負条件である。このモデルも先のスケジューリング問題のモデルと同様，説明のため冗長なモデルとなっている。

TSPの場合には車輌総数Nは常に1である。また，TSPおよび一般のVRPでは巡回順序に関する制約はなく常にrij = 0である。VRP-pdでは，一部の巡回順序に制約があり，荷物をPiで積載しPjへ配送する場合にのみrij = 1となる。

2.2.3 生産と物流の統合スケジューリング

本研究では，生産と物流の統合スケジューリングを提案する。一般に，資材の到着時刻や顧客への商品到着時刻を考慮した生産スケジュールを作成するためには物流の要素は無視できず，また，製品の配送スケジュールを作成するためには生産の要素を考慮しなければならない。このため，双方のスケジュールを，より詳細なレベルで最適化するためには統合されたモデルが必要になる。

前節で述べた既存のモデルについての差異および従来の研究と第 5章および第6 章で述べる統合スケジューリングの比較を表2.1にまとめる。「先行関係」は作業間の先行関係が，暗黙のうちに定まっている場合（固定），存在しない場合（なし），または問題によって明示的に与えられる場合（任意）

のいずれかを表している。「機械割当」は作業に割当てる機械が問題によって与えられている場合（固定），または複数の資源から決定しなければならない場合（代替資源あり）のいずれかを表している。

(13)

「車輌割当」は輸送の際に使用する車輌を決定する必要があるかどうかを，「混載輸送」は複数の品物を同時に 1 台の車輌で輸送することが可能かどうかを表している。「作業時間」「輸送時間」は，問題中で該当する時間を取り扱うかどうかを表している。

表2.1 従来のスケジューリング問題と本研究の比較

FSP OSP JSP fJSP TSP VRP VRP-pd

iRS/OS, APS

（Moon, 2004）

統合1

（5章）

統合2

（6章）

先行

関係固定なし固定固定なしなし一部あり任意任意任意機械

割当

全ジョブ

共通固定固定代替資源

あり - - - 代替資源

あり

代替資源あり

代替資源あり作業

時間ありありありあり - - - ありありあり車輌

割当 - - - - なし

（一台）ありありなし

（無制限）ありあり輸送

時間 - - - - ありありありありありあり

混載

輸送 - - - - 配送

のみ配送

のみありなしなしあり -: 該当する要素が存在しないことを意味する

2.3 既存の近似解法によるスケジューリング

問題の理論的な解析に基づく近似解法は，対象とする問題と同じモデルで表すことが可能な問題であっても，そのパラメータによっては良い解が得られない場合がある。

Beck et al.（2003）は，市販のスケジューリング向けエンジン（ILOG Scheduler）及び車輌ルーティ ング向けエンジン（ILOG Dispatcher）をJSPおよびVRPの特徴を持つ問題に適用し，それぞれの問題と解法の特性についての調査結果を述べている。用いられたエンジンはいずれも制約ベースのソルバーを拡張するもので，前者はEdge-findingやPrecedence graphなどの制約伝播（Constraint Propagation）を，後者は初期解にセービング法（Saving heuristics），解の改善に誘導局所探索法（Guided Local Search;

GLS）を用いている。この結果，これらの手法を本来の対象でない問題に適用した場合には，様々な問題があることが指摘されている。特に顕著な例として，車輌ルーティング向けエンジンを JSP に近い問題に対して適用した場合，すべての距離が 0 であるためセービング法による初期解の生成ができない点が述べられている。

このことから，本研究における生産と物流の両方の要素を含むスケジューリング問題に対して，スケジューリング問題や配送問題のために開発された既存の解析的な手法をそのまま適用することは，

難しいと考えられる。

(14)

2.4 遺伝的アルゴリズムとその特徴

遺伝的アルゴリズム（Genetic Algorithm; GA）は，1975年にミシガン大学のJohn Hollandによって提案された，近似解を探索するメタ戦略の一手法である。GAでは，解の候補を複数の遺伝子から成る染色体で表現し，この染色体を複数用意する。適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。利点として，評価関数の特性が十分に明らかでない場合にも適用可能なことが挙げられる。また，染色体設計を工夫することにより，様々な種類の組合せ最適化問題をはじめとするNP困難な問題に適用可能である。

GAは自然淘汰と自然界の遺伝メカニズムを参考にしている。従来のアルゴリズムとは異なりGAは群体（population）と呼ばれる初期の無作為の解から始まる。問題の潜在的解決を表して，群体における各々の解表現は個体（individual）または染色体（chromosome）と呼ばれる。ここで，個体が進化するときの繰り返しの単位を世代と呼ぶ。各世代の間，個体は適合値（fitness）を使用することによって評価される。次世代を形成するために，複数の染色体に対して交叉を行い，突然変異を行うことによって新しい染色体が形成される。各個体の適合値に従い，新しい世代は良い個体の集合で形成される。

図2.1に一般的なGAのプロシージャを示す。この図では，世代数tにおける親群体P(t)と子群体C(t) を用いてGAのアルゴリズムを表現している。

procedure: Genetic Algorithm input: GA parameters, problem data output: a best solution

begin t ← 0;

initialize P(t) by encoding routine;

evaluate P(t) by decoding routine;

while (not termination condition) do crossover P(t) to yield C(t);

mutation P(t) to yield C(t);

evaluate C(t) by decoding routine;

select P(t +1) from P(t) and C(t);

t ← t +1;

end

output a best solution;

end

図2.1 基本的なGAのプロシージャ

メタ戦略はGAの他にシミュレーテッド・アニーリング法（Simulated Annealing; SA），タブー探索法

（Tabu Search; TS）などが良く知られている。これらの中で，GAは多点探索を行う点が特徴となっており，問題の構造の変化に対する頑健性や多目的問題への適応性に優れている。一方，局所的な探索

(15)

性能が低いといった欠点もあるが，コーディングや遺伝的操作の工夫による性能の向上に関する研究が多数ある（Cheng et al., 1993）。また，欠点を補うために局所探索など他の手法を組み合わせたアルゴリズムも多数提案されている。本研究では，主に多段階決定型遺伝的アルゴリズム（Multistage Operation-based Genetic Algorithm; Scheduler moGA）（Gen & Zhang, 2006）を用い，第4章以降では局所探索を組み合わせたハイブリッド多段階決定型遺伝的アルゴリズム（Hybrid moGA; h-moGA）を用いる。

2.5 要約

本章では，過去に研究されてきた代表的なスケジューリング問題および配送問題について，基本的なモデルを示し，それらの共通点および相違点について明らかにした。また，本研究における統合スケジューリングの意義と位置づけについて述べた。

ここで，従来の問題に対する解析に基づく近似解法を本研究に適用する場合の問題点について述べ，

発見的解法の必要性について述べた。

さらに，発見的解法の一つである遺伝的アルゴリズムについて，基本的なアルゴリズムと特徴について述べ，本研究で用いる手法の要点を述べた。

(16)

第 3 章 GA スケジューラベースの生産情報システム

3.1 はじめに

製造業をはじめとする企業をとりまく現状として，需要動向の不確実性の増大や変動の激化，製品ライフサイクルの短縮化，サプライチェーンのグローバル化やEDI（Electronic Data Interchange）の変化などにより（PSLX, 2004），各企業は対応を迫られている。

企業のビジネスプロセスの変化に合わせて，情報システムも変化させる必要がある。近年，経営資源を統合的に管理するERP（Enterprise Resource Planning）パッケージをはじめ，高機能なソフトウェアが数多く開発され広く利用されているが，これらのソフトウェアは様々な要求に合わせて大規模になり，今日の変化には対応することが難しいといった問題が発生している。

ソフトウェアの開発手法においては，予め機能を十分に検討した上で大規模なソフトウェアを開発する従来からの方法を見直し，変更の容易な小規模のソフトウェアを素早く開発し，オープンな規格のもとで連携させる方法が提案されている（Highsmith & Cockburn, 2001）（Cockburn & Highsmith, 2001）。

企業情報システムにおいても，これらと共通する手法でより高度な機能と広範囲の統合を小規模なソフトウェアの集合で実現するAPS（Advanced Planning and Scheduling）が提案され，研究や実装が進められている（PSLX, 2003 (1)）（Moon et al., 2004）。

本研究では，要求の変化への素早く柔軟な対応が可能なAPSシステムを構築するための手法について提案を行い，有効性を検証する。3.2 節でスケジューリングの重要性について述べ，3.3 節で対象とするAPSモデルについて述べる。本研究の目的を達成する手段として，3.4節でスケジューラに用いる多段階決定型遺伝的アルゴリズム（スケジューラ moGA）について述べ，3.5 節で Extensible Markup Language（XML）（W3C, 2006）を用いたデータ交換について述べる。3.6節では試作したシステムを用いて設備保守要求の追加を例に有効性の検証を行う。

3.2 製造業におけるスケジューリング問題

3.2.1 APS システムとスケジューリング

APSは，「プランニングやスケジューリングなどの組織の意思決定の要素を統合させ，さらに各部門が組織間や企業間の枠を超えて同期をとりあいながら自律的に全体最適を志向するしくみ。」（PSLX, 2003 (5)）であり，APSシステムはこれを実現する製造業のためのシステムである。PSLXコンソーシアムによって提案されているAPSシステム（PSLX, 2003 (1)-(5)）では，プランニングとスケジューリングをはじめ様々な機能が個々のエージェントで実現され，それらがネットワークを介して連携することにより目的を達成している。

(17)

APS システムの中で，スケジューリング・エージェントは最も重要な位置を占め，最も多くの機能を提供する必要がある。PSLXのAPSエージェントモデル（PSLX, 2003 (2)）における各エージェントに対し，想定されているユースケース数（UC）と実装すべきとしているインタフェース数（IF）を表 3.1に示す。これらは必ずしもAPSシステムの実装と一致するものではないが，いずれもスケジューリング・エージェントに対する数が非常に多く，スケジューリング・エージェントに要求される機能が多いことを示していると言える。また，エージェント内の機能はそれぞれ密接な関連があり，エージェントを分割して実装することは困難である。

製造業におけるスケジューリングを行うシステムを作成する上で，考慮すべき点が二点ある。一つは製造業の現状に即したスケジューリングを行うことであり，他は今後の変化に対応が可能であることである。変化に対応させるためには，情報システムの開発体制や開発方法などを含め，様々な面での検討が必要である。

表3.1 PSLX・APSエージェント一覧

No. エージェント分類 UC IF

1 方針計画内部 2 -

2 プランニング内部 7 22

3 スケジューリング内部 13 28 4 製品設計外部（設計） 1 8 5 工程設計外部（設計） 3 8 6 購買計画外部（サプライヤ） 1 17 7 受注管理外部（顧客） 5 12

8 原価管理内部 1 -

9 SC管理外部（サプライヤ） 4 17

10 輸送管理内部 1 -

11 能力調整内部 2 -

12 在庫調整外部（顧客） 1 12 13 製造実施外部（製造） 2 15 14 設備保守外部（製造） 3 15

15 BOM管理内部 3 -

16 仕様決定内部 2 -

17 引当管理内部 8 -

18 連携管理内部 8 24

3.2.2 従来のスケジューリング問題

スケジューリングにおける基本的な問題として，巡回セールスマン問題の一種であるジョブショッ

(18)

プ・スケジューリング問題があり，制約や条件の違いによりフローショップ問題やオープンショップ問題など様々なバリエーションがある。また近年，代替資源の概念を導入したフレキシブル・ジョブショップスケジューリング問題が登場した。これは，一組の機械で複数の種類の作業を行うことができるFMS（Flexible Manufacturing System）の要素を取り入れている。

これらは組合せ最適化の問題として位置づけられ，現実の作業における様々な要素が取り除かれている。しかし，現実には作業順序の組合せだけでなく作業間の要素が全体の効率に大きく影響する場合がある。このため，より現状を反映したモデルを用いて評価を行う。

3.2.3 APS モデル

本研究で取り扱うAPSモデル（Moon et al., 2004）（Moon, 2004）は，複数の工場（Multi-Plant Chain:

MPC）による生産・流通を想定している。このモデルは，図 3.1 に示すように，需要予測を元に作成されたオーダや顧客からのオーダから各種のパラメータや制約を元にスケジューリングを行う。スケジューリングは自社・サプライチェーン内におけるAPSによるスケジューリングとアウトソーシングの 2 つにに大きく分かれる。作成されたスケジュール（作業指示）は，サプライチェーン内の各工場および工場間の輸送に用いられる。本研究ではこれらのうち，APS を中心に取り扱う。本モデルにおけるAPSには，作業順序・資源選択および作業スケジューリングの要素が含まれる。

図3.2にオーダおよび作業の例を示す。例中の2つのオーダはそれぞれ異なる製品を要求し，それぞれの製品は 5 つの作業を必要とする。また，各作業に用いる機械などの資源は複数の中から選択できる（表 3.2）。ただし，作業と選択した資源によって作業時間は異なる（表 3.3）。また，作業には先行関係がある（図3.3）。さらに，資源間の輸送には時間がかかる（表3.4）。

Precedence Constraints of Operations,

Machining Time, Set of Alternative Resources Set up time, Due date,

Volume, Demand Shipping time Forecasting Customer Order

Integrated APS Model

Resource Selection

Operation Sequence Operation Scheduling

Outsourcing Shipping Time Machine Selection

Supplier Fabrication + Assembly Process Customer

••

•

••

•

図3.1 MPC環境におけるAPSモデル（（Moon, 2004）を基に作成）

(19)

o₁₅

Order 1 Order 2

o₁₁ o₁₃ o₁₂ o₁₄

o₂₁

o₂₃

o₂₂ o₂₄

o₂₅

Product 1 Product 2

図3.2 オーダ及び作業の例表3.2 作業と資源選択の例

M

₃

, M

₅

milling

8 (2, o

₂₃

)

M

₁

, M

₃

milling

7 (2, o

₂₂

)

)

M

₃

, M

₅

milling

8 (2, o

₂₃

)

M

₁

, M

₃

milling

7 (2, o

₂₂

)

- - 12

- 8 7 (o₂₂)

- - - 5 3 6 (o₂₁)

- - - 9 - 5 (o₁₅)

Order 2 Order 1

Order k ：

- 7 8 -

8 - - M₅

- 10 - -

- 6 5 M₄

- - 5 -

5 - - M₃

5 - - -

6 - - M₂

6 10 - 6

- 7 7 M₁

10 (o₂₅) 9 (o₂₄) 8 (o₂₃) 4

(o₁₄) 3 (o₁₃) 2 (o₁₂) 1 (o₁₁)

(20)

o

₁₁

1

2

3

4 5 6

7

8

₂₂

o

₂₄

o

₁₃

図3.3 作業間の先行関係の例表3.4 資源間の輸送時間の例

- 30 27 10 17 M₅

5 14 18 18 M₅

- 4 20 8 M₄

36 - 17 5 M₃

19 15 - 19 M₂

26 27 7 - M₁

M₄ M₃ M₂ M₁

図3.4 スケジューリングエージェント・オブジェクト図

(21)

図3.5 スケジューリングエージェント・クラス図

3.3 APS スケジューリング・エージェントのためのデータモデル

3.3.1 基本オブジェクトモデル

スケジューリング・エージェントへの入力およびスケジューラへの入出力情報の関連の例（オブジェクトモデル）を図 4 に示す。スケジューリング・エージェントへの入力は，生産オーダである。生産オーダに含まれる情報は，要求される製品（コードや品名）・数量・納期などである。生産オーダの製品情報(1)を元に，製造BOM（Bill of Manufacturing）から必要な作業とその先行関係(2)が得られる。

スケジューラは，これらの情報を元に作業順序を決定する。また，現存する資源（機械など）の情報(3) と割当に関する生産ルール(4)から，割当(5)を決定する。得られた作業順序と資源制約から作業指示（スケジュール）(6)が作成される。これらのオブジェクトを元に PSLXドメインモデルに準拠した形式で作成したクラスを図3.5に示す。

生産ルールは，これらのオブジェクトのうち最も複雑な構造をもつ。PSLX ドメインオブジェクト

（PSLX, 2003 (3)）においては，生産ルールには制約式・論理式・ペナルティを記述するとし，詳細については定めていない。データ中に目的関数やあらゆる制約式を自由に記述し，それを元にスケジュールの最適化を行うことができれば柔軟性や拡張性に富んでいると言えるが，実装が複雑になりパフォーマンス上も問題がある。そこで，基本的な制約はデータとは分離した形で実装し，その他の想定される制約は後から拡張可能とする。

また，APS モデルにおいて，上記のモデルや制約以外に表現の難しい特殊な作業として，輸送

（transportation）や段取り（setup）がある。

(22)

3.3.2 特殊な作業

(1) 輸送

同一の半製品や仕掛品を消費・生成する作業の間で異なる資源を用いる場合，資源間の輸送が発生する。資源同士が同一工場の場合は単位ロットの生成ごとに輸送を行い（図 3.6），工場が異なる場合は作業の終了後に輸送を行う（図 3.7）。また，同一工場内でも資源の組合せによって輸送時間が異な

る。図 3.6（a）は，後続作業の作業時間が長い場合, 同（b）は，先行作業の作業時間が長い場合であ

る。

輸送はスケジューリングとあらゆる面で密接に関連している。輸送は作業のひとつとして取り扱うことができるが，作業順序や資源選択が決定するまで，どのような輸送が必要か確定しない。このため，スケジューラには資源間の輸送時間のマトリックスでデータのみ与え，輸送作業自体はスケジューラ内部でのみ取り扱う。

図3.6 同一工場内における輸送

図3.7 異なる工場への輸送

(2) 段取り

段取り（段取り替え）も輸送と同様にスケジューリングに密接に関連する。同一資源で連続して異なる作業を行う場合に段取りが発生するが，どのような段取りが発生するかは作業順序や資源選択に

(23)

依存する。この為，スケジューラに対しては輸送と同様に作業間の段取り時間のマトリックスでデータのみを与える。

3.4 多段階決定型遺伝的アルゴリズム

3.4.1 スケジューラ moGA の概要

本研究で用いる多段階決定型遺伝的アルゴリズム（スケジューラ moGA）の基本概念は，多段階決定問題を元にしている。多段階決定問題においては，開始ノードと終了ノードの間に複数の段階（stage）

があり，各段階にある状態（state）のうち1つを選択することにより，決定結果は経路として表現することができる（図3.8）。

遺伝的アルゴリズム（GA）を用いて問題を解く際，問題空間の表現型（phenotype）を遺伝子型

（genotype）にコード化（encoding）した後に遺伝的操作を行い，解を求め，求められた解を再び表現型にデコード（decoding）して評価を行う。この際，遺伝子型が問題空間の表現を適切に反映できることが重要である（Gen & Cheng, 1997）（Gen & Cheng, 2000）。GAにおける染色体は，一般にビット列や数列などで表現され，コンピュータ上では数値型や数値型の一次元配列として実現される。このため，

多対多の関係などの複雑なデータ構造をそのまま使用することは適していない。よって，GA を APS におけるスケジューリングに適用する上では，作業順序および資源選択を遺伝子型によって適切に表現する必要がある。

Yang（2001）は，FMS問題に対してDDP（Discrete Dynamic Programming）を適用するモデルを提案し，その解法にGAを用いたGA-DDPを適用している。この方法では，資源選択を多段階決定問題としてジョブごとの部分解を求め，その後ジョブの順序を決定することによって全体解を求めている。

本研究で用いるスケジューラmoGAも同様に資源選択を多段階決定問題として取り扱う。しかしながら，APSモデルにおいてはFMS問題とは異なり，先行関係制約に基づき作業順序は一意に定まらないことから，ジョブに相当するオーダごとの部分解を単純に求めることはできない。moGA におけるスケジューリングでは，多段階決定における段階を作業順序に，状態を資源選択に当てはめ，2つの染色体を用いる。

(24)

M₁

Stage 1

Stage 2

Stage 3

Stage 4

Stage 6

Stage 7 Stage

5

Stage 8

Stage 9

Stage 10 M₄

M₁

M₄

M₁ M₁

M₂

o₁₂ o₁₁ o₂₁ o₂₂ o₂₄ o₁₃ o₂₃ o₁₄ o₁₅ o₂₅

M₁

M₂ M₁

M₃ M₁

M₄

M₅ M₂

M₃

M₅ M₃

M₅

M₂

s t

図3.8 スケジューラmoGAにおける資源選択

3.4.2 スケジューラ moGA のアルゴリズム

スケジューラ moGAメインプロシージャを図 3.9に示す。作業順序を優先順位型エンコーディング

（Priority-based encoding）による染色体と先行関係の制約によって決定し，資源選択は資源番号エンコーディング（Machine Permutation encoding）による染色体によって決定している。本研究でも同様のアルゴリズムを用いた。交叉には一点交叉（one-cut point crossover），突然変異には2つの染色体に対して swap mutation および neighbor search mutation を，選択には roulette wheel selection を適用している

（Gen & Zhang, 2006）。スケジューラmoGAによって表3.2, 3.3, 3.4および図3.3の例から求めたスケジュール例を図3.10, 3.11に示す。

procedure: Scheduler moGA for APS input: Problem data set, GA parameters output: a best solution

begin t ← 0;

initialize P1(t) by priority-based encoding;

initialize P2(t) by machine permutation encoding;

fitness eval (P); by priority-based decoding and machine permutation decoding;

while (not termination condition) do

crossover P1(t) to yield C1(t) by one-cut point crossover;

mutation P1(t) to yield C1(t) by swap mutation;

mutation P2(t) to yield C2(t) by neighbor search mutation;

fitness eval (C) by priority-based decoding and machine permutation decoding;

select P(t+1) from P(t) and C(t) by roulette wheel selection;

t ← t + 1;

end

output a best solution;

end

図3.9 スケジューラmoGA メインプロシージャ

(25)

S = { (o12, M4: 0-240), (o11, M4: 240-440), (o21, M2: 0-250), (o22, M1: 69-469), (o24, M4: 440-940), (o13, M3: 294-494), (o23, M5: 650-1050),

(o14, M1: 469-709), (o15, M2: 536-896), (o25, M1: 828-1128) } 図3.10 スケジュールの結果例

図3.11 スケジュールの結果例のガントチャート

3.5 XML によるデータ交換

3.5.1 XML について

XMLは単純で柔軟なテキストフォーマットであり，SGML（ISO 8879）を元にしている。現在，電子出版の分野のみならず，Web等での広範なデータ交換における重要性が増している（W3C, 2006）。

XMLでは，木構造を成すデータをテキストとして表現する。多くの場合，ある目的を持ったデータの集合は，木構造によって表すことができるため，XMLの適用範囲は広い。また，テキストとして表現することによって，HTTP（Fielding et al., 1999）をはじめとするインターネット上の様々なプロトコルを用いてデータ交換を行うことができる。

3.5.2 XML によるデータ交換

複数の異なるソフトウェアを連携させる際，データ形式の共通化が必要である。これは，特定のOS や言語に依存しない形式であることが望ましい。また，各々のソフトウェアが個別に改良されることを考慮すると，データ形式の互換性を保ったまま拡張が可能であることが重要になる。さらに，システム構築時や改修後の連携の検証，あるいは例外的な処理の際に，データが人間に理解しやすく変更が容易であることも求められる。

XML を用いることによって，これらの要件をすべて満たすことが可能である。XML はプラットフォーム非依存であり，多くの言語で操作のためのライブラリが既に用意されている。また，要素や属

(26)

性の拡張が容易であり，拡張された部分が古いソフトウェアによって解釈されないことを考慮することによって互換性も保たれる。さらに，タグつきのテキストであるため，タグの名称等を理解しやすいものにすることによって，人間にも理解や操作がしやすいものとなる。

例として，PSLXのXML標準規約（PSLX, 2003(4)）に従って，顧客からのオーダを表現した例を図 3.12に示す。これには「顧客オーダ001」と名付けられたオーダに「製品001」を「70個」「2005年5 月14日17時」までに，また，「顧客オーダ002」と名付けられたオーダに「製品010」を「45個」「2005 年5月15日12時30分」までに，といった情報が含まれている。

従来の多くの情報システムでは，同じデータを図3.13のような形式，あるいはこれを更にバイナリ化した格納効率・伝送効率のよい形式を用いている。しかし，項目の詳細は情報システムに合わせて独自に作成されており互換性はなく，グローバルな環境下でのデータ交換には適さない。また，拡張性や可読性についても，多くの問題がある。

</order>

</order>

図3.12 XMLによる顧客オーダの例

顧客オーダ001,製品001,70,200505141700 顧客オーダ002,製品010,45,200505151230

図3.13 従来の顧客オーダの例

3.5.3 APS システムにおけるデータ交換

APS システムの各エージェントにおいて，オブジェクトのクラスは共通のドメインモデルに従って実装されているが，具体的なデータであるインスタンスはエージェントがそれぞれ保持している。このため，複数のエージェントで利用するデータについては，必要に応じてデータ交換を行う必要がある。本研究におけるエージェントでは，データ交換の厳格な仕様を作成せず，ドメインモデルを元にした柔軟な記述形式を許容する形式で実装を行った。一例として，スケジューリング・エージェントで作成した作業指示を他のエージェントに送信する際のデータ生成の手順を以下および図3.14に示す。

(1) 作業指示内容として必要な情報の境界を決め，木構造に変換する。この際，要素となるのはクラス名のみでなく，ロール等も要素になる場合がある。

(2) 自明な項目や使われていない項目を削除し，時間や数量等の一般化を行う。

(3) データの使用目的（ここでは“#setSchedule”）に合わせた最上位要素の下に XML データを生成し送信する。

(27)

受信側は要求に応じて，データの格納・更新・削除，あるいは問い合わせに対する応答を行う。また，最初に定めたデータ境界の外のデータ（例えば資源選択結果を示すタスク・現物など）が必要な場合は，境界にある要素の名前やIDを元に問合せを行い補完する。

図3.14 ドメインオブジェクトからのXMLの生成

図3.15 APSシステム・コンポーネント図

(28)

3.6 数値実験

3.6.1 数値実験の概要

APS モデルに基づくスケジューリング・エージェントの基本機能の動作確認として製造指示計画を行う。また，保守要求に基づく設備保守の機能を追加し，変更点についての検証を行う。機能追加に対する変更が少ないほど変化に対応しやすいと考えられる。

3.6.2 数値実験システム

本研究におけるAPS実験システムの構成の主要部分を図3.15に示す。スケジューリング・エージェントを中心に複数のエージェントが要求および提供インタフェースをもつ。また，顧客向けに受注管理エージェントが，製造向けに製造実施エージェントおよび設備保守エージェントがそれぞれ窓口となる。システム及び想定環境を図3.16に示す。

また，スケジューリング・エージェントは外部とのインタフェース部（XML を取り扱う部分）と，

スケジューラのコントロール部，およびスケジューラから成る。

3.6.3 製造指示計画

APS システムにおけるスケジューリング・エージェントの代表的な役割として，製造指示計画がある。顧客オーダや需要予測に基づく計画と製品在庫から求めた生産オーダを基に，各種制約を考慮して製造指示を作成する。これはスケジューリング・エージェントの最も基本的な機能である。

3.6.4 数値実験データ

数値実験に用いたデータ（aps-Ex.1）を図3.17および表3.5, 3.6, 3.7に示す。このデータはオーダ数 4, 作業数17, 工場数2, 資源数6から成り，資源M1, M2, M3が工場1に，資源M4, M5, M6が工場2に配置されている。

3.6.5 設備保守

APS システムにおいて，設備保守に関する処理は設備保守エージェントを中心に行われ，この結果を考慮してスケジューリング・エージェントが再スケジューリングを行う。

本実験では設備保守要求に基づき，設備保守を考慮したスケジューリングを行う。設備保守は，製造側からの保守要求以外にも設備保守計画や資源の稼働時間に基づくルールなどによって行われる。

PSLXにおいて設備保守要求のための文法は厳密に定められていないため，作業に対するオーダの形式で記述することとした。その記述例を図3.18に示す。また，保守作業の内容はマスタとして予め図3.19 のような形式で与えられているものとする。

統合スケジューリングに関する研究

ハイブリッド型遺伝的アルゴリズムを用いた 生産・物流情報システムのための

統合スケジューリングに関する研究

Study on Integrated Scheduling for Manufacturing and Logistics Information System using Hybrid Genetic Algorithm

2007 年 4 月

岡本 東

ハイブリッド型遺伝的アルゴリズムを用いた 生産・物流情報システムのための

統合スケジューリングに関する研究

Study on Integrated Scheduling for Manufacturing and Logistics Information System using Hybrid Genetic Algorithm

2007 年 4 月

早稲田大学大学院情報生産システム研究科

情報生産システム工学専攻 ソフトコンピューティング研究

岡本 東

目次

第 1 章 緒言 1

第 2 章 スケジューリング問題と遺伝的アルゴリズム 4

第 3 章 GA スケジューラベースの生産情報システム 11

第 4 章 スケジューリング・エージェントと輸送管理エージェントの連携 29

第 5 章 生産・輸送の統合スケジューリング 46

第 6 章 ピックアップ‐デリバリを考慮した多目的生産スケジューリング 67

第 7 章 結言 86 付録 A 実験データセット 88

参考文献 98 発表論文一覧 101

謝辞 103

第 1 章 緒言

1.1 研究の背景と目的

1.2 本論文の構成

生産オーダ 顧客からの BOM管理 注文情報

製造指示書 製造BOM

輸送管理 製造指示

XSLT プロセッサ

生産能力・

生産ルール

ガントチャート

生産オーダ 顧客からの BOM管理 注文情報

作業指示書 製造BOM

輸送管理 製造指示

XSLT プロセッサ

生産能力・

生産ルール

ガントチャート

設備保守 設備保守

第 2 章 スケジューリング問題と遺伝的アルゴリズム

2.1 はじめに

2.2 生産と物流に関する問題の分類

2.2.1 スケジューリング問題

インデックス

パラメータおよび決定変数

{ }

(

)

(

)

∑

(

)

{ }

{ }

2.2.2 配送問題

インデックス

パラメータおよび決定変数

( )

∑∑∑

∑∑ ∑∑

∑ ∑∑

∑ ∑

∑

{ }

{ }

2.2.3 生産と物流の統合スケジューリング

2.3 既存の近似解法によるスケジューリング

2.4 遺伝的アルゴリズムとその特徴

2.5 要約

第 3 章 GA スケジューラベースの生産情報システム

3.1 はじめに

3.2 製造業におけるスケジューリング問題

3.2.1 APS システムとスケジューリング

3.2.2 従来のスケジューリング問題

3.2.3 APS モデル

M

, M

ハイブリッド型遺伝的アルゴリズムを用いた生産・物流情報システムのための

岡本東

ハイブリッド型遺伝的アルゴリズムを用いた生産・物流情報システムのための

情報生産システム工学専攻ソフトコンピューティング研究

岡本東

第 1 章緒言 1

第 2 章スケジューリング問題と遺伝的アルゴリズム 4

第 4 章スケジューリング・エージェントと輸送管理エージェントの連携 29

第 5 章生産・輸送の統合スケジューリング 46

第 6 章ピックアップ‐デリバリを考慮した多目的生産スケジューリング 67

第 7 章結言 86 付録 A 実験データセット 88

第 1 章緒言

生産オーダ顧客からの BOM管理注文情報

製造指示書製造BOM

輸送管理製造指示

生産オーダ顧客からの BOM管理注文情報

作業指示書製造BOM

輸送管理製造指示

設備保守設備保守

第 2 章スケジューリング問題と遺伝的アルゴリズム