在實務界的生產系統中，相依整備時間 (sequence-dependent setups) 是排程不可或缺的考慮因素，而其中總延遲時間一直被視為最重要的目標之一。但儘管相依整備時間之延遲問題是如此的重要，過去的文獻卻鮮有相關的討論。因此在本論文中，我們利用螞蟻演算法 (Ant Colony Optimization；ACO) 在單機環境下求解相依整備時間之延遲問題。我們提出的螞蟻演算法有一些不同以往的特色，包括導入一個費洛蒙初始值的修正參數以及採用局部搜尋的時機等。我們針對標竿問題來做測試，發現它的績效凌駕了許多其它的演算法；我們更進一步地將此演算法應用在無權重的延遲問題上，實驗結果顯示，此演算法在面對其它擁有最佳表現的演算法時，也能顯現出它的優勢。
我們也嘗試將螞蟻演算法應用在求解最大完工時間以及總延遲時間的單機雙目標問題上，並將它與一種派工法則ATCS (Apparent Total Cost with Setups) 做比較，由實驗結果得知，在此問題下，螞蟻演算法亦有相當優秀的表現。

In many real-world production systems, it requires an explicit consideration of sequence-dependent setup times when scheduling jobs. As for the scheduling criterion, the weighted tardiness is always regarded as one of the most important criteria in practical systems. While the importance of the weighted tardiness problem with sequence-dependent setup times has been recognized, the problem has received little attention in the scheduling literature. In this paper, we present an ant colony optimization (ACO) algorithm for such a problem in a single machine environment. The proposed ACO algorithm has several features, including introducing a new parameter for the initial pheromone trail and adjusting the timing of applying local search, among others. The proposed algorithm is experimented on the benchmark problem instances and shows its advantage over existing algorithms. As a further investigation, the algorithm is applied to the unweighted version of the problem. Experimental results show that it is very competitive with the existing best-performing algorithms.
Furthermore, we try to apply ACO algorithm to the single machine problem with bi-criteria of makespan and total weighted tardiness. The ACO algorithm is compared with the constructive-type heuristic of Apparent Tardiness Cost with Setups (ATCS) and its superiority is demonstrated.

REFERENCES

