English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 112721/143689 (78%)
Visitors : 49695599      Online Users : 585
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version
    政大機構典藏 > 商學院 > 資訊管理學系 > 學位論文 >  Item 140.119/35286


    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/35286


    Title: 開發混合式巨集啟發式方法求解具順序相依整備時間之非等效平行機台排程問題
    Hybrid Meta-Heuristics for the Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times
    Authors: 黃文品
    Huang, Wen Pin
    Contributors: 陳春龍
    Chen, Chuen Lung
    黃文品
    Huang, Wen Pin
    Keywords: 總延遲工件權重數
    非等效平行機台問題
    順序相依整備時間
    變動鄰域尋優法
    禁忌演算法
    Weighted Number of Tardy Jobs
    Unrelated Parallel Machines
    Sequence-Dependent Setup
    Variable Neighborhood Descent
    Tabu Search
    Date: 2007
    Issue Date: 2009-09-18 14:38:26 (UTC+8)
    Abstract: 本研究將探討非等效平行機台問題中具備順序相依整備時間及不同開始工作時間（Unequal ready-time）之情況，並以最小化總延遲工件權重數為目標值，其目的在改善非等效平行機台問題應用於實際產業中製造環境裡所面對的各項挑戰，如印刷電路板的鑽孔和半導體的測試製程。因本研究欲求解之問題是屬於NP - Hard problems 性質之尋優問題，故利用啟發式方法(heuristics)求解為合適的選擇。此外，本研究計畫開發混合式巨集啟發式方法來求解非等效平行機台問題，主要以禁忌搜尋法為主，在鄰域的搜尋上，也藉由變動鄰域尋優法能夠透過鄰域轉換的機制，進而找出更多好的解。由於啟發式方法對於尋優問題常需花費許多時間來計算才能獲得更好的解，為確保增進求解效率與品質，將針對問題特性開發數種初始解產生法，並也嘗試定義幾個能夠減少尋找鄰近解之鄰域。在後續求解改善的過程中，主要整合變動鄰域(VND)及禁忌(TS)巨集啟發式演算法搜尋最佳解。此外，為了評估本文推導之演算法效能，本研究利用設定之條件隨機產生適量模擬現場狀況的測試情境，進而比較本研究所提出之混合式巨集啟發式方法及標準禁忌搜尋法在不同情境下之表現。
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    11. Conway, R. W., Maxwell W.L., and Miller L. W., (1967). “Theory of Scheduling”, Addison-Wesey, pp.42-51.
    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.
    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.
    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.
    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.
    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.
    17. Glover, F. (1989). “Tabu search”, part I. ORSA Journal on Computing, 1, 190–206.
    18. Guinet, A. (1995). “Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria”. Journal of Intelligent Manufacturing, 6, 95–103.
    19. Hansen, P., and Mladenović, N., (2001). “Variable neighborhood search: principles and applications”. European Journal of Operational Research, 130, 449–467.
    20. Hansen, P., Mladenović, N., and Urošević, D. (2004). “Variable neighborhood search for the maximum clique”. Discrete Applied Mathematics, 145, 117–125.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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.
    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
    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.
    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.
    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.
    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.
    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.
    35. Logendran, R., McDonell, B., and Smucker, B., (2007). “Scheduling unrelated parallel machines with sequence-dependent setups”. Computers & Operations Research, 34, 3420–3438.
    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.
    37. Mladenović, N., and Hansen, P., (1997). “Variable neighborhood search”. Computers & Operations Research, 24, 1097–1100.
    38. Moore, J.M. (1968). “An n job, one machine sequencing algorithm for minimizing the number of late jobs”. Management Science, 15, 102–109.
    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.
    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.
    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.
    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.
    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.
    44. Rabadi, G.. (2006). “Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times”. Journal of Intelligent Manufacturing, 17, 85–97.
    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.
    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.
    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.
    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.
    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.
    50. Suresh, V., and Chaudhuri, D. (1994). “Minimizing maximum tardiness for unrelated parallel machines”. International Journal of Production Economics, 34, 223–229.
    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.
    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.
    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.
    54. 田國興(2000)，「有設置時間之流程型工廠多階段平行機台總排程時間最小化問題」，中原大學工業工程學系碩士論文。
    55. 林我聰(1994)，「現場排程專家系統—應用個體技術建立之研究」，財團法人資訊工業策進會，資訊與電腦出版社。
    56. 林熙凱(2005)，「蟻群演算法於非等效平行機台之多階段流程型排程問題研究」，大葉大學工業工程與科技管理學系碩士論文。
    57. 林靖國(2007)，「阻隔條件考量下具非等效平行機台之流程型排程問題研究」 ，大葉大學工業工程與科技管理學系碩士論文。
    58. 吳思農(2004)，「模擬退火法於有限資源下不相關平行機台排程問題」，元智大學工業工程與管理學系碩士論文。
    59. 洪正鴻(2003)，「非等效平行機台之多階段流程型排程求解模式建構」，大葉大學工業工程系碩士論文。
    60. 曾毓文(2001)，「運用系統模擬與遺傳演算法從事非相關平行機器排程之研究」，台北科技大學生產系統工程與管理研究所碩士論文。
    61. 黃俊龍(2005)，「應用模擬退火法規劃具有加工順序限制之非相關平行機台多目標排程」，屏東科技大學工業管理系碩士論文。
    62. 熊詩敏(2007)，「結合優勢性質與基因遺傳演算法於具有整備時間之單機與非等效平行機台之研究」，元智大學工業工程與管理學系碩士論文。
    63. 鄭志傑(2006)，「基因演算法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與管理學系碩士論文。
    Description: 碩士
    國立政治大學
    資訊管理研究所
    94356014
    96
    Source URI: http://thesis.lib.nccu.edu.tw/record/#G0943560141
    Data Type: thesis
    Appears in Collections:[資訊管理學系] 學位論文

    Files in This Item:

    File Description SizeFormat
    014101.pdf99KbAdobe PDF2759View/Open
    014102.pdf165KbAdobe PDF2882View/Open
    014103.pdf126KbAdobe PDF2927View/Open
    014104.pdf116KbAdobe PDF2786View/Open
    014105.pdf325KbAdobe PDF21117View/Open
    014106.pdf206KbAdobe PDF26504View/Open
    014107.pdf777KbAdobe PDF22509View/Open
    014108.pdf144KbAdobe PDF2841View/Open
    014109.pdf152KbAdobe PDF2853View/Open
    014110.pdf139KbAdobe PDF2791View/Open
    014111.pdf205KbAdobe PDF21224View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback