應用基因演算法進行生產排程之研究：以SMT製程為例

Application Genetic Algorithm for the production scheduling research: A Case Study of SMT Process

鄭念中(Nien-Chung Chng)

指導教授 ： 邱昭彰

元智大學/資訊學院/資訊管理學系/碩士(2012年)

摘要

排程問題包含許多不同類型與績效衡量準則，在實際環境中，幾乎都屬於平行機台樣式，而非相關平行機台排程問題係組合最佳化問題，除少數特例外，此類問題皆屬於NP-Hard。
本研究綜合考量電子製造業中表面黏著技術(SMT)實際生產需要的排程影響因素，以基因演算法為基礎，建構排程求解模型；在排程績效的考量上，先考慮單一績效衡量指標訂單達交率最大化；後探討多目標績效衡量指標，並在所設定需滿足之訂單達交率下，結合總流程時間與產線總閒置時間加權最小化作為排程績效指標，求取排程近似最佳解。並針對基因演算法的系統參數進行實驗與分析，再藉由設定多目標不同權重之組合，提高模式求解的品質。而實驗結果顯示，與單一績效指標最大化相比，結合多目標績效指標並藉由不同的權重設定，能有效提升排程求解能力。

關鍵字

表面黏著技術 ； 非相關平行機台 ； 基因演算法

並列摘要

Scheduling problem contains many different types of performance criteria. In real environment, almost are the parallel-machine, such as the unrelated parallel machines problems are combinatorial optimization problem. A few exceptions, such as problems are NP-Hard. The research is using Genetic Algorithm construction a scheduling model to solve the production scheduling, a case SMT of electronics manufacturing. The performance criteria，first consider single performance measure of sales order fill rate, then consider multi-objective performance , combine the Makespan and Machines idle time as the scheduling performance indicators . By setting the Genetic Algorithms system parameters and multi-objective combination of different weights , improve the quality of solving model. The experimental results show that maximizing a single performance indicators, compared with multi-objective performance indicators set by different weights, multi-objective can effectively improve the schedule for solving capabilities.

並列關鍵字

Surface Mounting Technology ； Unrelated Parallel Machines ； Genetic Algorithm

參考文獻

[1] Akkan, C. and Karabat, S., “The two-machine flowshop total completion time problem: Improved lower bounds and a branch-and-bound algorithm,” European Journal of Operational Research, Vol.159, pp. 420-429, 2004

[3] Cochran, J. K., Horng, S. M., Fowler, J. W., “A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines,” Computers & Operations Research, Vol.30, no. 7, pp.1087-1102, 2003

[5] Eren, T. and E.Guner., “A bicriteria scheduling with sequence-depent setup times,” Applied Mathematics and Computation, Vol .179,pp. 378-385, 2006

[6] Goldberg, D. E., “Genetic Algorithms in Search,” Optimization and Machine Learning, Addison Wesley, Reading, MA, 1989.

[9] Hwang, J. S, “Modern solder technology for competitive electronics manufacturing,” McGraw-Hill, Inc., New York., 1996