(3.92.96.236) 您好!臺灣時間:2021/05/09 01:24
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:許洲榮
研究生(外文):Chou-Jung Hsu
論文名稱:在機器使用受限的條件下單機排程之研究
論文名稱(外文):Single-machine scheduling problems with availability constraint
指導教授:蘇純繒蘇純繒引用關係駱景堯駱景堯引用關係
學位類別:博士
校院名稱:國立雲林科技大學
系所名稱:工業工程博士班
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:93
中文關鍵詞:排程最大完工時間啟發式演算法總完工時間
外文關鍵詞:schedulingmakespanheuristic algorithmtotal completion time
相關次數:
  • 被引用被引用:0
  • 點閱點閱:186
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
所謂「機器使用受限」指的是機器連續處理一段時間後,必須停機調整、維修或換刀具,然後恢復使用。20年來這種生產排程問題不管是定期或彈性維修,已經被廣泛的探討,然而,同時考慮機器連續處理一段時間,或是一定數量的工作後必須停機維修的研究至今仍然少有,因應某些產業對產品高品質的要求,本研究針對單機生產模式,提出同時考慮上述兩種維修策略,探討定期維修和定期彈性維修,在最大完工時間最小化(Cmax)的目標下,這兩種維修模式都是NP-hard問題,針對定期的維修模式,本研究提出兩階段純整數規劃法求得最佳解,當問題規模很大,提出兩個有效的演算法供業界參考選用。針對定期彈性維修問題,提出一個新的彈性維修模式,利用啟發式演算法求近似解,並且針對所提之啟發式演算法當中最有效的演算法做誤差界限分析。近年來探討退化性工作在機器使用受限的條件下之生產排程問題,有如雨後春筍般的出現。所謂「退化性工作」指的是工作的處理時間是開始加工時間的遞增線性函數。觀諸研究先驅者的研究,都假設整個加工過程,工作的處理時間與工作要被處理的開始時間有關,因為這個假設只適合某些生產環境,所以本研究提出另外一個適合金屬加工製造業的生產模式,當機器在處理一段時間後,必須停機調整、維修或換刀具,所有在機器恢復使用之後才處理的工作,它的處理時間與機器停機以前的總處理時間無關,在最大完工時間最小化(Cmax)以及總處理時間(total completion time)的目標下分別探討問題之複雜度,證明所提之問題都是NP-hard,針對最大完工時間最小化問題,提出啟發式演算法求解並推導出理論上的最佳維修時間設定值公式;針對總處理時間最小化問題,本研究推導排程模式在理論上的一些特性,提出結合整數規劃法之演算法求得最佳解。
The thesis deals with the single-machine scheduling problems with availability constraint. The availability constraint means that machines need to maintained, adjusted, or changed tools and become unavailable during certain periods. Although the scheduling problem with single or periodic maintenance and non-resumable jobs has been well studied in the past two decades, most of past studies considered only one maintenance stratagem. For the deterministic job’s processing time case, these two stratagems are considered simultaneously: a machine should stop (1) to maintain after a periodic interval (T) or (2) to change tools after a fixed amount of jobs processed (K). A new technical sequence order and a new flexible maintenance model are presented. The objective is to minimize the makespan. The proposed problem is known to be NP-hard in the strong sense and some heuristic algorithms are provided. For the problem with periodic maintenance activities, a two-stage binary integer programming model is provided for driving the optimal solution up to 350-job instances. When the size of problem is larger than 400, two efficient heuristics are provided for the different combinations of T and K. For the problem with flexible periodic maintenance activities, computational results show that the algorithm first-fit decreasing (DFF) performs well. The thesis proved that the asymptotic worst-case performance ratio of DFF algorithm is 1 for and for .For the dynamic job’s processing time case, assume that the machine is subject to an availability constraint. The objectives are to minimize the makespan and the total completion time. The thesis showed that both problems are NP-hard. For the objective is minimize the makespan, the addressed problem is first described as a binary integer programming model, and is then solved optimally. For the objective is minimize the total completion time, the addressed problem is first formulated as an integer programming model and solved optimally. Next, the thesis presents some important lemmas for the basis of solving the problem. Finally, an algorithm is proposed to solve the problem economically and optimally.
中文摘要 i
Abstract ii
誌謝 iii
Table of contents iv
List of tables v
List of figures vi
Notation vii
1. Introduction 1
1.1. Motivation 1
1.2. Research scope and objective 3
1.3. Outline of the dissertation 5
2. Literature review 6
3. Single-machine scheduling problem with periodic maintenance activities 13
3.1. Problem description 13
3.2. The scheduling problem 15
3.2.1. Complexity and two-stage binary integer programming model 15
3.2.2. Heuristic approaches 17
3.2.3. The computational experiments. 21
3.2.3.1. Generation of test problems 21
3.2.3.2. Performance evaluation and discussion 22
3.3. The scheduling problem 24
3.3.1. Complexity and heuristic approaches 24
3.3.1.1. Heuristics 26
3.3.1.2. The Computational Experiments 29
3.3.2. Bound Analysis 30
4. Single-machine scheduling problem with an availability constraint under simple linear deterioration 36
4.1. Problem description 36
4.2. Minimizing the makespan 37
4.2.1. NP-hardness 37
4.2.2. Model construction 39
4.2.3. Heuristic approaches 41
4.2.4. Example illustration 44
4.2.5. The computational experiments 46
4.3. Minimizing the total completion time 48
4.3.1. NP-hardness 48
4.3.2. An economical algorithm of optimal solution 53
4.3.3. Example illustration and the computational experiments 56
5. The conclusions and the directions of future research 59
References 61
[1] Adiri, I., Frostig, E., and Rinnooy Kan, A. H. G., 1991, “Single-machine flow-time scheduling with a single breakdown to minimize stochastically the number of tardy jobs”, Naval Research Logistics, Vol.38, pp. 261–271.
[2] Akturk, M. S., Ghosh, J. B., and Gunes, E. D., 2003, “Scheduling with tool changes to minimize total completion time: a study of heuristics and their performance”, Naval Research Logistics, Vol.50, pp.15–30.
[3] Akturk, M. S., Ghosh, J. B., and Gunes, E. D., 2004, “Scheduling with tool changes to minimize total completion time: basic results and SPT performance”, European Journal of Operational Research , Vol.157, pp. 784–790.
[4] Browne , S., and Yechiali, U., 1990, “Scheduling deteriorating jobs on a single processor”, Operations Research, Vol.38, pp. 495-498.
[5] Chen, J. S., 2006, “Single-machine scheduling with flexible and period maintenance”, Journal of the Operational Research Society, Vol.57, pp. 703–710.
[6] Chen, J. S., 2006, “Optimization models for the machine scheduling problem with a single flexible maintenance activity”, Engineering Optimization, Vol.38, pp. 53-71.
[7] Chen, J. S., 2008, “Scheduling of nonresumable jobs and flexible maintenance activities on a single-machine to minimize makespan”. European Journal of Operations Research , Vol.190, pp.90-102.
[8] Chen, W. J., 2006, “Minimizing total flow time in the single-machine scheduling problem with periodic maintenance”, Journal of the Operational Research Society, Vol.57, pp. 410–415.
[9] Cheng, T. C. E., Ding , Q., and Lin, B. M. T., 2004, “A concise survey of scheduling with time-dependent processing times”, European Journal of Operations Research, Vol.152, pp. 1-13.
[10] Chen, Z. L., 1996, “Parallel machine scheduling with time dependent processing times”, Discrete Applied Mathematics, Vol. 70, pp.81–93.
[11] Garey, M. R., Johnson, D. S., 1979, “Computers and Intractability: A guide to the theory of NP-Completeness”, Freeman, San Francisco, CA.
[12]Graves, G. H., and Lee, C. Y., 1999, “Scheduling maintenance and semiresumable jobs on a single-machine”, Naval Research Logistics, Vol.46, pp. 845-863.
[13] He, Y., Ji, M., and Cheng, T. C. E., 2005, “Single-machine scheduling with a restricted rate-modifying activity”, Naval Research Logistics, 52, pp. 361-369, 2005.
[14] Ji, M., He, Y., and Cheng, T. C. E., 2006, “Scheduling linear deteriorating jobs with an availability constraint on a single-machine”, Theoretical Computer Science, 362, pp. 115-126, 2006.
[15] Ji, M., He, Y., and Cheng, T. C. E., 2007, “Single-machine scheduling with periodic maintenance to minimize makespan”, Computers and Operations Research, Vol.34, pp. 1764-1770.
[16] Johnson, D. S., 1981, “The NP-complete columns: An ongoing guide”, Journal of Algorithms, Vol.4, pp. 393-405.
[17] Kacem, I., Chu, C., and Souissi, A., 2008, “Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times”, Computers and Operations Research, Vol.35, pp. 827-844.
[18] Krause, K. L., Shen, V. Y., and Schwetman, H. D., 1975, “Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems”, Journal of the Association for Computing Machinery, Vol.33, pp. 522-550.
[19] Kunnathur, A. S., and Gupta, S. K., 1990, “Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem”, European Journal of Operations Research, Vol.47, pp. 56-64.
[20Kuo, W.H., and Yang, D. L., 2008, “Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect”, Journal of the Operational Research Society, Vol.59, pp.416-420.
[21] Lee, C. Y., and Liman, S. D., 1992, “Single-machine flow-time scheduling with scheduled maintenance”, Acta Informatica, Vol.29, pp. 375–382.
[22] Lee, C. Y., 1996, “Machine scheduling with an availability constraint”, Journal of Global Optimization, Vol.9, pp. 395-416.
[23] Lee, C. Y., Lei, L., and Pinedo, M., 1997, “Current trend in deterministic scheduling”, Annuals of Operations Research, Vol.70, pp. 1-42.
[24] Lee, C. Y., and Leon, J., 2001, “Machine scheduling with a rate-modifying activity”, European Journal of Operational Research, Vol.128, pp.119–128.
[25] Lee, C. Y., and Lin, C. S., 2001, “Single-machine scheduling with maintenance and repair rate-modifying activities”, European Journal of Operational Research, Vol.135, pp. 493–513.
[26] Lee, W.C., and Wu, C. C., 2008, “Multi-machine scheduling with deteriorating jobs and scheduled maintenance”, Applied Mathematical Modelling, Vol.32, pp.362-373.
[27] Leon, V. J., and Wu, S. D., 1992, “On scheduling with ready-times, due-dates and vacations”, Naval Research Logistics, Vol.39, pp. 53–65.
[28] Liao, C. J., and Chen, W. J., 2003, “Single-machine scheduling with periodic maintenance and non-resemable jobs”, Computers and Operations Research, Vol.30, pp.1335-1347.
[29]Low, C., Hsu, C.J. and Su, C.T., 2008, “Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration”, Computers & Mathematics with Applications, Vol. 56(1), pp. 257-265.
[30] Low, C., Ji, M., Hsu, C.J. and Su, C.T., 2009, “Minimizing the Makespan in a Single Machine Scheduling Problems with Flexible and Periodic Maintenance”, Applied Mathematical Modelling, (Accepted).
[31]Mosheiov, G., 1994, “Scheduling deteriorating jobs under simple linear deterioration”, Computers and Operations Research, Vol.21, pp. 653-659.
[32]Mosheiov, G., 1995, “Scheduling jobs with step-deterioration: Minimizing makespan on single and multi-machine”, Computers and Industrial Engineering, Vol.28, pp. 869-879.
[33]Mosheiov, G., 1998, “Multi-machine scheduling with linear deterioration”, INFOR, Vol.36, pp. 205-214.
[34]Mosheiov, G., and Oron, D., 2006, “Due-date assignment and maintenance activity scheduling problem”, Mathematical and Computer Modeling, Vol.44, pp. 1053–1057.
[35] Pinedo, M., 2002, “Scheduling theory, algorithms, and systems”, Prentice-Hall: New Jersey.
[36]Qi, X., Chen, T., and Tu, F., 1999, “Scheduling the maintenance on a single-machine”, Journal of the Operational Research Society, Vol.50, pp.1071-1078.
[37] Sadfi, C., Penz, B., Rapine, C., Blazewicz, J., and Formanowicz, P, 2005, “An improved approximation algorithm for the single-machine total completion time scheduling problem with availability constraints”, European Journal of Operational Research, Vol.161, pp. 3–10.
[38] Sanlaville, E., and Schmidt, G., 1998, “Machine scheduling with availability constraints”, Acta Informatica, Vol.9, pp. 795–811.
[39] Schmidt, G., 2000, “Scheduling with limited machine availability”, European Journal of Operational Research, Vol.121, pp. 1–15.
[40] Wang, G., Sun, H., and Chu, C., 2005, “Preemptive scheduling with availability constraints to minimize total weighted completion times”, Annuals of Operations Research, Vol.133, pp. 183-192.
[41]Wu, C. C., and Lee, W. C., 2003, “Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single-machine”, Information Processing Letters, Vol.87, pp. 89-93.
[42] Wu, C. C., and Lee, W. C., 2007, “A note on single-machine scheduling with learning effect and an availability constraint”, International Journal of Advance Manufacture Technology, Vol.33, pp. 540-544.
[43] Xu, D., Sun, K., and Li, H., 2008, “Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan”. Computers and Operations Research, Vol.35, pp.1344-1349.
[44] Xu, D., Sun, K., and Li, H., 2009, “A note on scheduling of nonresumable jobs and flexible maintenance activities on a single-machine to minimize makespan”. European Journal of Operations Research, Vol.197, pp.825-827.
[45] Yang, D. L., Hung, C. L., Hsu, C. J. , and Chern, M. S ., 2002, “Minimizing the makespan in a single-machine scheduling problem with a flexible maintenance” Journal of the Chinese Institute of Industrial Engineers, Vol.9, pp.63-66.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