生產排程是複雜且困難的，越是重要的訂單，越不允許延遲交貨的狀況發生，否則伴隨而來的各項違約成本與商譽損失，都將造成公司營運上有形或無形的損失，而太早提前完工則會導致完成品的庫存成本越高。若能以一個有效率的生產排程來解決生產線上的問題與顧客的需求，減少提前完工時間、延遲完工時間造成對生產上的傷害，對工廠來講是非常重要的。

本研究提出多種不同蟻群數、不同費洛蒙更新方式及不同局部搜尋機制的蟻群演算法，來求解單一機台上總加權延遲時間最小化和總加權提前完工時間最小化問題。蟻群演算法內狀態轉換法則之貪婪法則 ( 值)會因所需求解問題的不同而有所差異，在本研究中使用派工法則COVERTAU來求解總加權延遲時間，派工法則WMR則用來求解總加權提前完工時間。並針對總螞蟻數、局部搜尋的影響與參數設定做一探討。每種不同的蟻群演算法以柏拉圖最佳前緣來做比較，其中以五蟻群五區局部搜尋 – 混合全域更新法的蟻群演算法表現最佳。本研究亦期望提供多組排程方案，以供管理者在決策時的參考。

Production scheduling problem is complex and difficult in real world. Delay of the orders may cause the loss of business credibility, but on the hand the too early finish-up may lead to the tremendous inventory cost. Therefore, how to plan and implement an efficient production scheduling to meet customers’ due and demands has become a very important issue to enterprises.

This research proposes several ant colony optimization algorithms with different number of colonies, pheromone updating rules, and local search mechanisms. Two objectives were considered simultaneously – minimize total weighted tardiness and minimize total weighted earliness. In order to find an efficient local heuristic for each objective, a comprehensive study of dispatching rules is employed. The COVERTAU dispatching rule is selected for the total weighted tardiness objective while the WMR rule is used to assist the optimization of total weighted earliness. Experiments were conducted to investigate the effects of the number of ants, local search, and parameter settings. Using the best parameter settings, Pareto optimal front of each algorithm is collected to compare their performance. The ant colony algorithm with five colonies, five-region local search, and a mixed pheromone updating rule outperform others. This research also hopes to provide decision-maker many practical alternatives while facing different scheduling scenarios.

表目錄 3
圖目錄 4
第一章 緒論 6
1.1 研究背景與動機 6
1.2 研究目的 7
1.3 研究範圍 7
1.4 研究架構與流程 8
第二章 文獻探討 11
2.1 排程問題分類 11
2.2 單機單目標(Single Machine Single Objective) 13
2.3 單機多目標(Single Machine Multi-Objective) 15
2.4 蟻群演算法(Ant colony optimization, ACO) 20
2.4.1 蟻群演算法用於排程(Scheduling)問題文獻 26
2.4.2 蟻群演算法用於多目標(Multi-objective)方面文獻 27
第三章 研究方法………………………………………………………………..33
3.1 單機多目標之問題描述 33
3.2 問題之假設條件 33
3.3 單機多目標蟻群演算法之符號及目標式說明 34
3.3.1 符號說明 34
3.3.2 目標式說明 36
3.4 單目標蟻群演算法求解流程介紹 36
3.4.1 蟻群演算法之狀態轉換法則 39
3.4.2 蟻群演算法之局部費洛蒙更新 40
3.4.3 蟻群演算法之局部搜尋 41
3.4.4 蟻群演算法之全域費洛蒙更新 42
3.5 本研究之研究方法流程介紹 42
3.5.1 方法1 (M1)：單蟻群雙區局部搜尋法 44
3.5.2 方法2 (M2)：單蟻群三區局部搜尋法 47
3.5.3 方法3 (M3)：三蟻群雙區局部搜尋 - 重疊全域更新法 48
3.5.4 方法4 (M4)：三蟻群三區局部搜尋 - 重疊全域更新法 51
3.5.5 方法5 (M5)：三蟻群三區局部搜尋 - 端點全域更新法 52
3.5.6 方法6(M6)：五蟻群五區局部搜尋 – 混合式全域更新法 53
3.6 蟻群演算法用於單機多目標排程之貪婪法則( 值) 57
第四章 結果分析 60
4.1 測試例題說明 60
4.2 蟻群演算法之貪婪法則( 值)之選取…………………………………61
4.3 蟻群演算法之結果 64
4.3.1 多目標之衡量指標 64
4.3.2 螞蟻數目之影響 66
4.3.3 局部搜尋於單一蟻群的蟻群演算法之影響分析 68
4.3.4 局部搜尋於三蟻群演算法之影響分析 77
4.3.5 不同群數之蟻群演算法結果比較 85
第五章 結論……………………………………………………………………..98
5.1 結論…………………………………………………………………….98
5.2 未來發展………………………………………………………………..99
參考文獻 100

