～Modeling a Multi-Period Disassembly Planning
Problem with Capacity Constraint編～
平賀 友浩
０．Abstract
１．Introduction
２．Problem
Statement
３．Model
Approach
５．Numerical Experiment
６．Conclusion
７．おわりに
４．Heuristic
０．Abstract
１．Introduction
２．Problem
Statement
３．Model
Approach
５．Numerical Experiment
６．Conclusion
７．おわりに
４．Heuristic
今回の論文では、多期間および多数のアイテ
ムの解体プランを、解体能力の制約をつけて
考える
Plan Matrix）を
導入するが、それは可能な解体プランと対応
するパーツの情報を含んでいる
そこで、DPM（Disassembly
これは整数計画問題として定式化できるが、
原問題はNP完全で繰り返し解く必要があるこ
とから、ここでは繰り返しのないフォワード
スケジュールとバックワードスケジュールを
用いて近似解を求める
NP完全とは
NP（nondeterministic polynomial time）の略
簡単にいえば、その問題を解くアルゴリズムは存在す
るが、そのアルゴリズムでは時間がかかりすぎて実質
的には解くことにはならない。しかし、もっと早い時
間で解くアルゴリズムは存在しないであろう、と思わ
れている問題
フォワードスケジュール
フォワードスケジュールは解体プランとスケジュール
を検証する
バックワードスケジュール
バックワードスケジュールは解体能力が不適切な場合
に対する再スケジュールを目的とする
数値実験での近似解で、トレードオフの関係
にある解の質と計算時間に関して以下のよう
になるようにした
解の質・・・最適解からのずれが7.1％以下
計算時間・・12秒以下
０．Abstract
１．Introduction
２．Problem
Statement
３．Model
Approach
５．Numerical Experiment
６．Conclusion
７．おわりに
４．Heuristic
素早い市場ニーズに対する対応と、高品質低
価格を目指した競争によって、製品ライフサ
イクルが短くなった。
結果、数多くのEOL（end of life）商品が発生
している。
たとえば、1990年のアメリカでは11,000,000台の
自動車が破棄されている
これらの製品は、環境的、経済的理由から、
分解され、再利用されている。
この解体プランとスケジュールはいままでも
多くの研究者によって研究されているが、こ
の２つは、多くの場合、別々に取り扱われて
いる。
解体プランニングとは
適切な解体順序を策定すること
解体スケジューリングとは
市場のニーズに合わせて、いつどれだけの量のEOL製品
を解体すべきかを決定すること
また、多くの研究が、解体能力の制約と複数
期間にまたがることを考慮に入れないで研究
をしている。
しかしながら、プランとスケジュールには強
い関連性がある。
したがって、この研究では、多期間にわたる
分解プランとスケジュールを同時にモデル化
し、また以下の点に関しても考慮する
１）期間にわたり、部品のニーズを変更する
２）動的に必要な部品を得る分解をすること
３）生産すべき部品を考慮した解体スケジューリ
ング
４）解体能力の制約
０．Abstract
１．Introduction
２．Problem
Statement
３．Model
Approach
５．Numerical Experiment
６．Conclusion
７．おわりに
４．Heuristic
外部にある需要を充足するためには、分解す
ることによりパーツを調達するか、新しくパ
ーツを生産するかの２つの選択肢が存在する
多くの場合は、分解し調達する方が経済的で
ある
コストを最小化するためには、いつどのくら
い分解で調達するか決定する必要がある。
分解の手順の違いに、またどのレベルまで分
解するかによって調達できる部品の種類と、
かかるコストが異なる。
例として以下のような簡単な製品をかんがえる
d
c
b
a
この製品は４つの部品から構成されている
cはaの上に固定されている
第一の分解の選択肢としては、はじめにdの
みを取り外すか、cとdを一緒に取り外すかで
ある
Bを取り外すには、cを取り外す必要がある。
次のグラフでは、その解体の手順および得ら
れるパーツを示す
a/b/c/d
0
O1
DT=10
1
1
2
2
a/b/c
O3
a
4
5
b
6
c
DT=8
3
a/b
3
DT=5
4
O2
c/d
O4
5
DT=15
7
d
O5
DT=5
０．Abstract
１．Introduction
２．Problem
Statement
３．Model
Approach
５．Numerical Experiment
６．Conclusion
７．おわりに
４．Heuristic
DPMは可能な解体プランとそれに対応する部
品を示している
もし、プランiにより部品jを得た場合、１と
なる
具体的には次のようになる
A
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
0
1
0
1
0
1
1
1
0
0
1
0
0
0
1
0
0
1
1
1
1
1
1
0
0
1
1
これを用いて定式化すると以下のようになる
。
ただし、各期間ごとに必要となる各部品の数が与
えられ、まず解体によりその各部品を調達する
もし、解体能力が不十分で、需要を充足すること
が不可能な場合には、新たに部品を製造する。
したがって、このモデルはTRC（Total Relevant
costs）を最小化するモデルである。これは返品の
取得費用、解体費用、新しい部品の製造（or購入
）費用、解体に関する在庫費用などが含まれる
T
I
T
J
TRC (CP CD DTi ) Zit (CHj Yjt COj Njt )
t 1 i 1
t 1 j 1
(1)
Subject to
I
Aij X ijt Yj ( t 1) Njt Djt for all j, t
i 1
I
Aij X ijt Yj (t 1) Njt Djt Yjt for all j, t
(2)
(3)
i 1
I
DTi Z it MCt
i 1
for all j, t
(4)
Aij Xijt Zit
for all j, i, t
(5)
Xijt , Yjt , Zit , Njt 0,1,2...
for all j, i, t
(6)
ただし
i, 取り得るプラン,(i = 1,2,…I)
j, 部品またはその組み合わせ物,
(j =1,2,…J)
t,スケジュールする期間, (t = 1,2,…,T)
Aij , DPMのij要素
CP,返品物セットの取得費用
CD , 平均費用/セット・単位時間
DTi, プランiの実行所要時間
CHj, jの在庫費用
COj, jの取得費用
Djt , 時刻tにおけるjの需要
MCt, 時刻tにおける機械能力
Xijt , 時刻tにおけるプランiによって解体されたjの数
Yjt ,時刻tの解体されたjのt在庫量
Zit , 時刻tにおけるプランiによって解体される必要が
ある返品物のセット数、可変
Njt ,時刻tにおける新しく取得されるべきjの数、可変
とする
このモデルでは、
（2）では需要が解体された部品もしくは新規取
得された部品によって充足されていること
（3）では解体された部品の在庫量
（4）では分解の能力制約
（5）ではプランとそれに対応する部品の数
が示されている。
しかしながら、この問題はNP完全であり、多
項式時間でとくことができないので、次の
Heuristic Approachを提唱する
０．Abstract
１．Introduction
２．Problem
Statement
３．Model
Approach
５．Numerical Experiment
６．Conclusion
７．おわりに
４．Heuristic
この問題は、毎回の期間に対してそれぞれの条
件が存在し、その各条件の入力があった場合に
は、毎回あらたに問題を解く必要がある
したがって、Heuristicアルゴリズムを用いて解
くこととする.
このアルゴリズムは、フォワードスケジューリ
ングと、バックワードスケジューリングの２つ
のモジュールを持つ
まず、条件としてAという、解体セットの解
体しうるパーツと解体プランのマトリクスを
用意する.
初期条件として、すべての部品のすべての需
要が新規取得した場合を設定する.（解体して
取得するよりコストがかかることがほとんど
のため）これがコストの上界となる.
アルゴリズムの全体像は次のようになってい
る
Initialize: generate Aij, input demand data and cost parameters
Generate an initial solution
‘Forward-schedule’ module
‘Backward-schedule’ module
Check the possibility of disassembling more
at the periods
Determine the best disassembly plan
Determine the amount of used-product
Does the demands of all periods
are met?
YES
STOP
YES
NO
If there are periods further
available for disassembly,
NO
Purchase new items
TRCを減らすために各プランをランキングに
して、その順でプランを採択していく.
このランキングは、プランにかかる費用と、
そのプランによってもたらされる効果によっ
て効率をランキングしたものである.
それを以下のように計算する
Fi= {Benefit from plan i (BfPi)-cost for plan i
(CfPi)}
もし、新規取得費用が部品a/b/c, a/b, c/d, a,
b, c, dに対してそれぞれ65,45,55,25,20,30,40
であるならば以下のようなものとなる
Item j
BfPi
CfPi
CD·DTi
Fi
Plan i
1 2 3 4 5 6 7
P1
1 0 0 0 0 0 1
105
10
10
85
P2
0 1 0 0 0 1 1
115
15
10
90
P3
0 0 0 1 1 1 1
115
30
10
85
P4
0 1 1 0 0 0 0
45
8
10
27
P5
0 0 1 1 1 0 0
45
23
10
12
P6
0 1 0 0 0 1 1
115
13
10
92*
P7
0 0 0 1 1 1 1
115
28
10
77
Djt
3 5 0 9 7 8 2
CP
バックワードスケジューリングでは、解体能
力などの制約により需要が充足されなかった
場合に先行する期間において、能力の空きが
あって、実行可能解を落としこめるかをチェ
ックする。
ない場合は、部品を新規取得するとして、次
の期間に移行する。
０．Abstract
１．Introduction
２．Problem
Statement
３．Model
Approach
５．Numerical Experiment
６．Conclusion
７．おわりに
４．Heuristic
実験の条件として
５つの問題を設定し、
２つの期間長を考え（5期と10期）
３つの能力制約を設定
（S(280min),T(300min),A(350min)）
して、合計30回の実験を行った。
Heuristic model
IP model
Problem
2683
(4.1)
S
3992
(7.2)
3932
(8.8)
A
3881
(6.7)
2045
(4.8)
1993
(2.2)
1950
(2.5)
4315
(9.5)
4472
(11.8)
4267
(5.8)
4624
(1002)
2106
(2.8)
2064
(6.0)
2030
(1.3)
4826
(8.2)
4758
(10.3)
4721
(6.2)
4541
(5602)
4522
(2394)
2063
(5.2)
2056
(3.3)
2042
(2.3)
4624
(8.1)
4598
(7.3)
4522
(5.4)
5040
(3397)
5006
(1007)
1657
(4.2)
1654
(3.8)
1654
(2.8)
5200
(9.8)
5040
(8.7)
5006
(6.3)
3898
(1542)
S
2875
(3.7)
4315
(4928)
4267
(2248)
4229
(228)
2030
(1230)
4658
(5412)
4658
(5022)
2056
(1322)
2042
(93)
4541
(4899)
1654
(3803)
1654
(2821)
5067
(5630)
A
2630
(8)
S
3949
(5220)
2
2019
(3928)
1977
(1028)
1950
(845)
3
2098
(1202)
2064
(4022)
4
2063
(3302)
5
1567
(2240)
1
A
2644
(1.8)
A
3874
(1337)
T
S
*1)
2868
2634
(2347)*2) (1272)
2868 *1) : Objective function value
(2347) *2) : CPU time in seconds
10 periods
5 periods
10 periods
5 periods
T
T
T
Error
= [(TRCIP_model – TRCHeuristic)/ TRCIP_model
]100
として計算すると、以下のようなエラーレート
となった
5 periods
10 periods
T
A
Problem
S
T
A
S
1
2
3
4
7.04
1.29
0.38
0.00
1.86
0.81
0.00
0.00
0.53
0.00
0.00
0.00
1.08
7.11
3.64
1.83
0.87
4.80
2.15
1.25
0.18
0.90
2.10
0.00
5
Ave.
5.74
0.00
0.00
2.62
0.44
0.00
2.89
0.53
0.11
3.26
1.90
0.64
Heuristicな解法によってでも、十分に正確な
結果が短い時間で得られた。もし、十分な解
体能力が存在するならば、かなりの確率で
Heuristicな解法でも最適解を求めることがで
きた。
また、この実験から、部品の数と実施期間の
長さで、線形にかかる時間が延びるといえる
・・・！？
０．Abstract
１．Introduction
２．Problem
Statement
３．Model
Approach
５．Numerical Experiment
６．Conclusion
７．おわりに
４．Heuristic
この論文では、解体プランが動的に（期間ご
とに違った）なるようなプラン策定を行った
これにより、より高い精度での市場対応など
ができ、解体からより多くの利益をえること
ができる。
原問題はIPモデルであったが、ここで導入し
たHeuristicな解法は十分に効果を発揮した。
これは繰り返し解く必要があるこの問題に対
して有効である。
今回の解法では、フォワードスケジュールと
バックワードスケジュールを統合して用いた
が、バックワードスケジュールの実行により
、より長い時間がかかった。
ゆえに、今後の研究として、より高精度で実
行速度の速いものを開発するということは非
常に興味深い。
この研究では、戻ってくる製品は常に調達で
きると仮定し、また解体作業は確実に行われ
ると仮定したが、実際の場面では必ずしもそ
うとは言えない。
それらの仮定を排除し、より多くの制約を取
り入れることによって、決定論的なものから
、より推論的なものとしていくべきであろう
。
０．Abstract
１．Introduction
２．Problem
Statement
３．Model
Approach
５．Numerical Experiment
６．Conclusion
７．おわりに
４．Heuristic
実際の現場で使用するには、部品数を劇的に
増やし、期間も無限とまではいかずとも、か
なりの数を増やさなくてはならない。
また、論文の中でも述べられていたが、より
動的に、入力値が変化しても対応できるよう
になれば、だいぶ実践的になるであろうと考
えた。
© Copyright 2024 ExpyDoc
