| dc.contributor.advisor | 陳春龍 | zh_TW |
| dc.contributor.advisor | Chen, Chuen Lung | en_US |
| dc.contributor.author (Authors) | 黃文品 | zh_TW |
| dc.contributor.author (Authors) | Huang, Wen Pin | en_US |
| dc.creator (作者) | 黃文品 | zh_TW |
| dc.creator (作者) | Huang, Wen Pin | en_US |
| dc.date (日期) | 2007 | en_US |
| dc.date.accessioned | 18-Sep-2009 14:38:26 (UTC+8) | - |
| dc.date.available | 18-Sep-2009 14:38:26 (UTC+8) | - |
| dc.date.issued (上傳時間) | 18-Sep-2009 14:38:26 (UTC+8) | - |
| dc.identifier (Other Identifiers) | G0943560141 | en_US |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/35286 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 資訊管理研究所 | zh_TW |
| dc.description (描述) | 94356014 | zh_TW |
| dc.description (描述) | 96 | zh_TW |
| dc.description.abstract (摘要) | 本研究將探討非等效平行機台問題中具備順序相依整備時間及不同開始工作時間（Unequal ready-time）之情況，並以最小化總延遲工件權重數為目標值，其目的在改善非等效平行機台問題應用於實際產業中製造環境裡所面對的各項挑戰，如印刷電路板的鑽孔和半導體的測試製程。因本研究欲求解之問題是屬於NP - Hard problems 性質之尋優問題，故利用啟發式方法(heuristics)求解為合適的選擇。此外，本研究計畫開發混合式巨集啟發式方法來求解非等效平行機台問題，主要以禁忌搜尋法為主，在鄰域的搜尋上，也藉由變動鄰域尋優法能夠透過鄰域轉換的機制，進而找出更多好的解。由於啟發式方法對於尋優問題常需花費許多時間來計算才能獲得更好的解，為確保增進求解效率與品質，將針對問題特性開發數種初始解產生法，並也嘗試定義幾個能夠減少尋找鄰近解之鄰域。在後續求解改善的過程中，主要整合變動鄰域(VND)及禁忌(TS)巨集啟發式演算法搜尋最佳解。此外，為了評估本文推導之演算法效能，本研究利用設定之條件隨機產生適量模擬現場狀況的測試情境，進而比較本研究所提出之混合式巨集啟發式方法及標準禁忌搜尋法在不同情境下之表現。 | zh_TW |
| dc.description.abstract (摘要) | The problem considered in this paper is a set of independent jobs on unrelated parallel machines with sequence-dependent setup times and with unequal ready times so as to minimize total weighted tardy jobs. These problems can be found in real-life manufacturing environments, such as PCB fabrication drilling operations and semiconductor wafer manufacturing dicing. Since the problems are NP-hard in the strong sense, heuristics are an acceptable practice to finding good solutions. A hybrid meta-heuristics are proposed to solve this scheduling problem. The proposed heuristics belong to a type of solution improvement heuristic; therefore, the heuristics start with an effective initial feasible solution then a meta-heuristic is applied to improve the solution. To enhance both the efficiency and efficacy of the heuristics, several different initial solution generators, based on the characteristics of problems, are developed. The meta-heuristic is a hybrid heuristic integrating the principles of Variable Neighborhood Descent approach (VND) and Tabu Search (TS). In order to evaluate the performance of the proposed heuristics, two sets of large number test scenarios will be designed to simulate practical shop floor problems. Computational experiments will be performed to compare the performance of the proposed heuristics, and a basic tabu search algorithm. The results show the proposed heuristic perform better than the basic tabu search algorithm. | en_US |
| dc.description.tableofcontents | 第一章 緒論 -1-1.1研究動機 -1-1.2研究目的 -4- 1.3研究範圍 -5-1.4研究架構與流程 -5-第二章 文獻探討 -8-2.1排程定義之相關研究 -8-2.1.1生產排程之種類 -9-2.1.2排程問題之作業型態 -9-2.1.3排程績效衡量標準 -12-2.2求解非等效平行機台排程問題之相關研究 -13-2.3考量開始工作時間排程問題之相關研究 -16-第三章 研究方法 -22-3.1 問題描述與假設條件 -22-3.2 初始解產生法(Initial solution generators) -23-3.3 鄰域結構(Neighborhood structures) -28-3.4 混合巨集啟發式演算法之建構 -29-3.4.1 變動鄰域尋優法 (VND Heuristic) -30-3.4.2 禁忌搜尋演算法(Tabu search) -31-3.4.3 混合巨集啟發式演算法 -33-第四章 實驗設計 -36-第五章 實驗結果 -39-第六章 結論與未來展望 -50-6.1.研究結論 -50-6.2.未來展望 -51-參考文獻 -53- | zh_TW |
| dc.format.extent | 101541 bytes | - |
| dc.format.extent | 169528 bytes | - |
| dc.format.extent | 129889 bytes | - |
| dc.format.extent | 119793 bytes | - |
| dc.format.extent | 333357 bytes | - |
| dc.format.extent | 211277 bytes | - |
| dc.format.extent | 795876 bytes | - |
| dc.format.extent | 147893 bytes | - |
| dc.format.extent | 156554 bytes | - |
| dc.format.extent | 142440 bytes | - |
| dc.format.extent | 210682 bytes | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.format.mimetype | application/pdf | - |
| dc.language.iso | en_US | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0943560141 | en_US |
| dc.subject (關鍵詞) | 總延遲工件權重數 | zh_TW |
| dc.subject (關鍵詞) | 非等效平行機台問題 | zh_TW |
| dc.subject (關鍵詞) | 順序相依整備時間 | zh_TW |
| dc.subject (關鍵詞) | 變動鄰域尋優法 | zh_TW |
| dc.subject (關鍵詞) | 禁忌演算法 | zh_TW |
| dc.subject (關鍵詞) | Weighted Number of Tardy Jobs | en_US |
| dc.subject (關鍵詞) | Unrelated Parallel Machines | en_US |
| dc.subject (關鍵詞) | Sequence-Dependent Setup | en_US |
| dc.subject (關鍵詞) | Variable Neighborhood Descent | en_US |
| dc.subject (關鍵詞) | Tabu Search | en_US |
| dc.title (題名) | 開發混合式巨集啟發式方法求解具順序相依整備時間之非等效平行機台排程問題 | zh_TW |
| dc.title (題名) | Hybrid Meta-Heuristics for the Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times | en_US |
| dc.type (資料類型) | thesis | en |
| dc.relation.reference (參考文獻) | 1. Anghinolfi, D., and Paolucci, M. (2007). “Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach”. Computers & Operations Research, 34, 3471–3490. | zh_TW |
| dc.relation.reference (參考文獻) | 2. Armentano, V.A., and Yamashita, D.S. (2000). “Tabu search for scheduling on identical parallel machines to minimize mean tardiness”. Journal of Intelligent Manufacturing, 11, 453–460. | zh_TW |
| dc.relation.reference (參考文獻) | 3. Azizoglu. M. and Kirka O. (1999). “Scheduling jobs on unrelated parallel machines to minimize regular total cost functions”. IIE Transactions, 31, pp.153–159. | zh_TW |
| dc.relation.reference (參考文獻) | 4. Bilge, Ü., Kıraç, F., Kurtulan, M., and Pekgün, P. (2004). “A tabu search algorithm for parallel machine total tardiness problem”. Computers and Operations Research, 31, 397–414. | zh_TW |
| dc.relation.reference (參考文獻) | 5. Bräysy, O., (2003). “A reactive variable neighborhood search for the vehicle-routing problem with time windows”. INFORMS Journal on Computing, 15, 347–368. | zh_TW |
| dc.relation.reference (參考文獻) | 6. Cao, D., Chen, M., Wan, G. (2005). “Parallel machine selection and job scheduling to minimize machine cost and job tardiness”. Computers and Operations Research, 32, 1995–2012. | zh_TW |
| dc.relation.reference (參考文獻) | 7. Chen, C.L. and Chen, C.L. (2006), “Designing a Tabu Search Algorithm for Unrelated Parallel Machines Problem with Total Weighted Tardy Jobs as the Objective”. The 36th CIE Conference on Computers & Industrial Engineering, pp. 1128-1135. | zh_TW |
| dc.relation.reference (參考文獻) | 8. Chen, J.F. (2006). “Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups”. International Journal of Advanced Manufacturing Technology, 29, 557–563. | zh_TW |
| dc.relation.reference (參考文獻) | 9. Chen, J.F., and Wu, T.H. (2006). “Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints”. Omega, 34(1), 81–89. | zh_TW |
| dc.relation.reference (參考文獻) | 10. Choi, S.W., Kim, Y.D., and Lee, G.C. (2005). “Minimizing total tardiness of orders with reentrant lots in a hybrid flowshop”. International Journal of Production Research, 43, 2149–2167. | zh_TW |
| dc.relation.reference (參考文獻) | 11. Conway, R. W., Maxwell W.L., and Miller L. W., (1967). “Theory of Scheduling”, Addison-Wesey, pp.42-51. | zh_TW |
| dc.relation.reference (參考文獻) | 12. Davidović, T., Hansen, P., and Mladenović, N. (2005). “Permutation based genetic, tabu and variable neighborhood search heuristics for multiprocessor scheduling with communication delays”. Asia-Pacific Journal of Operational Research, 22, 297–326. | zh_TW |
| dc.relation.reference (參考文獻) | 13. Fleszar, K., and Hindi, K.S. (2004). “Solving the resource-constrained project scheduling problem by a variable neighbourhood search”. European Journal of Operational Research, 155, 402–413. | zh_TW |
| dc.relation.reference (參考文獻) | 14. Fowler J. W., M. Pfund and J. N. D. Gupta. (2004). “A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems”. Journal of the Chinese Institute of Industrial Engineers, Vol. 21, No. 3, pp. 230-241. | zh_TW |
| dc.relation.reference (參考文獻) | 15. Ghirardi, M., and Potts, C.N. (2005). “Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach”. European Journal of Operational Research, 165, 457–467. | zh_TW |
| dc.relation.reference (參考文獻) | 16. Glass, C.A., Potts, C.N., and Shade, P. (1994). “Unrelated parallel machine scheduling using local search”. Mathematical and Computer Modelling, 20(2), 41–52. | zh_TW |
| dc.relation.reference (參考文獻) | 17. Glover, F. (1989). “Tabu search”, part I. ORSA Journal on Computing, 1, 190–206. | zh_TW |
| dc.relation.reference (參考文獻) | 18. Guinet, A. (1995). “Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria”. Journal of Intelligent Manufacturing, 6, 95–103. | zh_TW |
| dc.relation.reference (參考文獻) | 19. Hansen, P., and Mladenović, N., (2001). “Variable neighborhood search: principles and applications”. European Journal of Operational Research, 130, 449–467. | zh_TW |
| dc.relation.reference (參考文獻) | 20. Hansen, P., Mladenović, N., and Urošević, D. (2004). “Variable neighborhood search for the maximum clique”. Discrete Applied Mathematics, 145, 117–125. | zh_TW |
| dc.relation.reference (參考文獻) | 21. Helal, M., Rabadi, G., and Al-Salem, A. (2006). “A tabu search algorithm to minimize the makespan for the unrelated parallel machines scheduling problem with setup times”. International Journal of Operations Research, 3, 182–192. | zh_TW |
| dc.relation.reference (參考文獻) | 22. Ho, J.C., and Chang, Y.L., (1995). “Minimizing the number of tardy jobs for m-parallel machines”. European Journal of Operation Research, 84, 343–55. | zh_TW |
| dc.relation.reference (參考文獻) | 23. Hsieh, J.C., Chang, P.C., and Hsu, L.C. (2003). “Scheduling of drilling operations in printed circuit board factory”. Computers and Industrial Engineering, 44(3), 461–473. | zh_TW |
| dc.relation.reference (參考文獻) | 24. Huang, D., H. Guo, and N. Qian, (2005). “Hybrid Genetic Algorithm for Minimizing the Range of Lateness and Make-span on Non-identical Parallel Machines”. In Proceedings of IEEE International Conference on Neural Networks and Brain, Vol. 1, pp.150-154. | zh_TW |
| dc.relation.reference (參考文獻) | 25. Jeffery K. et al., (2002). “A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines”. Computers & Operations Research, Volume 30, Issue 7, June 2003, Pages 1087-1102. | zh_TW |
| dc.relation.reference (參考文獻) | 26. Kim, C.O., and Shin, H.J. (2003). “Scheduling jobs on parallel machines: a restricted tabu search approach”. International Journal of Advanced Manufacturing Technology, 22, 278–287. | zh_TW |
| dc.relation.reference (參考文獻) | 27. Kim, D.W., Kim, K.H., Jang, W., and Chen, F.F. (2002). “Unrelated parallel machine scheduling with setup times using simulated annealing”. Robotics and Computer Integrated Manufacturing, 18, 223–231. | zh_TW |
| dc.relation.reference (參考文獻) | 28. Kim, D.W., Na, D.G., and Chen F.F. (2003). “Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective”. Robotics and Computer Integrated Manufacturing, 19, 173–181. | zh_TW |
| dc.relation.reference (參考文獻) | 29. Kim, S. I., Choi, H. S., Lee, D. H. (2006) . “Tabu Search Heuristics for Parallel Machine Scheduling with Sequence-Dependent Setup and Ready Times”. Computational Science and Its Applications - ICCSA (3) : 728-737 | zh_TW |
| dc.relation.reference (參考文獻) | 30. Lancia, G. (2000). “Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan”. European Journal of Operational Research , 120, pp. 277–288. | zh_TW |
| dc.relation.reference (參考文獻) | 31. Lawler, E.L., and Moore, J.M. (1969). “A functional equation and its application to resource allocation and sequencing problems”. Management Science, 16, 77-84. | zh_TW |
| dc.relation.reference (參考文獻) | 32. Lee, G.C., Kim, Y.D., and Choi, S.W. (2004). “Bottleneck-focused scheduling for a hybrid flowshop”. International Journal of Production Research, 42, 165–181. | zh_TW |
| dc.relation.reference (參考文獻) | 33. Lee, Y.H., Bhaskaran, K., and Pinedo, M. (1997). “A heursitic to minimize the total weighted tardiness with sequence-dependent setups”. IIE Transactions, 29, 45–52. | zh_TW |
| dc.relation.reference (參考文獻) | 34. Liaw, C.F., Lin, Y.K., Cheng, C.Y., and Chen, M., (2003). “Scheduling unrelated parallel machines to minimize total weighted tardiness”. Computers and Operations Research, 30, 1777–1789. | zh_TW |
| dc.relation.reference (參考文獻) | 35. Logendran, R., McDonell, B., and Smucker, B., (2007). “Scheduling unrelated parallel machines with sequence-dependent setups”. Computers & Operations Research, 34, 3420–3438. | zh_TW |
| dc.relation.reference (參考文獻) | 36. M`Hallah, R., and Bulfin, R.L. (2005). “Minimizing the weighted number of tardy jobs on parallel processors”. European Journal of Operational Research, 160(2), 471–484. | zh_TW |
| dc.relation.reference (參考文獻) | 37. Mladenović, N., and Hansen, P., (1997). “Variable neighborhood search”. Computers & Operations Research, 24, 1097–1100. | zh_TW |
| dc.relation.reference (參考文獻) | 38. Moore, J.M. (1968). “An n job, one machine sequencing algorithm for minimizing the number of late jobs”. Management Science, 15, 102–109. | zh_TW |
| dc.relation.reference (參考文獻) | 39. Moreno-Pérez, J.A., Moreno-Vega, J.M., and Martín, I.R., (2003). “Variable neighborhood tabu search and its application to the median cycle problem”. European Journal of Operation Research, 151, 365–378. | zh_TW |
| dc.relation.reference (參考文獻) | 40. Osman, I, H and Kelly, J, P, (1996). “Meta-heuristics: an Overview in I.H.Osman, & Kelly,J, P (eds.), Meta-heuristics: Theory and Applications”, Kluwer Academic Publishers,Massachusetts, pp. 1-21. | zh_TW |
| dc.relation.reference (參考文獻) | 41. Park M.W. and Kim Y.D. (1997). “Search Heuristics for a Parallel Machine Scheduling Problem with Ready Times and Due Dates”. Computers ind. Engng Vol. 33, Nos 3-4, pp. 793-796. | zh_TW |
| dc.relation.reference (參考文獻) | 42. Piersma, N., and van Dijk, W. (1996). “A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search”. Mathematical and Computer Modelling, 24(9), 11–19. | zh_TW |
| dc.relation.reference (參考文獻) | 43. Polacek, M., Hartl, R.F., and Doerner, K. (2004). “A variable neighborhood search for the multi depot vehicle routing problem with time windows”. Journal of Heuristics, 10, 613–627. | zh_TW |
| dc.relation.reference (參考文獻) | 44. Rabadi, G.. (2006). “Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times”. Journal of Intelligent Manufacturing, 17, 85–97. | zh_TW |
| dc.relation.reference (參考文獻) | 45. Randhawa, S.U., and Kuo, C.H., (1997). “Evaluating scheduling heuristics for non-identical parallel processors”. International Journal of Production Research, 35, 969–981. | zh_TW |
| dc.relation.reference (參考文獻) | 46. Ribeiro, C.C., and Souza, M.C., (2002). “Variable neighborhood search for the degree-constrained minimum spanning tree problem”. Discrete Applied Mathematics, 118, 43–54. | zh_TW |
| dc.relation.reference (參考文獻) | 47. Rios-Mercado, R.Z., and Bard, J.F. (1998). “Heuristics for the flow line problem with setup costs”. European Journal of Operational Research, 110, 76–98. | zh_TW |
| dc.relation.reference (參考文獻) | 48. Silva, C., and Magalhaes, J.M. (2006). “Heuristic lot size scheduling on unrelated parallel machines with applications in the textile industry”. Computers & Industrial Engineering, 50, 76–89. | zh_TW |
| dc.relation.reference (參考文獻) | 49. Sivrikaya F. and Ulusoy G., (1999) “Parallel machine scheduling with earliness and tardiness penalties”. Computers & Operations Research, Volume 26, Issue 8, July 1999, Pages 773-787. | zh_TW |
| dc.relation.reference (參考文獻) | 50. Suresh, V., and Chaudhuri, D. (1994). “Minimizing maximum tardiness for unrelated parallel machines”. International Journal of Production Economics, 34, 223–229. | zh_TW |
| dc.relation.reference (參考文獻) | 51. Tsai, T. I (2007). “A genetic algorithm for solving the single machine earliness/tardinessproblem with distinct due dates and ready times” , International Journal of dvanced Manufacturing Technology 31, pp. 994-1000. | zh_TW |
| dc.relation.reference (參考文獻) | 52. Weng, M.X., Lu, J., and Ren, H. (2001). “Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective”. International Journal of Production Economics, 70, 215–226. | zh_TW |
| dc.relation.reference (參考文獻) | 53. Yu, L., Shih, H.M., Pfund, M., Carlyle, W.M., and Fowler, J.W. (2002). “Scheduling of unrelated parallel machines: an application to PWB manufacturing”. IIE Transactions, 34, 921–931. | zh_TW |
| dc.relation.reference (參考文獻) | 54. 田國興(2000)，「有設置時間之流程型工廠多階段平行機台總排程時間最小化問題」，中原大學工業工程學系碩士論文。 | zh_TW |
| dc.relation.reference (參考文獻) | 55. 林我聰(1994)，「現場排程專家系統—應用個體技術建立之研究」，財團法人資訊工業策進會，資訊與電腦出版社。 | zh_TW |
| dc.relation.reference (參考文獻) | 56. 林熙凱(2005)，「蟻群演算法於非等效平行機台之多階段流程型排程問題研究」，大葉大學工業工程與科技管理學系碩士論文。 | zh_TW |
| dc.relation.reference (參考文獻) | 57. 林靖國(2007)，「阻隔條件考量下具非等效平行機台之流程型排程問題研究」 ，大葉大學工業工程與科技管理學系碩士論文。 | zh_TW |
| dc.relation.reference (參考文獻) | 58. 吳思農(2004)，「模擬退火法於有限資源下不相關平行機台排程問題」，元智大學工業工程與管理學系碩士論文。 | zh_TW |
| dc.relation.reference (參考文獻) | 59. 洪正鴻(2003)，「非等效平行機台之多階段流程型排程求解模式建構」，大葉大學工業工程系碩士論文。 | zh_TW |
| dc.relation.reference (參考文獻) | 60. 曾毓文(2001)，「運用系統模擬與遺傳演算法從事非相關平行機器排程之研究」，台北科技大學生產系統工程與管理研究所碩士論文。 | zh_TW |
| dc.relation.reference (參考文獻) | 61. 黃俊龍(2005)，「應用模擬退火法規劃具有加工順序限制之非相關平行機台多目標排程」，屏東科技大學工業管理系碩士論文。 | zh_TW |
| dc.relation.reference (參考文獻) | 62. 熊詩敏(2007)，「結合優勢性質與基因遺傳演算法於具有整備時間之單機與非等效平行機台之研究」，元智大學工業工程與管理學系碩士論文。 | zh_TW |
| dc.relation.reference (參考文獻) | 63. 鄭志傑(2006)，「基因演算法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與管理學系碩士論文。 | zh_TW |