[1]林純行，「多階平行機器零工式多目標排程之模式化與系統之研究」，東海大學，碩士論文，民國九十一年。

[2]陳建良，「排程概述」，機械工業雜誌12月號，民國八十四年，pp. 122-137。

[3]陳怡聲，「允許中斷之開放工廠總完工時間最小化問題之研究」，朝陽科技大學，碩士論文，民國九十一年。

[4]湯璟聖，「動態彈性平行機群排程的探討」，中原大學，碩士論文，民國九十二年。

[5]劉仲立，「雙重資源限制下開放型工廠派工法則模擬研究」，朝陽科技大學，碩士論文，民國九十二年。

[6]Abdul-Razaq, T.S., and C.N. Potts, “Dynamic Programming State-Space Relaxation for Single-Machine Scheduling,”Journal of the Operational Research Society, vol. 39, 1988, pp. 141-152.

[7]Alidaee, B., and K.R. Ramakrishnan, “A Computational Experiment of COVERT-AU Class of Rules for Single Machine Tardiness Scheduling Problem,” Computers and Industrial Engineering, vol. 30, no. 2, 1996, pp. 201-209.

[8]Almeida, M.T., and M. Centeno, “A Composite Heuristic For the Single Machine Early/Tardy Job Scheduling Problem,” Computers and Operations Research, vol. 25, no. 7/8, 1998, pp. 625-635.

[9]Applegate, D., amd W. Cook, “A Computational Study of the Job-Shop Scheduling Problem,”ORSA Journal on Computing, vol. 3, 1991, pp. 149-156.

[10]Azizoglu, M., S. Kondakci, and M. Koksalan, “Single Machine Scheduling with Maximum Earliness and Number Tardy,” Computers and Industrial Engineering, vol. 45, 2003, pp. 257-268.

[11]Baker, K. R., and J. C. Smith, “A Multiple-Criterion Model for Machine Scheduling,”Journal of Scheduling, vol. 6, 2003, pp. 7-16.

[12]Baptiste, P., A. Jouglet, C. Le Pape, and W. Nuijten, “A Constraint-Based Approach to Minimize the Weighted Number of Late Jobs on Parallel Machines,”Research report 2000/228, UMR, CNRS 6599, Heudiasyc, France, 2000.

[13]Baran, B., and M. Schaerer, “A Multiobjective Ant Colony Systems for Vehicle Routing Problem with Time Windows,”Proceeding Twenty First IASTED International Conference on Applied Informatics, Insbruck, Austria, 2003, pp. 97-102.

[14]Bauer, A., B. Bullnheimer, R. F. Hartl, and C. Strauss, “An Ant Colony Optimization Approach for the Single Machine Total Tardiness Problem,”Proceedings of the 1999 Congress on Evolutionary Computation, Washington, D.C., July 1999, pp. 1445-1450.

[15]Bell, J.E., and P.R. McMullen, “Ant Colony Optimization Techniques for the ehicle Routing Problem,”Advanced Engineering Informatics, vol. 18, 2004, pp. 41-48.

