(3.235.139.152) 您好!臺灣時間:2021/05/08 17:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:陳晁誠
研究生(外文):Jhao-Cheng Chen
論文名稱:具有變動維修單機排程問題之最佳解法
論文名稱(外文):Optimization algorithms for single machine scheduling problems with a variable maintenance activity
指導教授:應國卿應國卿引用關係
指導教授(外文):Kuo-Ching Ying
口試委員:林詩偉黃乾怡
口試日期:2016-06-24
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:工業工程與管理系所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
畢業學年度:104
中文關鍵詞:變動維修派工法則單機排程
外文關鍵詞:Dispatch ruleVariable maintenanceSingle Machine Scheduling
相關次數:
  • 被引用被引用:0
  • 點閱點閱:190
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:59
  • 收藏至我的研究室書目清單書目收藏:0
具有變動維修作業的排程問題,近十年來逐漸受到研究人員廣泛的注意,本論文主要在探討四個不同目標函數之具有變動維修作業單機排程問題,包括:最小化平均延誤時間(mean lateness)、最小化最大延遲時間(maximum tardiness)、最小化總流程時間(total flow time)及最小化平均延遲時間(mean tardiness)等四個目標函數的具有變動維修作業單機排程問題,這些單機排程問題的變動維修作業必須在所有工單加工完成前的某一給定期限前開始,其所需的變動維修作業時間則為開始變動維修時間的非遞減函數,本論文針對此四個目標函數的具有變動維修作業單機排程問題,分別提出可求得最佳解的多項式時間演算法。由於此四個目標函數的具有變動維修作業單機排程問題,係生產排程領域十分重要但卻從未被探討過的研究課題,因此,本論文所提出的演算法將有效拓展排程理論的研究領域,並推廣排程理論於產業之實務應用。
Scheduling jobs with machine maintenance in a manufacturing system has received considerable attention from researchers in the recent decades. In this study, we investigate some single-machine scheduling problems with a variable maintenance activity, which must start before a given deadline, and the maintenance duration is a non-decreasing function of the starting time of maintenance. This study presents polynomial-time algorithms to solve the problems in order to minimize the objectives of mean lateness, maximum tardiness, total flow time, and mean tardiness. The four addressed single-machine scheduling problems are significant but have not yet been investigated topics. With no research has been done on these problems, the results of this work would increase the applications of scheduling theory in industry.
摘 要 i
ABSTRACT ii
誌 謝 iii
目 錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與限制 3
1.4 研究流程 3
第二章 文獻探討 6
2.1 單機排程文獻 6
2.2 單機排程問題之派工法則 8
2.3 單機排程問題之多項式時間演算法 12
2.4 具有變動維修作業的排程問題 12
第三章 研究方法 14
3.1 數學符號之定義 16
第四章 研究結果 18
4.1 求解SMVM-ML問題 18
4.1.1 SMVM-ML之工單最佳排序 18
4.1.2 SMVM-ML問題之最佳解法 19
4.1.3 H1演算法 19
4.1.4 H1演算法複雜度分析 20
4.1.5 H1演算法之數值範例 20
4.2 求解SMVM-MT問題 23
4.2.1 SMVM-MT之工單最佳排序 23
4.2.2 SMVM-MT問題之最佳解法 24
4.2.3 H2演算法 24
4.2.4 H2演算法複雜度分析 25
4.2.5 H2演算法之數值範例 25
4.3 求解SMVM-TF問題 28
4.3.1 SMVM-TF之工單最佳排序 28
4.3.2 SMVM-TF問題之最佳解法 29
4.3.3 H3演算法 30
4.3.4 H3演算法複雜度分析 30
4.3.5 H3演算法之數值範例 31
4.4 求解SMVM-MET問題 34
4.4.1 SMVM-MET之工單最佳排序 34
4.4.2 SMVM-MET問題之最佳解法 35
4.4.3 H4演算法 35
4.4.4 H4演算法複雜度分析 36
4.4.5 H4演算法之數值範例 36
第五章 結論與未來展望 39
5.1 結論 39
5.2 研究貢獻 40
5.3 未來展望 40
參考文獻 42
[1]R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. RinnooyKan, "Optimization and approximation in deterministic sequencing and scheduling: a survey," Annals of Discrete Mathematics, vol.5, 1979, pp. 287-326.
[2]A. S. Jain, S. Meeran, "Deterministic job-shop scheduling: past present and future," European Journal of Operational Research, vol.113, no.2, 1999, pp. 390-434.
[3]K. R. Baker, G. D. Scudder, "Sequencing with earliness and tardiness penalties: A Review," Operations Research, vol.38, no.1, 1990, pp. 22-36.
[4]J. M. Moore, "An n job, one machine sequencing algorithm for minimizing the number of late jobs," Management Science, vol.15, no.1, 1968, pp. 102-109.
[5]T. D. Fry, L. Vicens, K. Macleod and S. Fernandez, "A heuristic solution procedure to minimize on a single machine," Journal of the Operational Research Society, vol.40, no.3, 1989, pp. 293-297.
[6]U. Bagchi, Y. L. Chang, and R. S. Sullivan, "Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date," Naval Research Logistics, vol.34, no.5, 1987, pp. 739-751.
[7]H. Emmons, "Scheduling to a common due date on parallel uniform processors," Naval Research Logistics, vol.34, no.6, 1987, pp. 803-810.
[8]Z. Liu, "Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints," Computers & Operations Research, vol.37, no.9, 2010, pp. 1537-1543.
[9]S. Chanas and A. Kasperski, "Minimizing maximum lateness in a single machine scheduling problem with fuzzy processing times and fuzzy due dates," Engineering Applications of Artificial Intelligence, vol.14, no.3, 2001, pp. 377-386.
[10]T. E. Cheng, C. J. Hung, "Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness," Computers & Operations Research, vol.38, no.12, 2011, pp. 1760-1765.
[11]M. M. Mazdeh, M. Rostami, "Minimizing maximum tardiness and delivery costs in a batched delivery system," Computers & Industrial Engineering, vol.66, no.4, 2013, pp. 675-682.
[12]I. Kacem, C. Chu, "Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint," International Journal of Production Economics, vol.112, no.1, 2008, pp. 138-150.
[13]Y. Yin, D. Ye, and G. Zhang, "Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval," Information Sciences, vol.274, no.1, 2014, pp. 310-322.
[14]Y. L. Chang, T. Sueyoshi, and S. R. Sullivan, "Ranking dispatching rules by data envelopment analysis in a job shop environment," IIE Transactions, vol.28, no.8, 1996, pp. 631-642.
[15]M. L. Pinedo, "Scheduling:Theory algorithms and systems," Prentice Hall, New Jersey, 1995.
[16]J. R. Jackson, "Simulation research on job shop production," Naval Research Logistics Quarterly, vol.4, no.4, 1957, pp. 287-295.
[17]R. W. Conway, W. L. Maxwell, and L. W. Miller, "Theory of scheduling," 1967, pp. 42-51.
[18]A. P. Vepsalainen, T. E. Morton, "Priority rules for job shops with weighted tardiness costs," Management Science, vol.33, no.8, 1987, pp. 1035-1047.
[19]J. H. Blackstone, D. T. Philips, and G. L. Hogg, "A state-of-the-art survey of dispatching rules for manufacturing job shop operations," International Journal of Production Research, vol.20, no.1, 1982, pp. 27-45.
[20]M. Baudin, "Manufacturing systems analysis with application to production scheduling,” International Journal of Computer Integrated Manufacturing, vol.3, no.6, 1990.
[21]S. S. Panwalkar, W. Iskander, "A survey of scheduling rules," Operations Research, vol.25, no.1, 1977, pp. 45-61.
[22]R. Haupt,"A survey of priority rule-based scheduling, " Operations -Research- Spektrum, vol.11, no.1, 1989, pp. 3-16.
[23]J. R. Jackson, "Scheduling a production line to minimize maximum tardiness," Management Science Research Project, vol.43, 1955.
[24]W. E. Smith, "Various optimizers for single state production," Naval Research Logistics Quarterly, vol.3, no.1, 1956, pp. 59-66.
[25]S. S. Panwalkar, M. L. Smith, and A. Seidmann, "Common due date assignment to minimize total penalty for the one machine scheduling problem," Operations Research, vol.30, no.2, 1982, pp. 391-399.
[26]Y. Mati, "Minimizing the makespan in the non-preemptive job-shop scheduling with limited machine availability", Computers & Industrial Engineering, vol.59, no.4 , 2010, pp. 537-543.
[27]Y. Ma, C. Chu, and C. Zuo, "A survey of scheduling with deterministic machine availability constraints", Computers & Industrial Engineering, vol.58, no.2, 2010, pp. 199-211.
[28]J. Q. Li, P. Q. Pan, and M. F. Tasgetiren, "A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities", Applied Mathematical Modelling, vol. 38, no.3, 2014, pp. 1111-1132.
[29]S. J. Yang, "Parallel machines scheduling with simultaneous considerations of position-dependent deterioration effects and maintenance activities," Journal of the Chinese Institute of Industrial Engineers, vol.28, no.4, 2011, pp.270-280.
[30]T. E. Cheng, C. J. Hsu, and D. L. Yang, "Unrelated parallel-machine scheduling with deteriorating maintenance activities," Computers & Industrial Engineering, vol.60, no.4, 2011, pp. 602-605.
[31]C. J. Hsu, S. J. Yang, and D. L. Yang, "Due-date assignment and optional maintenance activity scheduling problem with linear deteriorating jobs," Journal of Marine Science and Technology, vol.19, no.1, 2011, pp. 97-100.
[32]W. C. Lee, "A note on single-machine makespan scheduling with deteriorating jobs and scheduled maintenance," Journal of Information & Optimization Sciences, vol.28, no.3, 2007, pp. 469-477.
[33]S. J. Yang, D. L. Yang, and T. E. Cheng, "Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance," Computers & Operations Research, vol.37, no.8, 2010, pp. 1510-1514.
[34]C. L. Zhao, H. Y. Tang, "Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan," Applied Mathematical Modelling, vol.34, no.3, 2010, pp. 837-841.
[35]S. J. Yang, "Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activitiesconsideration," Computers & Industrial Engineering, vol.62, no.1, 2012, pp. 271-275.
[36]S. J. Yang, D. L. Yang, "Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deterioratingmaintenance activities," Computers & Mathematics with Applications, vol.60, no.7, 2010, pp. 2161-2169.
[37]G. Mosheiov, J. B. Sidney, "Scheduling a deteriorating maintenance activity on a single machine," Operations Research, vol.61, no.5, 2010, pp. 882-887.
[38]J. J. Wang, J. B. Wang, and F. Liu, "Parallel machines scheduling with a deteriorating maintenance activity," Journal of the Operational Research Society, vol.62, no.10, 2010, pp. 1898-1902.
[39]J. Y. Lee, Y. D. kim, "Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance," Computers & Operations Research, vol.39, no.9, 2012, pp. 2196-2205.
[40]W. Luo, T. E. Cheng, and M. Ji, "Single machine scheduling with a variable maintenance activity," Computers & Industrial Engineering, vol.79, 2015, pp. 168-174.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