臺灣博碩士論文加值系統

近年來，通用啟發法備受大眾關注，除了可以解高複雜度問題外，通用啟發法也可以求解不同領域之問題，如生產排程、物流運籌和產能規劃等問題。然而，大多通用啟發法邏輯過於複雜，不容易理解。因此，本研究將提出簡單易懂的通用啟發法，稱為多重變動鄰域搜尋法(multiple Variable Neighborhood Search；m-VNS)。因為在所有排程問題中，單機總加權延遲時間(single machine total weighted tardiness；SMTWT)問題是一個典型的離散型組合最佳化問題。因此，本研究以SMTWT問題為例，針對標準測試題庫進行驗證，並與文獻中的演算法進行比較，實驗結果顯示m-VNS同時兼顧求解效率與求解品質，並且最為優異。

In recent years, meta-heuristics are common and very popular methods in the industry to solve highly complex problems in different areas, such as production scheduling, logistic distribution, and capacity planning. However, most of the meta-heuristics are too complicated to understand and implement. Therefore, this paper proposes an easy-to-understand meta-heuristic, called multiple Variable Neighborhood Search (m-VNS). The single machine total weighted tardiness (SMTWT) problem is a typical discrete combinatorial optimization problem in the scheduling literature. The m-VNS will be used to solve this well-known problem and compared with several existing famous algorithms. Finally, we found m-VNS algorithm has an excellent performance and is of better results in the solution quality and computational time better than those reported previously in the literature. This research has demonstrated that the m-VNS meta-heuristic can be efficiently and effectively applied to the SMTWT problem.

CHINESE ABSTRACT 1
ENGLISH ABSTRACT II
LIST OF FIGURES IV
LIST OF TABLES V
Chapter 1. INTRODUCTION 1
Chapter 2. LITERATURE REVIEW 4
Chapter 3. PROPOSED HEURISTIC 7
3.1. Components of m-VNS 7
3.2. Framework of m-VNS 10
3.3. Neighborhood structures of m-VNS 13
Chapter 4. VARIABLE NEIGHBORHOOD SEARCH 15
Chapter 5. COMPUTATIONAL RESULTS 18
Chapter 6. CONCLUSIONS AND FUTURE RESEARCH 25
REFERENCES 27

