考量平行機台之彈性維護週期求極小化總完工時間排程問題

Parallel Machine Scheduling with Flexible Maintenance Activity Periods for Minimizing Total Completion Time

李彥漢(Yen-han Li)

指導教授 ： 沈國基

國立中央大學/管理學院/工業管理研究所/碩士(2014年)

摘要

本研究主旨在考慮機台具有彈性維護限制下，n個不可分割的工作和m台平行機台的排程問題求解最小化總完工時間。大部分的排程問題大多假設機台為連續可用，但此假設並不適用於實際工業環境，而近年來有越來越多研究考慮機台有可用區間的限制。彈性維護限制為機台無法一直處於可加工的工作狀態，每台機台在連續工作一段時間後必須進行維護以防止機台的故障發生和維護工作的良率。本研究給定機台最大連續工作時間和機台最小連續工作時間在連續的兩個維護中間，意旨機台維護的開始時間為不固定，限制在機台最大連續工作時間和機台最小連續工作時間內決定何時執行維護作業，此限制為機台具有彈性維護周期限制(Machine with flexible maintenance period)。
我們提出一個分枝界限演算法去尋找這個問題的最佳解。我們根據四個proposition來尋找最佳解。首先，這個問題上沿用區間內shortest processing time first(SPT)法則會找到最佳解。然後，考量每個可用區間的時間長度，決定多少工作可以排入和決定維護開始的時間。最後，lower bound、upper bound和dominance proposition用來消除無法成為最佳解不必要的節點。
實驗的分析顯示，分枝界限法配合提出的支配法則後，節點的產生率非常小，都在1.0E-4%以下，我們發現節點的產生率會隨著工作數目得增加而減少。

關鍵字

排程 ； 平行機台 ； 機台彈性維護周期 ； 分枝界限法

並列摘要

In this paper we consider the problem of scheduling n nonresumable jobs on m identical parallel machines with flexible maintenance activities, and the objective is to minimize total completion time of jobs. In this past, the majority of scheduling study assumed that machines are continuously available at all time. In recent year, there are more and more studies consider that each machine is not continuously available. The flexible maintenance activity constraint means that each machine must be maintained after it continuously working for a period of time to prevent breakdown of machine and keep the quality of process jobs. This study given the minimum working time and maximum working time within any two consecutive maintenance activities, which means the starting time of unavailability period are decision variable together with jobs to be scheduled.
We propose a branch and bound algorithm to find the optimal solution for our problem. Four propositions of an optimal solution are identified. First, we adopt that interval shortest processing time (SPT) algorithm will find optimal solution. Then, consider the capacity of available intervals and decide how many jobs processing in each available interval and when the maintenance activities starting. Finally, a lower bound, upper bound and dominance proposition are proposed to eliminate unnecessary node.
Computational analysis shows that the rate of nodes generated by using branch and bound algorithm with proposed propositions and properties is very low. It generated ratio is less than 1.0E-4%, we observe that the rate of generated nodes is decreasing with the number of jobs increase.

並列關鍵字

Scheduling ； Parallel machines ； Flexibility and period maintenance activity ； Branch and bound algorithm

參考文獻

Arts, R. H. P. M., Knapp, G. M., Lawrence, M. Jr. (1998), Some aspects of measuring maintenance performance in the process industry, Journal of Quality in Maintenance Engineering, 4, 6-11.

Chen, J. S. (2006), Optimization models for the machine scheduling problem with a single flexible maintenance activity, Engineering Optimization, 38, 53-71.

Chen, J. S. (2008), Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research, 190, 90-102.

Lee, C. Y., Liman, S. D. (1993), Capacitated two-parallel machine scheduling to minimize sum of job completion times, Discrete Applied Mathematics, 41, 211–222.

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