在此研究中，我們考慮最小化總完工時間時，在機器可用區間與機器和適度限制下， n 個具有不同發放時間且無法被分割的工作與 m 台工作效率相同的平行機台之排程問題。每台機器並非一直處於可使用狀態，也就是我們也考慮會有例行停機維修的狀況；而每個工作可開始執行的時間通常是不盡相同，工作也會因工作本身的特性而對應出其合適加工的機台。 我們提出一個分支界限的演算法去尋找此問題的最佳解。在演算法中，我們探討了兩種分支的方式：一種為採用Melloui et al. (2009)所提出的分支方法；另一種則是自己提出的分支方法，兩者最大不同在於後者方式具有順序排程的概念，根據自己提出的分支方式再提出減少分支的規則。接著在未排的時間區間下將原問題釋放機器和適度限制並允許工作可以被切割，藉此可採用Yalaoui and Chu (2006)提出之特性來解轉換後問題並求得下界。 ;In most scheduling problem, machines are always continuously available to process jobs all the time. However, it usually exist unavailable time intervals for routine maintenance in practice. Besides, some job is suitable for specific machines to process based on the property of job. In this study, we consider the problem of scheduling n non-preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time. For the scheduling problem, we use branch and bound method to find the optimal solution. In the branch and bound algorithm, we discuss two way of branching. First one is, we adopted the branching scheme from Mellouli et al. (2009) which concept is through assigning an additional job on each available interval. We also propose the other approach of branching which contained the concept of forward scheduling. Based on the branching scheme we proposed, we also propose a dominance rule to eliminate redundant nodes. We adopted the property in Yalaoui and Chu (2006) which could solve the reduced problem by relaxing the restriction of machine eligibility constraint and allow jobs split, and let the optimal solution to be our lower bound.
