臺灣博碩士論文加值系統

近年來，由於環保意識的提高，綠色製造已受到社會的高度關注，二次原料之利用為綠色製造的重要趨勢，因此製造業也更加重視產品與材料的回收與再製，而有效的拆卸線作業能夠提升產品回收率以及降低拆卸成本等優勢，並促進產業之競爭力。本研究針對考慮資源限制之多人工作站拆卸線平衡問題(disassembly line balancing problems with multi-manned workstations)，建構數學規劃最佳化模型，使用改良式AND/OR 圖(Transformed AND/OR Graph)作為拆卸作業之間的優序關係，以最小化工作站總數、機台類型總數以及操作員總數為規劃目標。為了提高求解效率，本研究發展混合模擬退火演算法(hybrid simulated annealing)與基因模擬退火演算法(genetic simulated annealing)，將演算法應用於筆記型電腦拆卸實務案例，並分析與比較不同演算法之間的目標函數值、工作效率以及配置組合，最後執行參數敏感度分析，將分析結果提供給拆卸線決策者作為參考依據。

With the improvement of environmental awareness, the manufacturing industry pays more attention to the recycling and remanufacturing of products and materials. An effective disassembly line can effectively increase the rate of product recovery and reduce the cost of disassembly tasks. This study proposes an integer programming model for the resource constrained disassembly line balancing problem with multi-manned workstations. The objective is to minimize the number of workstations, machine types, and operators to obtain the optimal allocation of tasks, machine types, and operators. The transformed AND / OR graph is utilized to ensure the feasibility of the precedence relations among the tasks. To improve the solving efficiency, this study develops two hybrid heuristic approaches, hybrid simulated annealing algorithm and genetic simulated annealing algorithm. The algorithms are applied to the practical disassembly case of tablet computer. Results in terms of solution quality, production efficiency, and allocation configuration are analyzed and discussed. The findings of this study can be used as reference for decision making in the allocation of tasks, workstations, machine types, and operators to the manager of practical case.

摘 要……………………i
Abstract…………ii
誌 謝……………………iii
目 錄……………………………iv
表目錄…………………………vii
圖目錄…………………………ix
第一章 緒論………………………………………1
1.1 研究背景與動機……………1
1.2 研究目的…………………………1
1.3 研究範圍與假設……………2
1.4 研究流程 …………………………3
第二章 文獻探討………………………………………5
2.1 拆卸線平衡問題…………………………5
2.2 多人工作站………………………………………11
2.3 資源限制下拆卸線平衡問題……………12
2.4 拆卸關係與圖表…………………………13
2.5 模擬退火演算法…………………………15
2.6 基因演算法………………………………………17
2.7 基因演算法結合模擬退火演算法……………19
2.8 實驗設計-反應曲面法……………20
2.9 小結……………………………………………………25
第三章 問題定義……………………………………………………26
3.1 定義問題…………………………26
3.2 數學規劃模型……………27
3.3 測試問題…………………………32
第四章 演算法測試與開發…………………………42
4.1 建立可行平衡解之流程……………42
4.2 混合模擬退火演算法流程……………60
4.3 基因模擬退火演算法流程……………68
4.4 參數設定……………………………………………………74
4.4.1 混合模擬退火演算法之參數設定…………………………74
4.4.2 基因模擬退火演算法之參數設定…………………………77
4.5 測試問題與驗證…………………………84
4.5.1 測試環境與測試問題…………………………84
4.5.2 混合模擬退火演算法測試結果……………84
4.5.3 基因模擬退火演算法測試結果……………87
4.6 測試結果比較……………89
第五章 實務案例……………92
5.1 案例說明……………92
5.2 規劃結果……………100
5.2.1 混合模擬退火演算法之結果……………100
5.2.2 基因模擬退火演算法之結果……………103
5.2.3 演算法結果分析…………………………107
5.3 規劃結果參數敏感度分析……………108
5.3.1 工作站操作員數上限對工作站配置之影響…………………………108
5.3.2 操作員熟練之機台類型數對工作站配置之影響……………110
5.3.3 週期時間對工作站配置之影響……………111
5.3.4 討論……………113
第六章 結論與建議……………114
6.1 結論……………114
6.2 建議……………115
參考文獻……………116
附錄A……………124
附錄B……………130
附錄C……………133
Extended Abstract……………144

