目錄
- 線性規劃
- 問題
續排程算法（一）
現在我們介紹線性規劃算法在排程問題中的應用。一個線性規劃問題通常以如下形式出現：
尋找長度為\(n\)的解向量\(x=(x_1,...,x_n)\)，滿足\(m\)個線性限制\(a_{i1}x1+a_{i2}x_2+...+a_{in}x_n\le b_i\)，其中\(1\le i\le n\)，并使得\(c_1x_1+c_2x_2+...+c_nx_n\)最小化，其中\(c=(c_1,...c_n)\)為成本向量。
有的時候，上面的一些限制可能是等式而非不等式，也有的時候甚至不存在需要最小化的目标函數，也就是說目标函數是任意的，我們隻需要尋找到滿足限制條件的解\(x\)即可。這些都算是線性規劃問題的不同形式。許多優化問題都可以轉化為線性規劃求解，而線性規劃問題存在多項式時間算法。本節主要考慮\(R|pmtn|C_{max}\)問題的線性規劃模型。
\(R|pmtn|C_{max}\)問題
在不相關并行環境下進行搶占式排程，優化最終完成時間，不熟悉問題定義的建議回顧一下前面章節。搶占式排程下，單個任務可能在任何機器上運作一部分，為了形式化這個問題，我們使用\(nm\)個變量\(x_{ij}\)，代表任務\(j\)的總任務量在機器\(i\)上執行的比例。例如，如果\(x_{1j}=x_{2j}=1/2\)，則說明任務\(j\)在機器1和機器2上各完成了一半的任務量。
現在我們考慮怎樣的線性限制能夠使\(x_{ij}\)的解符合\(R|pmtn|C_{max}\)問題的定義。顯然，每部分任務的比例必須是非負的，進而有：
\[x_{ij}\ge 0, \ 1\le i\le m,\ 1\le j\le n.
\]
同時，任意有效排程下，每個任務都必須被完成，這意味着：
\[\sum_{i=1}^m x_{ij}=1,\ 1\le j\le n.
我們的設計目标是最小化排程的最終完成時間\(D\)，顯然任何機器上的總處理時間不超過\(D\)，根據之前的定義，不相關并行環境下，任務\(j\)在機器\(i\)上的處理時間記為\(p_{ij}\)：
\[\sum_{j=1}^n p_{ij}x_{ij}\le D,\ 1\le i\le m.
最後，我們還需要保證，所有任務的總處理時間都不超過\(D\)：
\[\sum_{i=1}^m x_{ij}p_{ij}\le D,\ 1\le j\le n.
我們需要在滿足上述限制條件下最小化\(D\)。顯然，任何一個有效排程下的\(x_{ij}\)必然滿足這樣的限制，但是有一事不明：一個滿足限制條件的解并沒有确切指定具體的排程政策——\(x_{ij}\)僅能指定任務在不同機器上運作的比例，而不能保證排程時同一時刻隻能在一個機器上運作（這一條件無法寫成線性限制）。
有趣的是，這個問題可以通過定義一個開放工廠中的房間問題\(O\)來解決。我們為每個\(x_{ij}\)建立一個任務\(j\)在機器\(i\)上的操作，操作的處理時間為\(o_{ij}=x_{ij}p_{ij}\)，現在對于已經通過線性規劃求出的最優的\(x_{ij}\)，我們構造了一個搶占式的開放工廠中的房間問題，優化目标仍是\(C_{max}\)，此問題概括為\(O|pmtn|C_{max}\)，此問題已在上一節通過一個二分圖比對的形式化問題解決了，同時由于有\(D\)限制了任務的最長處理時間和機器的最長負載時間，也就是說\(P_{max},\Pi_{max} \le D\)，新問題的解就是原問題的最優排程。
線性規劃問題不止這點應用，它還能用于設計\(NP\)難問題的近似算法，這将在下一節介紹。
使用松弛法設計近似算法
現在我們轉向設計一些\(NP\)難的排程難題的近似算法。近似算法的設計通常基于相應的\(NP\)難問題的松弛版本。問題的松弛指的是從原問題中去除一些限制形成的新問題。例如\(1|r_j,pmtn|\sum C_j\)就是\(1|r_j|\sum C_j\)的松弛版本，因為實際上搶占式排程比非搶占式排程簡單多了，更容易計算最優解。另一種松弛的思路是移除“一個機器隻能同時處理一個任務”的條件，讓一個機器可以在同一時間運作多個任務。
顯然，原問題的解一定是松弛問題的解，反之不一定。我們在上面章節提到的所有非搶占式排程算法都能用于解決搶占式排程，其解雖然可能不最優，但合法。同樣地，松弛問題的最優解即使是合法的，也不一定達到原問題的最優解。
在這一課題上一個有效的想法是：設計一個可以在多項式時間内解決的松弛問題，然後再設計一個将松弛問題的解轉化為原問題可行解的算法，并保證解盡量接近最優解。問題的關鍵是設計的松弛問題盡可能包含原問題較多的資訊，使得松弛問題的最優解與原問題最優解盡可能接近。
本節将介紹兩種對排程問題的松弛方法，一是通過非搶占式到搶占式的松弛，二是通過構造線性規劃問題，松弛某些線性限制來實作。将松弛解轉化為原問題解的方法也有兩種，一是根據任務與機器的配對，二是根據任務在機器上的執行順序。後面會詳細介紹。
在開始本節内容之前，我們先介紹一個概念：松弛決策過程（relaxed decision procedure, RDP）。一個最小化問題的\(\rho\)-\(RDP\)定義為，接受一個目标值\(T\)，如果松弛問題沒有小于等于\(T\)的解則傳回\(None\)，否則傳回一個不超過\(\rho T\)的原問題解。一個多項式時間的\(\rho\)-\(RDP\)能夠很容易的轉化為原問題的\(\rho\)-近似算法：通過對\(T\)進行二分查找，尋找最小的\(T\)，使得松弛問題有解并将此解轉化為原問題的解。
為什麼是\(\rho\)-近似的呢？邏輯是這樣：假如原問題有最優解\(T^*\)，則松弛問題在\(T^*\)下必有解，将這個解轉化為不超過\(\rho T\)的原問題解，這個過程構成\(\rho\)-近似算法。下面将應用這個設計思路。
\(R||C_{max}\)問題
本節給出一個\(R||C_{max}\)的\(2\)-近似算法。我們剛剛用線性規劃解決過的\(R|pmtn|C_{max}\)問題，是這個問題的搶占式松弛版本，實際上，如果我們加一條限制\(x_{ij}\in \{0,1\}\)，就是非搶占式排程的線性規劃模型了。實際上加上這個條件後，原先的第3條限制可以使得第4條限制多餘，是以同樣的模組化下，本問題的線性限制為：
\[\sum_{i-1}^m x_{ij}=1,\ for\ j=1,...,n \\\sum_{j=1}^n p_{ij}x_{ij}\le D,\ for\ i=1,...,m \\x_{ij}\in \{0,1\},\ for\ i=1,...,m,\ j=1,...,n
這是一個整數線性規劃問題，相比于一般的線性規劃問題，整數線性規劃是\(NP\)難的，是以問題并沒有變簡單。但是，我們提出的模型是有用的，可以用來松弛某些限制，例如得到一個非整數解，然後舍入到整數。
現在我們再次将整數限制松弛為\(x_{ij}\ge 0\)，但這就太松了一點，我們還要添加一個限制：如果一個任務\(j\)在機器\(i\)上的效率過慢，即\(p_{ij}\ge D\)，就不把這個任務配置設定到機器\(i\)：
\[x_{ij}=0,\ if\ p_{ij}\ge D. \tag{4}
這個限制在原來的整數線性規劃模型中是天然成立的，但我們移除整數限制後就需要手動添加。注意到，當\(D\)固定時，這是個簡單的隻有線性限制的規劃問題（沒有成本函數），我們隻要找可行解即可。如果對于給定的\(D\)，問題沒有解，則輸出\(None\)，如果有解，我們就嘗試将非整數解轉化為原問題的可行整數解。
根據一個線性規劃問題的基本結論：我們可以找到一個此問題的可行解，其中最多隻有\(n+m\)個正值。這\(n+m\)個正的\(x_{ij}\)指定了\(n\)個任務的去向，假設這些\(x_{ij}\)中等于1的數量為\(k\)，則\(k\)個任務已經被完全指定去向，剩餘\(n-k\)個任務需要至少\(2(n-k)\)個\(x_{ij}\)指定去向（因為非整數意味着至少被配置設定在兩台機器上），故\(k+2n-2k\le m+n\)，故\(n-k\le m\)，意味着至多有\(m\)個任務被配置設定在不止一台機器上。
現在，我們将所有\(x_{ij}=1\)的任務\(j\)直接配置設定到機器\(i\)，這部分排程記為\(S_1\)，剩餘還有至多\(m\)個任務需要排程。我們簡單地按照\(x_{ij}>0\)的解将任務\(j\)比對到機器\(i\)，且保證每個機器至多一個任務（因為這部分任務不超過\(m\)個），這部分任務的排程記為\(S_2\)。關于\(S_2\)的存在性證明稍微有點複雜，感興趣的請讀[1]。
我們分析一下這樣形成的排程政策的完成時間，它顯然不超過\(S_1\)的完成時間加上\(S_2\)的完成時間。而由于\(x_{ij}\)是松弛問題的可行解，是以\(S_1\)的完成時間是\(\le D\)的，在\(S_2\)中，由于每個機器至多一個任務，且由于限制\((4)\)，\(x_{ij}>0\)意味着\(p_{ij}\le D\)，進而\(S_2\)的完成時間也是不超過\(D\)的，故這樣排程的時間不超過\(2D\)。是以假設原問題的最優解是\(D\)，則該松弛問題必有解，且該解不超過\(2D\)。
\(1|r_j|\sum C_j\)問題
前面已經提到，帶釋出時間的單機排程問題是\(NP\)難問題，本節将設計一個解決此問題的近似算法。對于此問題的搶占式版本，前面已經證明了最短剩餘時間優先算法\(SRPT\)的最優性。利用這個松弛，我們将從其最優解中找出各任務的完成時間順序，然後以相同的順序建構非搶占式排程政策。此算法稱為Convert-Preempt-Schedule，反轉搶占式排程。
我們首先使用\(SRPT\)算法建構搶占式排程版本的最優解，然後按照該最優解中各任務的完成時間排序，按照\(C_1^P\le ...\le C_n^P\)給這些任務重新編号。而後按照相同順序非搶占式的排程這些任務，如果某個時間點後繼任務還未釋出，就讓機器空閑即可。可以證明，這個算法是\(2\)-近似的。
證明：對于任務\(j\)，由于其在搶占式排程中能在\(C_j^P\)時完成，是以假如沒有其他任務，則它最晚也能在\(C_j^P\)時完成，當存在其他任務後，我們在其完成前插入了排在它前面的任務，是以它的最晚完成時間延長為：
\[C_j\le C_j^P+\sum_{k\le j}p_k
而由于在搶占式排程中，所有\(k\le j\)的任務都在\(C_j^P\)之前完成了，是以\(\sum_{k\le j}p_k\le C_j^P\)，進而有：
\[\sum_{j=1}^n C_j \le 2\sum_{j=1}^n C_j^P
假設非搶占式排程的最優解是\(\sum C_j^P\)，則對于搶占式的松弛版本必然有不超過\(\sum C_j^P\)的最優解，而通過上述分析可知此算法給出的解不超過搶占式最優解的兩倍，證畢。
\(1|r_j,prec|\sum w_jC_j\)問題
這一節依然使用松弛法來解決這個難題（基本上是目前遇到的最難的單機排程問題了），我們采用線性規劃來設計一個2-近似算法。
首先我們描述這個問題的線性規劃限制，和之前不同，我們不從整數/非整數的角度松弛，而是從問題定義中尋找必要條件，形成一個線性規劃問題。
對這個問題來說，任務運作的順序極其重要，是以我們要尋找一種能表示任務順序的形式化描述。很容易想到用時間來表示：定義\(C_j\)為任務\(j\)在排程政策中的完成時間。實際上這就能夠完确定一個排程了（比之前的\(x_{ij}\)更清晰）。顯然，最小化的成本函數是\(\sum w_jC_j\)。并且滿足如下條件：
\[C_j \ge r_j+p_j,\ j=1,...,n.\\C_k \ge C_j+p_k,\ for\ each\ j<k.\\C_k \ge C_j+p_k \ or\ C_j \ge C_k+p_j,\ for\ each\ j \not= k.
這三個條件很容易了解，首先任務必須在釋出時間後才能開始，其次需要等待任務所有的前驅任務完成才能開始，最後，任意兩個不同的任務存在先後關系（處理時間不重疊）。
不幸的是，最後一個限制有“或”運算，不是一個确定的線性限制，這導緻這個問題不是線性規劃問題。我們嘗試用不等式代替它。定義任務集\(J=\{1,...,n\}\)，對任意子集\(S\subseteq J\)，定義\(p(S)=\sum_{j\in S}p_j\)，\(p^2(S)=\sum_{j\in S}p_j^2\)。對任何可行的單機排程政策，可以證明下面的不等式成立：
\[\sum_{j\in S}p_jC_j\ge \frac{1}{2}(p^2(S)+p(S)^2),\ for\ each\ S\subseteq J.\tag{*}
證明：假設\(S\)中的任務按照完成時間升序編号。由于任意的任務\(j\)的完成時間大于在其前面完成的所有任務的處理時間之和，即\(C_j\ge \sum_{k=1}^j p_k\)，代入上式左邊得：
\[\sum_{j\in S}p_jC_j\ge\sum_{j\in S}p_j\sum_{k=1}^jp_k=\frac{1}{2}(p^2(S)+p(S)^2)
對于沒有釋出時間，沒有任務依賴的問題\(1||\sum w_jC_j\)問題，上面這個不等式的限制是完備的[37,41]，可以形成一個可行解。現在把上面這個不等式加上原先的第一個和第二個不等式，組成\(1|r_j,prec|\sum w_jC_j\)的線性限制，這個新的線性規劃問題是原問題的松弛問題。
注意到我們新提出來的不等式似乎有\(2^n\)個，但是它仍然可以被線性規劃的橢圓算法[37,41]在多項式時間内解決。
現在為了簡單起見，我們移除釋出時間限制，隻探讨\(1|prec|\sum w_jC_j\)問題，其對應的松弛問題将移除上面提到的第一個不等式。解上面的線性規劃問題得到的解為\(C_1\le C_2\le...\le C_n\)，我們将證明按照這個順序來排程任務是2-近似的。
假設上面的排程形成的新的完成時間為\(\tilde{C_j}\)，按照慣例，我們隻需證明\(\tilde{C_j}\le 2C_j\)就行。首先，設\(S=\{1,...,j\}\)，沒有了釋出時間機器是沒有空閑的，是以\(\tilde{C_j}=p(S)\)。同時根據上面提到的不等式\((*)\)，我們有：
\[\sum_{k=1}^jp_jC_j\ge \frac{1}{2}(p^2(S)+p(S)^2)\ge \frac{1}{2} p(S)^2
又因為\(C_1\le C_2\le...\le C_n\)，我們有：
\[C_jp(S)=C_j\sum_{k=1}^j p_k\ge\sum_{k=1}^j C_kp_k\ge \frac{1}{2} p(S)^2
故\(\tilde{C_j}=p(S)\le 2C_j\)，證畢。