[16]Ben-Daya, M., and M. Al-Fawzan, “A Simulated Annealing Approach for the One-Machine Mean Tardiness Scheduling Problem,”European Journal of Operational Research, vol. 93, 1996, pp. 61-67.

[17]Blum, C., and M. Sampels, “Ant Colony Optimization for FOP Shop Scheduling: A Case Study on Different Pheromone Representations,” Evolutionary Computation, vol. 2, 2002, pp. 1558-1563.

[18]Blum, C., and M. Sampels, “An Ant Colony Optimization Algorithm for Shop Scheduling Problems,”Journal of Mathematical Modelling and Algorithms, vol. 3, 2004, pp. 285-308.

[19]Brucker, P., J. Hurink, B. Jurisch, and B. Wostmann, “A Branch and Bound Algorithm for the Open-Shop Problem,”Discrete Applied Mathematics, vol. 76, 1997, pp. 43-59.

[20]Brun, O., and J.M. Garcia, “Ressource Allocation in Communication Networks,” High Speed Networks and Multimedia Communications 5th IEEE International Conference, 2002, pp. 229-233.

[21]Bullnheimer, B., R.F. Hartl, and C. Strauss, “An Improved Ant system Algorithm for the Vehicle Routing Problem,” Technical Report POM-10/97, Institute of Management Science, University of Vienna, 1997.

[22]Cardoso, P., M. Jesus, and A. Marquez, “MONACO – Multi-Objective Network Optimization Based on an ACO,”Proceeding X Encuentros de Geometria Computacional, Seville, Spain, 2003.

[23]Carroll, D.C., Heuristic Sequencing of Single and Multiple Component Jobs, Ph.D. Thesis, 1965, Sloan School of Management, M.I.T., Cambridge, MA.

[24]Chu, S.C., J.F. Roddick, and J.S. Pan, “Ant Colony System with Communication Strategies,”Information Sciences, vol. 167, 2004, pp. 63-76.

[25]Colorni, A., M. Dorigo, and V. Maniezzo, “New Results of an Ant System Approach Applied to the Asymmetric TSP,” Proceedings of the Metaheuristics International Conference, 1995.

[26]Colorni, A., M. Dorigo, V. Maniezzo, and M. Trubian, “Ant system for Job-shop Scheduling,” JORBEL - Belgian Journal of Operations Research, Statistics and Computer Science, vol. 34, no. 1, 1994, pp. 39-53.

[27]Dauzere-Peres, S., and M. Sevaux, “Using Lagrangean Relaxation to Minimize the (Weighted) Number of Late Jobs on a Single Machine,”Research report 99/8/AUTO, Ecole des Mines de Nantes, France, 1999.

[28]den Besten, M., T. Stutzle, and M. Dorigo, “Ant Colony Optimization for the Total Weighted Tardiness Problem,”Proceedings of the 6 International Conference on Parallel Problem Solving from Nature (PPSN VI), LNCS 1917, Berlin, 2000, pp. 611-620.

[29]Di Caro, G., and M. Dorigo, “AntNet: Distributed Stigmergetic Control for Communications Networks,” Journal of Artificial Intelligence Research (JAIR), vol. 9, 1998, pp. 317-365.

[30]Di Caro, G., and M. Dorigo, “Mobile Agents for Adaptive Routing,” roceedings of the 31st Hawaii International Conference on System, IEEE Computer Society Press, Los Alamitos, CA, 74-83.Also available as Technical Report IRIDIA/97-20, Université Libre de Bruxelles, Belgium, 1998.

[31]Dileepan, P., and T. Sen, “Bicriterion Static Scheduling Research for a Single Machine,”Omega, vol. 16, no. 1, 1988, pp. 53-59.

[32]Doerner, K., R.F. Hartl, and M. Teimann, “Are COMPETants More Competent for Problem Solving? – The Case of Full Truckload Transportation,”Central European Journal of Operations Research(CEJOR), vol. 11, no. 2, 2003, pp. 115-141.

