跳到主要內容

臺灣博碩士論文加值系統

(44.200.194.255) 您好!臺灣時間:2024/07/22 01:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:喻瀚寬
研究生(外文):Han-Kuan Yu
論文名稱:雙機流線型批次處理排程問題之工作總完工時間最小化
論文名稱(外文):Batch Scheduling to Minimize the Total Completion Time in a Two-Machine Flowshop
指導教授:林妙聰林妙聰引用關係黃宇翔黃宇翔引用關係
指導教授(外文):Miao-Tsong LinYeu-Shiang Huang
學位類別:碩士
校院名稱:銘傳大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:38
中文關鍵詞:流線型排程批次處理工作總完工時間動態規劃演算法分支與界定法經驗法則
外文關鍵詞:flowshopbatch schedulingtotal completion timedynamic programmingbranch-and-bound algorithmheuristic algorithm
相關次數:
  • 被引用被引用:3
  • 點閱點閱:465
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
排程理論之研究是希望將生產線上的工作透過數理分析,幫助規劃出最適當之排程決策,有效地提升生產效能。本篇研究主題是以「雙機流線型批次排程」做為探討之方向,假設生產線上之工作是以批次的型式進入機器中處理,並且所有工作都需依序經過兩種不同的處理程序才可完成。我們將工作的完成時間定義為其被包含批次之完成時間,並且每一批次進行處理前都需花費一段批次的前置設定時間。針對這樣的排程問題找出最佳的批次組合及批次處理順序,而使得所有工作的總完工時間最短。研究中我們提出了一些最佳解的排程性質,並設計動態規劃演算法及分支與界定法求解最佳排程。由於考量大批工作進行處理時不易在短時間內求得最佳解,我們應用了模擬退火及禁制搜尋法求解排程近似解。根據實驗結果,我們發現此兩種經驗法則都能在合理的時間範圍內,產生高品質的排程近似解。
In this thesis we study a batch scheduling problem in a two-machine flowshop that consists of two batch processors arranged in a pipelined way. There is a set of independent jobs to be grouped for processing, and the completion time of a job is defined as the completion time of the batch containing it. A constant setup time is incurred whenever a batch is formed on the batch processors. This problem seeks to find a batch composition and the sequence of the batches so that the total completion time of the jobs is minimized. We first demonstrate some optimality properties, and then present a dynamic programming algorithm and a branch-and-bound scheme to solve this problem. Two well-known heuristics, tabu search and
simulated annealing, are adopted for deriving approximate solutions. Our computational experiments evince that the structural properties are very effective in finding optimal solutions. Furthermore, the proposed heuristic algorithms can produce quality approximate solutions in a reasonable time.
Chapter 1 Introduction
Chapter 2 Literature Review and Problem Formulation
Chapter 3 Efficient Algorithm for a Special Case
Chapter 4 Finding an Optimal Solution
Chapter 5 Heuristic Algorithms
Chapter 6 Experiments and Analysis
Chapter 7 Conclusions
Bibliography
[1] J.H. Ahmadi, R.H. Ahmadi, S. Dasu and C.S. Tang, Batching and scheduling jobs on batch and discrete processors, Operations Research, Vol. 39, No. 4, July-August 1992, pp. 750-763.
[2] S. Albers and P. Brucker, The complexity of one-machine batching problems, Discrete Applied Mathematics, Vol. 47, 1993, pp. 87-107.
[3] A. Allahverdi, J.N.D. Gupta and T. Aldowaisan, A review of scheduling research involving setup considerations, Omega, Vol. 27, 1999, pp. 219-239.
[4] R.A. Armentano and D.P. Ronconi, Tabu search for total tardiness minimization in flowshop scheduling problems, Computers & Operations Research, Vol. 26, 1999, pp. 219-235.
[5] K.R. Baker, Lot streaming in the two-machine flow shop with setup times, Annals of Operations Research, Vol. 57, 1995, pp. 1-11.
[6] P. Brucker, A. Gladky, H. Hoogeveen, M.Y. Kovalyov, C.N. Potts, T. Tautenhahn and S.L. Van De Delde, Scheduling a batching machine, Journal of Scheduling, Vol. 1, 1998, pp. 31-54.
[7] T.C.E. Cheng, Z.-L. Chen, M.Y. Kovalyov and B.M.T. Lin, Parallel-machine batching and scheduling to minimize total completion time, IIE Transactions, Vol. 28, 1996, pp. 953-956.
[8] T.C.E. Cheng, J.N.D. Gupta and G. Wang, A review of flowshop scheduling research with setup times, to appear in Production and Operations Management, 1999.
[9] T.C.E. Cheng, B.M.T. Lin and A. Toker, Makespan minimization in the two-machine flowshop batch scheduling problem, Technical Report No. 04/95-96, Department of Management, The Hong Kong Polytechnic University, 1996.
[10] E.G.Jr. Coffman, A. Nozari and M. Yannakakis, Optimal scheduling of products with two subassemblies on a single machine, Operations Research, Vol. 37, No. 3, May-June 1989, pp. 426-436.
[11] E.G.Jr. Coffman, M. Yannakakis, M.J. Magazine and C. Santos, Batch sizing and job sequencing on a single machine,
Annals of Operations Research, Vol. 26, 1990, pp. 135-147.
[12] R.W. Conway, W.L. Maxwell and L.W. Miller, Theory of Scheduling, Addison Wesley, Reading, MA., 1967.
[13] M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, Vol. 1, 1976, pp. 117-129.
[14] F. Glover, Tabu search: a tutorial, Interfaces, Vol. 20, No. 4, 1990, pp. 74-94.
[15] S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, Vol. 1, 1954, pp. 61-67.
[16] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing, Science, Vol. 220, 1983, pp. 671-680.
[17] C.Y. Lee, L. Lei and M. Pinedo, Current trends in deterministic scheduling, Annals of Operations Research, Vol. 70, 1997, pp. 1-41.
[18] C.Y. Lee, R. Uzsoy and L.A. Martin-Vega, Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, Vol. 40, 1992, pp. 764-775.
[19] B.M.T. Lin and T.C.E. Cheng, Two-machine flowshop batching and scheduling, Technical Report No. 18/97-98, Department of Management, The Hong Kong Polytechnic University, 1998.
[20] M. Pinedo, Scheduling Theory, Algorithms, and Systems, Prentice Hall, New Jersey, 1995.
[21] S. Webster and K.R. Baker, Scheduling groups of jobs on a single machine, Operations Research, Vol. 43, No. 4, July-August 1995, pp. 692-703.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top