臺灣博碩士論文加值系統

在以顧客需求為導向的生產環境下，產品的設計變的多樣而且複雜，企業為了提高競爭力，整合多個廠區的資源來完成產品的生產，即以跨廠區的環境來規劃產品的生產。在跨廠區的製造環境之下，產品的零組裝次序規劃問題，除了需要考量零件在組裝次序上的限制，零件的組裝工廠也是需要規劃的重點。因此，單廠區的組裝次序規劃已不適用，如何有效率地規劃跨廠區的零件組裝次序以滿足需求，便為研究的重要課題。
本研究提出兩個不同的演算法，以最低組裝成本為目標，規劃跨廠區零件組裝次序。有別於以往將零件組裝次序和組裝工廠指派分為兩部分的求解模式，提出能同時求解零件組裝次序和組裝工廠指派的方法。基因演算法的部份，透過編碼的設計，在基因編碼中混合了代表零件以及工廠的基因碼，使染色體能夠同時表達零件的組裝次序和組裝工廠的指派。粒子群演算法的部份，利用零件組裝權重和工廠指派權重的設計，使粒子位置能夠表達組裝次序和工廠指派。最後，透過實例的驗證，比較兩者在不同特性的問題下的求解效率與求解品質，發現粒子群演算法在搬運成本差異大的情況下能搜尋到較佳的解。

Due to the product design have becoming variety and complexity. The enterprises in order to enhance the competitiveness use the multi-plant planning. The assembly sequence in multi-plant planning, it not only considers the assembly sequence to each component but also assign the component to a feasible plant. Therefore, the single-plant planning for assembly is no longer applied to the problem. How to solve the assembly sequence problem quickly in multi-plant planning has been a key issue.
In this thesis, using Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) solve the assembly sequence problem in multi-plant planning. The objective is to obtain optimum the assembly sequence in multi-plant for the minimum cost. The assembly sequence problem in multi-plant planning combines the sequence problem and the assignment problem. We using GA solve two problems at same time by a special encoding rule. And in PSO, we using different definition at multi-dimension in order to solve assignment and sequence problem at same time. Cases are given to show the effectiveness of two algorithm can find the solutions which close to optimal, and characteristics of the algorithm are discussed.

摘要........................i
Abstract...................ii
誌謝......................iii
目錄...................iv
圖目錄...............viii
表目錄..................x
第一章 緒論.............1
1.1 研究背景與動機......1
1.2 研究目的............3
1.3 問題定義與假設......5
1.4 論文架構............7
第二章 文獻探討.........9
2.1 組裝限制............9
2.2 組裝次序規劃.......10
2.3 基因演算法.........12
2.3.1 基因演算法簡介...12
2.3.2 名詞解釋.........13
2.3.3 基因演算法基本流程 14
2.3.4 基因演算法的應用 16
2.4 粒子群演算法 18
2.4.1 粒子群演算法簡介 18
2.4.2 名詞解釋 19
2.4.3 粒子群演算法基本流程 20
2.4.4 粒子群演算法的應用 22
2.5 文獻結語 23
第三章 研究方法 25
3.1 前言 25
3.2 已知條件與假設 26
3.3 名詞定義 28
3.4 第一階段模式建立 28
3.4.1 零件結合狀態分析 28
3.4.2 組裝在先次序分析 31
3.4.3 干涉矩陣分析 35
3.4.4 工廠組裝能力 38
3.5 成本函數 39
3.5.1 組裝為基的成本 39
3.5.1.1 組裝操作成本 39
3.5.1.2 組裝工具變換成本 40
3.5.1.3 組裝方向變換成本 41
3.5.2 運送為基的成本 42
3.5.2.1 貴重成本 42
3.5.2.2 搬運成本 43
3.5.3 目標函數 44
3.6 基因演算法 44
3.7 粒子群演算法 54
3.8 參數分析 64
3.8.1 基因演算法參數分析 65
3.8.2 粒子群演算法參數分析 67
第四章 實例探討 70
4.1 實例一：MP3隨身聽 70
4.1.1 第一階段 － 零件組裝限制分析 71
4.1.1.1 結合狀態分析 71
4.1.1.2 組裝在先關係分析 73
4.1.1.3 干涉矩陣分析 74
4.1.2 第二階段 － 跨廠區組裝次序求解模式 74
4.1.2.1 基因演算法 75
4.1.2.2 粒子群演算法 78
4.1.3 結果輸出 80
4.1.3.1 基因演算法 80
4.1.3.2 粒子群演算法 81
4.2 實例二：多媒體喇叭 83
4.2.1 第一階段 － 零件組裝限制分析 83
4.2.1.1 結合狀態分析 83
4.2.1.2 組裝在先關係分析 85
4.2.1.3 干涉矩陣分析 86
4.2.2 第二階段 － 跨廠區組裝次序求解模式 86
4.2.2.1 基因演算法 88
4.2.2.2 粒子群演算法 90
4.2.3 結果輸出 92
4.2.3.1 基因演算法 92
4.2.3.2 粒子群演算法 93
4.3 實例三：分離式冷氣室內機 95
4.3.1 第一階段 － 零件組裝限制分析 96
4.3.1.1 結合狀態分析 96
4.3.1.2 組裝在先關係分析 97
4.3.1.3 干涉矩陣分析 99
4.3.2 第二階段 － 跨廠區組裝次序求解模式 100
4.3.2.1 基因演算法 101
4.3.2.2 粒子群演算法 103
4.3.3 結果輸出 106
4.3.3.1 基因演算法 106
4.3.3.2 粒子群演算法 107
4.4 實例四：手機 109
4.4.1 第一階段－零件組裝限制分析 109
4.4.1.1 結合狀態分析 109
4.4.1.2 組裝在先關係分析 110
4.4.1.3 干涉矩陣分析 111
4.4.2 第二階段－跨廠區組裝次序求解模式 112
4.4.2.1 基因演算法 113
4.4.2.2 粒子群演算法 115
4.4.3 結果輸出 118
4.4.3.1 基因演算法 118
4.4.3.2 粒子群演算法 119
4.5 結論 121
第五章 結論與建議 123
5.1 研究特性 123
5.2 研究貢獻 124
5.3 後續研究發展與建議 124
參考文獻 126