[33]Doerner, K., W.J. Gutjahr, R.F. Hartl, and C. Strauss, “Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio Selection,”Annals of Operations Research, vol. 131, 2004, pp. 79-99.

[34]Donati, A.V., R. Montemanni, L.M. Gambardella, and A.E. Rizzoli, “Integration of A Robust Shortest Path Algorithm with a Time Dependent Vehicle Routing Model and Applications,”Proceedings of CIMSA 2003- Computational Intelligence for Measurement Systems and Applications, 2003, pp. 26-31.

[35]Dorigo, M., “Optimization Learning and Natural Algorithms,”Ph.D. Thesis, 1992, Politecnico di Milano, Italy.

[36]Dorigo, M., and L.M. Gambardella, “Ant Colonies for the Travelling Salesman Problem,”Biosystems, vol. 43, 1997, pp. 73-81.

[37]Dorigo, M., and L.M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,”IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, 1997, pp. 53-66.

[38]Dorigo, M., V. Maniezzo, and A. Colorni, “Ant System: Optimization By a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man and Cybernetics-Part B, vol. 26, no. 1, 1996, pp. 1-13.

[39]Duenas, A., “A New Approach to Multi-Objective Single Machine Scheduling under Fuzziness,” Proceedings of IFIP (International Federation of Information Processing) International Conference on Decision Support Systems, Prato, Italy, 2004, pp. 223-232.

[40]Emmons, H., “One Machine Sequencing to Minimize Certain Function of Job Tardiness,”Operations Research, vol. 17, 1969, pp. 701-715.

[41]Forsyth, P., and A. Wren, “An Ant System for Bus Driver Scheduling,” Presented at the 7th International Workshop on Computer-Aided Scheduling of Public Transport, Boston, August 1997.

[42]Fry, T.D., L. Vicens, K. Macleod, and S. Femandez, “A Heuristic Solution Procedure to Minimize T on A Single Machine,”Journal of the Operational Research Society, vol. 40, 1989, pp. 293-297.

[43]Gambardella, L., E. Taillard, and G. Agazzi, “News Ideas in Optimization,”MacGraw-Hill, London 1999, pp. 73-76.

[44]Gambardella, L., E. Taillard, and M. Dorigo, “Ant Colonies for the Quadratic Assignment Problem,” Journal of the Operational Research Society, vol. 50, 1999, pp. 167-176.

[45]Gambardella, L.M., and M. Dorigo, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem,” Proceedings of ML-95, Twelfth International Conference on Machine Learning, Tahoe City, CA, 1995, pp. 252-260.

[46]Gambardella, L.M., and M. Dorigo, “Solving Symmetric and Asymmetric TSPs by Ant Colonies,” Proceedings of IEEE International Conference on Evolutionary Computation, IEEE-EC 96, Nagoya, Japan, 1996, pp. 252-260.

[47]Garcia-Martinez, C., O. Cordon, and F. Herrera, “An Empirical Analysis of Multiple Objective Ant Colony Optimization Algorithms for the Bi-criteria TSP,”Proceedings of Ant Colony Optimization and Swarm Intelligence, 4th International Workshop, ANTS 2004, Brussels, Belgium, September 5 - 8, 2004, pp. 61-72.

[48]Gomez, J.F., H.M. Khodr, P.M. De Oliveira, L. Ocque, J.M. Yusta, R. Villasana, A.J. Urdaneta, “Ant Colony System Algorithm for the Planning of Primary Distribution Circuits,”IEEE Transactions on Power Systems, vol. 19, no. 2, 2004, pp. 996-1004.

[49]Gueret, C., and C. Prins, “A New Lower Bound for the Open-Shop Problem,”Ann. Oper. Res., vol. 92, 1999, pp. 165-183.

[50]Heck, H., and S. Roberts, “A Note on the Extention of a Result on Scheduling with Secondary Criteria,”Naval Research Logistics Quarterly, vol. 19, 1972, pp. 403-405.

