(34.229.64.28) 您好!臺灣時間:2021/05/06 07:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:周世杰
研究生(外文):ShieChieh Chou
論文名稱:三機組裝式流線型批次排程問題
論文名稱(外文):Batch Scheduling in a Three-Machine Assembly-Type Flowshop
指導教授:林妙聰林妙聰引用關係
指導教授(外文):Lin, Miao-Tsong
學位類別:碩士
校院名稱:銘傳大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:英文
論文頁數:30
中文關鍵詞:三機組裝式流線型批次排程完工時間下界經驗法則動態規劃演算法
外文關鍵詞:flowshopmakespanlower boundheuristic algorithmdynamic programmingNP-hardnessbatch scheduling
相關次數:
  • 被引用被引用:0
  • 點閱點閱:110
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
這篇論文所要探討的是三機組裝式流線型批次排程問題之完工時間最小化。在這個問題,第一台機器與第二台機器是一對平行處理的零組件製造機器,第三台機器是批次處裡的組裝機器。本論文分別對幾個特殊化的問題提出有效的演算法來求最佳解,並且證明3MAF/δ→β, pi2 = p/Cmax這個特殊化問題是NP-hard。此外,本論文亦提出最佳解的下界規範,並且提出兩個有效的工作排序經驗法則演算法,以經驗法則演算法搭配動態規化演算法求取近似解。在研究中我們將所提的演算法與其它三個之前學者提出的演算法做比較,從實驗數據上得知,本研究所提出的兩個演算法無論在執行效率或精確度上皆優於之前學者所提的三個演算法。

This thesis addresses a three-machine assembly-type flowshop scheduling problem. Machines one and two are fabrication areas arranged as two parallel machines for producing component parts discretely, and machine three is an assembly line arranged as a flowshop for receiving component parts in batches. In this study, we explore useful properties for some special cases and present an NP-hardness proof for a special case. We define a lower bound for solutions to the generic three-machine assembly-type flowshop batch scheduling problem, and then devise several heuristic algorithms and dynamic programming procedures to find approximate solutions. Computational experiments are also conducted to study the effectiveness of the proposed algorithms. Finally, we give some concluding remarks and directions for possible further studies.

Chapter 1. Introduction........................................1
Chapter 2. Problem Formulation and Literature Review...........3
2.1 Problem Formulation........................................3
2.2 Literature Review..........................................5
Chapter 3. Complexity Results..................................8
3.1 Efficient Algorithms for Four Special Cases................8
3.2 NP-Hardness Proofs........................................11
Chapter 4. Heuristic Algorithms and Computational Experiments.14
4.1 Heuristic Algorithms......................................14
4.2 Numerical Results.........................................16
Chapter 5. Conclusions and Further Studies....................26
Bibliography..................................................27

