本研究主旨在考慮極小化最晚完工時間之排程問題，首先探討n個可切割的工作在m台平行機台的排程問題，其中機器受限於可用時間與合適度的限制條件，而工作之間也有工作群組的限制。接著將問題延伸到一般性的n個不可切割工作在m台平行機台之排程問題。其限制條件有，機台無法一直處於可接受處理的狀態，例如：機台的損壞、維修；每個工作擁有其專有的特性，所以每個工作只能被安排在特定的機台接受服務；某些特性相近的工作會屬於同一個工作群組，當屬於同一個工作群組的工作要在同一台機台的同一個可用時間內接收服務，則將只能選擇其中之一接受服務。 我們首先提出結合最大流量法和二元搜尋法去求得在工作可切割的環境下的最佳解，接下來我們探討工作不可分割的情況下的延伸問題，首先將在工作可切割的環境下所得到的最佳解值，與我們所呈現的分支界限法每個節點所算出的下限值取較大者當分支界限法的下限值，再利用最大處理時間優先法則求得問題的上限值。最後我們提出三個優先法則來增加我們所提出的分支界限法的演算效率。 從數值分析的結果中可以呈現出，我們所提出的優先法則有效率的刪除掉一些不必要產生的節點。我們所提出的演算法能用於7個工作、5台機台和3個工作群組的問題下求得最佳解。In this paper we first consider the scheduling problem of n preemptive jobs on m identical parallel machine with machine availability, eligibility and job family constraints when minimizing the maximum completion time. Then we extend the scheduling problem to n non-preemptive jobs. Each machine could not available all time such as machine breakdown or preventive maintenance. Each job has its own characteristics, so it could only be processed on specified machines. Some similar jobs belong to the same family, it means that only one job of the family can be processed on the same availability interval of machine. We propose a maximum network flow and a binary search algorithm to solve the preemptive problem, and use its solution to compare with each node of lower bound by our propose branch and bound algorithm, then we obtain the bigger one to be the lower bound of non-preemptive problem, and use the longest processing time first rule (LPT) to find an upper bound. Finally, we provide three dominance rules to increase the efficiency of the branch and bound algorithm. Computational analysis shows that dominance rules could effectively eliminate unnecessary nodes. Our algorithm could get the optimal solution for the problem with up to 7 jobs, 5 machines, and 3 job families effectively.
