在此研究中，我們考慮在機器可用區間、機器合適度及與工作順序相關之設置時間限制下求取最小總完工時間之近似解的排程問題。我們有n個具不同發放時間及與工作順序相關之設置時間的工作，以及m台平行機台。每台機器並非可以一直使用，我們考慮在每部機台中皆會有一例行維修的情況；每個工作可以加工的機台與可以開始加工的時間也不同；並且還有工作順序相關之設置時間，也就是設置時間會根據目前將要加工的工作以及前一個在此機台上加工的工作來決定。為了減少求解問題的時間與記憶體，我們求取其近似解。 在本研究中，我們提出一個近似演算法去尋找這個排程問題的近似解。在演算法中，我們採Woeginger(2000)與Kacem and Mahjoub (2009)提出的方法。首先，用動態規劃來求取每一輪的子結果，再把每一輪中有近似關係的子結果刪除到僅剩一個，並用剩下的子結果再去進行下一輪計算直到動態規劃結束，並取最後一輪的子結果中最小的總完工時間作為此排程問題的答案。 ;In this research, we find the minimizing total completion time of a scheduling problem on parallel machines with consideration of machine eligibility, preventive maintenance and sequence-dependent setup times. In our problem, we have n non-preemptive jobs with their release times and sequence-dependent setup times on m parallel machines. Each machine cannot serve jobs at every time point, that is, we consider a preventive maintenance on each machine. Each job has its release time and a set of eligible machines, and also a sequence-dependent setup time which determined by current job and the previous job. In order to reduce CPU run time and memory while solving a scheduling problem by finding an optimal solution, we try to find out a near-optimal solution for the problem. We propose an approximation algorithm to solve our scheduling problem approximately. In the algorithm, we use methods which proposed by Woeginger (2000) and Kacem and Mahjoub (2009). At first, a dynamic program is presented to calculate output of partial schedule in each iteration. After mapping at the end of each iteration, we use trimming-the-state-space technique to trim outputs which are close to each other and left only one of these states in state space. Finally, at the end of the final iteration, we find the minimum objective value which is stored in the left states.