[1] A. Agnetis, D. Pacciarelli and F. Rossi (1997), “Batch scheduling in a two-machine flowshop with limited buffer”, Discrete Applied Mathematics 72, 243-260.
[2] J.H. Ahmadi, R.H. Ahmadi, S. Dasu and C.S. Tang (1992), “Batching and scheduling jobs on batch and discrete processors”, Operations Research 39, 750-763.
[3] S. Albers and P. Brucker (1993), “The complexity of one-machine batching problems”, Discrete Applied Mathematics 47, 87-107.
[4] A. Allahverdi, J.N.D. Gupta, T. Aldowaisan (1999), “A review of scheduling research involving setup considerations”, Omega 27, 219-239.
[5] K.R. Baker (1975), “A comparative survey of flowshop problems”, Operations Research 23, 62-73.
[6] K.R. Baker (1995), “Lot streaming in the two-machine flow shop with setup times”, Annals of Operations Research 57, 1-11.
[7] P. Brucker, A. Gladky, H. Hoogeveen, M.Y. Kovalyov, C.N. Potts, T. Tautenhahn and S.L. Van De Delde (1998), “Scheduling a batching machine”, Journal of Scheduling 1, 31-54.
[8] T.C.E. Cheng, Z.-L. Chen, M.Y. Kovalyov and B.M.T. Lin (1996), “Parallel-machine batching and scheduling to minimize total completion time”, IIE Transactions 28, 953-956.
[9] T.C.E. Cheng, J.N.D. Gupta and G. Wang (2000), “A review of flowshop scheduling research with setup times”, Production and Operations Management 9, 262-282.
[10] T.C.E. Cheng, B.M.T. Lin and A. Toker (2000), “Makespan minimization in the two-machine flowshop batch scheduling problem”, Naval Research Logistics 47, 128-144.
[11] T.C.E. Cheng and Q. Wang (1998), “Batching and scheduling to minimize the makespan in the two-machine flowshop”, IIE Transactions 30, 447-453.
[12] E.G.Jr. Coffman, A. Nozari and M. Yannakakis (1989), “Optimal scheduling of products with two subassemblies on a single machine”, Operations Research 37, 426-436.
[13] E.G.Jr. Coffman, M. Yannakakis, M.J. Magazine and C. Santos (1990), “Batch sizing and job sequencing on a single machine”, Annals of Operations Research 26, 135-147.
[14] R.W. Conway, W.L. Maxwell and L.W. Miller (1967), Theory of Scheduling, Addison Wesley, Reading, MA.
[15] F.D. Croce, V. Narayan and R. Tadei (1996), “The two-machine total completion time flow shop problem”, European Journal of Operational Research 90, 227-237.
[16] R.A. Dudek, S.S. Panswalkar and M.L. Smith (1991), A review of flowshop scheduling, Presented at 1991 ORSA/TIMS meeting in Nashville, TN.
[17] M.R. Garey, D.S. Johnson and R. Sethi (1976), “The complexity of flowshop and job shop scheduling”, Mathematics of Operations Research 1, 117-129.
[18] A. Guinet, M.M. Solomon, P.K. Kedia and A. Dussauchoy (1996), “A computational study of heuristics for two-stage flexible flowshops”, International Journal of Production Research 34, 1399-1415.
[19] S.M. Johnson (1954), “Optimal two- and three-stage production schedules with setup times included”, Naval Research Logistics Quarterly 1, 61-67.
[20] J.S. Kim, S.H. Kang and S.M. Lee (1997), “Transfer batch scheduling for a two-stage flowshop with identical parallel machines at each stage”, Omega 25, 547-555.
[21] C.Y. Lee (1997), “Minimize the makespan in the two-machine flowshop scheduling problem with an availability constraint”, Operations Research Letters 20, 129-139.
[22] Chung-Yee Lee, T.C.E. Cheng and B.M.T. Lin (1993), “Minimizing makespan in the 3-machine assembly-type flowshop scheduling problem”, Management Science 39, 616-625.
[23] C.Y. Lee, L. Lei and M. Pinedo (1997), “Current trends in deterministic scheduling”, Annals of Operations Research 70, 1-41.
[24] C.Y. Lee and S.D. Liman (1992), “Single machine flow-time scheduling with scheduled maintenance”, Acta Informatica 29, 375-382.
[25] C.Y. Lee, R. Uzsoy and L.A. Martin-Vega (1992), “Efficient algorithms for scheduling semiconductor burn-in operations”, Operations Research 40, 764-775.
[26] B.M.T. Lin and T.C.E. Cheng (1998), “Two-machine flowshop batching and scheduling”, Technical Report No. 18/97-98, Department of Management, The Hong Kong Polytechnic University,.
[27] B.M.T. Lin and T.C.E. Cheng (1998), “Assembly and fabrication scheduling in a two-machine flowshop”, Unpublished Manuscripts,.
[28] I.N. Lushchakova and S.A. Kravchenko (1998), “Two-machine shop scheduling with zero and unit processing times”, European Journal of Operational Research 107, 378-388.
[29] M. Pinedo (1995), “Scheduling Theory, Algorithms, and Systems”, Prentice Hall, New Jersey,.
[30] C.N. Potts and M.K. Kovalyov (2000), “Scheduling with batching: a review”, European Journal of Operational Research 102, 228-249.
[31] C.N. Potts and L.N. Van Wassenhove (1992), “Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity”, Journal of the Operational Research Society 43, 395-406.
[32] A. Reisman, A. Kumar and J. Motwani (1997), “Flowshop scheduling/sequencing research: a statistical review of the literature, 1952-1994”, IEEE Transactions on Engineering Management 44, 1997, 316-329.
[33] D.F. Shallcross (1992), “A polynomial algorithm for a one machine batching problem”, Operations Research Letters 11, 213-218.
[34] C.S. Sung and S.H. Yoon (1998), “Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines”, International Journal of Production Economics 54, 247-255.
[35] S. Webster and K.R. Baker (1995), “Scheduling groups of jobs on a single machine”, Operations Research 43, 692-703.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