Abdul-Razaq, T.S., Potts, C.N. and Van Wassenhove, L.N., A survey of algorithms for the single machine total weighted tardiness scheduling problems. Discrete Applied Mathematics, 1990, 26, 235–253.
Alidaee, B. and Ramakrishnan, K.R., A computational experiment of COVERT-AU class of rules for single machine tardiness scheduling problem. Computers and Industrial Engine, 1996, 30, 201–209.
Babu, P., Peridy, L. and Pinson, E., A branch and bound algorithm to minimize total weighted tardiness on a single processor. Annals of Operations Research, 2004, 129, 33–46.
Baker, K.R. and Schrage, L.E., Finding an optimal permutation by dynamic programming: an extension to precedence-related tasks. Operations Research, 1978, 26, 111–120.
Bilge, Ü., Kurtulan, M. and Kirac, F., A tabu search algorithm for the single machine total weighted tardiness problem. European Journal of Operational Research, 2007, 176, 1423–35.
Bożejko, W., Grabowski, J. and Wodecki, M., Block approach—tabu search algorithm for single machine total weighted tardiness problem. Computers and Industrial Engineering, 2006, 50, 1–14.
Congram, R.K., Potts, C.N. and Van de Velde, S.L., An iterated dynasearch algorithm for the single machine total weighted tardiness scheduling problem. INFORMS Journal on Computing, 2002, 14, 52–67.
Crauwels, H.A., Potts, C.N. and Van Wassenhove, L.N., Local search heuristics for the single machine total weighted tardiness scheduling problem. INFORMS Journal on Computing, 1998, 10, 341–350.
Den Besten, M.L., Stützle, T. and Dorigo, M., Ant colony optimization for the total weighted tardiness problem. Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature (PPSN-VI), LNCS 1917, 2000, 611–620.
Den Besten, M.L., Stützle, T. and Dorigo, M., Design of iterated local search algorithm: an example application to the single machine total weighted tardiness problem. Applications of Evolutionary Computing, edited by E.J.W. Boer, S. Cagnoni, J. Gottlieb, E. Hart, P.L. Lanzi, G.R. Raidl, R.E. Smith and H. Tijink, LNCS 2037, 441–451, 2001.
Emmons, H., One-machine sequencing to minimize certain functions of job tardiness. Operations Research, 1969, 17, 701–715.
Grosso, A., Della Groce, F. and Tadei, R., An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem. Operations Research Letters, 2004, 32, 68–72.
Gupta, S.R. and Smith, J.S., Algorithms for single machine total tardiness scheduling with sequence dependent setups. European Journal of Operational Research, 2006, 175, 722–739.
Hansen, P. and Mlasenović, N., Variable neighborhood search: Principles and applications. European Journal of Operational Research, 2001, 130, 449-467.
Held, M. and Karp, R.M., A dynamic programming approach to sequencing problems. Journal of the Society of Industrial and Applied Mathematics, 1962, 10, 196–210.
José E.C., André G., Fabrício L. S. and Alexandre F., A GRASP with path relinking for the single machine total weighted tardiness problem. Proceedings of the 8th International Conference on Hybrid Intelligent Systems, IEEE Computer Society, 2008, 726-731.
Lawler, E.L., On scheduling problems with deferral costs. Management Science, 1964, 11, 280–288.
Lenstra, J.K., Rinnooy Kan, A.H.G. and Brucker, P., Complexity of machine scheduling problems. Annals of Discrete Applied Mathematics, 1977, 1, 343–362.
Maheswaran, R. and Ponnambalam, S.G., An investigation on single machine total weighted tardiness scheduling problems. International Journal of Advanced Manufacturing Technology, 2003, 22, 243–248.
Maheswaran, R. and Ponnambalam, S.G., An intensive search evolutionary algorithm for single-machine total-weighted-tardiness scheduling problems. International Journal of Advanced Manufacturing Technology, 2005, 26, 1150–1156.
Matsuo, H., Suh, C.J. and Sullivan, R.S., A controlled search simulated annealing method for the single machine weighted tardiness problem. Annals of Operations Research, 1989, 21, 85–108.
McNaughton, R., Scheduling with deadlines and loss functions. Management Science, 1959, 6, 1–12.
Merkle, D. and Middendorf, M., An ant algorithm with global pheromone evaluation for scheduling a single machine. Applied Intelligence, 2003, 18, 105–111.
Mladenovic, N. and Hansen, P., Variable neighborhood search. Computers and Operations Research, 1997, 24, 1097–1100.
Potts, C.N. and Van Wassenhove, L.N., A branch and bound algorithm for the total weighted tardiness problem. Operations Research, 1985, 33, 363–377.
Rabadi, G., Moraga, R. J. and Al-Salem, A., Heuristics for the unrelated parallel machine scheduling problem with setup times. Journal of Intelligent Manufacturing, 2006, 17, 85-97.
Rinnooy Kan, A.H.G., Lageweg, B.J. and Lenstra, J.K., Minimizing total costs in one-machine scheduling. Operations Research, 1975, 23, 908–927.
Schrage, L.E. and Baker, K.R., Dynamic programming solution of sequencing problems with precedence constraints. Operations Research, 1978, 26, 444–449.
Shwimer, J., On the N-job, one-machine, permutation-independent scheduling problem with tardiness penalties: a branch-bound solution. Management Science, 1972, 18, B301–B313.
Tasgetiren, M.F., Liang, Y.C., Sevkli, M. and Gencyilmaz, G., Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem. International Journal of Production Research, 2006, 44, 4737–54.
Potts, C.N. and Van Wassenhove, L.N., A branch and bound algorithm for the total weighted tardiness problem. Operations Research, 1985, 33, 363–377.
Potts, C.N. and Van Wassenhove, L.N., Single machine tardiness sequencing heuristics. IIE Transactions, 1991, 23, 346–354.
Wang, X.P. and Tang, L.X., A population-based variable neighborhood search for the single machine total weighted tardiness problem. Computers and Operations Research, 2009, 36, 2105-2110