基因演算法應用於含燒機之組裝線排程問題

Application of Genetic Algorithm for Assembly Scheduling Problem with Burn-in Test

簡芸熙(Yun-Hsi Chien)

指導教授 ： 林則孟

國立清華大學/工學院/工業工程與工程管理學系/碩士(2020年)

摘要

本研究主要探討變頻器電子組裝產業後段組裝製程之排程問題。聚焦於組裝線製程並將組裝線視為非等效平行機台(unrelated parallel machine scheduling)，同時考慮次站的燒機問題。燒機站為批次排程問題，批次排程又可分為兩個決策點，第一，決定批次的組成，第二，將批次進行機台指派。本研究主要探討組裝線排程與燒機站的批次組成問題，考量生產系統的特性與限制，包含:機台限制、順序相依設置時間、不同容量大小、可用電壓級距限制等。
本研究在Joo & Kim(2015)以及Basir et al.(2018)提出的基因演算法架構下，根據問題特性做變化，提出「二階段排程基因演算法」與「整合式排程基因演算法」。「二階段排程基因演算法」主要提出一個進行機台排程同時粗估燒機站容量使用的派工法，另外，根據裝箱問題文獻提出一個優化批次組成的啟發式算法。「整合式排程基因演算法」則是將問題特性融入重新設計染色體組成，使組裝線排程與燒機的批次組成問題能夠在整合式方法中一次解決。
本研究經實驗發現在不同工單數量的問題下「二階段排程基因演算法」的求解效率表現較「整合式排程基因演算法」為佳。總結來說，進行組裝線排程時粗略估計工單使用的電壓級距容量，組裝線排程完成後再根據工單來到的先後順序進行批次組成，在本研究範圍內有較好的表現。

關鍵詞：非等效平行機台排程、批次排程、基因演算法

關鍵字

非等效平行機台排程 ； 批次排程 ； 基因演算法

並列摘要

This research investigates the scheduling of the assembly process in the back-end process of the variable-frequency drive assembly industry. The assembly line process is regard as an unrelated parallel machine scheduling. Also, parallel batch scheduling problem at burn-in station is considered. The batch scheduling can be divided into two decisions: (i) forming the batches; and (ii) assigning batches to the machines. This study mainly discusses the assembly line scheduling and the batch forming of the burn-in test station and considering the production characteristics: machine eligibility, sequence-dependent setup time, different capacity and burn-in level availability.
In this research, based on the genetic algorithm framework proposed by Joo & Kim (2015) and Basir et al. (2018), two heuristic models are developed to solve this problem. The “two-stage scheduling genetic algorithm” proposes a dispatching method that performs machine scheduling and roughly estimates the capacity of the burn-in station. In addition, an algorithm for optimizing batch forming is proposed based on the bin packing problem. "Integrated scheduling genetic algorithm" is to combine the characteristics of the problem into the chromosome composition, so that the assembly line scheduling and the batch forming can be solved at one time by the integrated method.
It is shown that the "two-stage scheduling genetic algorithm" performs better than the "integrated scheduling genetic algorithm" in both solution efficiency and performance. In the conclusion, if the burn-in level capacity is roughly estimated when arranging assembly line schedule, the batch forming will outperform in this research.
Keywords: Unrelated parallel machine scheduling, Batch scheduling, Genetic algorithm

並列關鍵字

unrelated parallel machine scheduling ； batch scheduling ； genetic algorithm

參考文獻

參考文獻

[1]. 林則孟(2012)，生產計畫與管理，華泰文化。

[2]. 李宇笙(2018)，「穩健最佳化應用於平行機台排程問題」，國立清華大學工業工程與工程管理研究所碩士論文。

[3]. Arroyo, J. E. C., & Leung, J. Y. T. (2017). Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times. Computers & Operations Research, 78, 117-128.

[4]. Afzalirad, M., & Shafipour, M. (2018). Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions. Journal of Intelligent Manufacturing, 29(2), 423-437.