臺灣博碩士論文加值系統

具有共同到期日限制的單機排程問題是一個非常重要的生產排程問題。本研究主要是在探討具有共同到期日限制的單機排程問題，並應如何排序以獲得近似最佳解。此排程問題之績效衡量準則為最小化加權提前及延遲成本。
由於上述問題已被證實為NP-hard之問題，一般最佳解法僅能求解小型問題，大型問題則不但費時且不符合成本效益;因此必須發展較快速且有效的近似解法（Approximation Method），以期能在可接受的時間內求解規模較大之問題。而蟻群系統（Ant Colony System ; ACS）為蟻群最佳化演算法(ACO)當中效果較好的方法，所以以蟻群系統求解CDD問題效果應不差。因此，本研究應用蟻群系統求解單機共同到期日問題。並透過標準題庫問題來測試所提出的演算法，實驗結果顯示本研究提出的演算法所求解的各項問題效果顯著。

Single machine scheduling problem with common due date (CDD) is a very important production scheduling problem. This study focuses on the single machine scheduling problem (SMSP) with common due date (CDD). Objective assessment of the scheduling is total weighted earliness and tardiness minimization.
The SMSP with CDD has been proven to be NP-hard. Exact methods can only solve small-scale problems. Large-scale problems will be time-consuming and cost-ineffective. Hence, it is required to develop a faster and effective approximation method to solve this problem. Ant colony system (ACS) is one of the most effective method among ant colony optimization (ACO) algorithm; hence we propose an ACS based algorithm for the SMSP with CDD. The proposed algorithm was examined on a benchmark problem data set used in earlier studies. The computational results showed that the proposed ACS algorithm is highly effective for this problem.

目錄
誌謝 I
中文摘要 III
英文摘要 IV
目 錄 V
表目錄 Ⅷ
圖目錄 Ⅸ
第一章、導論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 研究問題與限制條件 3
1.3.1 研究問題 3
1.3.2 限制條件 4
1.4 研究流程 5
1.5 論文架構 7
第二章、文獻探討 8
2.1 排程問題之簡述 8
2.1.1 排程問題之分類 8
2.1.2 排程問題求解方法 10
2.2 共同到期日(CDD)排程問題 11
2.3 蟻群最佳化(ACO)演算法 14
2.3.1 ACO演算法相關文獻 15
2.4 蟻群系統(ACS)演算法 18
2.4.1 蟻群系統(ACS)演算法架構 18
第三章、問題定義與研究方法 21
3.1 問題定義 21
3.2 研究方法 23
3.3 演算流程 27
3.4 鄰近搜尋法 30
3.4.1 鄰近搜尋法的定義 30
3.5 求得初始解的步驟 31
3.5.1 GA演算法求解CDD問題的主要演算步驟 31
3.5.2 SA演算法求解CDD問題的主要演算步驟 34
3.6 測試資料庫 35
3.6.1 Biskup and Feldmann所提出的第1個方法 35
3.6.2 Biskup and Feldmann所提出的第2個方法 36
第四章、結果分析 38
4.1 參數設計 38
4.2 初始解與最佳解之比較 39
4.3 ACS演算法與最佳解之比較 40
4.4 ACS演算法與啟發式演算法及初始解之比較 42
4.5 ACS演算法與其他啟發式演算法之比較 45
4.6 小結 46
第五章、結論與建議 50
5.1 結論 50
5.2 未來研究方向與建議 51
參考文獻 52
附錄 詳細測試結果 57
表目錄
表2.1 限制性與非限制性問題複雜度彙總表 13
表2.2 相關文獻彙整表 17
表4.1 初始解與最佳解之比較 39
表4.2 ACS演算法與最佳解之比較 41
表4.3 ACS演算法之求解績效 42
表4.4 改進率彙整表 45
表4.5 各演算法與ACS演算法做成對t檢定 46

圖目錄
圖1.1 研究流程圖 6
圖2.1 ACS演算法流程圖 19
圖3.1 本演算法流程圖 29

