知識処理を用いたフ V キシプノレ生産
オンラインスケジューリング
鳩野逸生，田村担之
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111.

プの割込，急なジョブのキャンセルなどの外的環境の変はじめに化によりオフラインで作成した生産スケジュール通りに一般に生産スケジューリングは，各生産システムにお生産することができなくなる場合が多い.本稿では，オける資源(工作機械，搬送機械など)におけるジョフの処

フラインスケジューリングでは対応することが実際的で理順序を決定する問題として設定される.スケジューリはない不確実な環境におけるスケジューリングの方法論

ング問題を組合せ最適化として定式化した場合，最適解について概説した後，ルールベースを用いることにより傑索のための計算量が膨大となり，実際規模の問題に対オンラインスケジューリングを行なった例 [18J および今して最適解を求めるのが困難であることが知られている

後知識ベースを用いたオンラインスケジューリングに必[2 , 3].

さらにFMSSystem) [IJ など，(Flexible Manufacturing

より柔軟性が高い生産システムでは.，(1)配置された工作機械の順序に依存しない(2) ロット単位でシステムに投入されるが各工作物毎に個別に扱われる要な技術課題について述べる.

2.

不砲実な環境下におけるスケジューリング

一般的なスケジューリング問題に対するアプローチとしては， (1)分岐限定法などの OR 手法 [2J ， (2) スケジュー(吟代替機械が存在する

リング・シミュレーション [5J ，(4) ジョブの搬送スケジューリングも必要である

telligence) 的手法 [9， IOJ などがあげられる.しかし，(5) 作業者に対する作業スケジューリングも必要である

動的かつ不確実な環境にある生産システムでは，オフラ(3)AI(ArtificialInｭ

(6)工具供給スケジューリングも必要である

インスケジューリングに比べてごく短い時間でスケジュ(7)各工作機械ごとのパップァとその容量，さらに生産シールを行なう必要があるため (1)-(3) の手法をそのままでステム全体での中間在庫を考慮する必要があるなどの特徴があるためさらに複雑なものとなる.一方，適用することは図難である.このような生産環境におけるスケジューリングの方法論としてはスケジューリング作成の形態として月間，週間単位など(1)再スケジューリング

一定期間のスケジューリングをオフラインで計算し，生(2)確率的最適化

産システムに適用するオフラインスケジューリングと，必要が生じた時点で必要最小限のスケジューリングをリ(3) オンラインスケジューリングの 3 つが考えられる.

アルタイムに行なうオンラインスケジューリングの 2 つ(1) のアプローチは，環境の変化が生じた時点で現時点が存在するが，通常生産システムにおけるスケジューリのスケジューんをキャンセルし環境の変化を考慮し再ス

ングとはオフラインスケジューリングを意味することがケジューリングを行なう方法であり，再スケジューリン多い.ところが，実際の生産においては，工作機械の故グを行なうタイミングを含めた研究が報告されている

障およびそれに伴う修理時間，加工時間のばらつきとい[6]. しかし，生産の周期性など計算量を減らすための仮った生産システム自体に内在する不確実性や，特急ジョ定を設けているものがほとんどであるため，そのままではより自由度の高いフレキシブル生産システム等には適はとのいつお，たむらひろゆき

大阪大学工学部精密工学科〒 565 吹田市山田丘 2 ー l10(16)

用することは困難である.
(2) のアプローチは不確実な環境を待ち行列ネットワー

ク等を用いて確率的にモデル化し，スケジューリング目© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リ+ーチ

的に対して，確率的に最適化することによりスケジューリングを行なう方法であり，工作機械の故障や処理時間の不確実性を考慮した上で、納期を満たすなどのスケジューリング目標を達成することをめざしたシステムが報告されている [7， 8J. このアプローチは不確実な状況を正確に確率的にモデル化できることが前提であり，FMS のように正確なモデル化が困難なシステムに適用することは困難なように思われる.また，このアプローチも計算量を減らすために非現実的な仮定が設定されることが多函 1

Anexampleo
fknowledge.basedo
nlineschedulin
gsystem

L 、.

一方，オンラインスケジューリングを行なう場合は簡単なディスパッチングルール [5J にもとづいて行なわれ部品が複数個存在する状態において，次に作業を行なうることが多く，オンラインスケジューリングの研究は (1)，べき部品を選択することを指し，ルーティングとはある(2) に比べて進んでいないのが現状である.これは (1) ， (め部品について次工程の作業ができる機械または搬送機械に比べて従来スケジューリングに用いられてきた手法がが複数台存在する状態において次工程を行なう工作機械

オンラインスケジューリングには計算量の点で不向きでまたは搬送機械を選択することを指す.
上述のディスパッチングやルーティングを行なわなけ

ジューリング研究の例としては，スケジューリング対象ればならない状態を検出した場合に，以下に示すようなを倣送車スケジューリングまたはジョブのルーティング

ルール [4J にしたがって優先規則を決定し，それに対応す等に限定した上で，小規模な準最適化問題をオンラインる作業または機械を優先的に選択する.

唱ii
fPthenRで解くことによりオンラインスケジューリングを行なったシステム [IIJ や，離散形状態方程式で‘モテール化するこ)(あることに起因していると考えられる.オンラインスケ

ここで，条件 P は FMS モデル内のバッファの状態やとにより最適制御理論を適用してスケジューリングを行

各部品の加工進展状況等を調べる述語を表わす.また，なう例 [12J ，ルールなどの人工知能手法を用いてオンラ

結果 R ，主優先規則 [5J かまたは次にチェックするルール

インスケジューリングを行なう例 [13 ， 14， 15 ， 16 ， 17 ， 18Jのグループ番号を表わす.本稿では，オンライン・スケなどがあげられる.部分的に最適化を行なうものや最適ジューリングにおける納期余裕および納期遅れの最小化

制御理論を応用するものは適用できる場面が限られておを第一義的な生産目標とするスケジュールを求めること

り，人工知能的な手法がオンラインスケジューリングにとし，以下に示すような D!-D. の優先規則を考えてい対して最も期待できる手法であると考えられる.以下のる.また，各工作機械が効率よく稼動し，生産目標を達章で・はルールベースを用いてオンラインスケジューリン成することを補助的な目標として Dg-Du を使用していグを行なった例 [17 ， 18J について，オンラインスケジューる.

リングのためのルールベースおよびその評価について述D!

納期順ジョプ優先

べる.

Dz

スラック時間最小ジョブ優先D.

最大納期遅れ時間最大ジョプ優先

3.

ルールベースを用いたオンライン・スケジューリング

3.
1 オンライン・スケジューリングのためのルールベース

D ，納期遅れ個数最大ジョブ優先
Ds

総納期余裕時間最小ジョブ優先D.

納期余裕率最小ジョブ優先

D7

ランダムにジョブを選択

ここでは，部品の加工に際し，ディスパッチングゃん

D.

どのジョブも負荷しないーティングに関する意思決定をノレールベースによってオDg

バッファ占有率最大ジョブ優先

ンラインで制御することによりスケジューリングを行なD!o: 次工程バッファ占有率最小ジョブ優先

う.システム構成を図 1 に示す.ここでディスパッチン

Dl1 :残り工程数最小ジョプ優先

グとは工作機械または搬送機械に対して次に作業可能なディスパッチングまたはルーティングが発生した時刻

1992 年 2 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(17)71

LDI0D6D1D2Dg
DI0D7}D8C偶 flict(2)D10

D1be~t-time2(b2) ;D2best‑timel(b3)DoD10DTltr旬 eprogress(l)best‑time2(b1)true

D10

Dl1

t7'ue

D1D4Dg
D7D8DlODg
D1

Dl1

D7t1"ueLcv
cl4

Levd3

Lev
el2
図 2Lcv
cl1

Lcv
cl0

P
riorityRule

An exampleof the rule base[17]において対象システムから得られる情報により述語 P を注個数すべてを仕上げるのにかかると予想される最小時構成する.以下に P の例を示す.

間を表わしている.納期遅れが生じないときは納期余裕

not(a):aが真のときのみ偽となる.

を小さくし，納期遅れが生じる場合は納期遅れが 1 つのtime(a い現時刻が a 以降のときのみ真となる.

部品に集中せず，納期遅れを小さくおさえようとする目

buffer1(a , b) :現工程より a工程先のパッファの占有率標を設定し，図 2 のようなんールベースを構築している.

が b%以上のものが存在するときのみ真となる.

推論の簡単化および高速化のため，スケジューリングのρrocessing-time(a ， b):現工程から a工程先の加工時間の最小・最大の比 x 100が b% 以上のときのみ真とな

8].
知識をグループ化しかっ推論木に展開している[ 13.
2 数値例によるルールベースの評価
簡単な数値jJlJ としてライン型 FMS のオンライン・スる.

progress(a い競合している部品の残りの工程数が a 以下のものがあるときのみ真となる.

att
ain: 競合している部品のうち，現時刻で l つでも完成しているものがあるときのみ真となる.

ケジューリングを考える. FMSは 3 台の工作機械 (M hM2， M ，) とローディングステーション，アンローディン
グステーションおよび l 台の搬送車から構成されているものとする.各部品川 ， b ， c) が加工される順序は以下のbest‑time1(a い競合している部品のうち納期までの残とおりである.ただし，カッコ内の数字は，各部品が各り時間とその部品についての 1min の比が a 以上のも工作機械で加工されるときに要する生産計画における加のがあるときのみ真となる.

工時間を示す.

ここで ， 1m師は述語の真偽を検証する時刻において受72(18)部品 α

M 1 (6)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

•M 2 (6)

オベレーションズ・リサーチ

部品 b:

M t(4) •M 2 (3)
部品 c:

•

表 1M a(5)M t(5) •Ma(6)各部品が工作機械聞を搬送される

Dispatching rules

Rule‑baseRule‑baseFCFS
SPT
MINSLACKFirstComeFirstServ巴dS
hortestProcessingTime
MinimulllSlackTime

MAXROBMINROBN

MinimumRateo
fOccupationf
orBuffersinNextProcessのにすべて 1 単位時聞かかるとし，各工程にはそれぞれ容量 5 のバッフ

MaximumRateo
fOccupationforBuffers

MAXLOSSMINSPARE
MAXTARD

ァが設置されているものとする.各工作機械において現在までと異なる

M日imum S
Ulllo
fLossTime

MinimumSUlIlofSpareTime
MaxilllulIlTardiness

種類の部品を次に加工する場合の工表 2

具付け替え時間を 1 単位時間と設定

FailureRatc

する.このような FMS において各部品ここではルールベースの評価を行なうため，図 2 に示すルールベースおよび表1 に示すディスパッチング・ルールに従ュレーションを行なっている.工作機械

きの各条件は表2 に示した 13種類であり，搬送機械については故障は発生せず，搬送における所要時間の分散は 0.7 である

0.000
0.001
0.005
0.010
0.015
0.005
0.005
0.005
0.005
0.005
0.005
0.005
0.005

Case1
Casc2
Case3
Casc4
Casc5間として生産を行なう例を考える.の故障率，修理時間，加工時間のばらつ

Varianc巴 ofMea巾 air Tim

Proc巴ssing Timeをそれぞれ 20個ずつ，納期を 300 単位時ってオンラインスケジューリングのシミ

Conditions ofnumerical experimentsCas 巴 6

Case7
Case8
Casc9
Casc1
0
Case1
1
Casc12
Case13ったものである.

ものとしている.

101010

1.00
1.00
1.00
1.00
1.00
0.00
1.00
2.00
3.00
1.00
1.00
1.00
1.00

10

10
1010

1010
51015
20

300単位時間とし、う納期は，故障や加工シミュレーシヨンには，確率ベトリネット [19 ， 20J に不時間のばらつきが生じないと仮定したとき，ほぽ最適なツト中のあるプレースから他のプレースへトークンが移スケジューリングが行なわれた場合に達成することので動するのにかかる時聞を経過した後に発火する階層化時きる納期で，非常に厳しい条件である.ここでの数値実timed transition) を験では，工作機械の故障や加工時間のばらつきが発生す間トランジション (hierarchical

導入した階層的確率ベトリネットを用いている [17 ， 18J.

ることを想定しているため，各実験結果とも設定した納表 3 に以上の条件のもとで行なった数値実験の結果を期からは大幅に遅れている.表 3 からもわかるようにル示す.表中の各要素はそれぞれの条件のもとで， 100 回スールベースを用いた方がし、ずれの条件でも短い加工時間ケジューリングを行ない，その加工終了時間の平均をとで終了していることがわかる.他のディスパッチングル

表 3Average completion time

ICase IRule‑base IFCFS ISPT IMINSLACK IMAXROB IMINRβB IMAXLOSS IMINSPARE IMAXTARD I
1234
56789101112
13337.
97
342.
3
8353.
98369.
67397.
82337 目 87

353.
7141
359.
369.
25348.
06355.
23369.
7
93
72.
49

1992 年 2 月号

380.
50
3
85.
3
9404.
0
8433.
9
3
457.
8
938l
J.
9l
J
404.
5
8
40
9.
8
940
4
2
1.
3
93.
5
1405.
3
4
4
1
9.
40
4
34.
8
0

3
71.9
3
3
77.
7
93
93.
9
84
12.
7
2
4
36.
3
63
63.
50
3
96.
2
6
4
0
5.
0
940
7.
3
73
82.
6
7
3
95.
7
0
403.
0
14.16.
41

5
24.
7
7
531.4
8
5
56.
0
95a1.49.8
9
6
21
5
14.
2
95S2.
2
3
566.
7
0
[， 77 目 22

53
9.
7
8
5
52.
6
5S
G
4.
G
9
5
92.
0
7

3
70.
2
7
3
74.
0
8
3
87.
4
8
4
0
7.
1
84
3
3.
5
8
3
60.
2
9
3
91.9
7
3
92.
1
3
401.7
3
3
81.4
6
3
87.
2
9401.4
2
4
0
7.
7
6

3
79.
8
6
3
86.
95400.
8
7
420.
6
9435.
45
362.
0
93
97.
8
6401.0
4
408.
753
92.
0
4
3
99.
49
406.
1
512U.
52

3
78.
1
83
83.
7
1398.
1
0
430 目 32

448.
2
3
3
73.
6
4
400.
8
9
405.
70
4
11.9
7
3
94.
7
8406.
0
1
4
10.
8
8
428.
3
6

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

386.
6
9384.
98406.
6
8428.
25J.
8
147l
380.
12407.
1
1419.
0
94
30.
0
4393.
5
1403.
76417 目 29

428.
3
5383.
7
2
389.
43
406.
2
1431.6
4J.
4
lJ
45l
3
77.
70
4
14.l
J3
409.
3
14
19.
30
3
94.
9
3
4
12.
7
74
18.
2
G
435.
49(19)73

ールに固定した場合でも特定の条件のもとではルールベ

参考文献

ースを用いた場合と比較して近いものもあるが，他の条件に対しては大幅に劣ると L 、う結果を示している.

4. 知識ペースを用いたオンラインスケジューリングの課題[1J 伊東，岩田:フレキシプル生産システム，日刊工業新聞社，

1984.

[2J K. R. Baker , Introduction to Sequencingand Scheduling , John Wiley & Sons , New

知識ベ}スを用いたオンラインスケジューリング実用化に対する課題としては， (1)知識ベース構築のための知識収集，知識ベースのデパッグをどのように行なうか?
(均実際の生産システムにおいて推論のための情報(知識)収集機構をどのようにモデル化しインプリメントするか?の 2 つがあげられる. (1) に対しては，知識ベース自体を外部環境の変化に対して対応しやすい構造にする方法や機械学習により自動的または半自動的に知識を生成す

York , 1
974.
[3J F. A. Rodammer , andK.P.White , JR , A
Recent Survey of Production Scheduling,IEEETrans. on Systems , Man , and Cyberneｭtics , Vol. 18, No.6 , 1988, 841‑851.
[4J 中村，鳩野，田村:ルールベースに基づいたフレ
キシプノレ生産システムのスケジューリング，計測自動制御学会論文集，

Vo.23 , No.1 , 1987 , 66‑71.

る方法などが期待される.しかし，いずれの方法もシミ[5J J. H. Bl
ackstone Jr ・， D. T. Phillips , andュレーションを知識源および知識ベースの評価に用いる

G. L. Hogg, A state.
of.
the.
art Survey of

必要があると考えられる.この点で，シミュレーション

Dispaching Rules forManufacturingJobShop

技術と知識処理技術の融合を計っていく必要がある.一

Operations , InternationalJournal ofProducｭ

方，知識ベース・オンラインスケジューリングシステム

を実際の生産システムに組み込む場合，スケジューリン

7‑45.
tionResearch , Vo 1. 20 , No.1 , 1982 , 2[6J S. Fujii , Y. Watanabe , and H. Sandoh ,グのための情報(知識)をリアルタイムに収集する必要がOptimalRescheduling Policy Based on Realある.この情報収集機構は生産システムをコントロール

Time Disturbance Information , Ja an.USA
on Flexible Automation , Kyoto ,するソフトウェアに組み込む必要があることを考える

Symρosiumと，将来の設備，および環境の変化に対して柔軟に対応

Japan , 1990, 1
147‑
1150.

可能な知識ベース向け情報モデルおよび情報交換プロト[7] 太田，斎藤，久村，時間付きプレースをもっペトコルを構築しておく必要がある.これは， \，、くら性能がリネットの繰返し工程スケジューリンジ問題への応用

高い知識ベースであっても得られる知識が外界の変化を計測自動制御学会論文集，表現できていなければ，スケジューリング目的を達成す‑
716.

ることが困難なことを考えれば，知識ベースと同等な重Vo 1. 25 ,No ム

1989，

714

[8J 斎藤，太田，久村，処理時間に不確定性を有する要性をもつものと思われる.この点で近年研究が活発化

スケジューリング問題への確率タイム・ペトリネットしている分散協調および自律分散 [21J などのアプローチの応用，計担tl 自動制御学会論文集，が注目される.

1989, 476‑
481.

5.

Vo 1. 25 ,No.4 ,[9J M. S. Fox and S. F. Smith, ISIS‑A

おわりにKnowledge.basedSystemforFactory Scheduｭ

本稿では，不確実性の多い生産システムに対するスケling , ExpertSystems , Vo 1.J, No.1 , 1984, 25‑49.

ジューリングの方法論の概要を述べた後，ルールベース[10J J.J. Kanet , ExpertSystemin Productionを用いることによりオンラインスケジューリングを行な

Scheduling , European Journal ofOperational

った例および知識ベースを用いたオンラインスケジューリングに対する課題について述べた.オンラインスケジ

Research , Vo 1. 29 , No.l , 1987, 51‑
59.

. Aribib , M. Lucertini , and[11J A. Agnetis , Cューリングは，不確実な環境におけるスケジューリング

F. Nicolo, PartRouting inFlexibleAssemblyに対する方法論の 1 つであり，この分野では今後ますまSystems, IEEE Trans. Robotics and Automaｭ

す知識処理の応用が期待される.

tion , Vo 1. 6, No.6 , 1990, 697‑
705.

[12J P. R. KumarandT.1.Seidman , Dynamic

74(20)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

Instabilities and Stabilization Methods in

ingSystems , Vol ム ~o.4， 1989, 287‑
307.

Distributed Real.time Scheduling of Manu‑.Hatono , K. Yamagata , andH. Tamura ,[17J 1facturing Systems , IEEE Trans. AutomaticModelingandOn.Line Schedulingo
fFlexible

Control , Vo 1. 35 , ~o.3 ， ω90 ， 289‑298.

ManufacturingSystemsUsingStochasticPetr
i.Krogh , and M. R. Singh ,[13J R.Akella , BEfficientComputaiono
fCoordinatingControls~ets ， IEEE Trans. Software Engineering ,Vo l. 17 , No.2, 1992,

126寸 3 1.

inHierarchicalStructuresfor Failure.Prone[18J 鳩野，山県，田村，ルールベースを用いたフレキ

Multi.CeI
lFlexible AssemblySystems , IEEE

シプル生産、ンステムのオンライン・スケジューリン

Trans. RoboticsandAutomation , Vol ム~o.6 ，1990, 659‑
671.

グ，ジステム制御情報学会論文誌，

Vo 1. 4 , ~o.9 ，1991 , 375‑
381.

[14J B.B.P. Brandimarte , C.Greco , and Gi.

[19J M. A. Marsan , G. ConteandG. Balbo , A

Menga , Hybrid Hierarchical Scheduling andClasso
fGeneralizedStochast
icPetriNetsfor

Control Systems in Manufacturing ,IEEEthePerformanceEvaluationo
f Multiprocessor

Trans. Roboticsand Automation , Vo 1. 6,~o.6 ，1990, 673‑
686.

Systems , ACMTrans. Computer Sys. , Vo l. 2,~o.2 ，1984, 93‑
122.

[15J J.SharitandG. Salvendy, A Real.Time[20J F. ArchettiandA.Sciomachen , Represen‑Interactiv
e Computer Model ofa Flexibletation , Analysis and Simulationo
f Manufac‑

manufacturing , IIE Transactions , Vo l. I9,~o.

2, 1987 , 1
67‑
177.

turingSystemsbyP
etr
i ~et Based Models ,Proc. ofIIASA Con，ρ rence on D
iscrete Event[16J D. Ben.Arieh , andC.L. Moodie , Knowle‑
dge Based Routingand Sequencingf
or Dis‑cretePartProduction , JournalofManufactur‑

Sopron , Hungary , 1987 , 1
62‑
178.
[21J 計測自動制御学会編，制御，(特集)分散と協調，計測とVo 1. 26 , No.l , 1
987.

-四・....・-・....・...........・.....・・....・-・・・・・・・....・-岡田....・-・・・・・ M ・ M ・.......・・・....・.......・-・・....・.......回目....・....・ M ・..........・-・・・....・..

報文集価格衰(会員価格)
T‑73‑1

ネットワーク構造を有するオペレーションズ・リサーチ問題の電算機処理 l 乙関する基礎研究

1200門

T‑78‑1

オペレーションズ・リサーチのためのデータとプログラムに関する研究 4000円

T‑77‑1

システムダイナミックス一一方法論と適用例

2500円

R-7判

rOR の実践とその有効活用 J 視察団報告

1200円

R‑82‑1 r 欧州における OR 実施状況J 視察団報告書

1200円

R‑84‑1 r米国における OR の実践」視察団報告

1200円

T‑88‑1 r南北協力の新しい戦略一一マイグロ電子技術を起爆として一一一J3500円

R‑88‑1 r南米諸国との OR 交流視察団」報告書

1200円

福田田町田・・・・・・・・・・岡田・・・・・.......・・・・・・........・m ・・・m ・・・・・・・・M ・・・ m ・・・・・・・・・.........................................・......・....・....・・・・・・・・・・・・出1992 年 2 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(21)75