段ボール箱製造スケジューリングの多目的最適化

近畿大学工学部研究報告 NQ39，2005年，pp.65‑73  Research Reports of  the  School of Engineering， 

Kinki University NQ39， 2005， pp.65^・73

段ボール箱製造スケジューリングの多目的最適化

金 指 正 和 * 三 沢 英 貴 付

Multi  ‑ o b j e c t i v e  Optimization o f  the Cardboard Box Production  Scheduling 

Masakazu KANEZASH ド andHidetaka MISAWA

付

A practica1  method for  solving  the  cardboard box production scheduling prob1em using genetic  a1gorithms is  presented. This prob1em is  formu1ated as a mu1ti‑objective combinatoria1 optimization  prob1em invo1ving minimization of the numbers of setup at printing line and minimization of the tota1  10ss.  Generally， the solution of a mu1ti"objective optimization prob1em is  obtained as a set of Pareto  optima1 solutions， which are compared manually to obtain the desired solution. 

However， it  is  very difficu1t  to  obtain mu1tip1e  Pareto optima1 solutions in  a sing1e  tria1  by the  conventiona1 method.  Genetic a1gorithms  have advantage  of excelling  in  mu1ti"point  search.  The  proposed method can efficient1y obtain a set of Pareto optima1 solution candidates by exp10iting the  advantage of GA.  Moreover， good solution is  obtained by combining genetic a1gorithms and 10ca1  search. The result of numerica1 test shows the effectiveness of the proposed method for a 1arge sca1e  cardboard box production scheduling prob1em. 

Keyword : schedu1ing， mu1ti"objective combinatoria1 optimization， Pareto optima1 solutions， hybrid  genetic a1gorithms 

1.緒言

段ボール箱の製造は典型的な個別受注生産であり、品 種毎に印刷内容、注文数、サイズが異なるため、その品 種数は膨大(ほぼ無限)である。更に、注文数は極めて 小量から大量までの広範囲に亘る。段ボール箱製造工程 は大きく分けて、板紙製造ラインと印刷ラインから成る。

板紙製造ラインは、その名の通り、段ボール箱を作るた めの段ボール紙(祝紙)を原紙から製造する工程であり、

印刷、型抜、組立の加工を行って段ボール箱を完成させ る工程である。これらの両ラインにおける単位作業時間 近畿大学工学部情報システム工学科

大学院システム工学研究科博士後期課程3年

65 

は微小であるが、板紙製造ラインと印刷ラインの効率的 なスケジュールが異なるため、仕掛品の滞留やストレー ジの不足が頻繁に発生する。ここで、新たに設備投資を 施さずに生産性の向上を図る方法として、 2品種を同時 に製造して1品種分の加工時間で2品種を同時に製造す る方法を提案する。しかし、段ボール箱のサイズは注文 毎に異なっているため、同時製造する2品種の特性によ っては、段取替回数とロスは互いにトレード・オフの関 係を有する。近年では、中国への古紙輸出が増加してお

Department of Information and Systems Engineering，  School of Engineering .Kinki U niversity 

Graduate School of Systems Engineering， Kinki University 

おり、祝紙製造時に発生するロスを販売する事が可能で ある。しかし、古紙相場の高騰は板紙の材料である原紙 の価格上昇につながり、ロス最小化は依然として大きな 課題である。従って、本問題は段取替回数と総ロス最小 化の 2つの目的を持つ多目的組合最適化問題に帰着す る。進化論的手法の 1つである遺伝的アルゴリズム (Genetic Algorithm:GA) 1)‑3)は、生物の進化の過程を 模倣したアルゴリズムで確率的な探索手法である。 GA は多点探索に優れ、従来の方法では探索が困難であった 最適化問題に対して解を与える、探索空間の仮定(連続 性、微分可能性)を必要としないために柔軟な評価関数 の設定が可能等の長所を持つ。このことからGAは多く の組合せ最適化問題に対して適用されている。多目的最 適化問題にGAを適用する場合、複数の目的に対してウ ェイトを与え、単一目的へ変換した問題を考える手法と 上述した GAの特徴を活かしてパレート最適解集合を 探索する手法仰)が存在する。多目的最適化の本質は複 数の目的関数聞におけるトレード・オフをいかにバラン スさせるかという点にあるω。単一の評価関数を用いた 場合、パレート最適性が考慮されておらず、得られた解 が意d思決定者を十分に満足させなかった場合、ウェイト の設定を変更し、再度GAの処理を繰り返さなければな らないという欠点がある。

