Complexity Estimation for Genetic Assembly Sequence Planning

組裝順序規劃之複雜度估計

王文派(Wen-Pai Wang) ； 曾懷恩(Hwai-En Tseng)

《工業工程學刊》 26卷1期 (2009/01) Pp. 44-52

https://doi.org/10.29977/JCIIE.200901.0005

摘要

組裝規劃涉及由相關的限制因素（幾何特性、時間、工具、機台）考量安排可行的組裝順序，進而決定特定之組裝的優先順序，故組裝規劃屬於限制複雜型態的問題，而在此類問題中採用傳統基因演算法對於尋找可行解甚或是最佳解，進而確認係整體最佳而言，可謂艱困而費力的工程；過去，引導式基因演算法的提出就是爲了修正傳統基因演算法的缺點，這種演算是專門用來解決複雜限制式型態的基因演算法，然而衍生的問題是何謂複雜限制式的問題，故本研究目的旨在爲建立一複雜度的衡量指標，以利往後作爲演算法採用的參考依據，透過實例的驗證，當指標在70以上時可以稱爲複雜的限制式問題。

關鍵字

組裝規劃 ； 基因演算法 ； 複雜度 ； 引導式基因演算法

並列摘要

Assembly planning involves in determining a particular assembly priority from which associated restraint factors such as geometric features, assembly time, tools, and machines are taken into account of arranging a feasible assembly sequence based upon the planner's individual heuristics. Suchlike planning lately may implement genetic algorithms (GAs) to go towards the assembly sequence features of speed and flexibility. However, finding feasible solutions or even optimal solutions is arduous to identify the global optimal solution in a short period. The purpose of this paper essentially aims at establishing a complexity index for practitioners to decide what type of algorithm employed, namely traditional GAs, or ameliorative GAs like Guided-GAs. The threshold of the proposed complexity judgment is hinged on the square of preceding constraints and the quantity of nodes in the event. As the complexity increases the frequency of feasible solutions found did not exactly come up by traditional GAs. According to the proposed index assembly sequence problems are asserted more constraints comparatively while the complexity approaches to 70 or above.

並列關鍵字

assembly planning ； genetic algorithms ； complexity ； guided-Gas

參考文獻

Abdullah, T. A.,K. Popplewhell,C. J. Page(2003).A review of support tools for the process of assembly method selection and assembly planning.International Journal of Production Research.41,2391-2410.

Akagi, F.,H. Osaki,S. Kikuci(1980).The method of analysis of assembly work based on the fastener method.Bulletin of the JSME.23,1670-1675.

Baldwin, D. F.,T. E. Abell,M. C. M. Lui,T. L. De Fazio,D. E. Whitney(1991).An integrated computer aids for generating and evaluating assembly sequences for mechanical products.IEEE Transactions on Robotics and Automation.7,78-94.

Bonneville, F.,C. Perrard,J. M. Henrioud(1995).A genetic algorithm to generate and evaluate assembly plans.Proceedings of the IEEE Symposium on Emerging Technology and Factory Automation.(Proceedings of the IEEE Symposium on Emerging Technology and Factory Automation).:

De Fazio, T. L.,D. E. Whitney(1987).Simplified generation of all mechanical assembly sequence.IEEE Transaction on Robotics and Automations.3,640-658.