簡易檢索 / 詳目顯示

研究生: 蘇啟祥
Chi-shiang Su
論文名稱: 考量工件運輸與機器維修時間之雙平行機生產排程研究
Two parallel machines scheduling problems with job delivery coordination and availability constraint
指導教授: 潘昭賢
Chao-Hsien Pan
許總欣
Tsung-Shin Hsu
口試委員: 林逾先
none
葉瑞徽
none
廖慶榮
none
林義貴
none
陳禎祥
none
學位類別: 博士
Doctor
系所名稱: 管理學院 - 工業管理系
Department of Industrial Management
論文出版年: 2010
畢業學年度: 99
語文別: 中文
論文頁數: 94
中文關鍵詞: 生產排程供應鏈管理啟發式法則最大完成時間兩個相同平行機時間複雜度受限時間
外文關鍵詞: Two identical parallel machines, Complexity theory; Availability constraint
相關次數: 點閱:413下載:7
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

在一個快速變遷的現代社會,企業競爭有轉向供應鏈整合的趨勢;過去,生產排程研究只定位在衡量生產階段各種指標,此已無法滿足實際情況,應擴展延伸至生產之後的運送階段;同時對於現今製造業而言,為獲取更大競爭利益,加強供應鏈間團隊整合與協調,已成為重要策略。本論文即在探討兩個以最大完工時間極小化為目標,考量工件運送情況下兩個相同平行機生產排程之指數複雜度(NP-hard)問題。
第一個問題,主要在考量每個工件尺寸大小不同,工件必須在兩個相同平行機中任一部機器完成加工,之後再輸送至單一消費者。這問題最早是由Chang 和 Lee(2004)所提出,Chang等學者提出最差/最佳解比值為2之法則。Zhong(2007)等學者進一步研究改善,提出最差/最佳解比值為5/3之法則。本研究提出一個新法則,除兩個特例其最差/最佳解比值為8/5外,其餘均為63/40。
第二個問題,本論文研究兩階段生產排程指數複雜度(NP-hard)問題,即工件必須在兩個相同平行機中任一部機器完成加工,之後再輸送至單一消費者,且其中一台機器存在ㄧ段因維修而無法運作之時間。這問題最早是由Wang 和 Cheng(2007)所提出,並研究提出最差/最佳解比值為5/3之法則。本研究提出一個新法則,其最差/最佳解比值為3/2。


In a rapid changing environment, the way of competition among enterprises has a tendency towards competing between supply chain systems instead of competing between individual companies. Traditional scheduling models which only address the sequence of jobs to be processed at the production stage under some criteria are no longer suitable and should be extended to cope with the distribution stage after production. Emphasizing on the coordination and the integration among various members of a supply chain has become one of the vital strategies for the modern manufacturers to gain competitive advantages. This paper studies two NP-hard problem of the two-stage scheduling in which jobs are processed by two identical parallel machines and delivered to a customer with the objective of minimizing the makespan
First, this study focuses mainly on a class of two identical parallel machines problem, in which jobs need to be delivered to single customer by a vehicle after their production stages and jobs size are different. The problem was first proposed by Chang and Lee(2004). Chang et al. presented a polynomial time algorithm with a worst-case ratio of 2. Zhong et al. [53] presented an improvement algorithm for the problem and reduced the worst-case ratio to 5/3. The purpose of this paper is to propose a new algorithm which leads to a best possible solution with a worst-case ratio of 63/40, except for the two particular cases where CMH3/C*  8/5.
Second, this paper studies the NP-hard problem of the two-stage scheduling in which jobs are processed by two identical parallel machines and delivered to a customer. We consider one of machines that exists an unavailable interval due to preventive maintenance. The problem was first proposed by Wang and Cheng(2007) and they proposed an algorithm H2 with a worst-case ratio of 5/3. We propose a new algorithm which leads to a best possible solution with a worst-case ratio of 3/2.

中文摘要I 英文摘要III 誌謝V 目錄VII 表目錄X 圖目錄XI 第一章 緒論1 1.1研究背景1 1.2研究動機、範圍與目的2 1.3研究限制與假設4 1.4研究內容與架構5 第二章 文獻探討7 2.1運送問題之生產排程7 2.2停機維護問題之生產排程12 第三章 考量運送問題與工件容量大小之兩個相同平行機問題14 3.1符號說明14 3.2 問題描述與相關研究16 3.3 Chang 和 Lee(2004)所提法則H217 3.4 Zhong, Do’sa 和Tan(2007)所提法則MH218 3.5 新法則MH3介紹21 3.6 範例演算25 3.7演算與證明31 3.8計算時間比較46 3.9小結47 第四章 考量運送與機器維護時間之兩個相同平行機問題49 4.1符號說明49 4.2問題描述與相關研究51 4.3 Wang 和 Cheng(2007)所提法則H252 4.4 新法則MH253 4.5 範例演算56 4.6演算與證明60 4.7計算時間比較67 4.8小結68 第五章 結論與未來研究方向69 5.1結論69 5.2未來研究方向70 參考文獻74 作者簡介80

