跳到主要內容

臺灣博碩士論文加值系統

(44.201.99.222) 您好!臺灣時間:2022/12/05 22:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:潘宣佑
研究生(外文):hsuan-Yu Pan
論文名稱:雙階段流程型工廠包含兩開放機台與單機之最小化最大完工時間排程問題
論文名稱(外文):Minimizing makespan in a two-stage system with open and discrete shop
指導教授:蘇玲慧蘇玲慧引用關係
指導教授(外文):Lin-Huey Su
學位類別:碩士
校院名稱:中原大學
系所名稱:工業工程研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:48
中文關鍵詞:分支界限演算法開放機台雙階段流程型工廠最小化最大完工時間啟發式演算法特殊問題
外文關鍵詞:heuristic algorithmbranch and boundtwo-stage systemopen shopspecial case
相關次數:
  • 被引用被引用:0
  • 點閱點閱:127
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究將針對雙階段流程型工廠包含兩開放機台與單機排程問題加以探討, 以最小化最大完工時間為目標,提出最佳化演算法與三個啟發式演算法。最佳化演算法為分支界限演算法,啟發式演算法一主要考慮在第一階段雙機開放型工廠中,以作業最大完工時間為最小值的情況下,再進行第二階段作業排序;啟發式演算法二乃從流程型工廠演算法Johnson’s Rule發展而成;啟發式演算法三為根據本研究之排程特性,建立一排序指標值,依此指標建立作業加工順序;透過實驗測試得到三個啟發式演算法求解品質分別在84%、96%、97%以上。最後提出當作業在第三台機器的加工時間大於第一、二機器的加工時間時,為本研究的特殊問題(Special Case)並提出特殊問題最佳解演算法。
This paper addresses the two-stage system with open shop in the first stage and discrete shop in the second stage. The performance considered is the minimum makespan. The approaches includes one optimization algorithm and three heusitic algorithms. The optimization algorithm is the branch and bound algorithm. The first heuristic algorithm is developed by construct a sequence with the minimum makespan to the open shop and then use the FCFS rule to sequence the job in discrete processor. The second heuristic algorithm is generated by adopting the Johnson's rule to the open shop and also use the FCFS rule to the discreate processor. The last heuristic adopts an index according to the property developed in this work . Experimental results show that the solution qualities of these three heursitic are 84%, 96% and 97%, respectively. Finally, an optimal algorithm of specail case in which the minimum processing time of discreate processor is larger than the maximum processing time of the open shop is developoed.
中文摘要 I
英文摘要 II
目錄 III
圖目錄 V
表目錄 VI
第一章 緒論 1
1.1 研究背景與目的 1
1.2 研究範圍與內容 2
1.3 研究方法 2
第二章 文獻探討 4
2.1開放型工廠相關文獻 4
2.2流程型工廠文獻 5
第三章 模式建構 6
3.1 本研究之基本假設 6
3.2 符號說明 6
3.3 問題定義 8
3.4 問題特性 8
3.5 整數規劃之建立 10
3.6啟發式演算法之建立 12
3.6.1啟發式演算法一 12
3.6.2啟發式演算法二 14
3.6.3啟發式演算法三 16
3.6.4特殊問題啟發式演算法 18
3.7分支界限法之建立 25
3.7.1上限值(First Upper Bound)的求法 25
3.7.2下限值(Lower Bound)的求法 25
3.7.3求解步驟 26
第四章 結果分析 34
4.1實驗參數設定 34
4.2實驗結果與分析 35
第五章 結論與未來展望 39
5.1 結論 39
5.2 建議與未來展望 40
參考文獻 41

圖目錄

