基于时索引非抢占式单机调度问题的高效有效不等式

《Discrete Optimization》：Valid inequalities for the Time-Indexed Non-Preemptive Single Machine Scheduling Problem

本篇论文针对T-SMSP这一NP-hard优化问题，提出了一类新颖的CNC（Clique and Node Cover）有效不等式。研究证明，在特定规划期假设下，这些不等式定义了一个比前人研究更紧的松弛问题的凸包面。更重要的是，新不等式不被经典的RHS不等式所支配，甚至在某些情况下能够支配或等效于它们。初步计算实验表明，将CNC不等式（特别是CNC1和CNC2）集成到切割平面算法中，能更显著地缩小对偶间隙，展现了优越的计算性能潜力。

　　

Highlight

本文介绍了一类用于时索引非抢占式单机调度问题（Time-Indexed Non-Preemptive Single Machine Scheduling Problem, T-SMSP）的新型有效不等式（Valid Inequalities, VI）。在对规划期长度做出一定假设后，我们证明了这些不等式能为T-SMSP的一个松弛问题（比文献中考虑的松弛更紧）的凸包定义面。此外，我们证明所提出的有效不等式集合不被某些针对该问题的现有有效不等式所支配，并且它们要么支配、要么与某些现有不等式等价。将这些不等式整合到切割平面算法中的计算性能表现出了显著的前景。

Section 2：基于节点覆盖的有效不等式

让我们定义所有“工单-时间”对的集合为V。G(V,E) 是问题P的无向冲突图，其中边集E的定义保证了若 ((u, t₁), (v, t₂)) ∈ E，则P中的任何解都满足 x_u,t1+ x_v,t2≤ 1。这本质上意味着两个工单的执行时间不能重叠。

Section 3：基于团和节点覆盖的有效不等式

本节我们提出了CNC₁有效不等式的推广形式。令C_k为图G(V,E)中所有规模为k的团的集合。对于C_k∈C_k中的每个节点f，让X^f表示所有节点覆盖的并集。利用这些记号，我们得到以下命题：

命题4：对于每个 C_k∈C_k，以下不等式对P有效：

∑_f∈Ckx_{jf, tf}≤ ∑_{(l,τ)∈∪f∈CkS^f}x_l,τ, ?S^f∈X^f, f∈C_k

其中 ∪_f∈CkS^f恰好包含每个节点f对应的一个节点覆盖。

Section 4：与现有有效不等式的比较

我们首先证明，没有一个CNC有效不等式被Van den Akker等人提出的RHS（Right-Hand-Side）有效不等式所支配。

命题7：CNC有效不等式不被RHS有效不等式支配。

证明：考虑某个C_k∈C_k和 X=∪_f∈CkS^f对应的CNC_k不等式。构造一个特定解x^*，它属于RHS不等式成立的松弛集P^L，因此满足所有RHS不等式。然而，这个x^*却违反了为C_k和X定义的CNC_k不等式。□

从命题7，我们可以推断出CNC有效不等式要么是全新的、更强大的不等式，要么在某些情况下与现有不等式有不同但等效的表达形式。

Section 5：计算实验

本节的目标是在假设有一个提供CNC有效不等式精确分离算法的“黑箱”前提下，评估CNC有效不等式的计算性能。我们通过测量将它们纳入T-SMSP的线性规划（LP）松弛后能缩小多少对偶间隙来评估其有效性。由于分离CNC_k不等式的难度随着k值增大而增加，我们将实验限制在CNC₁和CNC₂不等式上。实验结果表明，与RHS不等式相比，所提出的不等式平均能显著缩小更大的对偶间隙。

Section 6：结论

本文针对时索引非抢占式单机调度问题（T-SMSP）引入了一组新颖的有效不等式，称为CNC（Clique and Node Cover）不等式。我们证明，在关于规划期长度T的某些假设下，它们为T-SMSP的一个比Van den Akker等人[4]所考虑的松弛更紧的松弛问题的凸包定义面。此外，我们证明了CNC有效不等式不被Van den Akker等人[4]提出的任何RHS有效不等式所支配，并且其中一些不等式要么支配RHS不等式，要么与其等价。