MES Product Survey 2007/2008

MESA (Manufacturing Execution System Association)から、
2008/03/25に出された"MES Product Report 2007/2008"を、読み進める。

[MES Product Report 2007/2008]:
http://www.mescc.com/mes-report.html


MESA Internationalは、1992年、MES(Manufacturing Execution Systems) Vender/System Intergater主導で設立された協会。活動目的は、MES/Enterprise Solution関連の、革新とBest Practiceの共有。
有名な "11 MES functions "を設定したのも、このMESA International。

[MESA International]:
http://www.mesa.org/


[Reference]
MES入門―ERP、SCMの世界と生産現場を結ぶ情報システム
図解 MES活用最前線―実践事例でわかるMES(製造実行システム)導入のポイント

Moore, Breadth First Seach

Edward F. Moore の Breadth First Seach Algorithm。

[Original]Edward F. Moore, "The shortest path through a maze": Proceedings of the International Symposium on the Theory of Switching, pages 285-292 Harvard University Press, 1959.

Algorithm MOORE [G=(V, E), s, e]
開始Vertex sから終了Vertex eへの、
接続グラフ G =(V,E)の最短路を決定するAlgorithm。

入力:
・開始Vetexを s、終了Vertexを e
 全てのEdge (i,j)で長さl(i,j)=1の接続グラフを、G=(V,E)とする。
・最初は全てのVertexにラベルがない。

出力:
・G=(V,E)の中の最短路 s → e

手続き:

1.sにラベル0をつける

2.i=0 とする。

3.ラベル iが付いているVertexに隣接する、
 全てのラベル付けされていないVertexを検索する

4.見つかったVertexにラベル i+1 をつける

5.if(終了端 eにラベルがつけられた)
  ラベルの逆探索により、最短路を導出:
  k(eのラベル)、k-1, ..., 0とラベルを探索していき、
  各該当Vertexを出力する。

 else
  i=i+1 と増やし、Step 3へ戻る
 


計算量、メモリ使用量のOrderはそれぞれ次。

・計算量Order    ...O(Edge数)
(sから順にVertexを移動し、隣接Vertexを検索していく手続きが、"2×Vetex回"行われる。)

・メモリ使用量Order...O(Vertex数)
(Vertexにつけるラベルの成分数)


巡回セースルマン問題(Traveling Salesman Problem)で、全てのEdge(辺)の長さが 1 の場合の解法。(※巡回セールスマン問題:与えられたグラフの最短Hamilton経路(グラフの全てのVertex(頂点)を通る経路)を決定する問題)


[Reference]:
最適化とグラフ理論 (技術者のための高等数学)
Introduction to Algorithms, Second Edition
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)