考量機台的維護保養工作在排程規畫上具有其重要性，若安排得宜，將可以避免因為故障造成不可預期的損失，故我以機台維護保養的排程做為研究主題。本研究探討在單一機台環境下，機台須進行多次維護保養工作，每次維護具有不同的維護時間，並且必須在前一維護工作完成後的特定時間區間內開始下一次的維護，其目的在極小化總完工時間的排程問題。 本研究首先提出了一個混整數規劃模型，考慮工作與工作，工作與維護，兩兩之間的順序關係，依此關係對其開始、結束時間的限制建構模型。接著，本研究提出了一分枝界限法，考量每個可用區間的時間長度，對可能排入的工作從數量、加工時間上進行篩選。但由於最佳解演算法可處理問題規模較小，為了因應問題規模較大的狀況，我們也嘗試在這個問題上採用short processing time first(SPT)法則，並分析其績效。 由實驗的結果可以發現，本研究所提出之分枝定界法可以有效的的求得最佳解，也能刪去不必要的節點達99.9%以上。此外，應用本研究提出的分支定界法與SPT法則來求解此問題互有利弊，且對於SPT法則的績效較差的情況，本研究的分支定界法通常有較優的表現。? In this research, we consider the scheduling problem of processing n jobs on a single machine along with several maintenance activities. Each maintenance have different duration, and has to be perform within a period between it minimum time lag and maximum time lag. The objective is to minimize the total completion time. We proposed a math programming and a branch and bound algorithm to solve the problem optimally. The math programming model is base on the sequential order of jobs and maintenances, use it to restrict the starting time and ending time of each job and maintenance. The branch and bound algorithm consider the capacity and flexibility of available intervals between maintenances and branch the every possible job set to an interval. However, optimal approaches may not solve a problem with large problem size. So the performance of applying SPT rule to this problem is also tested and analysis in this research. Computation analysis shows that our proposed methods can solve the problem optimally and the branch and bound algorithm is can eliminate more than 99.9% unnecessary nodes. Besides, applying our algorithm or SPT rule to this problem both have goodness and shortcoming. For those instances that SPT rule has large error, our algorithm usually performs better.