本論文は段取替回数最小化と総ロス最小化の 2目的 を持つ段ボール箱製造スケジューリング問題に対し、パ レート最適性を考慮した多目的最適化を行う方法を提 案する。この問題に対してパレート最適性を考慮した多 目的最適化を行い、段ボール箱製造工程における生産性 の向上を図る。提案法は多点探索に秀でているという GAの長所を活用した方法であり、一度の処理で複数の パレート最適解(候補)を得ることが可能である7)。更 に、提案法は文献(カの処理に局所探索法(Local Search:LS)ωを組み込みこむことで探索性能を解の精 度の面において向上させている。本論文の最後では、 20 品種問題に対して提案法を適用し、その有効性を検証す る。

2.  現状の段ボール箱製造工程の問題点とその解決法

2.1  段ボール箱製造工程

段ボール箱製造工程は、大きく分けて板紙製造ライン と印刷ラインから成る。段ボール箱の製造は、段ボール (祝紙)を製造することから開始される。一強的に、高 さ (H)、幅 (W)、奥行き (D)の段ボール箱を製造す る場合、 2 (D+W) X (D+H)の面積の板紙が必要と なる。板紙はコルゲイトマシンと呼ばれる樹氏製造機に

より製造される。まず、中芯用の原紙を波状に加工した ものと表用原紙を接着し、片面段ボールを製造する。そ の後、片面段ボールに裏用原紙を接着したものを所定の 長さに切断して完成となる。板紙製造ラインでは、製造 する板紙の幅に適した原紙を用いるために原紙を取り 替える段取替時間が必要となり、その時間は約3分であ る。また、切断用の歯位置の変更に必要な時間は 2"'3 秒である。完成した協紙は一時的に保存された後、印刷 ラインで印刷、型抜、組立の加工を施される。印刷は樹 脂製の版下を用いて、版画と同様の原理で行われる。版 下を印刷用ローラーに取り付け、ローラーの上側でイン クを塗り、ローラーの下側を棋紙が通過することで印刷 される。このとき、同時に型抜(切込、折線)加工がな され、その後の組立加工で終了する。印刷ラインでは、

インク交換、版下取替え、型抜用の歯位置変更のための 段取替が必要となり、その時間は3分"'8分と非常に大 きい。

2.2  問魁県 2.2.1  ロスの発生

板紙を製造する原紙は 50mm間隔で 700mm'"が規 格として存在しており、製造すべき榔氏の横幅に合わせ て使用する原紙を決定する。しかし、注文される品種は ミリ単位で発生するために、ロスは必ず発生する。

2.2.2段取替時間の増大

近年の目覚しい科学技術の進歩により、様々な新商品 が開発されている。新商品がでると、それを梱包するた めの段ボール箱の種類も増加する。現在では一日最大 250品種の注文を受けることも少なくなく、それに伴う 段取替時間の増大も大きな問題である。

2.2.3効率的生産順序

板紙製造ラインにおける効率的生産順序は板紙寸法 の小さい順である。一方、印刷ラインにおいては色毎に まとめた生産順序が効率的であることは明白である。し かし、現状では板紙製造ラインの生産順序を引き継ぎ、

印刷加工を施しているので、ストレージ不足や仕掛品の 滞留が頻発する。

2.3  2品種同時製造 2.3.1  2品種同時製造の効果

2.2節の問題点を、新たに設備投資を施さずに解決す るために2品種同時製造を考える。 2品種同時製造とは 印刷用ローラーに2種類の版下を取り付けて、 1品種分 の加工時間で2品種を製造(印刷)する方法である。こ れにより、以下の効果が期待できる。

段ボール箱製造スケジューリングの多目的最適化 67 

( u  

板紙製造における段取替回数の減少

表1受注情報 (50品種)

品種 横幅 縦幅 横幅 縦幅

表1は50品種の受注情報(展開図サイズ)を表して いる。これらの品種がどの原紙で劉宣されるのかを表2 へ、また、その分布を図1へ示す。先述した通り原紙は 50mm間隔で700mm"‑'が規格として存在し、各板紙に 最も適した(ロスが最小となるように)原紙を用いて製 造する。 2品種を同時に製造するということは、板紙を 製造するために必要な原紙幅の分布が変化すると考え ることができる。同時製造時の原紙幅の分布を図2へ示 す。また、図2では1800mm以上の原紙の分布は示し ていない。なぜなら、実際の段ボール向上では非常に大 きな品種や特殊な型抜を必要とするものは専用ライン が存在している。そのため、2品種を組み合わせた結果、

非常に大きな板紙が必要になる組合せば対象としない。

表2品種・原紙幅対応表

割 合 ( % ) 30% 

25% 

20% 

15% 

10% 

5% 

0% 

700  750  800 

原紙幅 (mm) 700  750  800  850  900  950  1000  1050  1200 

850  900  950 

図1原紙幅の分布

品種番号

1

，

6

，

7

，

8

，

9

，

11

，

21

，

23

，

26

，

31

，

33

，

35

，

41  12

，

13

，

20

，

24

，

34，44，46

，

47，42 

10

，

14

，

15

，

22

，

39，49  3

，

5

，

1718

，

27

，

37

，

48  2

，

25

，

28

，

32

，

36，45

，

50 

4

，

16

，

30  38  43  19

，

29

，

40 

1000  1050  1200  原 紙 幅(mm)

割合(%) 18.00% 

16.00% 

14.00% 

12.00% 

10.00% 

8.00% 

6.00% 

4.00% 

2.00% 

1800  原 紙 幅(mm) 1750 

1700  1650 

1600  1550 

1500  1450 

1400  0.00% 

図2 原紙幅の分布(新)

板紙製造に使用する原紙幅の分布の変化より、例えば表 2.3.2  モデルの概要

1の品種1と品種36を組合して同時製造する場合と品 現状の製造工程(図3・現状)に対して、本研究では 種 目 と 品 種39を組合せる場合に必要となる杭紙幅は 同時製造(印局リ)により効率化を図った印刷ラインのス 1500mmと等しいため、品種変更による原紙取替のた ケジュールから、板紙劉宣ラインのスケジュールを決定 めの段取替は発生しないことが分かる。 する流れ(図3・新)を本研究におけるモデルと位置づ

ω

ローラーの回転数は半分へ ける。

同じ版下を2枚製造することにより、異なる品種の組 2品種同時製造を用いた場合、段取替回数、ローラーの 合せのみではなく同じ品種同士を組合せることも可能 回転数は確実に減少する。しかしながら、ロスの値は大 である。この場合、板紙製造、印刷の両ラインにおける きく変化する。2品種分の板紙をまとめて製造する場合、

ローラーの回転数は半分となる。 その縦側の長さは組合せる 2品種の長い方の値により (3) 印刷ラインにおける版下取替時の段取替回数減少 決定される。表4は表3の受注情報を用いて同時製造を 印刷ラインでは、版刊文替のための段取は必ず発生す 行った場合、段取替回数とロスにどのような関係がある る。このとき、 2人の作業者で版下を同時に取り替える のかを表したものである。

ことにより、段取替回数は減少する。更に、組合せる2 品種の需要量が全て等しければ段取替回数は半分まで 減少する。

(新) (現状)

協祇艶置の生産}II買序決定 (印刷の生産順序から)

， .  

印刷ラインE

印刷ライン

I

受注

+ 

印刷ラインの 生産1)関芋決定

