臺灣博碩士論文加值系統

基於生產計畫，模擬可提供對製程產出預測的估計，以用於評估並調整原計
畫。其中，各製程生產週期時間的估計為模擬預測中最重要部分，具正確的生產
週期時間方能進行有效的模擬。然而當製程具循序串級行為，且這些行為分佈殊
異時，目前典型配適方法如MLE僅適於單一分佈，即若EM 亦僅能處理相同分
佈的混合模型，對於不同且串級製程行為分佈，實缺乏有效的分佈參數配適方法。
由於不同串級分佈參數組合可構成相近的串級行為分佈，而這些串級分佈參
數組合將可構成所謂的多目標的柏拉前緣。因此，為有效配適製程的多分佈參
數，本研究提出一基於小生境基因演算法之多目標最佳化配適程序，因製程行為
週期時間實包含資訊傳輸延遲時間、物料等待時間與實際加工時間等三部分，若
以不同基因組代表不同串級分佈參數，藉由多組動態隔離小生境的基因交配與演
化，在柏拉前緣上，初期採用扶幼保護，中期採取新老更替與劣種不活的策略，
最後運用大數法則，將可獲得製程多分佈參數的最佳化組合。
在配適結果上，若以8 組不同串級行為分佈組合為例，其配適與實際重疊率
為84%以上。利用此程序，以8 組不同實際生產週期時間分析，與所配適參數重
建後的串級行為相較，當實際生產週期時間介於2.5 天到30 天時，參數重建後
之生產週期時間分布誤差均在0.5 天以內。因此，當進一步應用此分佈配適程序
於製程模擬時，所配適而得的製程生產時間將可提供產品於製程的可能加工時
間，以提供有效的生產模擬。

Using a production plan, production simulation assists users to predict process
outputs for evaluating and adjusting the plan. The simulation efficiency depends on
the correct estimation of the process cycle time for effective prediction. However,
when there are cascaded and various behaviors distributions existed in a process, the
conventional distribution fitting method such as MLE suited for single distribution,
even EM for identical mixture model. Currently, an effective parameter distribution
fitting is needed for various cascaded distributions.
If the distributions from different cascaded distributions combinations are similar
to the fitted distribution, then these cascaded distributed parameters will form a Pareto
front. Therefore, this research proposes a multi-parameters optimal fitting scheme
based on a niche genetic algorithm. Due to a process behavior including message
transmission delay, material waiting time, and actual processing time, let the different
chromosomes representing different distributed parameters evolve in multiple isolated
niches, and adopt the immature protection in the initial stage, the new superseding and
the worst die in the middle stage, the large number law in the final stage, then the
optimal combination of the process multi-parameters is derived.
In fitting result, given 8 cascaded distributed cases, the fitting over rates excess
84%. Using this proposed scheme to analyze 8 different actual process times, the
distributed errors are less than 0.5 days when the actual process cycle times are
between 2.5 to 30 days. Therefore, we also applied the scheme to find the feasible
processing time to simulate the Petri-Nets based processes for find an effective
production outputs.

中文摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與限制 3
1.3 預期結果 3
第二章 理論方法 5
2.1文獻探討 5
2.1.1 最大概似估計法(Maximum Likelihood Method, MLE) 5
2.1.2 期望值最大化法(Expectation Maximization, EM) 6
2.1.3 柏拉最佳前緣(Patero-Optimal Front) 7
2.1.4 小生境基因演算法(Niche Genetic Algorithm, NGA) 8
2.1.5 派區網路(Petri-Net) 10
2.2 提出方法 12
2.2.1 方法程序 13
2.2.2 評估指標 15
2.3 系統架構 16
2.3.1 系統架構 16
2.3.2 資料庫架構與系統關連 17
第三章 案例分析 19
3.1 案例研究 19
3.1.1 案例背景&假設 19
3.1.2 案例研究流程 20
3.2 實驗設計 22
3.2.1 實驗假設 22
3.2.2 實驗結果 23
3.2.3 MLE、EM與NGA配適結果比較 29
3.3實際案例分析 32
3.3.1 實際案例 32
第四章 結論 47
4.1 結論 47
4.2 未來研究方向 47
參考文獻 49

[1] I. J. Myung, “Tutorial on maximum likelihood estimation,” Journal of
Mathematical Psychology, no 47, pp. 90-100, 2003.
[2] A. Thummler, P. Buchholz, and M. Telek, “A Novel Approach for Phase-Type
Fitting with the EM Algorithm,” IEEE Trans. on Dependable and Secure
Computing, vol. 3, no. 3, pp. 245-258, July 2006.
[3] T. Murata, “Petri Net: Properties, Analysis and Applications,” Proceeding of the
IEEE, vol. 77, no. 4, April 1989.
[4] B. Berthomieu and M. Diaz, “Modeling and Verification of Time Dependent
Systems Using Time Petri Nets,” IEEE Transactions on Software Engineering,
vol. 17, no. 3, March 1991.
[5] S. Y. Lin and H. P. Huang, “Modeling and Emulation of a Furnace in IC Fab
Based on Colored-Timed Petri Net,” IEEE Transactions on Semiconductor
Manufacturing, vol.11, no. 3, Aug. 1998.
[6] C. H. Kuo and H. P. Huang, “Distributed Performance Evaluation of a
Controlled IC Fab,” IEEE Transactions on Robotics and Automation, vol. 19, no.
6, Dec. 2003.
[7] J. H. Chen, L. C. Fu, M. H. Lin, and A. C. Huang, “Petri-Net and GA-Based
Approach to Modeling, Scheduling, and Performance Evaluation for Wafer
Fabrication,” IEEE Transactions on Robotics and Automation, vol. 17, no. 5,
Oct. 2001.
[8] M. A. T. Figueiredo and A. K. Jain, “Unsupervised Learning of Finite Mixture
Models,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.
24, no. 3, Mar. 2002
50
[9] J. Horn, N. Nafpliotis, and D. E. Goldberg, “A niched Pareto genetic algorithm
for multi-objective optimization,” in Proc. 1st IEEE Conf. Evolutionary
Computation, vol. 1. pp. 82–87 Piscataway, NJ, June 1994.
[10] J. Horn, “The Nature of Niching: Genetic Algorithms And The Evolution Of
Optimal, Cooperative Populations,” Department of Computer Science,
University of Illinois at Urbana-Champaign 1997.
[11] D J. Cavicchio, “Adaptive Search Using Simulated Evolution,” University of
Michigan, Ann, Arbor 1970.
[12] Samir W. Mahfoud, “Niching Methods for Genetic Algorithms,” University of
Illinois at Urbana-Champaign, 1995
[13] 林明儀，2007，“IC 工程鏈之階段成熟度分析與評估方法”，國立高雄第
一科技大學系統與控制工程研究所碩士論文。
[14] 林嘉俊，2008，“基於可重組派區網路之製程行為變遷預測架構”，國立
高雄第一科技大學系統資訊與控制研究所碩士論文。
[15] 李明林，“小生境遺傳算法綜述”，福州大學機工程學院。