1.李世炳、鄒忠毅（2002），簡介導引模擬退火法及其應用，中央研究院物理研究所，碩士論文。
2.林志交（2002），基因演算法於模型影像套合計算之應用，國立成功大學測量工程學系，碩士論文。
3.林李旺（2013），突破品質水準-實驗設計與田口方法之實務應用，全華圖書股份有限公司，新北市。
4.陳俞安（2020），考慮操作員工作熟練度下之拆卸線平衡問題，國立虎尾科技大學工業管理系工業工程與管理碩士班，碩士論文。
5.楊育佳（2017），以適應性基因演算法搭配 AND/OR 圖之拆卸線生產線平衡問題研究，國立清華大學工業工程與工程管理研究所，碩士論文。
6.葉怡成（2005），實驗設計法-製程與產品最佳化，五南圖書出版股份有限公司，台北市。
7.蔣安國、蔣安仁、丁敬哲、鍾健平（2005），「以模擬技術和統計方法建構專案排程之可靠度」，管理科學研究特刊，1期，頁119 - 130。
8.蘇朝墩（2009），六標準差，前程文化事業有限公司，新北市。
9.Agrawal, S., & Tiwari, M. (2008). A collaborative ant colony algorithm to stochastic mixed-model U-shaped disassembly line balancing and sequencing problem. International Journal of Production Research, 46(6), 1405-1429.
10.Akagi, F., Osaki, H., & Kikuchi, S. (1983). A method for assembly line balancing with more than one worker in each station. The International Journal of Production Research, 21(5), 755-770.
11.Altekin, F. T., & Akkan, C. (2012). Task-failure-driven rebalancing of disassembly lines. International Journal of Production Research, 50(18), 4955-4976.
12.Altekin, F. T., Kandiller, L., & Ozdemirel, N. E. (2008). Profit-oriented disassembly-line balancing. International Journal of Production Research, 46(10), 2675-2693.
13.Altekin, F. T. (2017). A comparison of piecewise linear programming formulations for stochastic disassembly line balancing. International Journal of Production Research, 55(24), 7412-7434.
14.Aydemir-Karadag, A., & Turkbey, O. (2013). Multi-objective optimization of stochastic disassembly line balancing with station paralleling. Computers and Industrial Engineering, 65(3), 413-425.
15.Azargohar, R., & Dalai, A. (2005). Production of activated carbon from Luscar char: experimental and modeling studies. Microporous and Mesoporous Materials, 85(3), 219-225.
16.Bentaha, M. L., Battaïa, O., & Dolgui, A. (2014). A sample average approximation method for disassembly line balancing problem under uncertainty. Computers & Operations Research, 51, 111-122.
17.Bentaha, M. L., Battaïa, O., & Dolgui, A. (2015). An exact solution approach for disassembly line balancing problem under uncertainty of the task processing times. International Journal of Production Research, 53(6), 1807-1818.
18.Bentaha, M. L., Dolgui, A., Battaïa, O., Riggs, R. J., & Hu, J. (2018). Profit-oriented partial disassembly line design: dealing with hazardous parts and task processing times uncertainty. International Journal of Production Research, 56(24), 7220-7242.
19.Brennan, L., Gupta, S. M., & Taleb, K. N. (1994). Operations planning issues in an assembly/disassembly environment. International Journal of Operations & Production Management.
20.Cevikcan, E., Aslan, D., & Yeni, F. B. (2020). Disassembly line design with multi-manned workstations: a novel heuristic optimisation approach. International Journal of Production Research, 58(3), 649-670.
21.Cevikcan, E., Durmusoglu, M. B., & Unal, M. E. (2009). A team-oriented design methodology for mixed model assembly systems. Computers & Industrial Engineering, 56(2), 576-599.
22.Chen, Y.-Y., Cheng, C.-Y., & Li, J.-Y. (2018). Resource-constrained assembly line balancing problems with multi-manned workstations. Journal of Manufacturing Systems, 48, 107-119.
23.Corominas, A., Ferrer, L., & Pastor, R. (2011). Assembly line balancing: general resource-constrained case. International journal of production research, 49(12), 3527-3542.
24.Das, S., & Caudill, R. (1999). The design of high volume disassembly lines. Paper presented at the Demanufacturing of Electronic Equipment for Reuse and Recycling Information Exchange Meeting Archives.
25.Ding, L.-P., Feng, Y.-X., Tan, J.-R., & Gao, Y.-C. (2010). A new multi-objective ant colony algorithm for solving the disassembly line balancing problem. The International Journal of Advanced Manufacturing Technology, 48(5-8), 761-771.
26.Edis, E. B. (2021). Constraint programming approaches to disassembly line balancing problem with sequencing decisions. Computers & Operations Research, 126, 105111.
27.Edis, E. B., Ilgin, M. A., & Edis, R. S. (2019). Disassembly line balancing with sequencing decisions: A mixed integer linear programming model and extensions. Journal of Cleaner Production, 238, 117826.
28.Gottipolu, R., & Ghosh, K. (1997). Representation and selection of assembly sequences in computer-aided assembly process planning. International Journal of Production Research, 35(12), 3447-3466.
29.Gungor, A., & Gupta, S. M. (1999). Disassembly line balancing. Proceedings of the 1999 Annual Meeting of the Northest Decision Sciences Institute, 193-195.
30.Gungor, A., & Gupta, S. M. (2001). A solution approach to the disassembly line balancing problem in the presence of task failures. International journal of production research, 39(7), 1427-1467.
31.Gupta, S. M., McGovern, S. M., & Kamarthi, S. V. (2003). Solving disassembly sequence planning problems using combinatorial optimization.
32.Hezer, S., & Kara, Y. (2015). A network-based shortest route model for parallel disassembly line balancing problem. International Journal of Production Research, 53(6), 1849-1865.
33.Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence: MIT press.
34.Kalayci, C. B., & Gupta, S. M. (2013). Artificial bee colony algorithm for solving sequence-dependent disassembly line balancing problem. Expert Systems with Applications, 40(18), 7231-7241.
35.Kalayci, C. B., Gupta, S. M., & Nakashima, K. (2012). A simulated annealing algorithm for balancing a disassembly line. In Design for innovative value towards a sustainable society (pp. 714-719): Springer.
36.Kalayci, C. B., Polat, O., & Gupta, S. M. (2016). A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem. Annals of Operations Research, 242(2), 321-354.
37.Kazemi, A., & Sedighi, A. (2013). A cost-oriented model for balancing mixed-model assembly lines with multi-manned workstations. International Journal of Services and Operations Management, 16(3), 289-309.
38.Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
39.Koc, A., Sabuncuoglu, I., & Erel, E. (2009). Two exact formulations for disassembly line balancing problems with task precedence diagram construction using an AND/OR graph. LIE Transactions, 41(10), 866-881. doi:10.1080/07408170802510390
40.Kucukkoc, I. (2020). Balancing of two-sided disassembly lines: Problem definition, MILP model and genetic algorithm approach. Computers & Operations Research, 124, 105064.
41.Kucukkoc, I., Li, Z., & Li, Y. (2019). Type-E disassembly line balancing problem with multi-manned workstations. Optimization and Engineering, 1-20.
42.Lambert, A, F., & Gupta, S. M. (2004). Disassembly modeling for assembly, maintenance, reuse and recycling: CRC press.
43.Lambert, A. J. (2003). Disassembly sequencing: a survey. International Journal of Production Research, 41(16), 3721-3759.
44.Li, W.D., Ong, S., & Nee, A. (2002). Hybrid genetic algorithm and simulated annealing approach for the optimization of process plans for prismatic parts. International journal of production research, 40(8), 1899-1922.
45.Li, Z., Kucukkoc, I., & Zhang, Z. (2019). Iterated local search method and mathematical model for sequence-dependent U-shaped disassembly line balancing problem. Computers & Industrial Engineering,, 137, 106056.
46.Liang, J., Guo, S., Du, B., Li, Y., Guo, J., Yang, Z., & Pang, S. (2021). Minimizing energy consumption in multi-objective two-sided disassembly line balancing problem with complex execution constraints using dual-individual simulated annealing algorithm. Journal of Cleaner Production, 284, 125418.
47.Liu, J., & Wang, S. J. S. (2017). Balancing disassembly line in product recovery to promote the coordinated development of economy and environment. 9(2), 309.
48.McGovern, S. M., & Gupta, S. M. (2006a). Ant colony optimization for disassembly sequencing with multiple objectives. The International Journal of Advanced Manufacturing Technology, 30(5-6), 481-496.
49.McGovern, S. M., & Gupta, S. M. (2006b). Computational complexity of a reverse manufacturing line. Paper presented at the Environmentally Conscious Manufacturing VI.
50.McGovern, S. M., & Gupta, S. M. (2007a). A balancing method and genetic algorithm for disassembly line balancing. European Journal of Operational Research, 179(3), 692-708. doi:https://doi.org/10.1016/j.ejor.2005.03.055
51.McGovern, S. M., & Gupta, S. M. (2007b). Combinatorial optimization analysis of the unary NP-complete disassembly line balancing problem. International Journal of Production Research, 45(18-19), 4485-4511.
52.McGovern, S. M., & Gupta, S. M. (2011). Disassembly Line: Balancing and Modeling: McGraw-Hill Education.
53.McGovern, S. M., & Gupta, S. M. (2004). 2-opt heuristic for the disassembly line balancing problem. Paper presented at the Environmentally conscious manufacturing iii.
54.Mete, S., & Agpak, K. (2013). Multi objective generalized resource constrained two sided assembly line balancing problem and computational analaysis. Journal of The Faculty of Engineering and Architecture of Gazi University, 28(3), 567-575.
55.Mete, S., Çil, Z. A., Ağpak, K., Özceylan, E., & Dolgui, A. (2016). A solution approach based on beam search algorithm for disassembly line balancing problem. Journal of Manufacturing Systems, 41, 188-200.
56.Mete, S., Çil, Z. A., Özceylan, E., & Ağpak, K. (2016). Resource constrained disassembly line balancing problem. IFAC-PapersOnLine, 49(12), 921-925.
57.Mutlu, S., & Güner, B. (2021). A memetic algorithm for mixed-model two-sided disassembly line balancing problem. Procedia CIRP, 98, 67-72.
58.Özcan, U., & Toklu, B. J. T. I. J. o. A. M. T. (2009). A tabu search algorithm for two-sided assembly line balancing. The International Journal of Advanced Manufacturing Technology, 43(7-8), 822.
59.Paksoy, T., Güngör, A., Özceylan, E., & Hancilar, A. (2013). Mixed model disassembly line balancing problem with fuzzy goals. International Journal of Production Research, 51(20), 6082-6096.
60.Pistolesi, F., Lazzerini, B., Dalle Mura, M., & Dini, G. (2017). EMOGA: A hybrid genetic algorithm with extremal optimization core for multiobjective disassembly line balancing. IEEE Transactions on Industrial Informatics, 14(3), 1089-1098.
61.Prakash, P., Ceglarek, D., & Tiwari, M. (2012). Constraint-based simulated annealing (CBSA) approach to solve the disassembly scheduling problem. The International Journal of Advanced Manufacturing Technology, 60(9-12), 1125-1137.
62.Ren, Y., Yu, D., Zhang, C., Tian, G., Meng, L., & Zhou, X. (2017). An improved gravitational search algorithm for profit-oriented partial disassembly line balancing problem. International Journal of Production Research, 55(24), 7302-7316.
63.Roshani, A., & Nezami, F. G. (2017). Mixed-model multi-manned assembly line balancing problem: a mathematical model and a simulated annealing approach. Assembly Automation.
64.Roshani, A., Roshani, A., Roshani, A., Salehi, M., & Esfandyari, A. (2013). A simulated annealing algorithm for multi-manned assembly line balancing problem. Journal of Manufacturing Systems, 32(1), 238-247.
65.Şahin, M., & Kellegöz, T. (2019). Balancing multi-manned assembly lines with walking workers: problem definition, mathematical formulation, and an electromagnetic field optimisation algorithm. International Journal of Production Research, 57(20), 6487-6505.
66.Seidi, M., & Saghari, S. (2016). The balancing of disassembly line of automobile engine using genetic algorithm (GA) in fuzzy environment. Industrial Engineering and Management Systems, 15(4), 364-373.
67.Shaaban, S., Darwish, A. S., Kalayci, C. B., Polat, O., & Gupta, S. M. (2015). A variable neighbourhood search algorithm for disassembly lines. Journal of Manufacturing Technology Management.
68.Smith, S., Hsu, L.-Y., & Smith, G. C. (2016). Partial disassembly sequence planning based on cost-benefit analysis. Journal of Cleaner Production, 139, 729-739.
69.Tamilarasi, A. J. I. J. o. E., Science, & Technology. (2010). An enhanced genetic algorithm with simulated annealing for job-shop scheduling. 2(1), 144-151.
70.Tseng, H.-E., Chang, C.-C., Lee, S.-C., & Huang, Y.-M. (2018). A block-based genetic algorithm for disassembly sequence planning. Expert Systems with Applications, 96, 492-505.
71.Tuncel, E., Zeid, A., & Kamarthi, S. (2014). Solving large scale disassembly line balancing problem with uncertainty using reinforcement learning. Journal of Intelligent Manufacturing, 25(4), 647-659.
72.Wang, Li, X., & Gao, L. (2019). Modeling and optimization of multi-objective partial disassembly line balancing problem considering hazard and profit. Journal of Cleaner Production, 211, 115-133. doi:https://doi.org/10.1016/j.jclepro.2018.11.114
73.Wang, K., Li, X., Gao, L., Li, P., & Gupta, S. M. (2021). A genetic simulated annealing algorithm for parallel partial disassembly line balancing problem. Applied Soft Computing, 107, 107404.
74.Wang, S., Guo, X., & Liu, J. (2019). An efficient hybrid artificial bee colony algorithm for disassembly line balancing problem with sequence-dependent part removal times. Engineering Optimization, 51(11), 1920-1937.
75.Wang, S., Zuo, X., Liu, X., Zhao, X., & Li, J. (2015). Solving dynamic double row layout problem via combining simulated annealing and mathematical programming. Applied Soft Computing, 37, 303-310.
76.Wong, F. S. (1985). Slope reliability and response surface method. Journal of Geotechnical Engineering, 111(1), 32-53.
77.Xiao, S., Wang, Y., Yu, H., & Nie, S. J. E. (2017). An entropy-based adaptive hybrid particle swarm optimization for disassembly line balancing problems. 19(11), 596.
78.Yilmaz, H., & Yilmaz, M. (2020). A mathematical model and tabu search algorithm for multi-manned assembly line balancing problems with assignment restrictions. Engineering Optimization, 52(5), 856-874.
79.Zhang, L., Zhao, X., Ke, Q., Dong, W., & Zhong, Y. (2019). Disassembly line balancing optimization method for high efficiency and low carbon emission. International Journal of Precision Engineering and Manufacturing-Green Technology, 1-15.
80.Zhang, Z., Wang, K., Zhu, L., & Wang, Y. (2017). A Pareto improved artificial fish swarm algorithm for solving a multi-objective fuzzy disassembly line balancing problem. Expert Systems with Applications 86, 165-176.
81.Zhu, L., Zhang, Z., & Guan, C. (2020). Multi-objective partial parallel disassembly line balancing problem using hybrid group neighbourhood search algorithm. Journal of Manufacturing Systems, 56, 252-269.
82.Zhu, L., Zhang, Z., & Wang, Y. (2018). A Pareto firefly algorithm for multi-objective disassembly line balancing problems with hazard evaluation. International Journal of Production Research, 56(24), 7354-7374.