↑ 

2品種同時印刷 による効率化 生産順序決定

受 注 +

印刷ライン

E

が異なる

印刷ライン

I

段ボール箱製造工程(現状&モデル) 図3

段ボール箱製造スケジューリングの多目的最適化 69 

表3受注情報

品種 1  2  3  4 

需要(箱) 400  300  400  300  縦寸法匂1) 1.5  1.3  1.0  1.0  横寸法(m) 0.90  0.75  0.70  0.80 

表4 同時製造スケジュールの比較

生産順序 段取替回数 ロス(m) 同時製造1 (1，3)→(2，4)  2回(板車問

231.5 rri  (段取替重視) (40ω(300)  2回(印刷

D

同時製造2 (1，2)→(3，4)→(2，3)  3回(板五ro

102.5 rri  (ロス重視) (30ω(30ω(10ω  3回(印刷。

表4の同時製造1は段取替回数最小化を図った生産順序 を、同時製造 2はロス最小化を図った生産順序を表して いる。ここで、同時製造1と同時製造2を比較すると、

段取替回数に関しては同時製造 1が少なく、ロスに関し ては同時製造 2が少ないことがわかる。つまり、組合せ る品種の特性によっては段取替回数とロスは互いにト レード・オフの関係を持つ。これより、本問題は段取替 回数最小化と総ロス最小化の 2 目的を多目的組合最適 化問題である。

3.  数判句定式化

3.1  記号の定義

本論文で用いる記号を次のように定義する。

i，j :品種番号 m 品種数

n 機械台数d_{i :}品種 iの需要量

ld :機械kでにおけるi，j同時製造時の協紙一枚あたり のロス(ぱ/枚)

i   ( = 

1ム… ，

m ) 伊 =IL‑‑1)

x ; :

機械kにおける品種i，j同時製造時のロットサイ ズ(枚)

4:

^{機械 kで品種i，}jを同時製造する場合 1，しない場 合0の値を取る決定変数

s

ヴ : 品 種i，jを同時に製造する場合の板紙必要面積

(ぱ)

αi，b_i :品種 iの板紙の縦寸法と横寸法 (m) rq :概氏製造用の原紙横幅 (m)

( q   = 

0，1，"  .，6) 

3.2  目的関数 3.2.1

評価基準

I 

総ロス最小化

全品種の加工が完了した時点で発生する総ロス Lは (1)式で表される。

L=

エ

^;=12

二

^12;;:i444

^→

^{min (1)} 

ld = S

弓 ; ‑ ( ，

αibi+

ψ ' ))    ^{i (}

^‑:f‑

^{j )}  

⁽²⁾ 

lj=GI(q‑2bi)  (3) 

S

弓

=m

刈

αi，a))rq  (4)  rq = 1.2 

+ 

O.lp  (5) 

(bi 

+ 

b))

句 く

(bi+b))+O.l  (6) 

E 

段取替回数最小化

全品種を加工するために必要な段取替回数STは(7) 式で表される。

ST22;;=lz:lzzi 

; u →

min  3.2.2  制約条件

製造する段ボール箱の数と注文量は等しくなければ ならない。この制約は全品種に対して存在し、 (8)式で表

︑ ︑ . ︐ ︐ ︐

門i

d 'z

︑

される。

エ

ヱ

¹⁴⁴⁼

^{め   i ( =} 

^{1，2，… ，}

^{m )}  

⁽⁸⁾ 

u ; = 私 1 }

0壬

; x

壬min(di，d)

~t

(9) 

(10) 

4 .

ハイブリッド

GA

による多目的最適化 そこで本論では、

GA

と

LS

を併用したハイブリッド

GA

を用いてパレート最適性を考慮した多目的最適化を 4.1  パレート最適解

本論文で扱う問題のように、複数の目的が布宝する多 目的最適化問題では、一般に全ての目的を同時に満足さ せることは不可能である。何故なら、ある目的関数の値 を改善するためには、少なくとも他の1つ以上の目的関 数の値を改悪せざるを得ないからである。そのような解 をパレート最適解(非劣解)と呼び、その定義は以下の 通りである。

〔定義

J<

パレート最適解>

目 的 関 数 五

( x ) i   (

= 1，2・ .，，.

k )

に 対 し て fi(x)壬fi(x*)であり、なおかつ、任意のjについて

ん

^(x)壬ろい*)となるxが存在しない場合、

f

はパレ ート最適解である。

定義より、パレート最適解は集合として存在する。目 的関数がjしんの場合における最小化問題に対するパレ ート最適解集合を図4へ示す。

五 ( x )

a m 

みtu

ny  

o 

ω 

e 

v i 

a 

' p i

︐ 

・

' ' ' f L

t

︐

︐

︐  

I I J '  

止 が

0 . ' ρ

・ ・

₁

.ap

moor‑¥ 

料

︒

¥ .

・ ¥ J

Vハ

' f

¥

︐ . .

帥

﹄ / 込

v¥A'¥

h o o

¥

¥  

‑p

・ ・ ¥

a

・ '

・

・ ・

1 .

Non Pareto optimal 

1 2   ( x )  

図4 パレート最適解集合 4.2  提案法

(ω式の {0，1}決定変数

t ; t

^{の組合せ数は品種数m，}機 械台数nの増加に伴い膨大な数になる。そのため、実用

的な時間内で最適解を得る事は非常に困難である。

GA

はその探索課程において、多数の実行可能解を生成して 多点探索を行うという利点から大域的探索に秀でてい るが、局所探索に弱いという特徴を持つ。

行う方法を提案する。

4.2.1  探索手順

手順1 初期個体集団を生成する。

手順 2 個体集団に属す全個体に対して、段取替回数最 小化を目的とする一制面関数より適応度Fiを計 算する。更に、総口ス最小化を目的とする=訓面 関数より適応度五を計算する。つまり、全個 体は2種類の適応度を持つ。

手順3個体集団から適応度Fi、 fヨの値に基づいて、

2種類の部分個体群を生成する。部分個体群1 は適応度Fiの値の上位a番目までの個体から 成り、部分個体群2は適応度昂の値の上位b 番目までの個体からなる。当然、Fiと五の両 方の値が高い個体はどちらの部分個体群にも 属す。

手順4 手)'1員3で生成された各部分個体群における全個 体に対して、局所探索を m回適用する。この とき、部分個体群 1に属す個体はFi、部分個 体群2に属す個体は昂で評価する。

手順5 2種類の部分個体群から、ルーレット選択によ り片親ずつ決定し、交叉を行う。すなわち、部 分個体群 1から適応度Fiの値に基づいたルー レット選択により決定された個体と部分個体 群2から適応度五の値に基づいて選択された 個体の聞に交叉を適用する。この操作を個体数 a+b個の集団が生成されるまで繰返した後、突 然変異を適用する。

手順6 手順2から手JII貢5を決められた世代、または終 了条件を満たすまで繰り返す。

4.2.2個体の表現

個体p =

I 

10  4 1 9 6 3 5 8 7 2  個体Pは、トーナメント方式(図5)により得られる 同時製造の品種の組合せとスケジュールを表している。

段ボール箱製造スケジューリングの多目的最適化 71 

機械1

ここでは、品種数10、並列機械台数2台の場合を例に 挙げて述べる。個体Pは図5の網掛け部分を表している。

1から 10までの各品種はトーナメント試合を行う選手 であり、需要量を各選手の持ち点、各機械(図5の点線 部分)を試合会場と考える。 I

①"

""1④は試合会場Iでの 試合順序(機械Iにおける同時製造スケジュール)を表 している。各会場のシードは品種 6と品種 2であり、そ の遺伝子座は、それぞれ左から5番目、 10番目である。

ここで、シードとは一般のトーナメントにおけるシード 選手を意味する。試合は各選手の持ち点で争われ、持ち 点の大きい方が勝者(余り品種)となる。勝者は自身の 持ち点から対戦相手の持ち点を減少させた値で勝ち上 がり、次の試合(次の同時艶宣)を行う。敗者はその時 点で、需要量分の加工が終了したことになる。 I②は品 種1と品種9の需要量が等しいため、両者を持ち点Oで 一般の試合における失格と考え、 I③では6を不戦勝と

して扱う。

4.2.3  適応度関数

本研究における目的関数は段取替回数STと総ロス Lの最小化である。そこで、適応度関数を次のように設 定する。

円.1L

. ST 

戸、=ム

ー L

(11) 

(12)  ここで、 ST 段取替回数，L 総ロス，れ，乃:スケリ ーング係数

4.2.4選択・淘汰

4.2.1項の手)11貢3において、部州固体群1、部分個体 群2のどちらにも選択されなかった個体は淘汰される。

また、個体集団における全パレート最適解候補をエリー トとして次世代へ保存するパレート保存戦略を適用し ている。エリートを効率的に選択するために、図 6の Pl(現時点でのSTの値において最小)と乃(現時点で のLの値において最小)により構成される領域(斜線部)

加工終了

に属す解のみに対して多目的ランキング手法9)を適用す る。

