求取平行機台排程答案的近似方式

本研究將探討兩個平行機台排程問題（ !"|$% = $| '%(% 與!"|$% = $| '%(% ） ，這兩排程問題以極小化加權延遲時間為目標，工件(Job)皆有共同的交期。Tuong, Soukhal, and Billaut(2009)提出兩個類多項式動態規劃演算法(Pseudo-polynomial dynamic programming algorithms)分別來求解此兩問題，此 !"|$% = $| '%(% 的 演算法有複雜度O "#$%&'#()#*% ++ ，而解!"|$% = $| '%(% 的 演算法則有複雜度O "#$%&'($)*$+& !" = $%"%&' 有 可能是一個非常大的數值。目前為止，並沒有研究學者對此兩問題提出近似方式(Approximation scheme)以求解。根據我們的初步研究，當最佳解的求解方式是以動態規劃為基礎時，許多研究者皆已成功地以構建輸入技巧（Structuring input technique）來發展以完全多項式近似方式(Fullypolynomial-time approximation scheme)來求解。因此，本研究將以構建輸入技巧來發展兩個 ρ 近似演算法(ρ - approximation algorithm)來求解此兩排程問題，在此 ρ = 1 + ε for any ε > 0， 且此兩個完全多項式近似方式演算法的運算時間複雜度為問題大小（Input size）與 1/ε的 多項式。