U型組裝線平衡問題暨其遺傳演算求解法

U-shaped Assembly Line Balancing Problem and GA-Based Solving Approaches

楊傑翔(Chieh-Hsiaung Yang)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.03071

摘要

本研究針對U型組裝線平衡問題的特性，研擬一個「權重為基的染色體實數編碼法」。同時提出一個「基因值互換的實數交配法」使染色體可以均勻快速的演化求解。再配合編碼法提出一套「權重為基的染色體解碼法」支援遺傳演化以展示U型組裝線佈置結果和相關數據。「權重為基的染色體解碼法」是以遺傳演算法調配的染色體基因值引導，組成由前往後及由後往前兩條組裝作業序列後，據以進行組裝作業指派及工作站組成的演算程序。為驗證本研究所提的遺傳演算法演算機制，本研究並以U型組裝線標竿問題為測試對象，進行實例驗證與結果分析。結果顯示，在求解已知最佳解的標竿問題時，可以搜尋到全域最佳解。透過使用不同求解目標模式的比較，發現若以組裝線利用率最大化為求解目標，其求解結果並不如以各工作站閒置時間平方和最小化或是工作站負荷變異數最小化為目標的求解模式。本研究研擬的遺傳演算求解法可以有效地求解U型組裝線平衡問題以支援工廠的營運與決策。

關鍵字

U型組裝線平衡問題 ； 遺傳演算法 ； 實數編碼法 ； 權重為基 ； 組裝作業序列

並列摘要

In accordance with the character of U-shaped assembly line balancing problem (UALBP), this paper presents a real number encoding operation called “priority-based real number encoding operation”. According to let the chromosomes generate more uniform and quick, this paper also presents a crossover operation called “gene value exchange crossover operation”. Finally this paper presents a decoding operation called “priority-based decoding operation” to support genetic algorithm and display the U-shaped assembly line layout and relative data. “Priority-based decoding operation” is an operation which assign tasks to workstation depend on a forward task permutation and a backward task permutation. Those two task permutations all generate by gene values in the same chromosome. To justify our genetic algorithm model, we use UALBP benchmarks to verify model and analysis the results. The results show that using our genetic algorithm model can find the global optimal solution in some benchmarks. Compare with different objective functions in mathematical models, we find the result that using maximize line efficiency to be the objective function isn’t good enough to solve UALBP. Using minimize variation of workload or minimize sum of workstation idle time square to be the objective function can find better solutions than maximize line efficiency. This paper presents the genetic algorithm solving model can efficiently solve UALBP, and it also can help the engineer to do decisions.

並列關鍵字

U-shaped assembly line balancing problem ； Genetic Algorithm ； Real number encoding operation ； Priority-based ； Task permutation

參考文獻

2.Baykasoglu, A. (2006). "Multi-rule multi-objective simulated annealing algorithm for straight and U type assembly line balancing problems." Journal of Intelligent Manufacturing, 17(2), 217-232.

3.Becker, C., and Scholl, A. (2006). "A survey on problems and methods in generalized assembly line balancing." European Journal of Operational Research, 168(3), 694-715.

4.Bowman, E. H. (1960). "Assembly-line balancing by linear programming." Operations Research, 8(3), 385-389.

5.Falkenauer, E., and Delchambre, A. (1992) "A genetic algorithm for bin packing and line balancing." IEEE International Conference on Robotics and Automation, 1186-1192.

6.Ghosh, S., and Gagnon, R. J. (1989). "Comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems." International Journal of Production Research, 27(4), 637-670.