在此研究中，我們討論n個不可被分割的工作和m台平行機台的排程問題，針對每台機台具有不同的可用區間限制狀況，考慮最小化總完工時間。在大多數的排程問題研究中都不考慮機台有可用區間的限制，然而在實務上這種條件限制的情況是很常見的。例如在製造業中，機台不可能一直處於運轉的狀態，會針對機台進行例行停機維護，以提升機台在生產時的良率以及壽命。 為了找出此問題的最佳解，我們提出了一個分支定界演算法。在此演算法中，我們採用Chen (2016)所提出的分支方式作為我們的分支方法，此分支方是利用到順序排程的概念。接著提出兩個命題，比較兩個排滿工作的可用區間的開始時間以及所被安排工作數的關係，判斷此部分排程是否不可能為最佳解，藉以在展枝時減少展出不必要的節點。我們調整Chen (2006)所提出的下界方式，利用工作可以被搶斷以及可以同時在不同機台工作之特性求得下界。最後我們也與Chen (2006)所提出的演算法進行比較，不管是在比較演算法可以求解的問題大小，或者是在總共展出的節點數與CPU處理時間上，我們的演算法都表現得比較好。 ;In this research, we consider the scheduling problem with n non-preemptive jobs and m identical parallel machines under availability constraint. Cause of the availability constraint, each machine has its own available processing time. And the objective of our scheduling problem is to minimize the total completion time. Most research in scheduling area assumes machines can work continuously but that is not possible in reality. For example in industrial manufacturing, workers will stop the machines in a period for preventive maintenance. It can keep the machines status stable and have good production quantity. To find out the optimal solution for our problem, we propose a branch and bound algorithm. We adopt the branching scheme Chen. (2016) proposed which is based on the idea of forward scheduling. Then, we propose two propositions to eliminate the nodes which cannot lead to optimal. The propositions are developed by comparing the starting time and the number of jobs assigned in the available intervals which are filled up with jobs. The lower bound calculation is modified from Chen (2016). We add job splitting constraint into the original problem and solve by SPT rule. Finally, we compare our algorithm with the algorithm proposed from Chen (2016) which can solve our problem. No matter comparing the maximum size of instance the algorithm can solve or the performance of number of nodes and CPU run time, our branch and bound algorithm has better performance.
