在此研究中，我們考慮當極小化最大延遲時間時，在機器合適度限制與變動機器維修時間下，n個不可分割的工作和m台平行機台的排程問題。每台機器累積一段工作時間後必須進行維修以確保作業正確性，每個工作也只能被安排在某些特定的機器上?進行機器維修的時間點並未固定，在給定機台最大連續工作時間下，決定何時進行維修? 在極小化最大延遲時間的目標式下，首先我們將允許工作切割的排程問題，利用網路流技術轉變成最大流量問題；接著我們提出一個演算法其結合網路流技術與二元搜尋法尋找其問題的最佳解；最後，將結果作為分支界限法的下界，求取不允許工作切割排程問題的最佳解? 實驗的分析顯示，分支界限法所產生的節點數比例非常小，顯示提出的淘汰法則強而有力?我們的演算法能用於12個工作和5台機器問題下而得到一個最佳解。 In this paper we consider the problem of scheduling n independent and non-preemptive jobs into m parallel machines with eligibility constraints and variable machine maintenance intervals while minimizing the maximum lateness. Each machine is not always available for processing and should be shut down for maintenance to prevent malfunction. Each job is only allowed to be processed on a specific machine set. The maintenance of machine is not a fixed time interval known in advance, and the length of each interval is restricted to the given maximum continuously processing time. To minimizing the Lmax firstly, we utilize a network flow technique to formulate the scheduling problem of the preemptive jobs into a series of maximum flow problems. Then, we propose an algorithm which combines a network flow technique and a binary search procedure to solve the problem optimally. Finally, we use the result of the preemptive scheduling problem as the lower bound of the proposed branch and bound algorithm to get the optimal solution of the study problem. Computational analysis shows that the effectiveness of eliminating rules proposed is powerful and very low percentage of nodes is generated by the branch and bound algorithm. Our algorithm can get the optimal solution for the problem with up to 12 jobs and 5 machines.