ST 

‑ パレート解の可能

乃_{eァー7ア ァ‑7ヲ}

・ . . . . ‑ ‑ 一 一

_{性無し(領域外)}

1/  /  /  /  /  / 1

・

1/  / / ノ ノ / 1

1/ / / / / /1  T; 

I  /  /  / 

/ 司 . . " "

^.A

・

， 

1 /  / / / / 

/r...  可能性有り

1/ / / / / /1  の領域

ー ー ， ̲. . 4 ̲ ー ー ， ̲ . . .   ， ‑

^PJ. 

L  図 6 多目的ランキング適用領域 4.2.5 交叉・突然変異

提案法における交叉には一様交叉を、突然変異には転 座を適用した。提案法においては、突然変異は4.2.2項 の個体の表現におけるシード品種と非シード品種の間 で転座を適用しており、その効果を高めている。(例え ば、図5における品種10と品種4を入れ替えても適応 度の値に変化は無いが、品種10と品種6を入れ替える

とその値は変化する。) 4.2.6  局所探索の設定

GAの局所探索能力を補うために他の手法とGAを組 み合わせたハイブリッド化法が提案されている10)。提案 法は、文献(1

ω

にあるようなハイブリッド化の考えに基 づいてGAとLSを併用した多目的最適化法で探索の制 度向上を図る。

適用回数・適用手法

提案法ではランダム変異局所探索 <Randomascent  hill climimg : R1¥狂王C)11)を用いその適用回数をm回と する。

