臺灣博碩士論文加值系統

蟻拓尋優法是仿自然界中螞蟻尋找出發點至目標物之間路徑的方式，以求解最佳化問題。螞蟻在走過的路徑上會留下費洛蒙，並依循著強度最強的費洛蒙尋找路徑。蟻拓尋優法的特色是，每批次求解時能依尋先前所得較佳的結果繼續進行最佳解搜尋，讓後來的試驗能得到更好的結果。本研究在於運用蟻拓尋優法的手法，求解生產排程問題。典型的零工式生產排程問題只能求解序鏈型態的加工順序關係。為了更能應用於真實加工型態，本研究建構了擴充式零工生產排程問題。除了能定義更複雜的樹狀加工步驟順序結構外，每個加工步驟更能由多部加工機器執行，因此排程問題同時納入了加工步驟的機器選擇。
本研究並進一步設計及建構能求解擴充式零工生產排程問題的蟻拓尋優法為基的排程器，簡稱為ACOBEJS。系統開發採用Microsoft Visual Basic 6.0語言實作ACOBEJS，並在Microsoft Windows 2000作業系統下執行。本研究使用ACOBEJS求解典型零工式生產排程問題的標竿問題並與其他研究結果比較，結果顯示ACOBEJS的求解品質有小幅的改善。擴充式零工生產排程問題則採用自行設計的範例作試驗並與分析結果。

Ant Colony Optimization（ACO）is the method to solve optimization problem by imitating the real ants’ behavior that find out the way from the starting point to the destination. Each ant drops the pheromone behind on the way, and then the successors follow the way with the most pheromone. The characteristic of ACO is that each test will keep the good solution previously and try to find the better one.
This research tried to solve the job shop scheduling problem using ACO. There are a lot of kinds of type in job shop scheduling problem. The classical job shop scheduling problem can only model the operations sequencing in the chain structure. While this research constructed an extended job shop scheduling problem to model the operations sequencing in the tree structure and consider the selection of several non-identical parallel machines. Furthermore, we design an Ant Colony Optimization based extended job shop scheduler（ACOBEJS）, used Microsoft Visual Basic 6.0 to implement, and ran under the operation system of Microsoft Windows 2000. For classical job shop scheduling problems, the results of solving some benchmarks using ACOBEJS are better then other researches. For extended job shop scheduling problems, we used examples designed by ourself to solve and analyze.

