臺灣博碩士論文加值系統

三個尋找接近最佳解之優異技術：基因演算法 (Genetic Algorithm；GA)、模擬退火法 (Simulated Annealing；SA) 及塔布搜尋法 (Tabu Search；TS)，已廣泛地應用在求解組合式最佳化的問題，這些技術通常被稱為共通式演算法 (meta-heuristics) 或一般啟發式演算法 (general heuristics)。本論文首先介紹這三個方法的演算架構及其參數的設定，並且比較其差異性。然後，使用其中的一個方法——塔布搜尋法，提出有效的啟發式演算法，求解兩個排程問題。第一個問題是考量雙重設置時間下之單機排程問題，另一個問題是多重準則之流程型工廠排程問題。
對於第一個問題，我們分別以動態規劃法 (Dynamic Programming；DP) 和塔布搜尋法，發展出兩個啟發式演算法，這兩個演算法在工作個數不大於30個時，皆有良好的演算績效。但是，當問題變大時，以動態規劃法為基礎的演算法所求出的解，經常陷於局部最佳解，故採用TS技術來克服此現象。以 TS 技術為基礎的演算法，使用了區間式的鄰近結構和分散式策略，計算結果顯示，以 TS 技術為基礎的演算法較 DP 所發展的演算法為佳。
對於多目標之流程型工廠排程問題，我們也以TS技術來發展演算法。本研究所考慮的多目標有兩組，一是最大完工時間、總流程時間和機器的總閒置時間；另一是最大完工時間、總流程時間和總延遲時間。求解此問題的 TS 技術之演算法，主要是運用了簡易的鄰近結構，以及加強型與分散式的長期搜尋策略。計算結果顯示，此TS技術之啟發演算法較已發展出的GA演算法為佳。

Three prominent techniques, genetic algorithm (GA), simulated annealing (SA) and tabu search (TS), for finding near optimal solutions to combinatorial optimization problems have been used widely. These techniques are called meta-heuristics or general heuristics. In this research, we first introduce a basic version of each method, give indications about tuning parameters, and compare them. Then we select one of the three methods, tabu search, to solve two scheduling problems. The first problem is a single-machine scheduling problem with major and minor setups; the second problem is a permutation flow-shop scheduling problem with multiple objectives. We propose heuristics based on TS to compare with the existing heuristics.
For the first problem, we apply dynamic programming (DP) and TS to develop two heuristics, respectively. The performances of both heuristics dealing with small- or medium-sized problems are well. But for large-sized problems, the heuristic based on DP often traps in local optimum. Therefore, we try to deploy TS technique to overcome the problem. The TS based heuristic uses block neighborhoods and diversification. According to computational results, the performance of TS based heuristic is superior to the DP based heuristic.
The second problem, flow shop scheduling with multiple objectives, is frequently encountered in practice. We also develop a TS based heuristic to solve the problem. In particular, two problems with triple-criteria are under consideration, i.e., the minimization of makespan, total flow time, and total idle time, and the minimization of makespan, total flow time, and total tardiness. A heuristic based on TS technique is developed for the problems. The heuristic suggests a simple technique for generating neighborhoods of a given sequence and adopts a combined scheme for intensification and diversification, using frequency-based memory to search a new region. Computational results show that the heuristic is better than two existing genetic algorithm based heuristics.

摘 要i
誌 謝iv
目 錄v
圖 目 錄vii
表 目 錄viii
第一章 緒論1
1.1 研究動機1
1.2 研究範疇與目的3
1.3 研究架構4
第二章 局部搜尋法7
2.1 遞減（增）搜尋法7
2.2 基因演算法8
2.3 模擬退火法12
2.4 塔布搜尋法14
2.5 搜尋方法之比較16
第三章 塔布搜尋法18
3.1 起始解18
3.2 短期搜尋策略19
3.2.1 鄰域和移步19
3.2.2 塔布表23
3.2.3 期望水準26
3.3 長期搜尋策略26
3.4 塔布搜尋架構及流程27
第四章 雙重設置時間之單機排程的求解策略30
4.1 單機排程之文獻探討30
4.2 問題的假設與定義32
4.3 動態規劃法為基礎之啟發式演算法33
4.3.1 動態規劃模式的建立34
4.3.2HA1演算程序35
4.3.3HA1例子說明37
4.3.4HA1演算結果分析40
4.4 塔布搜尋法為基礎之演算法46
4.4.1 短期搜尋策略47
4.4.2 分散型之長期搜尋策略及停止條件53
4.5HA2之演算程序53
4.6HA2和HA1演算結果比較分析54
第五章 多目標之流程型工廠的求解策略59
5.1 流程型工廠排程之文獻探討59
5.2 問題的假設與定義61
5.3 以TS為基礎的演算法62
5.3.1 起始解62
5.3.2 短期搜尋策略63
5.3.3 長期搜尋策略68
5.3.4 停止條件69
5.3.5 演算法的特色與流程70
5.4 計算結果70
第六章 結論與未來的研究方向78
6.1 結論78
6.2 未來研究方向80
參考文獻82

