在此研究中，我們探討ｎ個不可被分割的工作以及ｍ個平行機台的排程問題，針對每個機台具有不同數量的可用時間間隔限制的狀況，考慮最小化總完工時間。在多數的排程問題都沒有考慮可用時間間隔的限制，然而在實際情形上這種情形十分地常見，例如在製造業中，機台不可能一直處於運轉的狀態，會針對機台進行例行停機維護，以提升機台在生產時的良率及壽命。 為了求解此問題的近似解，我們參考了Woeginger(2000)中的trimmed動態規劃演算法，利用定義ε的值，刪減一些相似的state，進而求出近似解，在此演算法中我們加入了Chen(2016)和Tsou(2017)中所提到的三個propositions，此方法是利用到順序排程的概念，其他的則是比較兩個排滿工作時可用區間的開始時間及所被安排工作數量的關係，判斷這部分的排程是否可能為最佳解，藉以減少需要被儲存的state。我們提出了一個方程式估算每次iteration大約會產生多少states，以方便我們計算記憶體量是否足夠進行運算。最後我們與Tsou(2017)所提出的分支定界演算法進行比較，比較處理時間及與最佳解的相似程度。 ;In this research, we discuss a scheduling problem including n non-preemptive jobs and m identical parallel machines with availability constraints. Our objective is minimizing the total completion time. . Most scheduling problems assume machines will work continuously, but in fact the situation is not always possible. So we consider the situation that each machine has its own available intervals For example, in the manufacturing industry, machines cannot always be in an operating state. Workers will stop the machines for a preventive maintenance period. It can keep the machines status stable and increase the yield of productions and the service life of the machines. To find out the approximation solution for our problem, we first develop a dynamic programming algorithm. We adopt the proposed schemes of Tsou.(2017) and Chen.(2016) which is/are based on the idea of scheduling. We used three propositions to eliminate the possibility which cannot lead to the optimal solutions. These propositions are compared by the starting time and the number of jobs which are assigned in the available intervals filled up with jobs. Finally, we compare our dynamic programming with the branch and bound algorithm proposed from Tsou(2017).