[51]Holsenback, J. E., and R. M. Russell, “A Heuristic Algorithm for Sequencing on One Machine to Minimize Total Tardiness,”Journal of the Operational Society, vol. 43, 1992, pp. 53-62.

[52]Holsenback, J. E., R. M. Russell, R. E. Markland, and P. R. Philipoom, “An Improved Heuristic for the Single-Machine, Weighted-Tardiness Problem,”The International Journal of Management Science, vol. 27, 1999, pp. 485-495.

[53]Huegler, P. A., and F. J. Vasko, “A Performance Comparison of Heuristics for the Total Weighted Tardiness Problem,” Computers and Industrial Engineering, vol. 32, no. 4, 1997, pp. 753-767.

[54]Iredi, S., D. Merkle, and M. Middendorf, “Bi-Criterion Optimization with Multi Colony Ant Algorithms,”Proceedings of the 1 International Conference on Evolutionary Multi-Criterion Optimization (EMO 01’), LNCS 1993, Zurich, 2001, pp. 359-372.

[55]Kaji, T., “Approach by ant tabu agents for Traveling Salesman Problem,” 2001 IEEE International Conference on Systems, Man, and Cybernetics, vol. 5, 2001, pp. 3429-3434.

[56]Kao, E.P.C., “A Multiple Objective Decision Theoretic Approach to One Machine Scheduling Problems,”Computers and Operations Research, vol. 7, no. 4, 1980, pp. 251-259.

[57]Kao, R.J., C.Y. Chiu, and Y.J. Lin, “Integration of Fuzzy Theory and Ant Algorithm for Vehicle Routing Problem with Time Window,”Fuzzy Information, 2004. Processing NAFIPS '04. IEEE Annual Meeting, vol. 2, 2004, pp. 925-930.

[58]Karl, D., F.H. Richard, and R.Marc, “Are COMPETants more Competent for Problem Solving? – the Case of a Multiple Objective Transportation Problem,”Working Paper W.P., 2001.

[59]Katangur, A.K., Akkaladevi Somasheker, Y. Pan, and M.D. Fraser, “Applying Ant Colony Optimization to Routing in Optical Multistage Interconnection Networks with Limited Crosstalk,” Proceedings of the 18th International Parallel and Distributed Processing Symposium(IPDPS’04), 2004.

[60]Kethley, R. B., and B. Alidaee, “Single Machine Scheduling to minimize Total Weighted Late Work：A Comparison of Scheduling rules and Search Algorithm,” Computers and Industrial Engineering, vol. 43, 2002, pp. 509-528.

[61]Koksalan, M., and A. B. Keha, “Using Genetic Algorithms for Single-Machine Bicriteria Scheduling Problems,” European Journal of Operational Research, vol. 145, 2003, pp. 543-556.

[62]Kopuri, S, and N. Mansouri, “Enhancing Scheduling Solutions Through Ant Colony Optimization,” Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium, vol. 5, 2004, pp. 257-260.

[63]Kwang, M.S., and H.S. Weng, “Multiple Ant-Colony Optimization for Network Routing,” Cyber Worlds, Proceedings. First International Symposium, 2002, pp.277-281.

[64]Kwang, M.S., and H.S. Weng, “Ant Colony Optimization for Routing and Load-Balancing: Survey and New Directions,”IEEE Transactions on Systems, Man and Cybernetics- Part A, vol. 33, no. 5, 2003, pp. 560-572.

[65]Liang, Y.C., Ant Colony Optimization Approach to Combinational Problems, Ph.D. Thesis, 2001, Industrial and Systems Engineering, Auburn University.

[66]Li, L., Z. Liu, and Z. Zhou, “A New Dynamic Distributed Routing Algorithm on Telecommunication Networks,” Communication Technology Proceedings, vol. 1, 2000, pp. 849-852.

