我们假设一个时间点只能处理一个任务，处理任务 j j j所需处理时长为 t j t_j tj且到期时间为 d j d_j dj。 如果任务 j j j的开始时间为 s j s_j sj，那么它的完成时间为 f j = s j + d j f_j = s_j + d_j fj=sj+dj 任务 j j j的延迟为： l j = m a x { 0 , f j − d j } l_j = max\{0,f_j-d_j\} lj=max{0,fj−dj} 目标：设计一种安排策略最小化最大延迟，即 L = m a x j l j L =max_j{l_j} L=maxjlj
按照到期时间从早到晚进行排序，然后无间隙执行，得到的就是最优解 下图就是贪心安排的一个图，最大时延为1
若一个最优解中任务之间存在间隙，则我们一定能找到另一个任务间不存在间隙的最优解。如下图： 我们的贪心策略中任务之间是不存在间隙的
逆序对：若任务 i i i的到期时间 d i d_i di小于任务 j j j的到期时间 d j d_j dj，但任务 j j j却安排在了任务 i i i的前面，那么我们称 ( i , j ) (i,j) (i,j)为一个逆序对。如下图所示： 我们的贪心策略是任务之间不存在间隙且无逆序对的唯一安排
如果一个任务之间不存在间隙的安排存在逆序对，那么一定存在一个相邻的逆序对 证明：（反证法） ①我们假设 ( i , j ) (i,j) (i,j)是最近的一个逆序对，且它们之间不相邻， k k k为与 j j j相邻的右边元素。如上图所示 ②则，如果任务 j j j的到期时间大于任务 k k k的到期时间，那么 ( i , j ) (i,j) (i,j)是一个相邻的逆序对，假设错误；如果任务 j j j的到期时间小于任务 k k k的到期时间，由于 l i < l j < l k l_i<l_j<l_k li<lj<lk，因此 ( i , k ) (i,k) (i,k)也是一个逆序对且比逆序对 ( i , j ) (i,j) (i,j)更近，假设错误； 综上：如果一个任务之间不存在间隙的安排存在逆序对，那么一定存在一个相邻的逆序对
交换两个相邻的逆序对，不会增加最大时延，且有可能减少最大时延。 证明： 我们设 l l l为交换之前的时延， l ′ l^{'} l′为交换之后的时延，则有以下结论 ①对于所有的 k ≠ i , j k\neq i,j k=i,j， l k ′ = l k l_k^{'} = l_k lk′=lk，因为这些任务前后没有进行交换 ② l i ′ ≤ l i l_i{'} \leq l_i li′≤li， 交换之后任务 i i i的处理时间提前，因此时延小于等于交换之前 ③ l j ′ = f j ′ − d j = f i − d j ≤ f i − d i ≤ l i l_j^{'} = f_j{'}-d_j= f_i - d_j\leq f_i - d_i \leq l_i lj′=fj′−dj=fi−dj≤fi−di≤li 综上结论：交换后无论任务 i , j i,j i,j的延迟都不会超过交换前任务 i i i的延迟
反证法：若最优解存在一些逆序对 我们可以假设其中一个最优解 S ∗ S^* S∗没有间隙时间 如果 S ∗ S^* S∗存在一个逆序对，那么我们可以保证不增加最大时延的情况下消除该逆序对。 重复上述操作，我们可以得到一种最优解不存在逆序对且没有间隙时间，而这种方案唯一且为我们的贪心解，因此我们的贪心策略可以得到最优解。
