排程問題已被研究了好幾十年，而常見的組合最佳化排程問題(combinatorial optimization scheduling problem)又多為NP-Hard問題，因此除了最佳化演算法的研究外，應用啟發式演算法以及演化式演算法求解排程問題的研究也不斷的被提出。

蟻族最佳化(Ant Colony Optimization，ACO)演算法是一種新的演化式演算法，常被用來求解困難的組合最佳化問題，自從Marco Dorigo成功利用螞蟻系統(Ant System)求解旅行銷售員問題後，也吸引了許多研究人員進行相關的研究，如在組合最佳化排程問題方面，可見到單機、流程型以及零工型等排程問題的應用。本研究針對蟻族系統的費洛蒙更新規則進行修改，並增加跳脫局部最佳解的機制，而提出一個新的具跳脫機制之蟻族最佳化演算法，並用來求解常見的排程問題，如單機總延遲時間問題、流程型排程問題之總完工時間最小化以及零工型排程問題之總完工時間最小化等問題，以證明本研究提出之演算法的效率。

具跳脫機制之蟻族最佳化演算法除了在局部費洛蒙更新作了修改外，另外也增加了以求解品質優劣為基的費洛蒙增減策略，而當螞蟻建構解的行為陷入停滯狀態時，演算法即開始進行跳脫局部最佳解的機制，其包括了探索比例變更策略以及費洛蒙重置策略等機制，經實例驗證發現本研究提出的具跳脫機制之蟻族最佳化演算法在三個排程問題中，能使用較少的螞蟻數，而得到求解品質更好或相同的結果。

Scheduling problems have been studied for decades, and almost all of the combinatorial optimization scheduling problems have been proved to be NP-Hard problems. Thus, the researches of scheduling problems solved by heuristic algorithms and evolutionary algorithms have been presented continuously except of optimization algorithms.

Ant Colony Optimization (ACO) is a novel evolutionary algorithm and is often used to solve difficult combinatorial optimization problems. Since Marco Dorigo successfully used Ant System to solve Traveling Salesman Problem, ACO has attracted many researchers to proceed with related researches. For example, we can find the applications in combinatorial optimization scheduling problems, such as the single machine scheduling problem, the flow shop scheduling problem, and the job shop scheduling problem. In this thesis, we propose a novel Ant Colony Optimization method based on an escaping mechanism which modifies the pheromone trail updating rules and adds an escaping mechanism to escape a local optimum solution. We also use the proposed algorithm to solve the single machine total weighted tardiness problem, the flow shop scheduling problem with minimizing makespan, and the job shop scheduling problem with minimizing makespan. Compared with the past algorithms, the algorithm we proposed can solve these scheduling problems with less artificial ants and the solution qualities we gained are better or the same.

[1] T. S. Abdul-Razaq, C. N. Potts, L.N Van Wassenhove, “A survey of algorithms for the single machine total weighted tardiness scheduling problem,” Discrete Applied Mathematics, vol. 26, pp. 235-253, 1990.

[2] J. Adams, E. Balas, D. Zawack, “The shifting bottleneck procedure for job shop scheduling,” Management Science, vol. 34, pp. 391-401, 1988.

[3] D. Alcaide, J. Sicilia, D. Vigo, “Heuristic approach for minimum makespan open shop problem,” Journal of the Spanish Operational Research Society, vol. 5, pp.283-296, 1997.

[4] A. Bauer, B. Bullnheimer, R. F. Hartl, C. Strauss, “Minimizing total tardiness on a single machine using ant colony optimization,” Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, pp.1445-1450, 1999.

[5] B. Bullnheimer, R.F. Hartl, “A New Rank Based Version of the Ant System – A Computational Study,” Central European Journal of Operations Research, vol. 7, pp. 25-38, 1999.

[6] A.-D. Belarmino, “An SA/TS mixture algorithm for the scheduling tardiness problem,” European Journal of Operation Research, vol. 88, pp. 516-524, 1996.

[7] M. den Bensten, T. Stützle , M. Dorigo, “Ant Colony Optimization for the Total Weighted Tardiness Problem,” Lecture Notes In Computer Science Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, pp. 611-620, 2000.

[8] M. Ben-Daya, M. Al Fawzan, “A tabu search approach for the flow shop scheduling problem,” European Journal of Operation Research, vol. 109, pp.88-95, 1998.

[9] P. Brucker, J. Hurink, B. Jurish, B.Wostmann, “A branch and bound algorithm for the open shop problem,” Discrete Applied Mathematics, vol. 76, pp. 43-59, 1997.

[10] B. Bullnheimer, R.F. Hartl, C. Strauss, “An improved Ant System algorithm for the Vehicle Routing Problem,” Annals of Operations Research, vol. 89, pp.319-328, 1999.

[11] J. Carlier, E. Pinson, “An algorithm for solving the job-shop problem,” Management Science, vol. 35, pp. 164-176, 1989.

[12] A. Colorni, M. Dorigo, V. Maniezzo, M. Trubian, “Ant system for job shop scheduling,” Belgian Journal of Operations Research, vol. 34, pp. 39-53,1994.

[13] F. Corno, M. S. Reorda, and G. Squillero, “The Selfish Gene Algorithm: a new Evolutionary Optimization Strategy,” SAC98: 13th Annual ACM Symposium on Applied Computing, Atlanta, Georgia (USA), pp. 349-355, 1998.