新たな解の生成

各部分個体群中の個体に対してランダムに 2つの遺 伝子座を選択し、それを入れ替えることで実現する。

5.  数値実験 表5 20品種問題

ltem  Demand  Length 

ω 

Breadth  提案法の有効性を検証するため、表5の20品種問題 1300 

  1 .

88  0.75 

500 

1 .  

60  0.76  を用いて実験を行った。また、実験時に用いたGAパラ 3  600  2.20  0.85  メーターは表6の値を用い、並列機械台数2台、協紙製 4  1100 

  1 .

45  0.75  造用の原紙幅を10cm間隔で102mから 108mの7種類 5  2200 

1 .  

38  0.82  6  700 

1 .  

62  0.90  として計算を行っている。なお、実装にはC言語(Visual 7  500 

1 .  

75  0.90  C++)を用い、シミュレーションはPenti

umN

3.0GHz  8  1200 

1 .  

90  0.80  のパソコンで行った。 9  700 

  . 1

76  0.60  10  300 

  . 1

65  0.86  11  1000 

  . 1

75  0.80  5.1  実験結果 12  1300 

1 .  

50  0.90  各世代のエリート(パレート最適解候補)が持つ2つ 13  100 

1 .  

65  O.  60  の適応度R，F2の平均値推移を図7へ、収束時に得られ 14  1500 

