儘量減少延遲

有很多問題可以減少延遲，這裡我們有一個資源，一次只能處理一個工作。Job j 需要 tj 個單位的處理時間，並且在時間 th3 到期。如果 j 在時間 sj 開始它將在時間 fj=sj+tj 結束。我們為所有 j 定義延遲 L=max{0,fj-dh}。目標是儘量減少最大延遲 L.

解決方案 L=7 顯然不是最佳的。讓我們看看一些貪婪的策略：

1. 最短的處理時間 ：按升序和處理時間 j`安排作業
2. 最早的截止日期 ：按截止日期的升序安排工作 13
3. 最小的鬆弛 ：按照鬆弛的順序安排工作 14

很容易看出，最短的處理時間首先不是一個好的反例

在最小的堆疊解決方案具有呈三角問題

最後一個策略看起來有效，所以我們從一些虛擬碼開始：

1. 按時間排序 n 工作，以便 d1<=d2<=...<=dn
2. 設定 t=0
3. 為 j=1 到 n
   • 將作業 j 分配給間隔 [t,t+tj]
   • 設定 sj=t 和 fj=t+tj
   • 設定 t=t+tj
4. 返回間隔 [s1,f1],[s2,f2],...,[sn,fn]

並且作為 C++中的實現：

#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <algorithm>

const int jobCnt = 10;

// Job start times
const int processTimes[] = { 2, 3, 1, 4, 3, 2, 3, 5, 2, 1};

// Job end times
const int dueTimes[]     = { 4, 7, 9, 13, 8, 17, 9, 11, 22, 25};

using namespace std;

int main()
{
    vector<pair<int,int>> jobs;
    
    for(int i=0; i<jobCnt; ++i)
        jobs.push_back(make_pair(processTimes[i], dueTimes[i]));
    
    // step 1: sort
    sort(jobs.begin(), jobs.end(),[](pair<int,int> p1, pair<int,int> p2)
                                    { return p1.second < p2.second; });
    
    // step 2: set t=0
    int t = 0;
    
    // step 3:
    vector<pair<int,int>> jobIntervals;
    
    for(int i=0; i<jobCnt; ++i)
    {
        jobIntervals.push_back(make_pair(t,t+jobs[i].first));
        t += jobs[i].first;
    }
            
    //step 4: print intervals
    cout << "Intervals:\n" << endl;
    
    int lateness = 0;
    
    for(int i=0; i<jobCnt; ++i)
    {
        auto pair = jobIntervals[i];
        
        lateness = max(lateness, pair.second-jobs[i].second);

        cout << "(" << pair.first << "," << pair.second << ") "
             << "Lateness: " << pair.second-jobs[i].second << std::endl;
    }
    
    cout << "\nmaximal lateness is " << lateness << endl;
    
    return 0;
}

這個程式的輸出是：

Intervals:

(0,2)   Lateness:-2
(2,5)   Lateness:-2
(5,8)   Lateness: 0
(8,9)   Lateness: 0
(9,12)  Lateness: 3
(12,17) Lateness: 6
(17,21) Lateness: 8
(21,23) Lateness: 6
(23,25) Lateness: 3
(25,26) Lateness: 1

maximal lateness is 8

演算法的執行時間顯然是Θ（n log n），因為排序是該演算法的主要操作。現在我們需要證明它是最優的。顯然，最佳時間表沒有空閒時間。在最早截止時間表也沒有空閒時間。

讓我們假設這些工作是編號的，以便 d1<=d2<=...<=dn。我們說時間表的反轉是一對工作 i 和 j，所以 i<j 但是 j 預定在 i 之前。由於其定義，最早的截止日期第一時間表沒有倒置。當然，如果時間表具有反轉，則其具有連續排程的一對倒置作業。

命題： 交換兩個相鄰的倒置作業會將反轉次數減少一次，並且不會增加最大延遲。

證明： 讓 L 成為交換之前的延遲，然後是延遲的時間。因為交換兩個相鄰的工作並沒有將其他工作從他們的位置移開，所以所有工作都是如此。

顯然，自從工作提前安排工作以來，這一點已經過去了。如果工作 j 延遲，那麼定義如下：

                         Mj = fi-dj    (definition)
                           <= fi-di    (since i and j are exchanged)
                           <= Li

這意味著交換之後的延遲比以前更少或相等。這證明了結論。

命題： 在最早截止時間表 S 是最佳的。

證明:( 矛盾）

讓我們假設 S*是最佳的時間表，反轉次數最少。我們可以假設 S*沒有空閒時間。如果 S*沒有倒置，那麼 S=S*就完成了。如果 S*具有反轉，則它具有相鄰的反轉。最後一個命題表明我們可以交換相鄰的反演而不增加延遲但是減少了反轉次數。這與 S*的定義相矛盾。

最小化延遲問題及其近似相關的最小完工時間問題，其中詢問最小時間表的問題在現實世界中具有許多應用。但通常你不只有一臺機器而是很多機器，它們以不同的速率處理相同的任務。這些問題非常快速地完成了 NP-complete。

另一個有趣的問題是，如果我們不檢視離線問題，我們手頭有所有任務和資料，但是線上變體，執行期間出現任務。