1.Akjiratikarl, C., P. Yenradee, and P. R. Drake, “PSO-based algorithm for home care worker scheduling in the UK,” Computers & Industrial Engineering, Vol.53, pp.559-583, 2007.
2.Biswas, S. and Mahapatra, S. S., “Modified particle swarm optimization for solving machine-loading problems in flexible manufacturing system,” International Journal of Advanced Manufacturing Technologies, 2007.
3.Bonneville, F., Perrard, C. and Henrioud, J. M., “A genetic algorithm to generate and evaluate assembly plans,” Proceedings of the IEEE Symposium on Emerging Technology and Factory Automation, pp.231-239, 1995.
4.Cao, P. B. and Xiao, R. B., “Assembly planning using a novel immune approach,” International Journal of Advanced Manufacturing Technologies, Vol.31, pp.770-782, 2007.
5.Chen, S. F. and Liu, Y. J., “An adaptive genetic assembly-sequence lanner,” International Journal of Computer Integrated Manufacturing, 14(5), pp.489-500, 2001.
6.Chen, Ruey-Shun, Kun-Yung Lu and Pei-Hao Tai, “Optimizing assembly planning through a three-stage integrated approach,” International Journal of Production Economics, Vol. 88, No. 3, pp.243-256, 2004.
7.Cheng, R., M. Gen, and T. Tozawz, “Minmax earliness/tardiness scheduling in identical parallel machine system using genetic algorithms,” Computer & Industrial Engineering, Vol. 29, pp. 513-517, 1995.
8.Choi, C. K., Zha, X. F., NG, T. L. and Lau, W. S., “On the automatic generation of product assembly sequences,” International Journal of Production Research, Vol. 36, No. 3, pp.617-633, 1998.
9.Heiko Mosemann and Friedrich M. Wahl, “Automatic Decomposition of Planned Assembly Sequences Into Skill Primitives,” IEEE Transactions on Robotics and Automation, Vol. 17, No.5, pp.709-718, 2001.
10.Ho, W. and Ji, P., “Component scheduling for chip shooter machines: a hybrid genetic algorithm approach,” Computers and Operations Research, Vol.30, pp.2175-2189, 2003.
11.Ho, W. and Ji, P., “A hybrid genetic algorithm for component sequencing and feeder arrangement,” Journal of Intelligent Manufacturing, Vol.15, pp.307-315, 2004.
12.Ho, W. and Ji, P., “A genetic algorithm to optimise the component placement process in PCB assembly,” International Journal of Advanced Manufacturing Technologies, Vol.26, pp.1397-1401, 2005.
13.Ho, W. and Ji, P., “A genetic algorithm approach to optimizing component placement and retrieval sequence for chip shooter machins,” International Journal of Advanced Manufacturing Technologies, Vol.28, pp.556-560, 2006.
14.Holland, J. H., “Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence,” University of Michigan Press, 1975.
15.Kennedy, J., and R. Eberhart, “Particle Swarm Optimization,” Proceedings of IEEE International Conference on Neural Networks, pp.1942-1948, 1995.
16.Kulak, O.,I. O. Yilmaz and H. –O. Günther, “PCB assembly scheduling for collect-and-place machines using genetic algorithms,” International Journal of Production Research, Vol. 45, No. 17, pp.3949-3969, 2007.
17.Lapperriere`, L., and ElMaraghy, H. A., “GAPP：a generative assembly process planner,” Journal of Manufacturing Systems, Vol. 15, No. 4, pp.282-293, 1996.
18.Lian, Z., Gu, X. and Jiao, B., “A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan,” Applied Mathematics and Computation, 175, pp.773-785, 2006.
19.Marain, R. M., Luong, L. H. S. and Abhary, K., “A genetic algorithm for the optimization of assembly sequences,” Computer and Industrial Engineering, Vol.50, pp.503-527, 2006.
20.Rahimi-Vahed, A. R. and Mirghorbani, “A multi-objective particle swarm for a flow shop scheduling problem,” Journal of Combinatorial Optimization, 13(1), pp. 79-102, 2007.
21.Senin, N.,Goppetti, R. and Wallace, D. R., “Concurrent assembly planning with genetic algorithms,” Robotics and Computer Integrated Management, 16(4), pp.65-72, 2002.
22.Smith, G. C. and Smith, S. F., “An enhanced genetic algorithm for automated assembly planning,” Robotics and Computer Integrated Management, 18, pp.355-364, 2002.
23.Su, Q., “Applying case-based reasoning in assembly sequence planning,” International Journal of Production Research, Vol.45, No.1, pp.29-47, 2007.
24.Tseng, H. E., Li, J. D. and Chang Y. H., “Connector-based approach to assembly sequences with genetic algorithms,” International Journal of Production Research, Vol.42, No.1, pp.2243-2261, 2004.
25.Tseng, H. E., “Guided genetic algorithms for solving a larger constraint assembly problem,” International Journal of Production Research, Vol. 44, No.3, pp.601-625, 2006.
26.Wang, J. F., Liu, J.H. and Zhong, Y. F., “A novel ant colony algorithm for assemble sequence planning,” International Journal of Advanced Manufacturing Technologies, 25, pp.1137-1143, 2005.
27.江吉祥，「以STEP為基進行產品組裝與拆卸分析之推演架構」，國立台灣科技大學機械工程系，碩士論文，2000。
28.江俊霖，「電子產品組裝廠之跨廠組裝次序」，元智大學工業工程與管理研究所，碩士論文，2002。
29.林吉宏，「組裝次序與加工次序之整合規劃研究－應用基因演算法」，元智大學工業工程與管理研究所，碩士論文，2000。
30.施欣怡，「改良式基因演算法求解複雜限制式之組裝規劃問題探討」，大葉大學工業工程與管理系，碩士論文，2005
31.徐誠佑，「粒子群演算法於離散最佳化問題之研究」，國立交通大學工業工程與管理研究所，博士論文，2007。
32.張銀和，「引導式基因演算法應用於Connector為基之組裝規劃」，大葉大學工業工程與管理系，碩士論文，2004。
33.曾懷恩、張堂聖、湯承恩，「組裝規劃中以模擬退火法產生組裝順序的探索」，Journal of the Chinese Institute of Industrial Engineers, Vol. 20, No. 2, pp.91-100, 2003。
34.蔡佳利，「跨廠組裝與加工次序整合規劃研究」，元智大學工業工程與管理研究所，碩士論文，2003。
35.黎長明，「改良式突變型態之粒子群演算法於客服人員排班的應用」，元智大學資訊管理學系，碩士論文，2007。
36.鍾清章等譯，田口式品質工程導論，中華民國品質學會，台北，民國九十四年。