臺灣人文及社會科學引文索引資料庫系統

:::

詳目顯示

回上一頁
第 1 筆 / 總合 1 筆   第一頁 上一頁 下一頁 最後一頁
/1頁
題名：塔布搜尋法求解排程問題之研究
作者：廖麗滿
作者(外文)：Liao, Li-Man
校院名稱：國立臺灣科技大學
系所名稱：工業管理系
指導教授：廖慶榮
學位類別：博士
出版日期：2001
主題關鍵詞：共通式演算法；基因演算法；模擬退火法；塔布搜尋法；單機；主要設置時間；次要設置時間；流程型工廠；Meta-heuristic；Genetic Algorithm；Simulated Annealing；Tabu Search；Single Machine；Major Setup；Minor Setup；Flow Shop
原始連結：連回原系統網址new window
相關次數：
  • 被引用次數被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:0
  • 點閱點閱:2
三個尋找接近最佳解之優異技術：基因演算法 (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.
[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.
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
QR Code
QRCODE

臺灣人文及社會科學引文索引資料庫

目前上線人數：1488（臺灣：1441，外國：47） ／ 本年度總使用人次：2488187 ／ 訪客人次（自102年09月）：68297206
國家圖書館著作權聲明 Copyright © 2013 All rights reserved.
本館地址: 100201臺北市中山南路20號． 本館地圖及交通資訊．
總機：(02)23619132．最佳瀏覽解析度為1024x768以上