[1]Chang, Y.C. and Lee, Y.L. (2004) Machine scheduling with job delivery coordination. European Journal of Operational Research, 158, 470-487.
[2]Chen, J.S. (2010) Integration of job scheduling with delivery vehicles routing. Information Technology Journal, 9(6), 1202-1206.
[3]Chen, Z.L. (2010) Integrated Production and Outbound Distribution Scheduling: Review and Extensions. Operations Research. 58, 130-148.
[4]Chen, Z.L. and Vairaktarakis, G.L. (1994) Integrated scheduling of production and distribution operations. Management Science, 51, 614-628.
[5]Cheng, T.C.E. and Gordon, V.S. (1994) Batch delivery scheduling on a single machine. Journal of the Operational Research Society, 45, 1211-1215.
[6]Cheng, T.C.E., Gordon, V.S. and Kovalyov, M.Y. (1996) Single machine scheduling with batch deliveries. European Journal of OperationalResearch, 94, 277-283.
[7]Cheng, T.C.E. and Kahlbacher, H.G. (1993) Scheduling with delivery and earliness penalties. Asia-Pacific Journal of Operational Research, 10, 145-152.
[8]Chung, D., Lee, K., Shin, K., and Park, J. (2005) A new approach to job shop scheduling problems with due date constraints considering operation subcontracts. International Journal of Production Economics, 98, 238–250
[9]Ganesharajah, T., Hall, N.G. and Sriskandarajah, C. (1998) Design and operational issues in AGV-served manufacturing systems. Annals of Operations Research, 76, 109-154.
[10]Gharbi, A. and Haouari, M. (2002) Minimizing makespan on parallel machines subject to release dates and delivery times. Journal of Scheduling, 5, 329-355.
[11]Garcia, J. M. and Lozano, S. (2005) Production and vehicle scheduling for ready-mix operations. Computers and Industrial Engineering, 46, 803-816.
[12]Gharbi, A. and Haouari, M. (2005) Optimal parallel machines scheduling with availability constraints. Discrete Applied Mathematics, 148, 63–87.
[13]Hall, L.A. and Shmoys, D.B. (1992) Jackson’s rule of single-machine scheduling: Making a good heuristic better. Mathematics of Operations Research, 17, 22-35.
[14]He, Y., Zhong, W. and Gu, H. (2006) Improved algorithms for two single machine scheduling problems. Theoretical Computer Science, 363, 257-265.
[15]Ji, M., He, Y. and Cheng, T. C. E. (2007) Batch delivery scheduling with batch delivery cost on a single machine. European Journal of OperationalResearch, 176, 745-755.
[16]Johnson, SM. (1954) Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61-68.
[17]Kellerer, H. and Pferschy, U. (1998) A new fully polynomial approximation scheme for the knapsack problem. Lecture Notes in Computer Science, 1444, 123-134.
[18]Kise, H. (1991) On an automated two-machine flowshop scheduling problem with infinite buffer. Journal of the Operations Research Society of Japan, 34, 354-361.
[19]Lawler, E. (1979) Fast approximation algorithms for knapsack problems. Mathematics of Operations Research, 4, 339-356.
[20]Lee, C.Y. (1991) Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathrmatics, 30, 53-61.
[21]Lee, C.Y. (1996) Machines scheduling with an availability constraint. Journal of Global Optimization, 9, 395-416.
[22]Lee, C.Y. and Chen, Z.L. (1999) Two-machines flowshop scheduling with availability constraints. European Journal of Operational Research, 114, 420-429.
[23]Lee, C.Y. and Chen, Z.L. (2001) Machine scheduling with transportation considerations. Journal of Scheduling, 4, 3-24.
[24]Lee, Y.H., Jeong, C.S. and Moon, C. (2002) Advanced planning and scheduling with outsourcing in manufacturing supply chain. Computers and Industrial Engineering, 43, 351–374.
[25]Lee, C.-Y., Lei, L. and Pinedo, M. (1997) Current trends in deterministic scheduling. Annals of Operations Research, 70, 1-41.
[26]Lee, I. S. and Sung, C. S. (2007) Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed. European Journal of Operational Research, 186, 931–952.
[27]Lin, C.H. and Liao, C.J. (2007) Makespan minimization for two parallel machines with an unavailable period on each machine. International Journal of Advanced Manufacturing Technology, 33, 1024–1030
[28]Liao, C.T., Shyur, D.L. and Lin, C.H. (2005) Makespan minimization for two parallel machines with an availability constraint. European Journal of Operational Research, 160, 445-456.
[29]Lu, L., Yuan, J. and Zhang, L. (2008) Single machine scheduling with release dates and job delivery to minimize the makespan. Theoretical Computer Science, 393, 102-108.
[30]Maggu, P.L. and Das, G. (1980) On 2×n sequencing problem with transportation times of jobs. Pure and Applied Mathematika Sciences, 12, 1-6.
[31]Maggu, P.L., Das, G. and Kumar, R. (1981) On equivalent job-for-job block in 2×n sequencing problem with transportation times. Journal of the Operations Research Society of Japan, 24, 136-146.
[32]Mastrolilli, M. (2003) Efficient approximation schemes for scheduling problems with release dates and delivery times. Journal of Scheduling, 6, 521-531.
[33]Mellouli, R., Sadfi, C., Chu, C.B. and Kacem, I. (2009) Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times. European Journal of Operational Research, 197, 1150–1165.
[34]Pan, C.H., Wu, C.L, Huang, H.C. and Su, C.S. (2009) Coordinating Scheduling with Batch Deliveries in a Two-Machine Flow Shop. International Journal of Advanced Manufacturing Technology, 40, 607-616.
[35]Panwalkar, S.S. (1991) Scheduling of a two machine flowshop with travel time between machines. Journal of the Operational Research Society, 42, 609-613.
[36]Pinedo, M. (1995) Scheduling: Theory, Algorithms, and Systems. Prentice-Hall: Englewoods Cliffs, NJ.
[37]Potts, C.N. (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research, 28, 1436-1441.
[38]Potts, C.N. and Kovalyov, M.Y. (2000) Scheduling with batching: A review. European Journal of Operational Research, 120, 228-249.
[39]Potts, C.N. and Van Wassenhove, L.N. (1992) Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. Journal of the Operational Research Society, 43, 395-406.
[40]Qi, X. (2011) Outsourcing and production scheduling for a two-stage flow shop. International Journal of Production Economics, 129, 43-50.
[41]Schmidt, G. (1984) Scheduling on semi-identical process. Zeitschrift fur Operational Research, 28, 153-162.
[42]Simchi-Levi, D. (1994) New worst-case results for the bin packing problem. Naval Research Logistics, 41, 579-585.
[43]Soukhal, A., Oulamara, A. and Martineau, P. (2005) Complexity of flow shop scheduling problems with transportation constraints. European Journal of Operational Research, 161, 32-41.
[44]Stevens, J.W. and Gemmill, D.D. (1997) Scheduling a two-machine flowshop with travel times to minimize maximum lateness. International Journal of Production Research, 35, 1-15.
[45]Stern, H.I. and Vitner, G. (1990) Scheduling parts in a combined production-transportation work cell. Journal of the Operational Research Society, 41, 625-632.
[46]Sun Lee, I. and Yoon, S.H. (2010) Coordinated scheduling of production and delivery stages with stage-dependent inventory holding costs. Omega, 38, 509-521.
[47]Woeginger, G.J. (1994) Heuristics for parallel machine scheduling with delivery times. Acta Informatica, 31, 503-512.
[48]Wang, H. and Lee, C.Y. (2005) Production and Transport Logistics Scheduling with Two Transport Mode Choices. Naval Research Logistics, 52, 796-809.
[49]Wang, S. and Yu, J. (2009) An effective heuristic for flexible job-shop scheduling problem with maintenance activities. Computers and Industrial Engineering, 59, 436-447.
[50]Wang, X. and Cheng, T. C. E. (2009) Logistics scheduling to minimize inventory and transport costs. International Journal of Production Economics, 121, 266-273.
[51]Wang, Xiuli. and Cheng, T. C. E. (2007) Machine Scheduling with an Availability Constraint and Job Delivery Coordination. Naval Research Logistics, 54, 11-20.
[52]Yue, M. (1991) A simple proof of the inequality FFD(L)  11OPT(L)/9 + 1 L, for the FFD bin-packing algorithm. Acta Mathematica Applicate Sinica, 7, 321-331.
[53]Zhong, W., Do’sa, G. and Tan, Z. (2007) On the machine scheduling problem with job delivery coordination. European Journal of Operational Research, 182, 1057-1072.

QR CODE