https://scholars.lib.ntu.edu.tw/handle/123456789/81859
標題: | 以遺傳演算法求解轉塔式插件機的元件插置排序問題和料帶儲位安排問題 Using Genetic Algorithms to Solve Placement Sequencing Problems and Feeder Arrangement Problems for Turret-type Insertion Machines |
作者: | 張朕豪 Chang, Chen-Hao |
關鍵字: | 表面黏著技術;印刷電路板組裝;轉塔式插件機;遺傳演算法;元件插置順序;料帶儲位安排問題;Turret-Type Insertion Machine;PCB Assembly;Surface Mount Technology;Feeder Arrangement;Insertion Sequence | 公開日期: | 2004 | 摘要: | 本研究針對印刷電路板轉塔式插件機(turret-type insertion machine)元件插置順序問題(insertion sequence problem)和料帶儲位安排問題(feeder arrangement problem),提出一種啟發式求解模式和三種遺傳演算求解模式(分段求解模式、交互凍結模式、和同步優化模式)。並且比較以不同模式求解元件插置順序問題和料帶儲位安排問題的效率。其中啟發式分段求解模式是先以貪婪演算法進行料帶儲位安排,再依所得的解以最鄰近演算法進行元件插置順序。分部求解模式則是把料帶儲位安排問題和元件插置排序問題視為兩個子問題分別進行求解,將使用數量相近類別的元件安排在相鄰儲位進行料帶儲位安排且以使元件插置作動路徑最短為目標進行元件插置排序。交互凍結模式則能在元件插置排序和料帶儲位安排兩條染色體交互凍結的過程中分別調整未凍結染色體以改善總元件插置時間。同步優化模式在每代遺傳演算中同時以元件插置順序染色體以及料帶儲位安排染色體進行演化,其搜尋範圍涵蓋了所有可行解區域以保留搜尋到全域最佳解的機會。經過四種不同元件數量和元件類別數的範例和一個引用自相關研究的標竿問題測試,並且以元件總插置作動距離及料帶架總移動長分別做為衡量插件機工作負荷的標準。結果顯示啟發式分段求解模式能使料帶架總移動長最小;分部尋優模式可使總元件插置作動距離最短;而採用交互凍結模式所排得的元件插置順序及料帶儲位安排在四種模式中能最有效改善插件機進行插件時的瓶頸。 In this thesis, we focus on the insertion sequence problem and the feeder arrangement problem for turret-type insertion machine. One model of heuristic algorithm and three model of genetic algorithm has been display. We compared the performance of these four models on dealing with the insertion sequence problem and the feeder arrangement problem. The 2-section heuristic model is to arrange the feeder arrangement by greedy algorithm, then deciding the insertion sequence by nearest neighbor algorithm. The 2-stage genetic algorithm model is to arrange the insertion sequence and feeder arrangement separately with different fitness function. The mutual freezing genetic algorithm model is to freeze one of the insertion sequence chromosome and the feeder arrangement chromosome, and using just one chromosome to evaluate. But calculate the fitness function by both two chromosomes. The synchronizing genetic algorithm model is to evaluate the insertion chromosome and the feeder arrangement chromosome in the same time. The test data including a benchmark problem obtained from former research, and the others are developed by us to test the performance of these four model. The result shows that the mutual freezing genetic algorithm model can decrease the bottleneck of printed circuit board assembly more than the others. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/51158 | 其他識別: | zh-TW |
顯示於: | 工業工程學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。