參考文獻
英文部分:
[1] Bauer, A., Bullnheimer, B.Hartl, R.F. and Strauss, C.(1999)“Minimizing total tardiness on a single machine using ant colony optimization,”Proceedings of the 1999 Congress on Evolutionary Computation,IEEE Press,pp.1445-1450.
[2] Biskup, and Feldmann. (2001) “Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates,” Computers and Operations Research,28,pp.787-801.
[3] Bullnheimer, B., Hartl, R.F. and Strauss, C. (1999)a “An improved ant system algorithm for the vehicle routing problem,” Annals of Operations Research,89,pp.88-99.
[4] Bullnheimer, B., Hartl, R.F. and Strauss, C. (1999)b “Applying the ant system to the vehicle routing problem,”In:Voss S., Martello S., Osman I.H., Roucairol C.(Eds.). Meta-Heuristics:Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic, Bosten, 1999.
[5] Colorni, A., Dorigo, M., V. and Trubian, M. (1994) “Ant system for job shop scheduling,”Belgian Journal of Operations Research,34,pp.39-53.
[6] Dorigo, M.(1992) “Optimization,learning and natural algorithm,” Ph.D., Thesis, DEI, Politecnico di Milano, Italy.
[7] Dorigo, M. and Gambardella , L.M.(1997)a “Ant colonies for the traveling salesman problem,”Biosystem,43,pp.73-81
[8] Dorigo, M.and Gambardella, L.M.(1997)b “Ant colony system:a cooperative learning approach to the traveling salesman problem,”IEEE Transactions on Evolutionary Computation,1,pp.53-66.
[9] Dorigo, M., Maniezzo, V.and Colorni, A.(1996) “The ant system:optimization by a colony of cooperating agents,” IEEE Transactions on System,26,pp.1-13.
[10] Feldmann, M. and Biskup, D. (2003) “Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches,” Computers and Industrial Engineering,44,pp.307-323.
[11] Gambardella, L.M., Taillard, E. and Dorigo, M. (1999) “Ant colonies for the quadratic assignment problem,” Journal of Operational Research Society,50,pp.167-176.
[12] Hao, Q., Yang, Z., Wang, D. and Li Z., (1996) “Common due-date determination and sequencing using tabu search,” Computers and Operations Research,23,pp.409-417.
[13] Hall, N.G., Posner, M.E., (1991). “Earliness-tardiness scheduling problems, I:Weighted deviation of completion times about a common due date,” Operations Research,39,pp.836-846.
[14] Hino, C.M., Ronconi, D.P.,and Mendes, A.B. (2005) “Minimizing earliness and tardiness penalties in a single-machine problem with a common due date,” European Journal of Operational Research,160,pp.190-201.
[15] Hung, K.S., Su, S.F., and Lee,Z.J. “A Dynamic Updating Rule for Heuristic Parameters Based on Entropy in Ant Colony Optimization,”
[16] Kanet, J.J., (1981). “Minimizing the average deviation of job completion times about a common due date,” Naval Research Logistics Quarterly,28,pp.643-651.
[17] Kuntz, P., and Snyers, D. (1997) “Emergent colonization and graph partitioning,”Proceedings of the 3th International Conference on Simulation of Adaptive Behavior:From Animals to Animates,3,The MIT Press,Cambridge,MA.
[18] Kuntz, P., Layzell, P. and Snyers, D, (1997) “A colony of ant-like agents for partitioning in VLSI technology,” Proceedings of the 4th European Conference on Artificial Life,The MIT Press,Cambridge,MA.
[19] Lin, S.W., Chou, S.Y., and Ying, K.C. (2007) “A sequential exchange approach for minimizing earliness-tardiness penalties of single-machine scheduling with a common due date,” European Journal of Operational Search,177,pp.1294-1301.
[20] Maniezzo, V. and Colorni, A. (1999) “The ant system applied to quadratic assignment problem,” IEEE Transactions on Knowledge and Data Engineering,11,pp.769-784.
[21] Mellor, P., (1966) “A review of job shop scheduling,” Operational Research Quarterly,vol.17,No.2,pp.161-170
[22] O uz Ceyda, Lin, Bertrand M,T., Edwin Cheng, T. C.. (1997) “Two-stage flowshop scheduling with a common second-stage machine.”Computer & Operations Research,24,pp.1169-1174.
[23] Roux Olivier, Fonlupt Cyril, Talbi El-Ghazali, Robilliard Denis, (1999) “ANTabu-enhanced version.”LIL-99-1.
[24] Sivrikaya-Serifoglu, F. and Ulusoy, G. (2004) “Multiprocessor task scheduling in multistage hybrid flow-shops:a genetic algorithm approach.” Operational Research Society,55,pp.504-512.
[25] Song, Y.H. and Chou, C.S. (1998) “Application of ant colony search algorithms in power system optimization,” IEEE Power Engineering Review,18,pp.63-78.
[26] Stützle Thomas and Hoos. H.H. (2000) “MAX MIN Ant System,” Journal of Future Generation Computer Systems,16,pp.889-914.
[27] Stützle, Thomas (1997) “An Ant Approach to the Flow Shop Problem,”
[28] T’kindt, V., Monmarché, N., Tercinet, F. and Laügt, D. (2002) “An ant colony optimization algorithm to solve a
2-machine bicriteria flowshop scheduling problem,” European Journal of Operational Research,42,pp.250-257.
[29] Tony White and Bernard Pagurek and Franz Oppacher. (1998)
“{ASGA}:Improving the Ant System by Integration with Genetic Algorithms,” Genetic Programming 1998:Proceedings of the Third Annual Conference, month 22-25, Morgan Kaufmann, University of Wisconsin, Madison, Wisconsin,USA,pp.610-617.
[30] Ying, K.C. (2003) “Ant Colony System for Solving Scheduling Problems”doctoral dissertation,National Taiwan University of Science and Technology.
[31] Zwaan S. van der and Marques. C. (1999) “Ant Colony Optimisation for Job Shop Scheduling,” Proceedings of the Third Workshop on Genetic Algorithms and Artificial Life(GAAL 99).




中文部分:
[1] 江朋南 (2003) “蟻族系統在零工型排程問題之應用”,國立台灣科技大學工業管理系碩士論文.
[2] 鍾承志 (2004) “多目標零工式平行機台排程之研究-應用蟻群最佳化演算法”,東海大學工業工程與經營資訊學系碩士論文.
[3] 廖顯明 (2005) “蟻群系統在混合式流程型工廠排程問題之應用”,華梵大學工業工程與經營資訊學系碩士論文.
[4] 王峙淳 (2006) “應用RBS演算法求解單機排程問題”,華梵大學工業工程與經營資訊學系碩士論文.