[1] Allahverdi A, Gupta JND, Aldowaisan TA. A review of scheduling research involving setup considerations. OMEGA 1999;27:219-39.
[2] Das SR, Gupta JND, Khumawala BM. A saving index heuristic algorithm for flowshop scheduling with sequence dependent set-up times. Journal of the Operational Research Society 1995;46:365-73.
[3] Gravel M, Price WL, Gagné C. Scheduling jobs in an Alcan aluminium factory using a genetic algorithm. International Journal of Production Research 2000;38:3031-41.
[4] Wortman DB. Managing capacity: getting the most from your company’s assets. Industrial Engineering 1992;24:47-49.
[5] Wisner JD, Siferd SP. A survey of US manufacturing practices in make-to-order machine shops. Production and Inventory Management Journal 1995;1:1-7.
[6] Rubin PA, Ragatz GL. Scheduling in a sequence dependent setup environment with genetic search. Computers and Operations Research 1995;22:85-99.
[7] Wilbrecht JK, Prescott WB. The influence of setup time on job performance. Management Science 1969;16:B274-B280.
[8] Emmons H. One machine sequencing to minimize certain functions of job tardiness. Operations Research 1969;17:701-715.
[9] Lawler EL. A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics 1977;1:331-42.
[10] Du J, Leung JY. Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research 1990;15:483-494.
[11] Abdul-Razaq TS, Potts CN, Van Wassenhove LN. A survey of algorithms for the single machine total weighted tardiness scheduling problems. Discrete Applied Mathematics 1990;26:235-253.
[12] Potts CN, Van Wassenhove LN. A branch and bound algorithm for the total weighted tardiness problem. Operations Research 1985;33:363-377.
[13] Pinedo M. Scheduling: Theory, Algorithm, and System. Englewood Cliffs, NJ: Prentice-Hall, 1995.
[14] Potts CN, Van Wassenhove LN. Single machine tardiness sequencing heuristics. IIE Transactions 1991;23:346-354.
[15] Vepsalainen APJ, Morton TE. Priority rules for job shops with weighted tardiness cost. Management Science 1987;33:1035-1047.
[16] Lee YH, Bhaskaram K, Pinedo M. A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions 1997;29:45-52.
[17] Cicirello VA. Weighted tardiness scheduling with sequence-dependent setups: a benchmark library. Technical Report, Intelligent Coordination and Logistics Laboratory, Robotics Institute, Carnegie Mellon University, USA, 2003.
[18] Ragatz GL. Scheduling to minimize tardiness on a single machine with sequence dependent setup times. Working paper, Department of Management, Michigan State University, 1989.
[19] Tan KC, Narasimhan R. Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach. OMEGA 1997;25:619-34.
[20] Gagné C, Gravel M, Price WL. A new hybrid Tabu-VNS metaheuristic for solving multiple objective scheduling problems. Proceedings of the Fifth Metaheuristics International Conference. Kyoto, Japan, 2003.
[21] Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1997;1:53-66.
[22] Bullnheimer B, Hartl RF, Strauss C. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research 1999;89:319-28.
[23] Gambardella LM, Taillard ÉD, Dorigo M. Ant colonies for the quadratic assignment problem. Journal of Operational Research Society 1999;50:167-76.
[24] Bauer A, Bullnheimer B, Hartl RF, Strauss C. An ant colony optimization approach for the single machine total tardiness problem. Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, 1999. p. 1445-50.
[25] Den Besten M, Stützle T, Dorigo M. Ant colony optimization for the total weighted tardiness problem. Proceeding PPSN VI, 6th International Conference Parallel Problem Solving from Nature, vol. 1917, Lecture Notes in Computer Science, 2000. p. 611-20.
[26] Gagné C, Price WL, Gravel M. Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times. Journal of the Operational Research Society 2002;53:895-906.
[27] Ying GC, Liao CJ. Ant colony system for permutation flow-shop sequencing. Computers and Operations Research 2004;31:791-801.
[28] T’kindt V, Monmarché N, Tercinet F, Laügt D. An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operational Research 2002;42:250-57.
[29] Nagar A, Haddock J, Heragu S. Multiple and bicriteria scheduling: A literature survey. European Journal of Operations Research 1995;81:88-104.
[30] T’kindt V, Billaut JC. Some guidelines to solve multicriteria scheduling problems. IEEE International Conference on Systems, Man and Cybernetics Proceedings 1999;6:463-468.
[31] Lee CY, Vairaktarakis GL. Complexity of single machine hierarchical scheduling: A survey. Pardalos PM. Complexity in Numerical Optimization. Singapore, World Scientific Publishing Co, 1993.
[32] Hoogeveen JA. Single machine bicriteria scheduling. Ph.D. Thesis, CWI, Amsterdam 1992.
[33] Dorigo M, Stützle T. The ant colony optimization metaheuristics: algorithms, applications, and advances. In Glover F, Kochenberger G, editors, Handbook of metaheuristics, vol. 57, International Series in Operations Research & Management Science, Kluwer, 2002. p. 251-85.
[34] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on System, Man and Cybermetics 1996;26:29-41.
[35] Gambardella LM, Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. In Proceedings of the Twelfth International Conference on Machine Learning, Palo Alto, GA, Morgan Kaufmann 1995.
[36] Stützle T, Hoos HH. The MAX-MIN ant system and local search for the traveling salesman problem. In Baeck T, Michalewicz Z, and Yao X, editors, IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference 1997.
[37] Bullnheimer B, Hartl RF, Strauss C. A new rank-based version of the ant system: A computational study. Central European Journal for Operations Research and Economics 1999;23:156-174.
[38] Maniezzo V, Colorni A, Dorigo M. The ant system applied to the quadratic assignment problem. Technical Report IRIDIA 94-128, Belgium, 1994.
[39] Stützle T, Hoos HH. The MAX-MIN ant system and local search for combinatorial optimization problems. In Martello SS, Osman IH, Roucairol C, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization 1998.
[40] Maniezzo V, Colorni A. The ant system applied to the quadratic assignment problem. IEEE Transactions on System, Knowledge and Date Engineering 1999;33:192-211.
[41] Maniezzo V. Exact and approximate nondeterministic tree-search procedures for
the quadratic assignment problem. Technical Report CSR 98-1, Italy, 1998.
[42] Gambardella LM, Taillard ÉD, Agazzi G. A multiple ant colony system for vehicle routing problems with time windows. In Corne D, Dorigo M, Glover F, editors, New Ideas in Optimization, United Kingdom, McGraw-Hill, 1999;63-76.
[43] Colorni A, Dorigo M, Maniezzo V, Trubian M. Ant system for job-shop scheduling. Belgian Journal of Operations Research 1994;34:39-53.
[44] Gambardella LM, Dorigo M. HAS-SOP: An hybrid ant system for the sequential ordering problem. Technical Report 11-97, Lugano, 1997.
[45] Stützle T, Hoos HH. Max-min ant system. Future Generation Computer System 2000;16:889-914.
[46] Ignizio JP. Linear Programming in Single and Multiple Objective Systems. NJ: Prentice-Hall 1982.
[47] Murata T, Ishibuchi H, Tanaka H. Multi-objective genetic algorithm and its applications to flowshop scheduling. Computers and Industrial Engineering 1996;30:957-968.