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
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)