臺灣博碩士論文加值系統

在競爭激烈的大環境下，生產製造業該如何有效率地管理生產排程，保有其競爭力與優勢，已經成為刻不容緩的議題。然而，因為實際生產排程中存在許多的不確定性，所以，近幾年來已經有許多學者從事有關模糊排程之研究。
在本論文中，我們提出模糊-基因演算法，以研究有關單機排程問題，目標為使總加權完工時間最小，且考慮模糊處理時間。模糊-基因演算法為一個基於基因演算法與模糊理論之方法。工作處理時間以梯形模糊數的型式表示，並利用基因演算法協助我們尋找最佳的生產排序。此外，我們使用VBA程式語言與Evolver實作排程問題的模型。
我們從OR-library排程問題的加權延後問題中，選取40個工作數之問題共125個問題作測試。根據實驗的結果顯示，模糊-基因演算法可以搜尋出一組使可能與必要最佳之程度最大化，並同時使模糊總加權完工時間趨近最小化之排序，且平均改善率高達38.09%，所需的執行時間僅為數分鐘。

It is an imperious issue to efficiently manage the production scheduling for the production manufacturing industries. The results help them to hold the competitiveness and advantage in the extremely competitive environment. Nowadays, many scholars devote themselves to the research of the fuzzy scheduling in recent few years because this issue exits many uncertainties in the real production scheduling.
This thesis presents a Fuzzy-Genetic Algorithm (FGA) to solve the single machine scheduling problems for minimizing the total weighted completion time while considering the uncertain processing time. The FGA method is based on the genetic algorithm and fuzzy theory. The processing time can be represented by a trapeziod fuzzy number. Here the genetic algorithm is applied to find a best solution for processing sequence. In addition, VBA programming language and Evolver are integrated to realize the model for the scheduling problems.
In the experiments, 125 test examples of 40 jobs scheduling problems with the weighted tardiness are acquired from the OR-library. According to the experimental results, the FGA can perform the search to find a schedule of maximizing the degrees of possible and necessary optimality while minimizing the fuzzy total weighted completion time within a few minutes. Also, the average improvement rate is 38.09%.

摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究限制 4
1.4 研究方法 4
1.5 研究流程 5
1.6 論文架構 6
第二章 文獻回顧 7
2.1 排程理論 7
2.1.1 排程問題之分類 8
2.1.2 排程問題之解法 12
2.2 模糊理論於生產排程上之應用 13
2.3 基因演算法於生產排程上之應用 24
第三章 研究方法 28
3.1 模糊理論 28
3.1.1 模糊集合 29
3.1.2 模糊數 29
3.1.3 模糊數之運算 32
3.1.4 解模糊化 33
3.1.5 模糊數之可能性與必要性 33
3.2 可能與必要最佳排序之觀念 34
3.3 可能與必要最佳程度之計算 39
3.3.1 典型單機排程問題以總加權完工時間最小為目標( ) 40
3.3.2 問題考慮模糊處理時間之可能最佳 41
3.3.3 問題考慮模糊處理時間之必要最佳 42
3.4 基因演算法 44
3.4.1 基因演算法的運算流程 45
3.5 衡量指標 47
3.6 模糊-基因演算法之流程 48
第四章 實驗分析 50
4.1 問題資料處理與計算 50
4.2 Evolver軟體簡介 55
4.3 問題測試結果 55
4.4 結果分析與比較 65
第五章 結論與建議 79
5.1 結論 79
5.2 建議 80
中文參考文獻 81
英文參考文獻 84

中文參考文獻
李允中、王小璠、蘇木春（2003），模糊理論及其應用，全華科技圖書股份有限公司。
賴郁玲(2005)，以基因演算法求解最少延遲工作數下總延遲時間最小化之單機排程問題，南台科技大學工業管理研究所碩士論文。
施智懷(2004)，具動態權重之混合基因演算法求解順序相依整備時間下單機排程問題之研究，華梵大學資訊管理研究所碩士論文。
賴榮耀(1991)，模糊綜合評判模式在訂單組裝型主生產排程技術之應用，國立交通大學資訊管理研究所碩士論文。
莊宗南(1996)，模糊理論於流程排程之應用，高雄工學院管理科學系研究所碩士論文。
呂宜修(1996)，模糊排程參數之研究及以模糊數學為基礎縮減可行解集合之新式演算法，國立台灣工業技術學院管理技術研究所碩士論文。
宋敏如(1997)，應用模糊集合方法於研發專案排程之探討，逢甲大學工業工程研究所碩士論文。
陳安亭(1997)，專案工程模糊排程最適化求解之探討，國立台灣科技大學營建工程技術研究所碩士論文。
胡志德(1997)，單機排程模糊演算法，東海大學工業工程研究所碩士論文，1997。
吳景福(1997)，啟發式排程模糊演算法-以工作為導向之研究，東海大學工業工程研究碩士論文。
羅友廷(1998)，模糊多目標混合式遺傳演算法在零工式排程系統之應用，東海大學工業工程學系研究所碩士論文。
翁佳麟(2000)，模糊多目標混合灰色關聯之零工式工作導向啟發排程系統，國立台北科技大學生產系統工程與管理研究所碩士論文。
謝忠志(2000)，DBR現場排程及管理決策支援系統之建構-運用基因演算法及模糊理論，國立台北科技大學生產系統工程與管理研究所碩士論文。
莊宗南(2001)，模糊零工式排程之研究，國立成功大學企業管理系研究所碩士論文。
詹蕙珍(2003)，模糊多目標非線性規劃在有限資源多專案排程問題之應用，屏東科技大學工業管理系研究所碩士論文。
王憲盟(2003)，探討模糊排程問題之過早性與延遲性，暨南國際大學資訊管理學系碩士論文。
吳光耀(2003)，最佳排列問題與模糊線性規劃之研究及其在主生產排程案例之應用，國立清華大學工業工程與工程管理學系研究所碩士論文。
彭心慈(2004)，模糊理論應用在研發專案組合選擇與排程，逢甲大學工業工程與系統管理學研究所碩士論文。
趙文涼(2000)，基因演算法於單機交期絕對偏差及整備成本最小化排程問題之應用，元智大學工業工程研究所碩士論文。
劉政偉(2005)，非正規型單機排程問題之基因演算法，義守大學工業工程與管理學系碩士班碩士論文。

