本研究主旨在考慮機台具有彈性維護限制下，n個不可分割的工作和m台平行機台的排程問題求極小化總完工時間。早期的排程問題大多假設機台為連續可用，但此假設並不適用於實際工業環境，而在近年來有越來越多研究考慮機器有可用時間的限制。彈性維護限制為機台無法一直處於可處理工作的狀態，每台機台在連續工作一段時間後必須進行維護以防止機台的故障發生和確保工作的良率。本研究將會給定機台最大連續工作時間，意指機台維護的開始時間為不固定的，限制在最大連續工作時間內決定何時執行維護工作，此限制稱為機台具有彈性維護限制(Machine with flexible maintenance activities)。 我們提出一個分枝界限演算法去尋找這個問題的最佳解。首先，我們提出一個啟發式演算法基於剩餘工作具有最小處理時間之優先處理(SPT)法則去找到問題的可行解，並將該可行解作為分枝界限法之上限。接著我們提出兩個支配法則來提升分枝界限法的效率。 實驗的分析顯示，分枝界限法配合使用提出的支配法則後，節點的產生率非常小，在4個工作2台機台的問題下，節點產生率達0.066%以下，我們發現節點的產生率會隨著工作數目的增加而減少。我們的演算法能用於8個工作8台機台的問題下求得最佳解。 In this paper we consider the problem of scheduling n non-preemptive jobs on m identical machines with flexible maintenance activities, and the objective is to minimize total completion time of jobs. In the past, the majority of scheduling studies assumes that machines are continuously available at all time, in the recent, 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 maximum continuously working time for each machine, which means the start time of each maintenance is unfixed, and perform the maintenance activity cannot exceed the given time. This constraint is called as machine with flexible maintenance activities. We propose a branch and bound algorithm to find out the optimal solution for our problem. First, we propose a heuristic algorithm which based on the Shortest Processing Time First (SPT) rule to find out a feasible solution for our problem, its result as an upper bound of branch and bound algorithm. Then we propose two related propositions to increase the efficiency of branch and bound algorithm. Computational analysis shows that the rate of nodes generated by using branch and bound algorithm with propose propositions is very low. For the problem with 4 jobs and 2 machines, its rate of generated nodes is less than 0.006%, we observe that the rate of generated nodes is decreasing with the number of job n increase. Our algorithm can get the optimal solution for the problem with up to 8 jobs and 8 machines.
