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

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

蔡曉玲(Hsiao-Ling Tsai)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2007年)

https://doi.org/10.6840/cycu200700497

摘要

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

關鍵字

彈性維修 ； 平行機台 ； 最大完工時間

並列摘要

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.

並列關鍵字

Parallel Machine ； Flexibly Maintenance ； Makespan

參考文獻

[1]C.Y. Lee, Machine scheduling with an availability constraint, Journal of Global Optimization 9 (1996) 395–416.

[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]C.Y. Lee, Z.L. Chen, Scheduling jobs and maintenance activities on parallel machines, Naval Research Logistics 47 (2000) 145–165.

[4]Garey, M.R. and Johnson, D.S., 1979, Computers and intractability：A guide to the theory of NP-completeness, Freeman, San Francisco.

[5]G. Mosheiov, Minimizing the sum of job completion times on capacitated parallel machines, Math Comput Model 20 (1994), 91-99.