1 .  

98  0.68  た全エリートが持つ目的関数の値を表7へ示す。多目的 15  1100 

  1 .

55  0.85  16  2000 

  . 1

70  0.75  最適化問題の解であるパレート最適解は集合として存 17  800 

  . 1

85  0.73  在し、 GAにおいてその収束判断が非常に難しい。本研 18  500 

  1 .

65  0.62  究では 500世代の間新たなエリートが得られなかった 19  200  2.  10  0.75  20  1200 

  . 1

75  0.58  時点で収束と判断している。また、収束までにかかった

時間は約57秒である。更に、比較として同問題へ提案

表6 GAパラメーター 法からLSを除いた手法を適用した結果を表 6へ示す。

Crossover probab出ty

当然、 GAパラメーター、収束の判断等の実験条件は等 80% 

Mutation probab出ty 10% 

しくしてある。

Population size  100 

γ1  100 

/2  10000  α  50 

。

50 

F1  4.8  F² 

6.5  4.6 

4.4  6.3 

4.2 

6.1  4 

3.8 

5.9  3.6 

5.7  3.4 

3.2 

5.5  3 

1 5  50  1 00  300  700  900  1200  1600  1900  2000  2200 

generation 

図7数値実験結果(‑Fi，一五)

段ボール箱製造スケジューリングの多目的最適化 73 

表7パレート最適解候補集合 ST (回) L (rrl)  E

1 i

te 1  13  3673.92  E

1 i

te 2  15  2672.62  E

1 i

te 3  16  2373.02  E

1 i

te 4  17  1940.12  E

1 i

te 5  18  1840.72  E

1 i

te 6  19  1673.82 