第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範疇 4
1.4 論文架構 4
第二章 文獻探討 5
2.1 蟻拓尋優法 5
2.1.1 螞蟻尋找目標的行為探討 5
2.1.2 蟻拓尋優法的演進 8
2.1.2.1 螞蟻系統（Ant System） 9
2.1.2.2 Ant-Q 12
2.1.2.3 AS rank 15
2.1.2.4 蟻拓法（Ant Colont System） 17
2.1.2.5 MMAS（MAX-MIN Ant System） 19
2.1.2.6 AntNet 19
2.1.2.7 平行運算的螞蟻系統 21
2.1.2.8 蟻拓尋優巨集啟發式演算法(ACO Meta-Heuristic)與蟻拓尋優法（ACO） 22
2.2 蟻拓尋優法的應用 26
2.2.1 旅行銷售員問題（traveling salesman problem）26
2.2.2 二次指派問題（quadratic assignment problem 30
2.2.3 排程問題（scheduling problem） 33
2.2.4 網路途程問題（network routing problem） 36
2.2.5 著色問題（graph coloring problem） 38
2.2.6 排序問題（sequential ordering problem） 39
2.2.7 車輛途程問題（vehicle routing problem） 40
2.3 零工式生產排程問題 42
2.3.1 典型零工式生產排程問題的簡介 42
2.3.2 求解零工式生產排程問題的方法 42
2.3.2.1 數學解析法（Mathematical analysis) 43
2.3.2.2 模擬法（Simulation） 43
2.3.2.3 派工法則（Dispatching rule） 43
2.3.2.4 區域性搜尋法（Local search） 44
第三章 蟻拓尋優法為基之零工式生產排程系統 46
3.1 零工式生產排程問題的探討 46
3.1.1零工式生產排程問題模式的描述 46
3.1.2 典型零工式生產排程問題限制的探討 51
3.1.3 擴充式零工生產排程問題 57
3.2 蟻拓尋優法求解擴充式零工生產排程問題的概念 62
3.2.1 ACOBEJS運作的概念 62
3.2.2 導入ACOBEJS求解零工式生產排程問題的系統架 65
3.2.3 ACOBEJS的系統流程 68
3.3 ACOBEJS系統的資料結構 70
3.3.1 描述ACOBEJS所使用的數學模式 71
3.3.2 零工式生產排程問題相關的資料結構 72
3.3.3 ACOBEJS系統運作使用的資料結構 74
3.4 ACOBEJS演算法的內容細節 76
3.4.1螞蟻實作的細節 76
3.4.2 派工法則（dispatching rule）的選取 80
3.4.3 仲裁者實作的細節 86
3.5 ACOBEJS與AS-JSP的不同 87
第四章 ACOBEJS求解效能分析及排程實例驗證 89
4.1 ACOBEJS系統的設定 89
4.1.1 ACOBEJS系統執行參數的設定 89
4.1.2 ACOBEJS螞蟻求解過程分析 91
4.1.3 避免求解效率便差及品質下降的改善機制 97
4.2 零工式生產排程問題實例驗證 98
4.2.1 典型零工式生產排程問題的測試 98
4.2.2 （具多重機器選擇條件）擴充式零工生產排程問題測101
4.2.3 具樹狀結構順序限制的擴充零工生產排程問題測試109
第五章 結論與未來展望 115
5.1 結論 115
5.2 後續研究建議 115
參考文獻 117

