具機器可用區間限制之平行機台排程之完全多項式近似方式

本研究將探討平行機台排程問題，這排程問題以極小化總完工時間為目標，每一機台有一事先排定的維修時間。Mellouli 等於2009年提出一個類多項式動態規劃演算法(Pseudo-polynomial dynamic programming algorithms)來求解此問題。目前為止，並沒有學者對此問題提出完全多項式近似方式(Fully polynomial-time approximation scheme；FPTAS)來求解。Schuurman 與 Woeginger (2011) 以及 Woeginger (2000) 指出，為了保證能有具修剪求解空間法(trimming-the-state-space approach)為基礎的FPTAS的存在，排程問題與其動態規劃演算法須具有某些特性且能符合某些條件。根據我們初步的研究，本排程問題與Mellouli 等提出的動態規劃演算法都能符合這些特性及條件。因此，本研究嘗試依據修剪求解空間法，於動態規劃演算法各階段(phase)中減小求解之空間(Thin out the state space)，以降低求解所需要的時間，並求能掌控誤差的增長(Propagation of error)，以發展一個 ρ近似演算法(ρ-approximation algorithm)來求解此排程問題(在此 ρ=1+ε for any ε > 0；ε為誤差)， 且此一個完全多項式近似方式的運算時間複雜度為問題大小（Input size）與 1/ε的多項式。