[14] D. Costa, A. Hertz, “Ants can color graphs,” Journal of the Operational Research Society, vol. 48, pp. 295–305, 1997.

[15] H. A. J. Crauwels, C. N. Potts, L. N. Wassenhove, “Local search heuristics for the single machine total wighted tardiness scheduling problem,” INFORMS Journal on Computing, vol. 10, pp. 341-350, 1998.

[16] M. Dorigo, V. Maniezzo, A. Colorni, “Ant System: Optimization by a Colony of Cooperating Agents,” IEEE transactions on systems, man, and cybernetics-part B, vol. 26, pp. 29-41, 1996.

[17] H. L. Fang, P. Ross, D. Corne, “A promising hybrid GA/heuristic approach for open-shop scheduling problem,” A. cohn (Ed.) Proceeding of ECAI 94, 11th European Conference on Artificial Intelligence, pp. 590-594, 1994.

[18] L. M. Gambardella, M. Dorigo, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem,” Proceeding of ML-95, Twelfth International Conference on Machine Learning, Morgan Kaufmann, pp. 252-260, 1995.

[19] L. M. Gambardella, M. Dorigo, “Solving symmetric and asymmetric TSPs by ant colonies,” Evolutionary Computation, Proceedings of IEEE International Conference, pp. 622-627, 1996.

[20] L. M. Gambardella, E. Taillard, M. Dorigo, “Ant colonies for the quadratic assignment problem,” Journal of Operational Research Society, vol. 50, pp. 167-176, 1999.

[21] B. Giffler and G.L. Thompson, “Algorithm for solving production scheduling problems,” Operations Research, vol. 8, pp. 487-503, 1960.

[22] R. J. W. James, “Using tabu search to solve the common due date early/tardy machine scheduling problem,” Computers and Operations Research, vol. 24, pp. 199-208, 1997.

[23] Y.-M. Li, Z.-B. Xul, “An ant colony optimization heuristic for solving maximum independent set problems,” Computational Intelligence and Multimedia Applications, 2003. ICCIMA 2003. Proceedings. Fifth International Conference on , 27-30 Sept, pp. 206 – 211, 2003.

[24] C.-F. Liaw, “A tabu search algorithm for the open shop scheduling problem,” Computer and Operations Research, vol. 26, pp. 109-126, 1999.

[25] C.-F. Liaw, “A hybrid genetic algorithm for the open shop scheduling problem,” European Journal of Operation Research, vol. 124, pp. 28-42, 2000.

[26] V. Maniezzo, A. Colorni, “The ant system applied to quadratic assignment problem,” IEEE Transactions on Knowledge and Data Engineering, vol. 11, pp. 769-784, 1999.

[27] M. Nawaz, J.E.E. Enscore, I. Ham, “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem,” Management Science, vol. 11, pp. 91-95, 1983.

[28] IH Osman , C.N. Potts, “Simulated annealing for permutation flow-shop scheduling,” OMEGA, International Journal of Management Science, vol. 17, pp. 551-557, 1989.

[29] D. S. Palmer, “Sequencing jobs through a multi-stage process in the minimum total time – a quick method of obtaining a near optimum,” Operation Research Quarterly, vol. 16, pp. 101-107, 1965.

[30] B. J. Park, H. R. Choi, H. S. Kim, “A hybrid genetic algorithm for the job shop scheduling problems,” Computer and Industrial Engineering, vol. 45, pp. 597-613, 2003.

[31] M. Pinedo, “Scheduling: theory, algorithm, and systems,” second edition, Prentice Hall, 2002.

[32] C. N. Potts, L. N. Wassenhove, “Single machine tardiness sequencing heuristics,” IIE Transactions, vol. 23, pp. 346-354, 1991.

[33] T. Stützle, H.H. Hoos, “The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem,” Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC’97), pp. 309-314, 1997.

[34] T. Stützle, “An ant approach to the flow shop problem,” Proceedings of EUFIT'98, Verlag Mainz, Aachen, pp. 1560-1564, 1998.

[35] M. Tadahiko, I. Hisao, T. Hideo, ”Genetic algorithms for flowshop scheduling problems,” Computer and Industrial Engineering, vol. 30, pp. 1061-1071, 1996.

[36] E. Taillard, “Benchmarks for basic scheduling problems,” European Journal of Operation Research, vol. 64, pp. 278-285, 1993.

[37] E. Taillard, L.M. Gambardella, “Adaptive Memories for the Quadratic Assignment Problem,” Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland, 1997.

[38] T. Vincent, M. Nicolas, Tercinet Fabrice, Laugt Daniel, “An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem,” European Journal of Operation Research, vol. 142, pp.250-257, 2002.

[39] K.-C. Ying, C.-J. Liao, “An ant colony system for permutation flow-shop sequencing,” Computers and Operations Research, vol. 31, pp. 791-801, 2004.

[40] 江朋南, 蟻族系統在零工型排程問題之應用, 國立台灣科技大學工業工程研究所碩士論文(2003).

[41] 徐誠佑, 螞蟻演算法求解零壹多限制式背包問題, 國立清華大學工業工程
研究所碩士論文(2003).

[42] 陳夏祥, 蟻族系統求解相依整備時間之單機總延遲問題, 國立台灣科技大學工業工程研究所碩士論文(2002).

[43] J. E. Beasley, “OR-Library,” http://people.brunel.ac.uk/~mastjjb/jeb/info.html