本研究探討雙機等效平行機台(Two Identical Parallel Machine)之排程問題,考慮有 個獨立工件在兩台機台上進行加工,考慮只有單一操作人員且工件具有整備時間及交貨時間之限制條件下,以最大延遲時間最小化為目標,數學表達形式為 。 在考慮工件具有交替的排序之下,提出一個整數規劃模式求最佳解,並利用EDD(Earliest Due Date)與SST(Smallest Slack Time)兩個演算法則與其比較,並探討兩個演算法與最佳解之求解誤差,找出適合兩個演算法的求解環境。本研究之實驗結果顯示在不同的工作數之下,兩個演算法與數學規劃模式之平均誤差在交貨時間落於兩組因子組合之下,求解誤差為最小,若考慮求解速率下我們可以說這兩個演算法在這兩組交貨時間範圍是適用的。
In this work studies we consider the problem of scheduling n jobs on two identical parallel machines with a single server and jobs have setup time and due date. Our objective is to minimize maximum lateness and problem is denoted as . Consider the jobs are processed alternately on the machines, we developed a integer programming model to compute this scheduling problem, and to used Earliest Due Date and Smallest Slack Time two rules to compare result, and to discuss two algorithms’ solved error, find the appropriate two algorithms solving environment. In the experimental results we known that the two algorithms for solving the error under the two groups of the experimental factor with due date range, the errors are the smallest, so if we consider execution time we can say that these two algorithms in these two groups of factor with due date range is applicable.