最小迟序排工问题（Minimum tardiness sequencing）

作为排工问题，该问题和区间排工问题相似但又不同。不同之处有：

该问题的形式化定义如下：

实例： 任务集合 T,T, 每个任务 t∈T,t \in T, 都有加工长度 L(t)=1,L(t)=1, 加工最后期限 d(t)∈Z+d(t) \in Z^{+}。 在集合 TT 上有半序关系 ⋖\lessdot 以及非负整数 K⩽T⌉∘K \leqslant T\rceil_{\circ}

询问： 是否存在 TT 的排工表 σ:T→{0,1,⋯ ,∣T∣−1},\sigma: T \rightarrow\{0,1, \cdots,|T|-1\}, 使得当 t≠tt \neq t '有 σ(t)≠σ(t′),\sigma(t) \neq \sigma\left(t^{\prime}\right), 当 t⋖t′t \lessdot t^{\prime} 时, 有 σ(t)<σ(t′),\sigma(t)<\sigma\left(t^{\prime}\right), \quad 且| {t∣t∈T,σ(t)+1>d(t)}∣⩽K\{t \mid t \in T, \sigma(t)+1>d(t)\} \mid \leqslant K。

该问题询问中条件 ∣{t∣t∈T,σ(t)+1>d(t)}∣⩽K|\{t \mid t \in T, \sigma(t)+1>d(t)\} \mid \leqslant K 表示在排工表 σ\sigma 中，未能按期完成任务的 数目不超过 K∘K_{\circ}

该问题可以通过将图的 团问题 归约到该问题证明。

NPC 证明

如果一个图内有一个 NN 个点的团（也即完全图），那么相应的，就会有N(N−1)2\frac{N(N-1)}{2} 条边。

现在逐步将团问题实例 G={V,E},J∈Z+G=\{V,E\}, J \in Z^{+} 转换为最小迟序排工问题。

首先，将团问题实例中的图 G={V,E}G=\{V,E\} 中的边和点都视为加工长度为 1 的任务，此时任务总数就是 ∣V∣+∣E∣|V|+|E|。

随后添加半序约束：当两点 u,vu,v 之间存在边 ee 时，这两个点任务的优先级要比边任务 ee 要大。形式化表述为：

u⋖e,v⋖e, 当且仅当 e=(u,v),u,v∈V,e∈Eu \lessdot e, v \lessdot e, \text { 当且仅当 } e=(u, v), u, v \in V, e \in E

此时，令排工问题中 最多不需要按期完成任务的数目 K=∣E∣−J(J−1)2K =|E|-\frac{J(J-1)}{2}，那么 最少需要完成的任务数 也可以根据总数计算得到，为 ∣E∣+∣V∣−K=∣V∣+J(J−1)2|E|+|V|-K = |V|+\frac{J(J-1)}{2} 个任务

注意到 ∣V∣|V| 刚好是原图点的数量，而剩下的 J(J−1)2\frac{J(J-1)}{2} 则刚好是原图中完全子图（若能找到）的边的数量。

此时，定义所有边任务 e 和所有点任务 v 的最后期限分别为：

d(e)=J(J+1)2,e∈Ed(e)=\frac{J(J+1)}{2},e\in E

d(v)=∣V∣+∣E∣,v∈Vd(v)=|V|+|E|, v\in V

因为 J=J(J+1)2−J(J−1)2J=\frac{J(J+1)}{2}-\frac{J(J-1)}{2}，且点任务的优先级比其连接的边任务高，所以在边任务的期限 J(J+1)2\frac{J(J+1)}{2} 结束之前，最多只能完成 J(J−1)2\frac{J(J-1)}{2} 个边任务，且必须附带完成 JJ 个点任务。

(<-) 此时，设在期限 J(J+1)/2J(J+1)/2 之前完成的边任务为 E′E',点任务为 V′V'，那么 (V′,E′)(V',E') 根据其数量和优先级，显然一定构成了一个完全图。

(->) 如果团问题的任意实例 G=(V,E)G=(V,E) 含有 JJ 个顶点的团，则最小迟序排工问题相应实例的排工安排即为团对应的点任务和边任务。

ps1： 是否存在任务安排，使得点任务完成了个 ∣V∣−1|V|-1，而边任务完成了 J(J−1)2+1\frac{J(J-1)}{2}+1 个? 答案是否，因为完成 J(J−1)2+1\frac{J(J-1)}{2}+1 个边任务需要至少 J+1J+1 个点，而边任务的最后期限是 d(e)=J(J+1)2d(e)=\frac{J(J+1)}{2}，边任务的完成数量不可能超过 J(J−1)2\frac{J(J-1)}{2} 个。