臺灣博碩士論文加值系統

針對組合最佳化的問題，蟻族系統 (Ant Colony System ; ACS) 是許多共通式演算法 (meta-heuristics) 中的一種。在這篇論文裡，我們提出蟻族系統演算法運用在衡量準則為總延遲時間的情況，並且考慮相依整備時間 (sequence-dependent) 的限制條件，來解決單機排程的問題。綜觀目前的相關文獻，本論文是第一次將蟻族系統演算法當成改善型啟發式演算法來解決此問題，蟻族系統演算法也透過結構式演算法(construction heuristic) 以利於排程的進行。
經由實驗分析，不同的問題大小下，我們可以推論所提案之演算法(proposed algorithm) 的績效。且由實驗的結果顯示，我們所提案的演算法，在小問題的情況下，幾乎都可以達到最佳解，例如：在32個例子裡頭有31個問題達到最佳解。同樣地，在大問題的情況下，所提案的演算法能夠針對結構式演算法得到顯著的改善率，例如：若所提案的演算法考慮區域搜尋法，將得到28%以上的改善率，但是，如果不考慮區域搜尋法，則改善率將高達67%以上。
在本研究中，我們也考慮在不同的派工規則下，所提案演算法對於績效改善的優劣情形。例如：ATCS (Apparent Total Cost with Setups) 等派工規則。
最後，由實驗的結論可以得知，在此問題下，蟻族系統演算法是相當有效率和效能以及穩定的方法。

Ant colony system (ACS) is one of the most recent meta-heuristics for combinatorial optimization problems. In this paper, an ACS algorithm is proposed for the single machine total weighted tardiness problem with sequence-dependent setup times. To the best of our knowledge, this is the first attempt to propose an improved heuristic, as opposed to the construction heuristic, for this problem.
To verify the developed algorithm, computational experiments were conducted on different sizes of problems. The experimental results show that the algorithm find optimal solutions for almost all small size problems. For large size problems, the algorithm significantly improves the best solutions obtained by the construction heuristics.
Furthermore, we incorporate different dispatching rules into our ACS algorithm. The results verify that the proposed algorithm is an efficient and effective method for this problem.

CHINESE ABSTRACT i
ENGLISH ABSTRACT ii
ACKNOWLEDGEMENTS iii
CONTENTS iv
LIST OF TABLES v
LIST OF FIGURES vi
Chapter 1. INTRODUCTION 1
Chapter 2. LITERATURE REVIEW 3
Chapter 3. The BACKGROUND OF ACS 6
Chapter 4. The PROPOSED ALGORITHM 10
4.1. Parameters of ACS Description 11
4.2. The State Transition Rule 12
4.3. The Pheromone Updating Rule 14
4.4. Local Improvement Method 15
Chapter 5. COMPUTATIONAL RESULTS 17
5.1. Test Problems 17
5.2. Parameters Setting 17
5.3. Results and Discussions 18
Chapter 6. CONCLUSIONS AND FUTURE RESEARCH 26
REFERENCES 28
APPENDIX. THE ACS ALGORITHM 33
AUTHOR 36

