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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:江孟青
研究生(外文):Meng-Ching Chiang
論文名稱:雙階段流程型工廠包含等效平行機台之工作延遲個數最小化問題
論文名稱(外文):Minimizing number of tardy jobs in a two-stage system with identical parallel machines
指導教授:蘇玲慧蘇玲慧引用關係
指導教授(外文):Ling-Huey Su
學位類別:碩士
校院名稱:中原大學
系所名稱:工業與系統工程研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:41
中文關鍵詞:工作延遲個數下限值雙階段流程型工廠等效平行機台
外文關鍵詞:number of tardy jobstwo-stage flowshopidentical parallel machineslower bound
相關次數:
  • 被引用被引用:0
  • 點閱點閱:81
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究主旨在探討具有等效平行機台的雙階段流程型工廠之生產排程問題。研究目標為總延遲工作個數最小化。第一階段與第二階段皆為等效平行機台,等效平行機台一次處理一個工作。本問題在過去的文獻中提到類似問題已證明為NP-Hard,故本研究提出了兩個啟發式演算法,同時建立下限值演算法驗證啟發式演算法之求解品質。實驗結果得知,啟發式演算法ㄧ的平均求解時間較快,但平均求解品質則是啟發式演算法二為最好。
This research explores two-stage flowshop including identical parallel machines and the main purpose is to minimize the number of tardy jobs. At the first stage and the second stage, the identical parallel machine can only process one task at a time. The restricted version of the problem under study is strongly NP-hard, which implies the general problem is also strongly NP-hard. This paper proposes two heuristics. Two kinds of algorithms will be adopted and along with a lower bound algorithm in order to solve the problem in this study. Experiment results show that the CPU time for heuristic one is less than the others, and the solution for heuristic two is best.
目錄

摘要...................................................I
Abstract..............................................II
誌謝..................................................III
目錄...................................................IV
圖目錄.................................................VI
表目錄................................................VII
第一章 緒論
1.1 研究背景與目的.......................................1
1.2 研究範圍與內容.......................................1
1.3 研究方法............................................2
第二章 文獻探討
2.1 流程型工廠之相關文獻..................................5
2.2 平行機台機台之相關文獻................................6
2.3 最小化工作延遲個數之相關文獻...........................7
第三章 模式建構
3.1 研究基本假設.........................................8
3.2 符號說明............................................9
3.3 問題定義............................................9
3.4 啟發式演算法之建立...................................10
3.5 下限值之建立........................................18
第四章 結果分析
4.1 實驗參數設定........................................22
4.2 實驗結果與分析......................................24
第五章 結論與未來展望
5.1 結論...............................................31
5.2 建議與未來展望......................................31
參考文獻...............................................32

圖目錄

圖1.1 雙階段流程型工廠圖..................................2
圖1.1 研究流程圖.........................................4
圖3.1 工作發生延遲示意圖.................................12
圖3.2 啟發式演算法一結果圖...............................13
圖3.3 判斷Critical Job是否為工作示意圖...................14
圖3.4 工作不為Critical Job示意圖........................16
圖3.5 工作為Critical Job示意圖..........................17
圖3.6 啟發式演算法二結果圖...............................17
圖3.7 第ㄧ個下限值結果圖.................................20
圖3.8 第二個下限值結果圖.................................21
圖4.1 工作數與演算法求解時間關係圖........................24
圖4.2 工作數與演算法求解誤差關係圖........................25
圖4.3 擁塞率與演算法求解誤差關係圖........................26

表目錄

表3.1 範例資料表........................................12
表3.2 範例(LB1)計算資料表...............................19
表3.3 範例(LB2)計算資料表...............................20
表4.1 (n<=1000)實驗參數設定表...........................23
表4.2 (n>1000)實驗參數設定表............................23
表4.3 (n<=1000)求解誤差數據彙整表........................27
表4.4 (n>1000)求解誤差數據彙整表.........................28
表4.5 (n<=1000)求解時間數據彙整表........................29
表4.6 (n>1000)求解時間數據彙整表.........................30
參考文獻

[1]Allaoui H., Artiba A., Scheduling two-stage hybrid flow shop with availability constraints, Computers & Operations Research 33 (2006) 1399-1419.

[2]Baptiste P., Peridy L, Pinson E., A branch and bound to minimize the number of late jobs on a single machine with release time constraints, European Journal of Operational Research 144 (2003) 1-11.

[3]Bulfin R.L., M’Hallah R., Minimizing the weighted number of tardy jobs on a two-machine flow shop, Computers & Operations Research 30 (2003) 1887-1900.

[4]Gupta J.N.D., Hariri A.M.A., Two-machine flowshop scheduling to minimize the number of tardy jobs, Journal of the Operational Research Society 48 (1997) 212-220.

[5]Gupta J.N.D., Tunc E.A., Minimizing tardy jobs in a two-stage hybrid flowshop, International Journal of Production Research 36 (1998) 2397-2417.

[6]Hariri A.M.A., Potts C.N., A branch and bound algorithm to minimize the number of late jobs in a permutation flow-shop, European Journal of Operational Research 38 (1989) 228-237.

[7]Ho J.C., Chang Y.L., Minimizing the number of tardy jobs for m parallel machines, European Journal of Operational Research 84 (1995) 343-355.

[8]Haouari M., M’Hallah R., Heuristic algorithms for the two-stage hybrid flowshop problem, Operations Research Letters 21 (1997) 43-53.

[9]Johnson S.M., Optimal two- and three- stage production schedules with setup times included, Naval research logistics Quarterly (1954) 161-168.

[10]Lenstra J.K., Rinnooy Kan A.H.G., Brucker P., Complexity of machine scheduling problems, Annals of Discrete Mathematics 1 (1977) 343-362.

[11]Leung J.Y.T., Yu V.K.M., Heuristic for minimizing the number of late jobs on two processors, International Journal of Foundation of Computer Science 5 (1994) 261-279.

[12]Li C.L., A heuristic for parallel machine scheduling with agreeable due dates to minimize the number of late jobs, Computers and Operation Research 22 (1995) 277-283.

[13]McNaughton R., Scheduling with deadlines and loss functions, Management Science 6 (1959) 1-12.

[14]Moore J.M., An n job,one machine sequencing algorithm for minimizing the number of late jobs, Management Science 15 (1) (1968) 102-109.

[15]Mokotoff E. An exact algorithm for the identical parallel machine scheduling problem, European Journal of Operational Research 52 (2004) 758-769.

[16]Süer G.A., Báez E., Czajkiewicz Z., Minimizing the number of tardy jobs in identical machine scheduling, Computers and Industrial Engineering 25 (1993) 243-246.

[17]Santos D.L., Hunsucker J.L., Deal D.E., Global lower bounds for flow shops with multiple processors, European Journal of Operational Research 80 (1995) 112-120.

[18]Su L.H., A hybrid two-stage flowshop with limited waiting time constraints, Computers and Industrial Engineering 44 (2003) 409-424.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