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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:邱欽鴻
論文名稱:運用模擬退火法解決雙機總絕對偏差之排程問題
論文名稱(外文):A simulated annealing approach for the two-machine total earliness and tardiness scheduling problem
指導教授:廖慶榮廖慶榮引用關係
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:管理研究所工業管理學程
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:中文
論文頁數:51
中文關鍵詞:模擬退火法雙機排程總絕對偏差
相關次數:
  • 被引用被引用:0
  • 點閱點閱:158
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在這篇論文中,我們提出了一個雙機排程的問題,其目標函數可視為最小化工件總提早時間及延遲時間和(或稱總絕對偏差),每個工件皆有其個別的處理時間及到期日,且不一定相同。近幾年來,學者們經常使用模擬退火法解排程問題。模擬退火法為部分搜尋法(local search)的一種,但模擬退火法改退了一般部分搜尋法易侷限於局部最佳解的情況,我們利用了模擬退火法解決此一排程問題,且經由實驗發現模擬退火法可以求出較佳的問題解。

目錄
摘要 i
誌謝 ii
目錄 iii
圖目錄 v
表目錄 vi
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 2
1.3 符號說明 3
1.4 排程之績效衡量準則 4
1.5 研究範圍與研究限制 5
1.6 研究流程 6
第二章 文獻探討 8
2.1 模擬退火法相關文獻 8
2.2 即時生產系統(JIT)相關文獻 9
2.3 雙機排程相關文獻 13
第三章 研究方法 14
3.1 問題描述 14
3.1.1 問題架構 14
3.1.2 問題模式 15
3.2 模擬退火法 15
3.2.1 Metropolis演算法 16
3.2.2 模擬退火演算法 18
3.2.3 實例 26
3.3 其他演算法 27
3.3.1 遞減演算法 27
3.3.2 FRY演算法 28
3.3.3 ET-DT演算法 29
第四章 實驗設計及結果分析. 31
4.1 測試問題的產生 31
4.2 實驗方法 32
4.3 內部參數分析 32
4.3.1 起始解 33
4.3.2 不同的起始溫度 36
4.3.3 冷卻函數及停止準則 38
4.4 與其它演算法之比較 41
第五章 結論與建議 45
5.1 結論 45
5.2 未來展望及建議 46
參考文獻 47
圖目錄
圖1.5.1 研究流程 7
圖3.2.1 模擬退火法之特性 19
圖3.2.2 SA演算法流程圖 21
圖4.3.1 不同溫度次數求解趨勢圖 40
圖4.4.1 四種演算法求解趨勢圖 42
表目錄
表4.3.1 不同初始解之總絕對偏差比較表 35
表4.3.2 不同R值之總絕對偏差比較表 36
表4.3.3 不同起始溫度之總絕對偏差比較表 37
表4.3.4 冷卻函數及停止準則之總絕對偏差比較表40
表4.3.5 執行時間比較表 39
表4.4.1 與其它演算法之總絕對偏差比較表 41
表4.4.2 四個演算法的雙因子變異數分析:重複試驗43
表4.4.3 SA與FRY的單因子變異數分析 43
表4.4.4 SA與ET-DT的雙因子變異數分析:重複試驗44