圖1. 1研究流程圖 3
圖3. 1工廠加工流程示意圖 8
圖3. 2啟發式演算法一範例甘特圖 13
圖3. 3啟發式演算法二範例甘特圖(a) 15
圖3. 4啟發式演算法二範例甘特圖(b) 16
圖3. 5啟發式演算法三範例甘特圖(a) 18
圖3. 6啟發式演算法三範例甘特圖(b) 18
圖3. 7 , 可排入 [ , ]的範圍內 21
圖3. 8 > 0, 無法排入 [ , ]的範圍內 21
圖3. 9區間移動後甘特圖 22
圖3. 10全域移動後甘特圖 23
圖3. 11 [ , ]間的區域移動甘特圖 25
圖3. 12分支界限法範例分支樹狀圖 33
圖4. 1作業時間服從不同機率分配分與各作業數間的分支界限演算法平均求解時間關係圖 37
圖4. 2作業加工時間服從U(1,10)下各作業數間求解品質比較圖 38
圖4. 3作業加工時間服從U(1,100)下各作業數間求解品質比較圖 38

表目錄
表3. 1範例工作資料表 13
表3. 2啟發式演算法二Aj、B1j計算表 15
表3. 3啟發式演算法二Aj、B2j計算表 16
表3. 4啟發式演算法三範例工作資料與CVj值計算表 18
表3. 5分支界限演算法範例資料表 28
表3. 6分支界限演算法範例作業可開始加工時間資料表 29
表3. 7分支界限演算法範例作業可開始加工時間資料表 29
表3. 8分支界限演算法範例作業可開始加工時間資料表 30
表4. 1實驗次數彙整表 35
表4. 2作業服從U(1,10)情況下分支界限演算法求解時間與啟發式演算法求解品質彙整表 36
表4. 3作業服從U(1,100)情況下分支界限演算法求解時間與啟發式演算法求解品質彙整表 36
參考文獻

[1] 林安祥, 開放工廠總加權延遲最小化排程問題之研究, 朝陽科技大學工業工程與管理碩士班碩士學位論文,(1999).

[2] 廬慶煒, 不可中斷開放工廠總完工時間最小化之排程問題, 朝陽科技大學工業工程與管理碩士班碩士學位論文,(2002).

[3] 丁威清, 雙階段流程型與開放型生產型態之排程研究, 中原大學工業工程學系碩士學位論文,(2002).

[4] Adiri, I., Aizikowitz, N., Open-shop scheduling problems with dominated machines, Naval research logistics 36(1989)273-281.

[5] Chung, Y. L., Cheng, T. C. E., Lin, B.M., Minimizing the Makespan in the 3-machine assembly-type flowshop scheduling problem, Management science 39(1993)616-625.

[6] Gonzalez, T., Sahni, S., Open shop scheduling to minimize finish time, Journal of the association for computiong machinery 23(1976)665-679.

[7] Johnson, S. M., Optimal two- and three- stage production schedules with setup times included, Naval research logistics Quarterly 1(1954)61-68.

[8] Kyparisis, J. K., Koulamas, C., Open shop scheduling with makespan and total completion time criteria, Computers & operations research 27(2000)15-27.

[9] Kyparisis, J. K., Koulamas, C., Flow shop and open shop scheduling with a critical machine and two operations per job, European journal of operational research 127(2000)120-125.

[10] Lawler, E. L., Lenstra, J. K., Rinnooy Kan. A. H. G., Minimizing maximum lateness in a two-machine open shop, Mathematics of operations research 6(1981)153-158.


[11] Liaw, C. F., Scheduling two-machine preemptive open shops to minimize total completion time, Computers & operations research 31(2004)1349-1363.

[12] Liaw, C. F., Scheduling two-machine no-wait open shops to minimize makespan, Computers & operations research 32(2005)901-917.

[13] Mosheiov, G., Yovel, U., Comments on “Flow shop and open shop scheduling with a critical machine and two operations per job”, European journal of operational research 157(2004)257-261.

[14] Sevastianov, S. V., Woeginger, G. J., Makespan minimizatin in open shops:A polynomial time approximation scheme, Mathematical programming 82(1998)191-198.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