Title

最大完工時間最小化之雙平行機台彈性維修時間排程問題

Translated Titles

Flexible preventive maintenance planning for two parallel machines problem to minimize makespan

DOI

10.6840/CYCU.2007.00353、10.6840/cycu200700497

Authors

蔡曉玲

Key Words

彈性維修 ; 平行機台 ; 最大完工時間 ; Parallel Machine ; Flexibly Maintenance ; Makespan

PublicationName

中原大學工業工程研究所學位論文

Volume or Term/Year and Month of Publication

2007年

Academic Degree Category

碩士

Advisor

蘇玲慧

Content Language

繁體中文

Chinese Abstract

本研究探討雙平行機台彈性維修問題,每部機器都需要適時的停機進行維修保養以維持良好的運作狀態。由一位維修人員在一段已知的可執行維修區間 內對每部機器維修保養一次,兩部機台的維修時段不可同時發生,且維修時段不可超過可執行維修區間,本研究目標為最大完工時間最小化。將此問題區分為維修時段長度不相同( )、維修時段長度相同( )、連續維修(優先維修機台一、優先維修機台二)四種情況加以分析,並發展在不同情況下的最佳解演算法。雖然本研究所提出的演算法有指數性的複雜度,但對處理工作量大的問題卻非常有效率。實驗測試處理的最大工作量可以至10000個。

English Abstract

This study addresses the two parallel machines problem, where machines are flexibly maintained within a given interval and the makespan is used as a performance measure. The maintenance interval is set in advance and the maintenance is attended by a single server which can perform one maintenance at a time. The maintenance times for both machines do not exceed the maintenance interval. The problem is strongly NP-hard. Four case, unequal or equal maintenance times combined with separate and continuous maintenance operations between two machines, are considered. Optimal solution for there cases are proposed and size complexity and computer solution times are provided to demonstrate the models'efficiency.

Topic Category 工學院 > 工業工程研究所
工程學 > 工程學總論
Reference
  1. [1]C.Y. Lee, Machine scheduling with an availability constraint, Journal of Global Optimization 9 (1996) 395–416.
    連結:
  2. [2]C.Y. Lee, S.D. Liman, Capacitated two-parallel machines scheduling to minimize sum of job completion times, Discrete Applied Mathematics 41 (1993) 211–222.
    連結:
  3. [3]C.Y. Lee, Z.L. Chen, Scheduling jobs and maintenance activities on parallel machines, Naval Research Logistics 47 (2000) 145–165.
    連結:
  4. [4]Garey, M.R. and Johnson, D.S., 1979, Computers and intractability:A guide to the theory of NP-completeness, Freeman, San Francisco.
    連結:
  5. [5]G. Mosheiov, Minimizing the sum of job completion times on capacitated parallel machines, Math Comput Model 20 (1994), 91-99.
    連結:
  6. [6]Graves, G. H. and C.-Y. Lee, “Scheduling Maintenance and Semiresumable Jobs on a Single Machine,” Naval Research Logistics, 46, (1999) 845-863.
    連結:
  7. [7]Gupta, J. N. D., and J. C. Ho.. A new heuristic algorithm for the onedimensional bin-packing problem, Production Planning and Control, (1999) Volume 10, Issue 6, pp. 598-603.
    連結:
  8. [8]I. Adiri, J. Bruno, E. Frostig, and A.H.G. Rinnooy Kan, Single machine flow-time scheduling with a single breakdown, Acta Inf 26 (1989), 679-696.
    連結:
  9. [9]J.C. Ho, J.S. Wong, Makespan minimization for m parallel identical processors, Naval Research Logistics 42 (1995) 935–948.
    連結:
  10. [10]Chen, JS (2005) Single-machine scheduling with flexible and periodic maintenance. Journal of the Operational Research Society , (2006) 57, 703–710
    連結:
  11. [11]Chen, Jen-Shiang Optimization models for the machine scheduling problem with a single flexible maintenance activity. Engineering Optimization ,Vol. 38, No. 1, January 2006, 53–71
    連結:
  12. [12]Liao, C.J., D.L. Shyur, and C.H. Lin, Makespan minimization for two parallel machines with an availability constraint, European Journal of Operational Research 160, (2005) 445-456.
    連結:
  13. [13]Lin, Chien-Hung Makespan minimization for two parallel machines with an unavailable period on each machine. The International Journal of Advanced Manufacturing Technology 33: (2007) 1024–1030
    連結:
  14. [15]Yang, D.L., Hung, C.L., Hsu, C.J. and Chern, M.S., Minimizing the makespan in a single machine scheduling problem with a flexible maintenance. J. Chinese Inst. Indust. Eng., 2002, 19(1), 63–66.
    連結:
  15. 參考文獻
  16. [14]X. Qi, T. Chen and F. Tu, Scheduling the maintenance on a single machine, working paper, Depart-ment of Computer and System Sciences, Nankai University, Tianjin, People's Republic of China,1997.