Bauer, A., Bullnheimer, B., Hartl, R.F., Strauss, C., 1999, “Ant Colony Optimization Approach for the Single Machine Total Tardiness Problem”, Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, Piscataway, NJ, pp. 1445-1450.
Blum, C., 2002, “ACO Applied to Group Shop Scheduling: A case study on Intensification and Diversification,” Proceedings of the 3rd International Workshop on Ant Algorithms.
Blum, C. and Sampels, M., 2002, “Ant Colony Optimization for FOP Shop scheduling: A case study on different pheromone representations,” Technical report TR/IRIDIA/2002-3, IRIDIA, Université Libre de Bruxelles, Belgium.
Bullnheimer, B., Hartl, R. F., Strauss, C., 1997, “An Improved Ant System Alorithm for the Vehicle Routing Problem,” Technical Report POM-10/97, Institute of Management Science, University of Vienna, Austria, Annals Operational Research.
Bullnheimer, B., Hartl, R. F., Strauss, C., 1997, “An New Rank baseed Version of the Ant System: A Computational Study,” Technical report POM 3/97, Institute of Management Science, University of Vienna, Austria.
Bullnheimer, B., Hartl, R. F., Strauss, C., 1999, “An New Rank-based Version of the Ant System: A Computational Study,” Central European Journal Operational Research Economics 7(1), pp. 25-38.
Bullnheimer, B., Kotsis, G., Strauss, C., 1997, “Parallelization strategies for the ant system,” Technical report POM 9/97, Institute of Management Science, University of Vienna, Austria.
Caro, G. D. and Dorigo, M., 1997,” AntNet: A Mobile Agents Approach to Adaptive Routing,” Technical Report IRIDIA/97-12, Université Libre de Bruxelles, Belgium.
Caro, G. D. and Dorigo, M., 1998, “AntNet: Distributed Stigmergetic Control for communication networks,” Journal of Artificial Intelligence Research 9, pp. 317-365.
Caro, G. D. and Dorigo, M., 1998, “Mobile Agents for Adaptive Routing,” Proceedings of the 31st Hawaii Internal Conference on system, IEEE Computer Society Press, Los Alamitos, CA, pp.74-83.
Colorni, A., Dorigo, M., Maffioli, F., Maniezzo, V., Trubian M., 1994, “Ant system for Job Shop Scheduling,” JORBEL Belgian Journal of Operation Research, Statistics and Computer Science, Vol. 34, pp. 39-53.
Colorni, A., Dorigo, M., Maffioli, F., Maniezzo, V., Righini, G., Trubian, M., 1997, “Heuristic from Nature for Hard Combinatorial Optimization Problems,” Published in International Transaction in Operational Research, 3, 1, pp. 1-21.
Colorni, A., Dorigo, M., Maniezzo, V., 1991, “Distributed Optimization by Ant Colonies,” Proceedings of the First European Conference on Artificial Life, Paris, France, December 11-13.
Colorni, A., Dorigo, M., Maniezzo, V., 1992, “An Investigation of Some Properties of an Ant Algorithm,” Proceedings of the Parallel Problem Solving from Nature Conference, Brussels, Belgium, R.Männer and B.Manderick (Eds.), Elseriver Publishing, pp. 509-520.
Costa, D. and Hertz, A., 1997, “Ants Can Colour Graphs,” Journal of the Operational Research Society, Vol.48, pp. 295-305.
Dorigo, M. and Caro, G. D., 1999, “Ant Colony Optimization: A New Meta-Heuristic”, Evolutionary Computation, 1999 CEC 99 Proceedings of the 1999 Congres, Vol. 2, pp. 1470 —1477.
Dorigo, M., Caro, G. D., Gambardella, L. M., 1999, “Ant Algorithm for Discrete Optimization,” Artificial Life, Vol. 3, pp. 137-172.
Dorigo, M. and Gambardella, L.M., 1996, “A Study of Some Properties of Ant-Q,” Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature, September, pp. 22-27.
Dorigo, M., Maniezzo, V., Colorni, A., 1996, “The Ant System: Optimization by A Colony of Cooperating Agents,” IEEE transactions on System, Man, and Cybernetics-Part B, Vol.26, No.1, pp.1-13.
Dorigo, M. and Maria L., 1997, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, vol.1, no. 1.
Dorigo, M., Maniezzo, V., Colorni, A., 1991, “Positive Feedback as A Search Strategy”, Technical Report No. 91-016, Politecnico di Milano, Italy
Gambardella, L.M. and Dorigo, M., 1995, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem,” Proceedings of the 12th International Conference on Machine Learning, ML-95, Morgan Kaufmann, Palo Alto, CA.
Gambardella, L. M. and Dorigo, M., 1996, “Solving Symmetric and Asymmetric TSPs by Ant Colonies,” Proceedings of the IEEE Conference on Evolutionary Computation, ICEC’96, IEEE Press, New York, pp. 622-627.
Gambardella, L.M. and Dorigo, M., 1997, “HAS-SOP: An Hybrid Ant System for the Sequential Ordering Problem,” Technical Report IDSIA-11-97, IDSIA, Lugano, Switzerland.
Gambardella, L.M., Taillard, E., Dorigo, M., 1999, “Ant Colonies for the Quadratic Assignment Problem,” Journal of the Operational Research Society 50, pp. 167-176.
Gambardella, L.M., Taillard, E., Agazzi, G., 1999, “MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows,” D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization. McGraw-Hill, UK, pp. 63-76.
Gould, L. S., 1998, “Introduction APS: Getting Production in Lock Step with Customer Demand,” Automotive Manufacturing & Production, pp. 54-58.
Hillier, F. S. and Lieberman, G. J., 1999, Introduction To Operations Research, McGraw Hill.
Holldobler, B. and Wilson, E. O., 1994, Journey to the Ants：A Story of scientific exploration, Harvard University Press.
i2, RHYTHM Factory Planner User Manual
i2, TradeMatrix Factory Planner White Paper
Maniezzo, V., 1998, “Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem,” Technical Report CSR 98-1, C. L. in Scienze dell’Informazion.
Maniezzo, V. and Colorni, A., 1999, “The Ant System Applied to the Quadratic Assignment Problem,” IEEE Transactions on Knowledge and Data Engineering, to appear.
Maniezzo, V., Colorni, A., Dorigo, M., 1994, “The Ant System Applied to the Quadratic Assignment Problem,” Tecnical Report IRIDIA/94-28, Université Libre de Bruxelles, Belgium.
Moustakas, C., 1990, Heuristic Research: Design, Methodology, and Applications, Addison Wesley.
Pearl, J., 1984, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison Wesley.
Pinedo, M., 1995, Scheduling: Theory, Algorithms, and Systems, Prentice Hill.
Schoonderwoerd, R., Holland, O., Bruten, J., 1997, “Ant-like Agents for Load Balancing in Telecommunications Networks,” Proceedings of Agents''97, Marina del Rey, CA, ACM Press, 209-216.
Schoonderwoerd, R., Holland, O., Bruten, J., Rothkrantz, L., 1997, “Ant-based Load Balancing in Telecommunications Networks”, Adaptive Behavior, 5(2) pp. 169-207.
Smith, V. J. R., 1996, Modern Heuristic Search Methods, Wiley.
Stevenson, W. J., 1999, Production/Operations Management, McGraw Hill.
Stützle, T. 1997, “MAX-MIN Ant System for the Quadratic Assignment Problem”, Technical Report AIDA-97-04, Darmstadt University of Technology, Computer Science Department, Intellectics Group.
Stützle, T., 1998, “An Ant Approach to the Flow Shop Problem,” Proceedings of EUFIT''98, Aachen, pp. 1560-1564.
Stützle, T., 1998, “Parallelization strategies for ant colony optimization,” Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, pp. 722-731.
Stützle, T. and Hoos, H., 1997, “Improvements on the Ant System: Introducing the MAX-MIN Ant System”, ICANNGA97 - Third International Conference on Artificial Neural Networks and Genetic Algorithms, University of East Anglia, Norwich, UK, Wien: Springer Verlag.
Stützle, T. and Hoos, H., 1997, “The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem”, Proceedings of ICEC''97 - 1997 IEEE 4th International Conference on Evolutionary Computation, IEEE Press, pp. 308-313.
Stützle, T., Hoos H., 1997, “The MAX-MIN Ant System and local Search for Combinatorial Optimization Problems: Towards Adaptive Tools for Global Optimization,” 2nd Metaheuristics International Conference (MIC-97), Sophia-Antipolis, France - July pp. 21-24.
Stützle, T. and Hoos, H., 2000, “MAX-MIN Ant System,” Future Generation Computer Systems Journal 16(8) pp. 889-914.
Stützle, T. and Dorigo, M., 1999, “ACO Algorithms for the Traveling Salesman Problem,” In K. Miettinen, M. Makela, P. Neittaanmaki, J. Periaux, editors, Evolutionary Algorithms in Engineering and Computer Science, Wiley, Chichester, UK.
Taillard, É. D. and Gambardella, L. M., 1997, “Adaptive Memories for the Quadratic Assignment Problem,” Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland.
Taillard, É. D. and Gambardella, L. M., 1997, “An Ant Approach for Structured Quadratic Assignment Problems,” 2nd Metaheuristics International Conference (MIC-97), Sophia-Antipolis, France — July, pp. 21-24.
VoB, S., Martello, S., Osman, I. H., Roucairol, C., 1999, Meta-Heuristics：Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers.
White, T., Pagurek, B., Oppacher, F., 1998, “Connection Management using Adaptive Mobile Agents,” Proceedings of 1998 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA''98).
Yu, I. K., Chou, C.S., Song, Y. H. 1998, “Application of the Ant Colony Search Algorithm to Short-term Generation Scheduling Problem of Thermal Units,” Power System Technology, Proceedings. POWERCON 98. 1998 International Conference on, Vol. 1, pp. 552-556.
Zwaan, S. V. D. and Marques, C., 1999, “Ant Colony Optimisation for Job Shop Scheduling,” Proceedings of the Third Workshop on Genetic Algorithms and Artificial Life (GAAL 99).