Complexity Estimation for Genetic Assembly Sequence Planning

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

10.29977/JCIIE.200901.0005

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

組裝規劃 ； 基因演算法 ； 複雜度 ； 引導式基因演算法 ； assembly planning ； genetic algorithms ； complexity ； guided-Gas

工業工程學刊

26卷1期（2009 / 01 / 01）

44 - 52

英文

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

1. 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.
2. 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.
3. 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.
4. 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,Paris, France:
5. De Fazio, T. L.,D. E. Whitney(1987).Simplified generation of all mechanical assembly sequence.IEEE Transaction on Robotics and Automations,3,640-658.
6. Dini, G.,F. Failli,B. Lazzerini,F. Marcelloni(1999).Generation of optimized assembly sequences using genetic algorithms.Annals of the CIRP,48,17-20.
7. Fujimoto, H.,M. F. Sebaaly(2000).A new sequence evolution approach to assembly planning.Transaction of the ASME. Journal of Manufacturing Science and Engineering,122,198-205.
8. Gottipolu, R. B.,K. Ghosh(1997).Representation and selection of assembly sequences in computer-aided assembly process planning.International Journal of Production Research,35,3447-3465.
9. Guan, Q.,J.H. Liu,Y.F. Zhong(2002).A concurrent hierarchical evolution approach to assembly process planning.International Journal of Production Research,40,3357-3374.
10. Homem De M. L. S.,A. C. Sanderson(1991).A correct and complete algorithm for the generation of mechanical assembly sequences.IEEE Transactions on Robotics and Automation,7,228-240.
11. Kaimann, R.A.(1974).Coefficient of network complexity.Management Science,21,172-177.
12. Lim, S. S.,B. H. Lee,E. N. Lim,K. A. Ngoi(1995).Computer- aided concurrent design of product and assembly processes: a literature review.Journal of Design and Manufacturing,5,67-88.
13. Sebaaly, M. F.,H. Fujimoto(1996).A genetic planner for assembly automation.Proceedings of IEEE Conference on Evolution Computation,Japan:
14. Smith, G. C.,S. S. F. Smith(2002).An enhanced genetic algorithm for automated assembly planning.Robotics and Computer Integrated Manufacturing,18,355-364.
15. Smith, G. C.,S. S. F. Smith(2003).Automated initial population generation for genetic assembly planning.International Journal of Computer Integrated Manufacturing,16,219-228.
16. Tseng, H. E.(2006).Guided genetic algorithms for solving the larger constraint assembly planning.International Journal of Production Research,44,601-625.
17. Tseng, H. E.,C. E. Tang(2006).A sequential consideration for assembly sequence planning and assembly line balancing using the connector concept.International Journal of Production Research,44,97-116.
18. Tseng, H. E.,J. D. Li,Y. H. Chang(2004).Connector-based approach to assembly planning using a genetic algorithm.International Journal of Production Research,42,2243-2261.
19. Tseng, H. E.,R. K. Li(1999).A novel means of generating assembly sequences using the connector concept.Journal of Intelligent Manufacturing,10,423-435.
20. Tseng, H. E.,W. P. Wang,H. Y. Shih(2007).Using memetic algorithms with guided local search to solve assembly sequence planning.Expert Systems with Applications,33,451-467.
21. Yin, Z. P.,H. Ding,H. X. Li,Y. L. Xiong(2003).A connector-based hierarchical approach to assembly planning for mechanical assemblies.Computer Aided Design,35,37-56.
22. Zha, X. F.,S. Y. E. Lim,S. C. Fok(1998).Integrated intelligent design and assembly planning: a survey.International Journal of Advanced Manufacturing Technology,14,664-685.