跳到主要內容

臺灣博碩士論文加值系統

(44.222.189.51) 您好!臺灣時間:2024/05/26 21:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳立騫
研究生(外文):Chen-Li Chien
論文名稱:有時間時窗限制與加權提早/延遲成本之單機排程研究
論文名稱(外文):Single-Machine Scheduling with Time Windows and Weighted Earliness/Tardiness Penalties
指導教授:蘇玲慧蘇玲慧引用關係
指導教授(外文):Ling-Huey Su
學位類別:碩士
校院名稱:中原大學
系所名稱:工業工程研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:38
中文關鍵詞:單機時間時窗提早/延遲排程權重
外文關鍵詞:WeightedTime windowsEarliness/tardinessSingle machineScheduling
相關次數:
  • 被引用被引用:0
  • 點閱點閱:261
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文主要研究有時間時窗限制與加權提早/延遲成本之單機排程,當安排工作於其時間時窗內加工,無處罰成本產生,工作安排提早加工或延遲完工時,會產生其中一項加權處罰成本,而研究目標為總加權成本最小化。文中並指出本問題屬於NP-hard,因此所建立之數學規劃模式,需大量求解時間。針對此問題。首先我們提出五個在特定條件下決定加工次序之性質,並參考一針對SMET(Single Machine Earliness/Tardiness)問題所發展之演算法架構,提出啟發式排程演算法。我們也提出一程序,決定已知工作加工次序之工作開始加工時間。實驗測試後得知,啟發式演算法和最佳解比較之結果,其平均求解差異小於2.99%,較大工作數的情況,平均總加權成本低於API演算法4.106%。

This study deals with the single machine scheduling with time windows and weighted earliness/tardiness penalties problem. Jobs processed entirely within their respective windows incur no cost, otherwise the corresponding early or tardy cost incurred. This problem is proved to be NP-hard. An efficient heuristic and a mathematical programming model are presented. Several solution properties on which the heuristics and the mathematical programming models are based are developed. For small problem up to 12 jobs, the average deviation between the optimal and heuristic solution is less than 2.99%. Computational results show that the heuristic algorithm has an average error less than 2.99% when the number of jobs is small. For the larger problem, five heuristics based on API are proposed to find an approximate solution and are evaluated with the heuristic proposed in this paper. The results show that the proposed heuristic averages to 4.106% above the API heuristic.

中文摘要………………………………………………………………………Ⅰ
英文摘要………………………………………………………………………Ⅱ
誌謝……………………………………………………………………………Ⅲ
目錄……………………………………………………………………………Ⅳ
表目錄…………………………………………………………………………Ⅵ
圖目錄…………………………………………………………………………Ⅶ
符號說明………………………………………………………………………Ⅷ
第一章 緒論……………………………………………………………………1
1.1 研究背景與動機…………………………………………………………1
1.2 研究目的…………………………………………………………………1
1.3 研究範圍與內容…………………………………………………………2
1.4 研究方法…………………………………………………………………2
第二章 文獻探討………………………………………………………………5
2.1含時間時窗排程相關文獻………………………………………………5
2.2單機提早與延遲排程相關文獻…………………………………………6
第三章 模式建構………………………………………………………………7
3.1問題定義與前提假設……………………………………………………7
3.2整數規劃模式建構………………………………………………………8
3.3性質與定理………………………………………………………………9
3.4啟發式排程演算法………………………………………………………14
3.4.1 最佳化工作開始時間………………………………………………15
3.4.2 最佳化工作開始時間範例說明……………………………………18
3.4.3 工作開始加工時間產生步驟………………………………………20
3.4.4 工作開始加工時間產生步驟範例說明……………………………23
3.5 API演算法……………………………………………………………25
第四章 結果分析………………………………………………………………28
第五章 結論與未來發展………………………………………………………35
5.1 結論………………………………………………………………………35
5.2 未來發展…………………………………………………………………35
參考文獻………………………………………………………………………37

[1] Baker, K. R., and Scudder, G. D., “Sequencing with earliness and tardiness penalties: A review”, Operations Research 38 (1990) 22-36.[2] Chen, Z.-L., and Lee, C.-Y., “Parallel machine scheduling with a common due window”, European Journal of Operational Research 136 (2002) 512-527.[3] Garey, M. R., Tarjan, R. E., and Wilfong, G. T., “One-processor scheduling with symmetric earliness and tardiness penalties”, Mathematics of Operations Research 13 (1988) 330-348.[4] Gabrel, V., “Scheduling jobs windows on identical parallel machine: New model and algorithms”, European Journal of Operational Research 83 (1995) 320-329.[5]Kim, Y. D., and Yano, C. A., “Minimizing mean tardiness and earliness in single-machine problems with unequal due dates”, Naval Research Logistics 41 (1994) 913-933.[6]Koulamas, C., “Single-machine scheduling with time windows and earliness/tardiness penalties”, European Journal of Operational Research 91 (1996) 190-202.[7]Koulamas, C., “Maximizing the weighted number of on-time jobs in single machine scheduling with time windows”, Mathematical and Computer Modelling 25 (1997) 57-62.[8] Lakshminarayan, S., Lakshmanan, R., Papineau, R., and Rochette, R., “Optimal single-machine scheduling with earliness and tardiness penalties”, Operations Research 26 (1978) 1079-1082.[9] Mazzini, R., and Armentano, V. A., “A heuristic for single machine scheduling with early and tardy costs”, European Journal of Operational Research 128 (2001) 129-146.[10]OW, P. S., and Morton, T. E., “The single machine early/tardy problem”, Management Science 35 (1989) 177-191.[11] Potts,C. N., and Van Wassenhove, L.N. “Single machine tardiness sequencing heuristic”, IIE Transactions 23 (1991) 346-354.[12] Panwalkar, S. S., Smith, M. L., and Koulamas, C. P., “A heuristic for the single machine tardiness problem”, European Journal of Operational Research 70 (1993) 304-310.[13] Sidney, J., “Optimal single-machine scheduling with earliness and tardiness penalties”, Operations Research 25 (1977) 62-69.[14]Yano, C. A., and Kim, Y. D., “Algorithms for a class of single machine weighted tardiness and earliness problems”, European Journal of Operational Research 52 (1991) 167-178.

電子全文 電子全文(本篇電子全文限研究生所屬學校校內系統及IP範圍內開放)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top