[1] Adenso-Diaz, B. (1992), “Restricted neighbourhood in the tabu search for the flowshop problem,” European Journal of Operational Research, 62, 27-37.
[2] Ahn, B. H. and Hyun, J. H. (1990), “Single facility multi-class job scheduling,” Computers and Operations Research, 17, 265-272.
[3] Armentano, V. A. and Ronconi, D. P. (1999), “Tabu search for tardiness minimization in flowshop scheduling problems,” Computers and Operations Research, 26, 219-235.
[4] Belarmino, A. D. (1992), “Restricted neighborhood in the tabu search for the flowshop problem,” European Journal of Operational Research, 62, 27-37.
[5] Ben-Daya, M., and Al-Fawzan, M. (1998), “A tabu search approach for the flow shop scheduling problem,” European Journal of Operational Research, 109, 88-95.
[6] Burdett, R. L. and Kozan E. (2000), “Envolutionary algorithms for flowshop sequencing with non-unique jobs,” International Transactions in Operational Research, 7, 401-418.
[7] Campbell, H. G., Dudek, R. A., and Smith, M. L. (1970), “A heuristic algorithm for job machine sequencing problem,” Management Science, 16, B-630-637.
[8] Carlton, W. B. and Barnes, J. W. (1996), “A Note on Hashing Function and Tabu Search Algorithm,” European Journal of Operational Research, 95, 237-239.
[9] Cerny, V. (1985), “Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm,” Journal of Optimization Theory and Applications, 45, 45-51.
[10] Chen, C. L., Vempati, V. S., and Aljaber, N. (1995), “An application of genetic algorithms for flow shop problems,” European Journal of Operational Research, 80, 389-396.
[11] Daniels, R. L. and Mazzola, J. B. (1993), “A tabu-search heuristic for the flexible-resource flow shop scheduling problem,” Annals of Operations Research, 41, 207-230.
[12] Dannenbring, D. G. (1977), “An evaluation of flow-shop sequencing heuristics,” Management Science, 23, 1174-1182.
[13] Dudek, R. A., Panwalkar, S. S., and Simth M. L. (1992), “The lessons of flowshop scheduling research,” Operations Research, 40, 7-13.
[14] Gangadharan, R. and Rajendran, C. (1994), “A simulated annealing heuristic for scheduling in a flowshop with bicriteria,” Computers and Industrial Engineering, 27, 473-476.
[15] Geiger, C. D., Kempf, K. G., and Uzsoy, R. (1997), “A tabu search approach to scheduling an automated wet etch station,” Journal of Manufacturing Systems, 16, 102-116.
[16] Glover, F. (1989), “Tabu search-part I,” ORSA Journal on Computing, 1, 190-206.
[17] Glover, F. (1990), “Tabu search: a tutorial,” Interfaces, 20, 74-94.
[18] Glover, F. (1990), “Tabu search-part II,” ORSA Journal on Computing, 2, 4-32.
[19] Glover, F. (1993), “A user’s guide tabu search,” Annals of Operations Research, 41, 3-28.
[20] Grabowski, J. and Pempera, J. (2000), “Sequencing of jobs in some production system,” European Journal of Operational Research, 125, 535-550.
[21] Gupta, J. N. D. (1984), “Optimal schedules for single facility with classes,” Computers and Operations Research, 11, 409-413.
[22] Gupta, J. N. D. (1988), “Single facility scheduling with multiple job classes,” European Journal of Operational Research, 33, 42-45.
[23] Gupta, J. N. D. (1988), “Two stage hybrid flowshop scheduling problem,” Journal of the Operational Research Society, 39, 359-364.
[24] Gupta, J. N. D. and Tunc, E. A. (1994), “Scheduling a two-stage hybrid flowshop with separable setup and removal times,” European Journal of Operational Research, 77, 415-428.
[25] Haouari, M. and M’Hallah, R. (1997), “Heuristic algorithms for the two-stage hybrid flowshop problem,” Operations Research Letters, 21, 43-53.
[26] Held, M. and Karp, R. M. (1962), “Dynamic Programming Approach to Sequencing Problem,” SIAM, 19, 196-210.
[27] Ho, J. C. and Chang, Y. L. (1991), “A new heuristic for the n-job, m-machine flow-shop problem,” European Journal of Operational Research, 52, 194-202.
[28] Holland, J. (1975), “Adaptation in natural and artificial systems,” University of Michigan Press, Ann Arbor.
[29] Ishibuchi, H., Misaki, S., and Tanaka, H. (1995), “Modified simulated annealing algorithms for the flow shop sequencing problem,” European Journal of Operational Research, 81, 388-398.
[30] James R. J. W. and Buchanan, J. T. (1998), “Performance enhancement to tabu search for early/tardy scheduling problem,” European Journal of Operational Research, 106, 254-265.
[31] Kim, Y. D. (1993), “Heuristics for flowshop scheduling problems minimizing mean tardiness,” Journal of the Operational Research Society, 44, 19-28.
[32] Kirkpatrick, S., Gelatt, Jr., C. D, and Vecchi, M. P. (1983), “Optimization by simulated annealing,” Science, 220, 671-680.
[33] Koulamas, C. (1998), “A new constructive heuristic for the flow shop scheduling problem,” European Journal of Operational Research, 105, 66-71.
[34] Laguna, M., Barner, J. W., and Glover, F. W. (1991), “Tabu search methods for single machine scheduling problem,” Journal of Intelligent Manufacturing, 2, 63-74.
[35] Liao, C. J. and Liao, L. M. (1997), “Single facility scheduling with major and minor setups,” Computers and Operations Research, 24, 169-178.
[36] Linn, R. and Zhang, W. (1999), “Hybrid flow shop scheduling: a servey,” Computers and Industrial Engineering, 37, 57-61.
[37] Lopez, L., Carter, M. W. and Gendreau, M. (1998), “The hot strip mill production scheduling problem: a tabu search approach,” European Journal of Operational Research, 106, 317-335.
[38] Metropolis, N., Rosenblush, A., Rosenblush, M., Teller, A., and Teller, E. (1953), “Equation of state calculations by fast computing machines,” Journal of Chemical Physics, 21, 1087-1092.
[39] Michalewicz, Z. (1994), “Genetic algorithms + data structures = evolution programs,” 2nd ed., NY: Springer-Verlag.
[40] Moccellin, J. V. (1995), “A new heuristic method for the permutation flow shop scheduling problem,” Journal of the Operational Research Society, 46, 883-886.
[41] Moccellin, J. V., and Nagano, M. S. (1998), “Evaluating the performance of tabu search procedures for flow shop sequencing,” Journal of the Operational Research Society, 49, 1296-1302.
[42] Morizawa, K., Nagasawa, H., and Nishiyama, N. (1994), “Complex random sample scheduling and its application to an problem,” Computers and Industrial Engineering, 27, 23-26.
[43] Murata, T., Ishibuchi, H., and Tanaka, H. (1996), “Genetic algorithms for flowshop scheduling problems,” Computers and Industrial Engineering, 30, 1061-1071.
[44] Murata, T., Ishibuchi, H., and Tanaka, H. (1996), “Multi-objective genetic algorithm and its applications to flowshop scheduling,” Computers and Industrial Engineering, 30, 957-968.
[45] Nagar, A., Haddock, J., and Heragu, S. (1995), “Multiple and bicriteria scheduling: a literature survey,” European Journal of Operational Research, 81, 88-104.
[46] Nawaz, M., Encore, E. E. and Ham, I. (1983), “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem,” Omega, Journal of Management Science, 11, 91-95.
[47] Norman, B. A. (1999), “Scheduling flowshops with finite buffers and sequence-dependent setup times,” Computers and Industrial Engineering, 36, 163-177.
[48] Nowicki, E. (1999), “The permutation flow shop with buffers: a tabu search approach,” European Journal of Operational Research, 116, 205-219.
[49] Nowicki, E. and Smutnicki, C. (1996), “A fast tabu search algorithm for the permutation flow-shop problem,” European Journal of Operational Research, 91, 160-175.
[50] Nowicki, E. and Smutuicki, C. (1998), “The flow shop with parallel machines: a tabu search approach,” European Journal of Operational Research, 106, 226-253.
[51] Nowicki, E., and Zdrzalka, S. (1996), “Single machine scheduling with major and minor setup times: a tabu search approach,” Journal of the Operational Research Society, 47, 1054-1064.
[52] Ogbu, F. A. and Smith, D. K. (1992), “Simulated annealing for the permutation flowshop problem,” Omega, 19, 64-67.
[53] Ogbu, F. A. and Smith, D. K. (1990), “The application of the simulated annealing algorithm to the solution of the flowshop problem,” Computers and Operations Research, 17, 243-253.
[54] Osman, I. H. and Potts, C. N. (1989), “Simulated annealing for permutation flow-shop scheduling,” Omega, Journal of Management Science, 17, 551-557.
[55] Ow, P. S. (1985), “Focused scheduling in proportionate flowshops,” Management Science, 31, 852-869.
[56] Pirlot, M. (1996), “General local search methods,” European Journal of Operational Research, 92, 493-511.
[57] Psaraftis, H. N. (1980), “A dynamic programming approach for sequencing groups of identical jobs,” Operations Research, 28, 1347-1359.
[58] Rajendran C. and H. Ziegler (1999), “Heuristic for scheduling in flowshops and flowline-dased manufacturinf cells to minimize the sum of weighted flowtime and weighted tardiness of jobs,” Computers and Industrial Engineering, 37, 671-690.
[59] Rajendran, C. (1995), “Heuristics for scheduling in flowshop with multiple objectives,” European Journal of Operational Research, 82, 540-555.
[60] Rajendran, C. and Chaudhuri, D. (1992), “An efficient heuristic approach to the scheduling of jobs in a flowshop,” European Journal of Operational Research, 61, 318-325.
[61] Rajesh, G. and Rajendran, C. (1994), “A simulated annealing heuristic for scheduling in a flowshop with bicriteria,” Computers and Industrial Engineering, 27, 473-476.
[62] Raman, N. (1995), “Minimum tardiness scheduling in flow shops: construction and evaluation of alternative solution approach,” Journal of Operations Management, 12, 131-151.
[63] Reeves, C. L. (1995), “A genetic algorithm for flowshop sequencing,” Computers and Operations research, 22, 5-13.
[64] Reeves, C. R. (1993), “Improving the efficiency of tabu search for machine sequencing problems,” Journal of the Operational Research Society, 44, 375-382.
[65] Sridhar, J. and Rajendran, C. (1996), “Scheduling in flowshop and cellular manufacturing systems with multiple objectives--a genetic algorithm approach,” Production Planning and Control, 7, 374-382.
[66] Taillard, E. (1990), “Some efficient heuristic methods for flow shop sequencing problem,” European Journal of Operational Research, 47, 65-74.
[67] Tang, C. S. (1990), “Scheduling batches on parallel machine with major and minor setups,” European Journal of Operational Research, 46, 28-37.
[68] Wang, C., Chu, C., and Proth, J. M. (1997), “Heuristic approaches for scheduling problems,” European Journal of Operational Research, 96, 636-644.
[69] Webster S. and Baker, K. R. (1995), “Scheduling groups of jobs on a single machine,” Operations Research, 43, 692-703.
[70] Widmer, M. and Hertz, A. (1989), “A new heuristic method for the flow shop sequencing problem,” European Journal of Operational Research, 41, 186-193.
[71] Woodruff, D. L. and Zemel, E. (1993), “Hashing vectors for tabu search,” Annals of Operations Research, 41, 123-137.
[72] Yeh, W. C. (1999), “A new branch-and-bound approach for the n/ 2/ flowshop/ flowshop scheduling problem,” Computers and Operations Research, 26, 1293-1310.
[73] Zegordi, S., Itoh, H., K., and Enkawa, T. (1995), “Minimizing makespan for flow shop scheduling by combining annealing with sequencing knowledge,” European Journal of Operational Research, 85, 515-531.