(3.237.97.64) 您好!臺灣時間:2021/03/09 09:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:劉廣平
研究生(外文):Liu, Kuang-Ping
論文名稱:零工廠排程問題新近似演算法
論文名稱(外文):A New Heuristic Method for Job-Shop Scheduling Problem
指導教授:賴聰乾
指導教授(外文):Lai, Tsung-Chyan
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:商學研究所
學門:商業及管理學門
學類:一般商業學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:16
中文關鍵詞:零工廠排程
外文關鍵詞:JOB SHOPSCHEDULING
相關次數:
  • 被引用被引用:1
  • 點閱點閱:223
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:22
  • 收藏至我的研究室書目清單書目收藏:1
本論文針對零工廠排程問題提供一個新的近似演算法。零工廠排程問題的目標在最小化完成工時,本研究以工作在各機器台上的先後關係為決策變數,並以最小化該先後關係對完成工時所造成的最大影響為決策手段,發展出複雜度為O(n2)的啟發性演算法。以本演算法在電腦上計算經典的十件工作/十部機器零工廠排程問題,在不保證為最佳解的條件下,計算時間為八點二七二秒。最後,本研究試解一個一百件工作/三十部機器的大規模的零工廠排程問題作為未來相關研究的新指標問題。
We describe an approximation method for solving the minimum makespan problem of job shop scheduling. It makes use of the disjunctive graph, and set the direction of the disjunctive arcs as decision variables. The decision variables, as micro bottlenecks, are cleared one by one, following the critical path algorithm. Once a new disjunctive arc is adopted all the implicit disjunctive arcs will be decided. The time complexity is O (n2). Computational testing is performed to solve the notorious ten machines /ten jobs problem in running time of 8.272 CPU seconds on a P-II 450MHz PC, however, without finding an optimal solution. Finally, we verified the algorithm by testing a 100x30 (100 jobs/30machines) problem, which may contribute to be one of the new benchmark problems.
CONTENTS
1. INTRODUCTION ………………………………………...1
2. PAPER REVIEW …………………………………….……1
3. THE PROBLEM …………………………………….…….2
4. THE NEW APPROXIMATION METHOD ………….…...3
5. IMPLEMENTATION ……………………………………..7
6. COMPUTATION EXPERIENCE ………………………...9
7. CONCLUSION ………………………………………….11
REFERENCE ………………………………………………12
APPENDICES ………………………………………….......13
References
Adams J.,Balas E,and Zawack(1988) The Shifting Bottleneck Procedure for Job Shop Scheduling Management Science Vol.34,No.3 391-401
Applegate D. and Cook W.(1991)A Computational Study of Job-Shop Scheduling Problem ORSA Journal on Computing Vol.3,No.2 149-156
Balas E.(1969) Machine sequencing via disjunctive graphs: an implicit enumeration algorithm Oper.Res.,17,941-957
Carlier J, and Pinson E.(1989) An Algorithm for Solving the Job-Shop Problem, Management Science 35,164-176
French S.(1982) Sequencing and Scheduling: An introduction to the Mathematics of Job Shop Wiley, Chichester
Garey M.R. and Johnson D.S.(1979) Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman, San Francisco.
Jain A.S. and Meeran S.(1999) Deterministic Job-Shop Scheduling: Past Present and Future, European Journal of Operation Research Vol.113, Issue2,390-434
Lenstra J.K.,Rinnooy Kan A.H.G. and Brucker P.(1977)Complexity of machine scheduling problem Ann.Discr.Math., 1,343-362
Muth, J.F., and G.L.Thompson, Industrial Scheduling, Prentice-Hall,Englewood Cliffs,N.J.,1963
Pinedo M. , Scheduling-Theory, Algorithms, and Systems, Prentice Hall
Pinedo M. and Chao X.,Operation Scheduling with Applications in Manufacturing and Service, McGraw-Hill.
Pinson E.(1995)The Job Shop Scheduling Problem: A Concise Survey and Some Recent Development, Scheduling Theory and its Applications, John Wiley&Sons Ltd
Potts C.N.(1980)An Algorithm for the Single Machine Sequencing Problem with Precedence Constraints, Mathematical Programming Study 13,78-87, North-Holland Publishing Company
Roy B. and Sussman B.(1964) Les problémes d’ordonnancement avec constraints disjunctives. Note DS no 9 bis, SEMA, Paris
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 35.夏家承,1999.08,【淺談民間參與基礎建設與BOT模式遭遇之環保問題】,人與地第188期,頁48-56
2. 23.李燦東,1994.06,【都市計畫民眾參與問題之研究】,計畫經緯第18期,頁33-42
3. 21.李培芬,2000.03,【當前生態保育問題】,政策月刊第56期,頁22-25
4. 20.李訓煌,1993.06,【淺談國內之自然保留(護)區及其保育措施】,自然保育季刊第2期,頁20-23
5. 19.李素馨、蔡淑美1995.04,【民眾參與在觀光規劃中之運用】,觀光研究學報第1卷第1期,頁66-79
6. 17.李永展,1998,【從環保運動之演變思考台灣環保團體之出路】,規劃學報第25期,頁97-114
7. 78.鄭欽龍、古曉燕,1999,【社區林經營與公眾參與】,中華林學季刊第32卷第1期,頁79-89
8. 71.廖淨修,【福爾摩”殺”?令人寒心的森林保育工作】,中國環保第14期,1992.10,頁196-199
9. 63.黃躍雯,1999.11,【台灣國家公園原住民保留地政策—制度與空間觀點的檢視】,國家公園學報第9卷第2期,頁182-198
10. 62.黃錦堂,1999.06,【民主化對環保政策之衝擊與因應之道】,理論與政策第51期,頁19-46
11. 61.黃錦堂,1998.11,【從「拜耳案」論地方自治團體之參與權】,月旦法學雜誌第42卷,頁74-87
12. 56.湯曉虞,1993.01,【台灣自然生態及野生動物之保育概況】,中國環保第21卷第22期,頁66-70
13. 55.曾華璧,1998.09,【1970年代台灣資源保育主義之發展:以政府角色為主之研究】,思與言第36卷第3期,頁61-104
14. 53.彭國棟,1998.04,【勾勒自然保育的新希望談現階段保育策略及行動】,主計月報第85卷,頁97-102
15. 52.彭國棟,1996.09,【淺談現階段自然保育策略】,自然保育季刊第15卷,頁6-13
 
系統版面圖檔 系統版面圖檔