基於模擬的複合派工法則應用於多目標排程問題

Simulation-based Composite Dispatching Rule forSolving Multi-objective Scheduling Problems

黃朕庭(Chen-Ting Huang)

指導教授 ： 林妙聰

國立交通大學/管理學院/資訊管理研究所/碩士(2019年)

摘要

半導體排程一直是半導體產業中複雜而難解的問題之一，在追求產出最大化的同時也要最小化加權延遲時間與平均在系統時間，並且受到溫群轉換與截止時間等諸多限制，本研究提出一種新型的複合式派工法則，不同於直接使用傳統的派工法則如SPT或FIFO，本研究使用的是依照不同的比例做參數最佳化搭配出一個新的派工法則，透過多目標的非支配排序基因演算法做大量的模擬，並透過資料包絡分析降低支配解的數量，實驗研究指出這種派工法則有更好的表現，我們也實作了一個網頁做為簡易版的決策支援系統去展示成果。

關鍵字

派工法則 ； 多目標 ； 複合式法則 ； 半導體排程 ； 非支配排序基因演算法 ； 資料包絡分析

並列摘要

Manufacturing scheduling in semiconductor wafer fabs is a sophisticated and hard problem. This thesis aims to optimize throughput, mean flow time and mean weighted tardiness simul-taneously subject to the presence of the sequence-dependent setup time and common deadlineconstraints. A new composite dispatching rule is proposed in this study. Different from the tra-ditional elementary dispatching rules like SPT and FIFO, the proposed composite dispatchingrule is composed of elementary rules and associated with the relative importance indicators. TheNSGA-II-based simulation is adopted to perform relative importance optimization. Then DataEnvelopment Analysis is applied to reduce the number of Pareto optimal solutions. The experi-ments on test instances show thathe proposed composite rule has better overall performance thanthe elementary rules. We also built a web site as a simplified decision support system (DSS) todemonstrate our results.

並列關鍵字

Dispatching rules ； Multi-objective ； Composite dispatching rules ； Semiconductor scheduling ； Non-dominant Sorting Genetic Algorithm ； Data Envelopment Analysis

參考文獻

[1]Chang, Y.-L., Sueyoshi, T., and Sullivan, R. S., “Ranking dispatching rules by data en-velopment analysis in a job shop environment”,IIE transactions, vol. 28, no. 8, pp. 631–642, 1996.

[2]Charnes, A., Cooper, W. W., and Rhodes, E., “Measuring the efficiency of decision mak-ing units”,European journal of operational research, vol. 2, no. 6, pp. 429–444, 1978.

[3]Chen, X., Wen Lin, H., and Murata, T., “Composite dispatching rule design for dynamicscheduling with customer-oriented production priority control”,IEEJ Transactions onElectrical and Electronic Engineering, vol. 7, no. 1, pp. 53–61, 2012.

[4]Cooper, W. W., Seiford, L. M., and Tone, K., “Data envelopment analysis”,Handbookon Data Envelopment Analysis, 1st ed.; Cooper, WW, Seiford, LM, Zhu, J., Eds, pp. 1–40,2000.

[5]Dabbas, R. M. and Fowler, J. W., “A new scheduling approach using combined dispatch-ing criteria in wafer fabs”,IEEE Transactions on semiconductor manufacturing, vol. 16,no. 3, pp. 501–510, 2003.