英文參考文獻
Potts, C.N. and Van Wassenhove, L.N. (1982). “Decomposition algorithm for the single machine total tardiness problem,” Operation Research Letters, 1, pp.177–181.
Webster, S. and Baker, K.R. (1995). “Scheduling groups of jobs on a single machine,” Operations Research, 43, pp.692–703.
Cheng, T.C.E. and Sin, C.C.S. (1990). “State-of-the-art review of parallel-machine scheduling research,” European Journal of Operational Research, 47, pp.271–292.
Ovacik, I.M. and Uzsoy, R. (1995). “Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times,” International Journal of Production Research, 33, pp.3173–3192.
Taillard, E. (1990). “Some efficient heuristic methods for the flow shop sequencing problem,” European Journal of Operational Research, 47, pp.65–74.
Gupta, J.N.D. and Stafford Jr., E.F. (2006). “Flowshop scheduling research after five decades,” European Journal of Operational Research, 169, pp.699–711.
Adams, J., Balas, E., and Zawack, D. (1988). “Shifting bottleneck procedure for job shop scheduling,” Management Science, 34, pp.391–401.
Applegate, D. and Cook, W. (1991). “Computational study of the job-shop scheduling problem,” ORSA Journal on Computing, 3, pp.149–156.
Gonzalez, T. and Sahni, S. (1976). “Open shop scheduling to minimize finish time,” Journal of The Association Computing Machinary, 23, pp.665–679.
Sevastianov, S.V. and Woeginger, G.J. (1998). “Makespan minimization in open shops: A polynomial time approximation scheme,” Mathematical Programming, Series B, 82, pp.191–198.
Chanas, S. and Kasperski, A. (2001). “Minimizing maximum lateness in a single machine scheduling problem with fuzzy processing times and fuzzy due dates,” Engineering Applications of Artificial Intelligence, 14, pp.377–386.
Wang, C., Wang D., Ip, W.H., and Yuen, D.W. (2002). “The single machine ready time scheduling problem with fuzzy processing times,” Fuzzy Sets and Systems, 127, pp.117-129.
Chanas, S. and Kasperski, A. (2004). “Possible and necessary optimality of solutions in the single machine scheduling problem with fuzzy parameters,” Fuzzy Sets and Systems, 142, pp.359–371.
Ishibuchi, H., Yamamoto, N., Murata, T., and Tanaka, H. (1994). “Genetic algorithms and neighborhood search algorithms for fuzzy flowshop scheduling problems,” Fuzzy Sets and Systems, 67, pp.81-100.
Ishibuchi, H., Murata, T., and Lee, K.H. (1996). “Formulation of Fuzzy Flowshop Scheduling Problems with Fuzzy Processing Time,” IEEE International Conference on Fuzzy Systems, 1, pp.199-205.
Cheng, J., Kise H., and Matsumoto, H. (1997). “A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem,” European Journal of Operational Research, 96, pp.578-590.
Kuroda, M. and Wang, Z.(1996). “Fuzzy job shop scheduling,” International Journal of Production Economics, 44, pp.45-51.
Sakawa, M. and Mori, T.(1999). “An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate,” Computers and Industrial Engineering, 36, pp.325-341.
Young, Y.S. (2002). “Genetic algorithm with fuzzy logic controller for preemptive and non-preemptive job-shop scheduling problems,” Computers and Industrial Engineering, 43, pp.623-644.
Lee, J., Tim, A., and Yen, J. (1994). “A Fuzzy Rule-Based Approach to Real-Time Scheduling,” IEEE International Conference on Fuzzy Systems, 2, pp.1394-1399.
Chan, F.T.S., Chan, H.K., and Kazerooni, A. (1994). “Real time fuzzy scheduling rules in FMS,” Journal of Intelligent Manufacturing, 14, pp.341-350.
Litoiu, M. and Tadei, R. (2001). “Real-time task scheduling with fuzzy deadlines and processing times,” Fuzzy Sets and Systems, 117, pp.35-45.
Turksen, I.B. (1995). “Knowledge representation and approximate reasoning with type II fuzzy sets,” IEEE International Conference on Fuzzy Systems, 4, pp.1911-1917.
Turksen, I.B. (1999). “Type I and type II fuzzy system modeling,” Fuzzy Sets and Systems, 106, pp.11-34.
Liu, J. and Tang, L. (1999). “Modified genetic algorithm for single machine scheduling,” Computers and Industrial Engineering, 37, pp.43-46.
Armentano, V.A. and Mazzini, R. (2000). “A genetic algorithm for scheduling on a single machine with set-up times and due dates,” Production Planning and Control, 11, pp.713-720.
Sevaux, M. and Dauzere-Peres, S. (2003). “Genetic algorithms to minimize the weighted number of late jobs on a single machine,” European Journal of Operational Research, 151, pp.296-306.
L.A. Zadeh (1965). “Fuzzy sets,” Information and Control, 8, pp.338-353.
OR-library (http://people.brunel.ac.uk/~mastjjb/jeb/info.html)