表8 パレート最適解候補 (LS無し)

S

1(回) L (ぱ) E

1 i

te 1  13  3673.92  E

1 i

te 2  15  2937.92  E

1 i

te 3  16  2419.32  E

1 i

te 4  17  2117.62  E

1 i

te 5  18  1999.92 

5.2考 察

図 7よりエリートは集団単位で良好に進化している と考える事ができる。図7において適応度平均の一方が 増加し、他方が減少している場合が確認できる。すなわ ち、この現象が確認できる世代において、新たなエリー トが生成されたことを意味する。また、両適応度平均が 上昇している場合には、より真のパレート最適解(大域 的パレート最適解)が生成されたことで、エリート集合 内におけるいくらかの解がその集合から除外された事 を意味する。表 5より、提案法は一度の施行でパレート 最適解候補集合を得ることが可能であり、表 7と表 8を 比較すると、提案法が解の精度において優れている事は 明らかである。これはGAが持つ集合による探索という 利点とLSがうまく融合した結果であると考えられる。

6.結 言

段ボール箱製造スケジューリング問題は段取替回数 最小化と総口ス最小化の 2つの目的を持つ多目的組合 最適化問題に帰着する。 2品種同時製造は従来の製造と 比較して、より少ない段取替回数で加工を完了すること が可能なので、段ボール箱製造工程全体の生産効率は上 昇する。しかし、 2品種の板紙を同時に製造することか ら、ロスの値は大きく変化する。本論文はこの問題に対 してGAとLSを併用したハイブリッドGAを用いて多 目的最適化を行う手法を提案した。多目的最適化問題を

考える場合、そのパレート最適性が重要となる。提案法 は、探索過程において多数の実行可能解を生成し、集合 による探索を行うという GAの利点を活かすことによ り、 1度の施行で複数のパレート最適解候補を得ること が可能であり、 20品種問題に対して数値実験を行いそ の有効性を確認した。更にLSと組合すことにより、GA が苦手とする局所探索を補っているために得られる解 も高品質である。

参考文献

(1)  M. Gen and 

R .  

Cheng: Genetic Algorithms 

￥& 

Engineering  Deign， Jhon  W

i L

EY

￥& 

SONS  (1997) 

(2)  白石洋一(訳):組合せ最適化アルゴリズムの最新 手法，丸善株式会社 (2002)

(3)  北野宏明:遺伝的アルゴリズム産業図書 (1993) (4)  H.  Tamaki， H. 

Ki

ta， and  S.  Kobayashi:  Multiobjective 

Op

timization  By  Genetic  Algorithms"， Proc.  of  1996 IEEE Internatinal  Conference  on  Evolutiona巧 Computation， pp.517・522(1996) 

(5)  K. Deb， A. Prata却p，S.Aga訂rwal，and T.司

A Fast  and  E

1 i

tist  Mu吐ut註10ぬbj炉ecti討、.veGenetic  Al誌gorithm:NSAGA‑II"

，

IEEEτI旨ans. On  Evolutionary  Computation，  Vo

1 .

6  No.2，  pp.182・197(2002) 

(6)  北野宏明:遺伝的アルゴリズム2，産業図書(1995) (吟 三沢英貴，金指正和多目的遺伝的アルゴリズム

による段ボール箱製造スケジューリング問題の解 法?'，JIMA論文誌人To

1 .

56，No.2，pp74‑83(2005)  (8)  伊庭斉志:探索のアルゴリズムと技法‑基本的アプ

ローチとその評価サイエンス社 (2002) (9)  C.M.Fonseca  and 

P .

J.Fleming:"Genetic 

Algorithmsおr multiobjective  optimization:  formulation

， 

discussion and generalization"

， 

in  Proceedings  of  the  Fifth  International  Conference  on  Genetic Algorithms

， 

Morgan 

Ka

u金nannPub

1 i

shers， pp.416・423(1993). (1ωL.ム.D

五島:lrmi位lll1也註iml白zationof polypeptide s叩，pe舵ci温宣.cenergy  mo吋deぽy，'一 Proceedings  of  IEEE  International  Conference  on  Evolutionary  Computation，  pp.396・400

，

(1996) 

(11)  伊庭斉志:進化論的計算手法(人工知能学会編) オーム社(2005)