以群組基因演算法求解成衣業車縫線之生產線設計問題

A Grouping Genetic Algorithm for the Assembly Line Design Problem of Sewing Lines in Garment Industry

蕭秀惠(Mabel H. Hsiao)

指導教授 ： 陳建良

中原大學/工學院/工業工程研究所/碩士(2005年)

https://doi.org/10.6840/cycu200500597

摘要

成衣製造屬於傳統及流行的產業，面對以顧客為中心的國際化競爭。車縫作業需要最多的人力及物力，是成衣製程中的關鍵作業。成衣業車縫作業中的生產線平衡計畫，其目的在於妥善指派工序至各工作站，使工作站之機台能執行所分派之工序，並平衡各工作站的工作負荷。生產線設計問題（Assembly Line Design Problem，ALDP）除了考慮生產線平衡，更考慮機台種類的限制，亦即工序分派至工作站必須考慮機台能執行所分派之工序。由於生產線設計問題屬於NP-hard問題，因此，對於成衣業車縫作業具複雜的先行作業關係而言，啟發式演算法能在合理時間內求得近似最佳解。
本論文應用群組基因演算法（Genetic Grouping Algorithm，GGA）發展出求解成衣業生產線設計問題的模式。Falkenauer於1992提出群組基因演算法，改良基因演算法的缺點以適用於生產線平衡問題。本研究之目的是透過求解最小相對平均誤差（Mean Absolute Deviations，MAD）以達成最大工作站負荷平衡。本研究以實際之成衣業生產數據來驗證所發展之群組基因演算法之績效。由實驗結果得知：相較於基因演算法，群組基因演算法在求解較簡單及較複雜問題分別有13.81%及8.81%的相對改善百分比。因此，群組基因演算法是一個能有效應用於求解成衣業車縫作業的生產線平衡設計問題的方法。

關鍵字

群組基因演算法 ； 生產線設計問題 ； 組裝線平衡問題 ； 成衣業

並列摘要

The garment manufacturing is a traditional and fashion industry, that is globally competitive and customer centric. The most critical operation process is sewing, as it generally involves a great number of operations. The aim of assembly line balancing planning in sewing lines is to assign task to the workstation in order that the machines of the workstation can perform the assigned tasks with a balanced loading. Different from simple assembly line balancing problem, the assembly line design problem (ALDP) has constraints related to machine types. While tasks are being assigned to the workstations, the tasks can be performed by the same machine/tool type. ALDP is known as an NP-hard problem. Thus, the heuristic methodology could be a better way to plan the sewing lines in a reasonable time.
This thesis presents a grouping genetic algorithm (GGA) of GGA for assembly line design problem of sewing lines in garment industry. GGA was first developed by Falkenauer in 1992 as a type of GA which exploits the special structure of grouping problem, and overcomes the drawbacks of GA. GGA allocates workload among machines as evenly as possible, so the minimum mean absolute deviations (MAD) can be minimized. The performance is verified through solving two real problems. The computational results reveal that GGA outperforms GA in the simple and complex problems are 13.81% and 8.81%, respectively. This shows GGA’s effectiveness in solving ALDP.

並列關鍵字

Garment Industry ； Assembly Line Balancing Problem ； Grouping Genetic Algorithm ； Assembly Line Design Problem

參考文獻

Agpak, K. and Gökçen, H. (2005), “Assembly line balancing: Two resource constrained cases”, International Journal of Production Economics, 96, pp. 129-140.

Amen, M. (2001), “ Heuristic methods for cost-oriented assembly line balancing: A comparison on solution quality and computing time”, International Journal of Production Economics, 69, pp. 255-264.

Baybars, I. (1986), “A survey of exact algorithms for the simple assembly line balancing problem”, Management Science, 32, pp. 909-932.

Bock, S. and Rosenberg, O. (2000), “A new parallel breadth first tabu search technique for solving production planning problems”, International Transactions in Operational Research, 7, pp. 625-635.

Bowman, E. H. (1960), “Assembly-line Balancing by Linear Programming”, Operations Research, 8, pp. 385-389.