[67]Liu, N., M. A. Abdelrahman, and S. Ramaswamy, “A Genetic Algorithm for the Single Machine Total Weighted Tardiness Problem,”Proceedings of the 35th Southeastern Symposium, March 2003, pp. 34-38.

[68]M’Hallah, R., and R.L. Bulfin, “Minimizing the Weighted Number of Tardy Jobs On a Single Machine,”European Journal of Operational Research, vol. 145, 2003, pp. 45-56.

[69]Madureira, A. M., “Meta-Heuristics for the Single-Machine Scheduling Total Weighted Tardiness Problem,”Proceedings of the 1999 IEEE International Symposium on Assembly and Task Planning (ISATP 99’), Porto, Portugal, July 1999, pp. 405-410.

[70]Maniezzo, V., “Exact and Approximate Nondeterministic Tree-search Procedures for the Quadratic Assignment Problem,” Research Report CSR 98-1, Scienze dell'Informazione, University di Bologna, Sede di Cesena, Italy, 1998.

[71]Maniezzo, V., and A. Colorni, “The Ant System Applied to the Quadratic Assignment Problem,”IEEE Transactions on Knowledge and Data Engineering, vol. 11, no. 5, 1999, pp. 768-778.

[72]Maniezzo, V., A. Colorni and M. Dorigo, “The Ant System Applied to the Quadratic Assignment Problem,” Technical Report IRIDIA/94-28, University Libre de Bruxelles, Belgium, 1994.

[73]Mariano, C.E., amd E. Morales, “MOAQ an Ant-Q Algorithm for multiple Objective Optimization Problems,” In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference, vol. 1, 1999, pp. 894-901.

[74]Mazzini, R., and R. A. Armentano, “A Heuristic for Single Machine Scheduling with Early and Tardy Costs,”European Journal of Operational Research, vol. 128, 2001, pp. 129-146.

[75]McMullen, P. R., “An Ant Colony Optimization Approach to Addressing a JIT Sequencing Problem with Multiple Objectives,”Artificial Intelligence in Engineering, vol. 15, 2001, pp. 309-317.

[76]Merkle, D., and M. Middendorf,“Ant Colony Optimization with Global Pheromone Evaluation for Scheduling a Single Machine,”Applied Intelligence, vol. 18, 2003, pp. 105-111.

[77]Merkle, D., M. Middendorf, and H. Schmeck, “Ant Colony Optimization for Resource-Constrained Project Scheduling,” Evolutionary Computation, vol. 6, no. 4, 2002, pp. 333-346.