[1] Abdul-Razaq, T., and C. Potts (1988), "Dynamic programming state-space relaxion for single-machine scheduling", Journal of Operational Research Socieity 39, 141-152.
[2] Alex, R. T., E. Enscore, and R. Barton (1997), "Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problem", Computers and Industrial Engineering 33, 257-260.
[3] Bagchi, U., R. Sullivan and Y. Chang (1986), "Minimizing mean absolute deviation of completion times about a common due date", Naval research logistics quarterly 33, 227-240.
[4] Bagchi, U., R. Sullivan and Y. Chang (1987), "Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date", Naval research logistics quarterly 34, 739-751.
[5] Baker, K.and G. Scudder, (1990) "Sequencing with earliness and tardiness penalties: A review", Operations Research 38, 22-36.
[6] Bector, C., Y. Gupta and M. Gupta (1988), "Determinatin of an optimal common due date and optimal sequence in a single machine job shop", International journal of production research 26, 613-628.
[7] Ben-Daya, M. and M. Al-Fawzan (1996), "A simulated annealing approach for the one-machine mean tardiness scheduling problem", European Journal of Operational Research 93, 61-67.
[8] Cerny, V. (1985), "Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm", Journal of Optimization Theory and Applications 45, 45-51.
[9] Chen Z. L. (1997), " Theory and methodology: Scheduling with batch setup times and earliness-tardiness penalties", European Journal of Operational Research 96, 518-537.
[10] Crauwels, H. J., C. N. Potts, and L. N. Van Wassenhove (1996), "Local search heuristic for single-machine scheduling with batching to minimize the number of late jobs", European Journal of Operational Research 90, 200-213.
[11] EGLESE, R.W. (1990), "Simulated annealing: A tool for operation research." European Journal of Operational Research 46, 271-281.
[12] Fry, T., L. Vicens, K. Macleod, and S. fernandez, (1989), "A heuristic solution procedure to minimize T on a single machine", Journal of the Operational Research Society 40, 293-297.
[13] Fry, T., G. Leong and T. Rakes (1987), "Single machine scheduling: A comparison of two solution procedures", OMEGA 15, 277-282.
[14] Hall, N. (1986), "Single- and multiple-processor models for minimizing completion time variance", Naval research logistics quarterly 33, 49-54.
[15] Hisao I., M. Shinta, and T. Hideo, (1995), "Modified simulated annealing algorithn for thr flow-shop sequencing problem", European Journal of Operational Research 81, 388-398.
[16] Johnson, D. S., C. R. Aragon, L. A. McGroch, and C. Schevon (1989), "Optimization by simulated annealing: An experiment evaluation; Part 1, Graph partitioning", Operations Research 37, 865-892.
[17] Kirkpatick, S., C. Gelatt, Jr., and M. Vecchi (1983), "Optimization by simulated annealingm", Science 220, 671-680.
[18] Lann, A. and G. Mosheiov (1996), "Single machine scheduling to minimize the number or early and tardy jobs", Computers Operations Research 23, 769-781.
[19] Metropolis, N., A. Rosenblush, M. Rosenblush, A. Teller, and E. Teller (1953), "Equation of state calculations by fast computing machines", Journal of Chemical Physics 21, 1087-1092.
[20] Marangos, C., V. Govande, G. Srinivasan and E. W. Zimmers, Jr. (1998), "Algorithm to minimize completion time variance in a two machine flowshop", Computers and Industrial Engineering 35, 101-104.
[21] Osman, I. H., and C. N. Potts (1990), "Simulated annealing permutation flow shop sequencing problem", OMEGA 19, 551-557.
[22] Ow, P., and T. Morton (1989), "The Single Machine Early-Tardy Problem", Management Science 2, 177-191.
[23] Park, M. W. and Y. D. Kim (1998), "A systematic procedure for setting parameters in simulated annealing algorithm", Computers Operations Research 25, 207-217.
[24] Panwalkar, S., M. Smith and A. Seidmann. (1982), "Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem", Operations Research 30, 391-399.
[25] Potts, C. N. and V. Wassenhove (1991), "Single machine tardiness sequencing heuristics", IIE Transaction 23, 346-354.
[26] Sidney, J. B. (1977), "Optimal single-machine scheduling with earliness and tardiness penalties", Operations Research 25, 62-69.
[27] Sridharan, V. and Z. Zhou (1996), "A Decision Theory based Scheduling Procedure for Single-Machine Weighted Earliness and Tardiness Problems", European Journal of Operational Research, 94, 292-231.
[28] Szwarc, W. (1989), "Single Machine Scheduling to Minimize Absolute Deviation of Completion Times from a Common Due Date", Naval research logistics quarterly 36, 663-673.
[29] Tadei, R., J. Gupta, F. Croce and M. Crotesi (1998), "Minimising makespan in the two-machine flow-shop with release times", Journal of the Operational Research Society 49, 77-85.
[30] Van laarhoven, P. J., E. H. Aarts and J. K. Lenstra (1992), "Job shop scheduling by simulated annealing", Operations Research, 40, 113-125.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