尽量减少延迟

有很多问题可以减少延迟，这里我们有一个资源，一次只能处理一个工作。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。

另一个有趣的问题是，如果我们不查看离线问题，我们手头有所有任务和数据，但是在线变体，执行期间出现任务。