[78]Merz, P., and B. Freisleben, “A Comparison of Memetic Algorithms, Tabu Search, and Ant Colonies for the Quadratic Assignment Problem,” Proceedings of the 1999 International Congress of Evolutionary Computation (CEC'99), 1999, pp. 2063-2070.

[79]Montagne, E. R. Jr., “Sequencing with Time Delay Costs,”Arizona State University Industrial Research, vol. 24, no. 11, 1997, pp. 1097-1100.

[80]Moore, J.M., “An N Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs,”Management Science, vol. 15, 1968, pp. 102-109.

[81]Morton, T.E., and D.W. Pentico, Heuristic Scheduling Systems with Applications to Production Systems and Project Management, 1993, John Wiley & Sons.

[82]Morton, T.E., and R.M.U. Rachamudugu, “Myopic Heuristics for the Single Machine Weighted Tardiness Problem,” Technical Report CMU-RI-TR-83-09, Robotics Institute, Carnegie Mellon University, November, 1982.

[83]Morton, T.E., R.M.U. Rachamudugu, and A.P.J. Vepsalainen, “Accurate Myopic Heuristics for Tardiness Schduling,”Working Paper W.P. 36-83-84, Carnegie Mellon University, 1984.

[84]Negar, A., J. Haddock, and S. Heragu, “Multiple and Bicriteria Scheduling：A Literature Survey,” European Journal of Operation Research, vol. 81, 1995, pp. 88-104.

[85]Navarro Varela, G., and M.C. Sinclair, “Ant Colony Optimisation for Virtual-Wavelength-Path Routing and Wavelength Allocation,” Proceedings of the Congress on Evolutionary Computation (CEC'99), Washington DC, USA, July 1999, pp. 1809-1816.

[86]Ning, S., W. Wei, L. Yaohua, and O. Shusheng, “Application of Modified Ant Colony Optimization Algorithm to Hot Rolling Lot Planning,” Intelligent Control and Automation, 2004. WCICA 2004. Fifth World Congress, vol. 4, 2004, pp. 2933-2937.

[87]Nowicki, E., and C. Smutnicki, “A Fast Taboo Search Algorithm for the Job-Shop Problem,”Management Science, vol. 42, no. 2, 1996, pp. 797-813.

[88]Ow, P.S., and T.E. Morton, “The Single Machine Early/Tardy Problem,”Management Science, vol. 35, 1989, pp. 177-191.

[89]Palmer, D.S., “Sequencing Jobs Through a Multi-Stage Process in the Minimum Total Time – A Quick Method of Obtaining a Near Optimum,”Operational Research Quarterly, vol. 16, 1965, pp. 101-107.

[90]Pinedo, M., Scheduling: Theory, Algorithms, and Systems, 1995, Prentice Hall.

[91]Potts, C.N., and Van Wassenhove, L.N., “A Decomposition Algorithm for the Single Machine Total Tardiness Problem,”Operations Research Letters, vol. 32, 1982, pp. 177-181.

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

[93]Schoonderwoerd, R., O. Holland, and J. Bruten, “Ant-like Agents for Load Balancing in Telecommunications Networks,” Proceedings of Agents'97, Marina del Rey, CA, ACM Press, 1997, pp. 209-216.

[94]Schoonderwoerd, R., O. Holland, J. Bruten, and L. Rothkrantz, “Ant-based Load Balancing in Telecommunications Networks,” Adaptive Behavior, vol. 5, no. 2, 1997, pp. 169-207.

[95]Schrage, D., and P.G. Gonsalves, “Sensor Scheduling using Ant Colony Optimization,” Information Fusion, vol. 1, 2003, pp. 379-385.

[96]Sevaux, M., and S. Dauzere-Peres, “Genetic Algorithms to Minimize the Weighted Number of Late Jobs on a Single Machine,”European Journal of Operational Research, vol. 151, 2003, pp. 296-306.

[97]Shanthikumar, R., “Scheduling n Jobs on One Machine to Minimize the Maximum Tardiness with Minimum Number Tardy,”Computers and Operations Research, vol. 10, no. 3, 1983, pp. 255-266.

[98]Shwimer, J., “On the n-job, One-Machine, Sequence-Independent Scheduling Problem with Tardiness Penalties: a Branch-Bound Solution,”Management Science, vol. 18, no. 6, 1972, pp. 301-303.

[99]Shyu, S.J., B.M.T. Lin, and P.Y. Lin, “Application of Ant Colony Optimization for No-wait Flowshop Scheduling Problem to Minimize the Total Completion Time,”Computers and Industrial Engineering, vol. 47, 2004, pp. 181-193.

[100]Smith, W.E., “Various Optimizers for Single Stage Production,”Naval Research Logistics Quarterly, vol. 3, no. 1, 1956, pp. 59-66.

[101]Solimanpur, M., P. Vrat, and R. Shanker, “Ant Colony Optimization Algorithm to the Inter-Cell Layout Problem in Cellular Manufacturing,”European Journal of Operational Research, vol. 157, 2004, pp. 592-606.

[102]Sousa, J.P., and L.A. Wolsey, “A Time Indexed Formulations of Non-Preemptive Single-Machine Scheduling Problems,”Mathematical Programming, vol. 54, 1992, pp. 353-367.

[103]Stutzle, T., and M. Dorigo, “ACO Algorithms for the Traveling Salesman Problem,” Evolutionary Algorithms in Engineering and Computer Science, 1999, pp. 163-183.

[104]Stutzle, T., and M. Dorigo, “ACO Algorithms for the Quadratic Assignment Problem,” McGraw-Hill’s Advanced Topics In Computer Science Series archive New ideas in optimization archive, 1999, pp. 33 - 50.

[105]Stutzle, T., and H. Hoos, “MAX-MIN Ant System,”Future Generation Computer Systems, vol. 16, 2000, pp. 889-914.

[106]Stutzle, T., and H. Hoos, “MAX-MIN Ant System and Local Search for the Traveling Salesman Problem,”IEEE International Conference on Evolutionary Computation, 1997, pp. 309-314.

[107]Taillard, E.D., and L.M. Gambardella, “An Ant Approach for Structured Quadratic Assignment Problems,” Technical Report IDSIA-22-97, Instituto Dalle Molle di Studi sull'Intelligenza Artificiale, University di Bologna, Sede di Cesena, Italy, January 22, 1997.

[108]Taillard, E.D., L.M. Gambardella, M. Gendreau, and J.Y. Potvin, “Adaptive Memory Programming: A Unified View of Metaheuristics,”European Journal of Operational Research, vol. 135, 2001, pp. 1-16.

[109]Talbi, E.G., O.Roux, C. Fonlupt, and D. Robillard, “Parallel Ant Colonies for the Quadratic Assignment Problem,”Future Generation Computer Systems, vol. 17, 2001, pp. 441-449.

[110]T’kindt, V., N. Monmarche, F. Tercinet, and D. Laugt, “An Ant Colony Optimization to solve a 2-Machine Bicriteria Flowshop Scheduling Problem,” European Journal of Operational Research, vol. 142, 2002, pp. 250-257.

[111]Tsai, C.F., and C.W. Tsai, “A New Approach for Solving Large Traveling Salesman Problem using Evolutionary Ant Rules,” Proceedings of the 2002 International Joint Conference on Neural Networks(IJCNN '02), 2002, pp. 1540-1545.

[112]Tsai, C.F., C.W. Tsai, and C.C. Tseng, “A New Hybrid Heuristic Approach for Solving Large Traveling Salesman Problem,”Information Sciences, vol. 166, 2004, pp. 67-81.

[113]Van Wassenhove, L.N., and F. Gelders, “Solving a Bicriterion Scheduling Problem,”European Journal of Operational Research, vol. 4, no. 1, 1980, pp. 42-48.

[114]Woolsey, R.E.D., and H.S. Swanson, Operations Research for Immediate Application: A Quick and Dirty Manual, Harper and Row Publisher, New York, 1975.

[115]Xiao, J.T., “Applying the Ant Colony Optimization Algorithm to the Spatial Cluster Scheduling Problem,” Machine Learning and Cybernetics, vol. 3, 2004, pp. 1341-1346.

[116]Ying, K. C., and C. J. Liao, “An Ant Colony System for Permutation Flow-Shop Sequencing,”Computers and Operations Research, vol. 31, 2004, pp. 791-801.

[117]Zhou, P., X.P. Li, and H.F. Zhang, “An Ant Colony Algorithm for Job Shop Scheduling Problem,” Intelligent Control and Automation, vol. 4, 2004, pp. 2899-2903.

[118]http://iridia.ulb.ac.be/~mdorigo/ACO/RealAnts.html, Ant Colony Optimization

[119]Czyzak, P., A. Jaszkiewicz, “A Multiobjective Metaheuristic Approach to the Localization of a Chain of Petrol Stations by the Capital Budgeting model,” Control and Cybernetics, vol. 25, no. 1, 1996, pp. 177-187.

[120]Chang, P.C., and H.C. Lee, “A Greedy Heuristic for Bicriterion Single Machine Scheduling Problems,” Computers and Industrial Engineering, vol. 22, no. 2, 1992, pp. 121-131.

[121]Carlier, J., “The One-Machine Sequencing Problem,” European Journal of Operational Research, vol. 11, no. 42, 1982.