[1] S.S. Panwalker, R.A. Dudek, M.L. Smith, Sequencing research
and the industrial scheduling problem. In, M. Beckmann,
P.G. Goos, H.P.K. Zutich, editors, Symposium on the Theory
of Scheduling and Its Applications, 1973.
[2] C.N. Potts, L.N. Van Wassenhove, Single machine tardiness
sequencing heuristics. IIE Transactions 23 (1991) 346-354.
[3] C.N. Potts, L.N. Van Wassenhove, Dynamic programming and
decomposition approaches for the single machine total
tardiness problem. European Journal of Operational Research
32 (1987) 405-414.
[4] K.C. Tan, R. Narasimhan, P.A. Rubin, G.L. Ragatz, A
comparison of four methods for minimizing total tardiness
on a single processor with sequence-dependent setup times.
Omega 28 (2000) 313-326.
[5] D.B. Wortman, Managing capacity: getting the most from your
compamy’s assets. Industrial Engineering 24 (1992) 47-49.
[6] L.M. Gambardella, M. Dorigo, Ant colony system hybridized
with a new local search for the sequential ordering
problem. INFORMS Journal on Computing 12 (2000).
[7] H. Emmons, One machine sequencing to minimize certain
functions of job tardiness. Operations Research 17 (1969)
701-715.
[8] E.L. Lawler, A ‘pseudopolynomial’ algorithm for
sequencing jobs to minimize total tardiness. Annals of
Discrete Mathematics 1 (1977) 331-342
[9] J. Du, J.Y. Leung, Minimizing total tardiness on one
machine is NP-hard. Mathematics of Operations Research 15
(1990) 483-494.
[10] T.S. Abdul-Razaq, C.N. Potts, L.N. Van Wassenhove, A
survey of algorithms for the single machine total weighted
tardiness scheduling problems. Discrete Applied
Mathematics 26 (1990) 235-253.
[11] C.N. Potts, L.N. Van Wassenhove, A branch and bound
algorithm for the total weighted tardiness problem.
Operations Research 33 (1985) 363-377.
[12] A.P.J. Vepsalainen, T.E. Morton, Priority rules for job
shops with weighted tardiness cost. Management Science 33
(1987) 1035-1047.
[13] Y.H. Lee, K. Bhaskaran, M. Pinedo, A heuristic to minimize
the total weighted tardiness with sequence-dependent
setups. IIE Transactions 29 (1997) 45-52.
[14] A. Volgenant, E. Teerhuis, Improved heuristic for the n-
job single-machine weighted tardiness problem. Computers
and Operations Research 26 (1999) 35-44.
[15] M. Dorigo, V. Maniezzo, A. Colorno, Ant system:
Optimization by a colony of cooperating agents, IEEE
Transactions on Systems, Man and Cybermetics 26 (1996) 29-
41.
[16] L.M. Gambardella, M. Dorigo, Ant colony system hybridized
with a new local search for the sequential ordering
problem. INFORMS Journal on Computing 12 (2000).
[17] S. Webster, P. D. Jog, A. Gupta, A genetic algorithm for
scheduling job families on a single machine with arbitrary
earliness/tardiness penalties and an unrestricted common
due date. International Journal of Production Research 36
(1998) 2543-2551.
[18] A. Islam, M. Eksioglu, A tabu search approach for the
single machine mean tardiness problem. Journal of
Operational Research Society 48 (1997) 751-755.
[19] S.H. Zegordi, K. Itoh, T. Enkawa, Minimizing makespan for
flow shop scheduling by combining simulated annealing with
sequencing knowledge. European Journal of Operational
Research 85 (1995) 515-531.
[20] F. Glover, H.J. Greenberg, New approaches for heuristic
search: A bilateral linkage with artificial intelligence.
European Journal of Operational Research 39 (1989) 119-130.
[21] M. Dorigo, G.D. Caro, The ant colony optimization meta-
heuristic. In D. Corne, M. Dorigo, F. Glover, editors, New
Ideas in Optimization, McGraw-Hill, 1999 .
[22] M. Dorigo, L.M. Gambardella, Ant colony system: A
cooperative learning approach to the traveling salesman
problem. IEEE Transactions on Evolutionary Computation 1
(1997) 53-66.
[23] V. Maniezzo, Exact and approximate nondeterministic tree-
search procedures for the quadratic assignment problem.
INFORMS Journal on Computing 11 (1999) 358-369.
[24] L.M. Gambardella, E.D. Taillard, G.. Agazzi, A multiple
ant colony system for vehicle routing problrms with time
windows. In D. Corne, M. Dorigo, F. Glover, editors, New
Ideas in Optimization, McGraw-Hill, 1999.
[25] A. Colorni, M. Dorigo, V. Maniezzo, M. Trubian, Ant system
for job-shop scheduling, Belgian Journal of Operations
Research, Statistics and Computer Science 34 (1994) 39-53.
[26] L.M. Gambardella, M. Dorigo, Ant-Q: A reinforcement
learning approach to the traveling salesman problem. In
Proceedings of the Twelfth International Conference on
Machine Learning, Palo Alto, CA, Morgan Kaufmann, 1995.
[27] T. Stutzle, H. Hoos, The MAX-MIN ant system and local
search for the traveling salesman problem. In T, Baeck, Z.
Michalewicz, and X. Yao, editors, IEEE International
Conference on Evolutionary Computation and Evolutionary
Programming Conference, 1997.
[28] B. Bullnheimer, R.F. Hartl, C. Strauss, A new rank-based
version of the ant system: a computational study. Central
European Journal for Operations Research and Economics 23
(1999) 156-174.
[29] V. Maniezzo, A. Colorni, M. Dorigo, The ant system applied
to the quadratic assignment problem. Technical report
IRIDIA 94-28, Belgium, 1994.
[30] L.M. Gambardella, E.D. Taillard, M. Dorigo, Ant colonies
for the QAP. Journal of the Operational Research Society
52 (2001) 301-315.
[31] T. Stutzle, H. Hoos, MAX-MIN ant system and local search
for combinatorial optimization problems. In S. S.
Martello, I.H. Osman, and C. Roucairol, editors, Meta-
Heuristics: Advances and Trends in Local Search Paradigms
for Optimization, 1998.
[32] V. Maniezzo, A. Colorni, The ant system applied to the
quadratic assignment problem. IEEE Transactions on System,
Knowledge and Data Engineering 33 (1999) 192-211.
[33] V. Maniezzo, Exact and approximate nondeterministic tree-
search procedures for the quadratic assignment problem.
Technical Report CSR 98-1, Italy, 1998.
[34] B. Bullnheimer, R.F. Hartl, C. Strauss, An improved ant
system algorithm for the vehicle routing problem. Annals
of Operations Research (1996) 21 336-357.
[35] L.M. Gambardella, M. Dorigo, HAS-SOP: An hybrid ant system
for the sequential ordering problem. Technical Report 11-
97, Lugano, 1997.
[36] T.E. Morton, R.M. Rachamadugu, A. Vepsalainen, Accurate
myopic heuristics for tardiness scheduling. Working paper
No. 36-83-84, Graduate School of Industrial
Administration, Carnegie Mellon University, 1984.
[37] J.E. Holsenback, R.M. Russell, R.E. Markland, P.R.
Philipoom, An improved heuristic for the single-machine,
weighted-tardiness problem. Omega 27 (1999) 485-495.
[38] T.E. Morton, R.M. Rachamadugu, Myopic heuristics for the
single machine weighted tardiness problem. Working paper
No. 30-82-83, Graduate School of Industrial
Administration, Carnegie Mellon University, 1982.
[39] R.K. Congram, C.N. Potts, S.L. Van de Velde, An iterated
dynasearch algorithm for the single-machine total weighted
tardiness problem. Technical report, Faclty of
Mathematical Studies, University of Southampton, 1998.
[40] R.K. Ahuja, J.B. Orlin, A. Tiwari. A greedy genetic
algorithm for the quadratic assignment problem. Computers
and Operations Research 27 (2000) 917-934.
[41] M.B. Daya, M.A. Fawzan, A simulated annealing approach for
the one-machine mean tardiness scheduling problem.
European Journal of Operational Research 93 (1996) 61-67.
[42] V.A. Armentano, C.R. Scrich, Tabu search for minimizing
total tardiness in a job shop. International Journal of
Production Economics 63 (2000) 131-140.