2.4　问题1｜ r _j ｜∑w _j C _j

对于工件具有就绪时间的排序问题1｜ r _j ｜ ∑w _j C _j ，显然线性规划（LP 2.7）与线性规划（LP 2.8）也都是其线性规划松弛，因此，算法2.2也是求解排序问题1｜ r _j ｜ ∑w _j C _j 的3-近似算法。在这一小节里，我们将引入新的决策变量来刻画排序问题1｜ r _j ｜ ∑w _j C _j ，这一新决策变量就是时间指标变量。时间指标变量最早由Dyer & Wolsey（1990）引入，定义如下：表示工件在某一单位时间加工的0-1决策变量｛ y _{j τ} ｜ j ＝1，2，…， n；τ＝r _j ，…，T －1｝，其中， T 表示工件最迟完工时间的一个上界，比如这个上界可以取值为 T ＝ r _max （ J ）＋ ，若工件 j 在时间区间 ［τ，τ＋1） 上加工，则定义 y _{j τ} ＝1，否则定义 y _{j τ} ＝0。

对于排序问题 1｜r _j ｜∑w _j C _j ，下面将给出两种不同线性规划松弛，并根据这两种线性规划松弛得到性能比更好的近似算法（Geomans et al.，2002）。为了得到排序问题 1｜r _j ｜∑w _j C _j 的线性规划松弛，我们先给出下列结果。

引理2.3 对于排序问题1｜ r _j ｜ ∑w _j C _j 的任意可行序，设 C _j （j＝1，2，…，n） 是工件 j 的完工时间，｛ y _{j τ} ｜ j ＝1，2，…， n；τ＝r _j ，…，T－1 ｝的值按上述定义取值，则

证明 设工件 j 的开工时间为 t _j ，则

由引理2.3得到下列排序问题 1｜r _j ｜∑w _j C _j 的线性规划松弛：

我们将工件完工时间

代入线性规划（LP 2.9）的目标函数中，这样得到一个运输问题（Dyer & Wolsey，1990），从而可以假设｛ y _{j τ} ｜ j ＝1，2，…， n；τ＝r _j ，…，T －1｝是整数，即有下列结论（Geomans et al.，2002）。

引理 2.4 对于线性规划（LP 2.9），存在一最优解满足｛ y _{j τ} ｜ j ＝1，2，…， n；τ＝r _j ，…，T －1｝是整数。

为了得到线性规划（LP 2.9）的最优解，下面给出LP序的概念。将所有工件按 的非降序标号，即工件标号 （1，2，…，n） 满足 。

每当一个工件可开始被安排加工时，即时间到达了这个工件的就绪时间（也称为该工件被释放）。如果这个可被安排加工的工件其标号小于正在加工工件的标号，则这个正在加工的工件将被中断加工，由这个可被安排加工的工件加工；如果这个可被安排加工的工件其标号大于正在加工工件的标号，则原来正在加工的工件继续加工；如果某个工件加工完毕，则在全部可被安排加工的工件中选择标号最小的工件接着加工。这样得到的工件加工可中断的排序称为排序问题 1｜r _j ｜∑w _j C _j 的LP序，显然得到LP序的算法执行时间是 O （ n log n ）。

设 （ j ＝1，…， n ； τ＝r _j ，…，T －1）的取值是对应排序问题1｜ r _j ｜ ∑w _j C _j 的LP序，即在LP序中，若工件 j 在区间［ τ，τ ＋1）上加工，则令 ＝1，否则令 ＝0。

定理2.6 设工件标号满足 ，若

的取值是对应排序问题 1｜r _j ｜∑w _j C _j 的LP序，则 y ^LP 是线性规划（LP 2.9）的最优解。

证明 接下来的证明是基于交换工件的加工次序。

根据引理2.4的结果，设线性规划（LP 2.9）的最优解

满足每个分量取值为1或0。

若存在两个工件 j 与 k 满足 j＜k ，以及 σ＞τ≥r _j ，则

成立。我们将 与 替换为0，将 与 替换为1，其他分量保持不变，即令

得到线性规划（LP 2.9）的另一个可行解 ỹ ，并且新得到的可行解 ỹ 与原来最优解 y ^* 的差

由于 j＜k ，得 ，即 ，所

即可行解 ỹ 也是线性规划（LP 2.9）的最优解。因此，通过若干次交换工件的加工次序可得到 y ^LP 是线性规划（LP 2.9）的最优解。

下面我们引入工件的平均被占用时间概念，从而给出排序问题 1｜r _j ｜∑w _j C _j 的另外一种线性规划松弛。对于任何工件加工可中断排序，设 I _j 是工件 j 的加工示性函数，即

为了避免无意义的情况出现，对于任何工件加工可中断排序，我们要求当机器开始加工某一工件时，一定是加工一个正的时间量。

对于任何工件加工可中断排序，工件 j 的平均被占用时间定义为

首先讨论一下工件 j 的平均被占用时间 M _j 所具有的重要性质。

引理2.5 对于任何工件加工可中断排序，设 C _j 与 M _j 分别表示工件 j 的完工时间与平均被占用时间，则有

并且等式成立当且仅当工件 j 的加工没有发生被中断的情况。

证明 若工件 j 的加工没有发生被中断的情况，则

因此， 。

若工件 j 的加工被中断，则在时间 r _j 与 C _j －p _j 之间一定存在若干时间区间机器是在加工工件 j； 又由于 I _j （t） 非零所对应的区间长度之和是定值 p _j ，因此， I _j （t） 在时间 r _j 与 C _j －p _j 之间非零所对应的区间长度之和等于 I _j （t） 在时间 C _j －p _j 与 C _j 之间为零所对应的区间长度之和，即 （1－I _j （t）） 非零所对应的区间长度之和，所以有

得

设 S J ，令 ，由于机器在同一时间只能加工一个工件，所以对所有 t，I _S （t）∈｛0，1｝ 。我们将 I _S （t） 看成工件集合 S 的示性函数，这样我们可以定义集合 S 的平均被占用时间为

并且有

引理2.6 对任意工件集合 S J ，以及任何工件加工可中断排序，有

并且等式成立，当且仅当 S 中所有工件在时间区间 ［r _min （S），r _min （S）＋p（S）］ 内加工。

证明 由于当 t＜r _min （S） 时， I _S （t）＝0； 当 t≥r _min （S） 时， 0≤I _S （t）≤1 ，以及

所以当

时， 取到最小值，最小值为

因此，在所有可行工件加工可中断排序中， S 中所有工件在时间区间 ［r _min （S），r _min （S）＋p（S）］ 内加工是使 p（S）M _S 为最小的排序，所以

并且等式成立当且仅当 S 中所有工件在时间区间 ［r _min （S），r _min （S）＋p（S）］ 内加工。

根据上面引理2.6得到工件加工可中断排序问题 1｜r _j ，pmtn｜∑w _j C _j 的线性规划松弛，当然也是排序问题 1｜r _j ｜∑w _j C _j 的线性规划松弛：

下面的内容以及定理的证明需要用到正则分解的概念（Geomans，1996；Geomans et al.，2002）。对于一个工件集合 S ，按工件的就绪时间尽可能早地加工 S 中的工件，如果这样的工件加工排序导致工件集合 S 有一个划分｛ S ₁ ，…，S _k ｝满足机器被 S 中工件占用恰好在不相交的时间区间

则称这一划分 ｛ S ₁ ，…，S _k ｝是 S 的正则分解。如果 S 的正则分解为 ｛ S ｝，则称 S 是正则的，即 S 是正则的当且仅当 S 中所有工件安排在时间区间 ［r _min （S _t ），r _min （S _t ）＋p（S _t ）］ 内加工是可行的。

设｛ S ₁ ，…，S _k ｝是 S J 的正则分解，令

则由引理2.6得

这样，线性规划（LP 2.10）也可表示为下列线性规划：

定理2.7 设 是LP序中工件 j 的平均被占用时间，则 M ^LP ＝｛ ｜ j ＝1，2，…， n ｝是线性规划（LP 2.10）的最优解。

证明 显然，由引理2.6可得 M ^LP 是线性规划（LP 2.10）的可行解。

为了证明 M ^LP 的最优性，我们构造线性规划（LP 2.10）最优值的一个下界，并证明这个下界等于 f _{LP 2.10} （M ^LP ）。

为了证明方便，不妨假设工件按 的非增序标号，设 J _[i]: ＝｛1，2，…，i｝ ，并设 J _[i] 的正则分解为｛ ，…， ｝，则成立

其中， 。这样，我们将 表示为正则集上表达式 的非负组合。

根据LP序的构造，在LP序中正则集 中的所有工件在时间区间 内连续加工，根据引理2.6的结果，对于线性规划（LP 2.10）的任意可行解 M ＝｛ M _j ｜ j ＝1，2，…， n ｝和正则集 ，成立

即

所以 M ^LP ＝｛ ｜ j ＝1，2，…， n ｝是线性规划（LP 2.10）的最优解。

定理2.8 排序问题1｜ r _j ｜∑w _j C _j 的线性规划松弛（LP 2.9）与（LP 2.10）的最优值相等。

证明 注意： 是LP序中工件 j 的平均被占用时间， y ^LP 的取值由LP序得到，显然成立

由定理2.6与定理2.7得到线性规划（LP 2.9）与（LP 2.10）的最优值相等。

若所有工件的加工时间都等于1，则LP序是排序问题 1｜r _j ，p _j ＝1｜∑w _j C _j 的最优解，由于LP序可以在时间 O （ n log n ）内得到，所以排序问题1｜ r _j ，p _j ＝1｜ ∑w _j C _j 是多项式时间可解。

对于排序问题 1｜r _j ｜∑w _j C _j ，由于其LP序工件加工是可中断的，所以LP序不是排序问题 1｜r _j ｜∑w _j C _j 的可行序。为了将LP序转换成一个工件加工不中断的工件加工排序，即排序问题 1｜r _j ｜∑w _j C _j 的可行序，我们引进工件的 α -点概念。

设 0＜α≤1 ，工件 j 的 α -点 t _j （α） 定义为在LP序中工件 j 完成其 α 部分加工的第一时间点，即在时间 t _j （α） 时工件 j 已完成加工 αp _j ，显然 t _j （1） 就是工件 j 的完工时间，我们定义 t _j （0 ^＋ ） 为工件 j 的开始加工时间。显然根据上述工件 j 的 α -点的定义，对于LP序，成立工件 j 的平均占用时间 等于工件 j 的所有 α -点的平均，即

对于固定的工件 j ，设 0＜α≤1 ，在LP序中我们用 （α） 表示在时间 t _j （α） 之前工件 k 已完成加工的比例，即工件 k 已完成加工 （α）p _k ，显然， （α）＝α。 用 τ _j 表示在LP序中时间0到工件 j 的开始加工时间之间的机器空闲时间，根据LP序的构造，从工件 j 开始加工的时间到其完工的时间之间机器没有空闲时间，所以工件 j 的 α -点可表示为

下面给出将LP序转换成一个工件加工不中断排序的办法。

算法2.4

对于给定的 α（0＜α≤1） ，所有工件按其 α -点的非降序尽可能早地安排工件不中断加工。

由上述算法得到的这一排序称为 α -序。将工件加工可中断排序按其 α -点的非降序得到工件不中断加工最早是由Phillips et al.（1998）引入，下面将这一想法推广到各自工件。对于工件 j 给定 α _j （0＜α _j ≤1） ，定义向量 （α _j ）：＝（α ₁ ，α ₂ ，…，α _n ） ，按工件的 α _j -点｛ t _j （α _j ） ｜ j ＝1，2，…， n ｝的非降序尽可能早地加工工件，这样得到的排序称为（ α _j ）-序，并用 C _j （α _j ） 表示 （α _j ） -序中工件 j 的完工时间。当 α _j ＝α（j＝1，2，…，n） 时， （α _j ） -序就是前面定义的 α -序，并用 C _j （α） 表示 α -序中工件 j 的完工时间。为了分析 （α _j ） -序的工件完工时间，我们考虑下面这个稍微不同的算法。

算法2.5 （α _j -Conversion算法）

以LP序中 α _j -点｛ t _j （α _j ） ｜ j ＝1，2，…， n ｝的非增序考虑工件 j（j＝1，2，…，n） ，应用下列步骤重复将工件加工中断的排序变为工件加工不中断的排序。

步骤1：将工件 j 在 t _j （α _j ） 前加工部分 α _j p _j 移去，留下对应时间区间为机器空闲，称这一空闲时间是由工件 j 产生的。

步骤2：将 t _j （α _j ） 后的所有加工延迟 p _j 。

步骤3：将工件 j 的剩余 （1－α _j ） 部分移去，收缩相应的时间区间。

步骤4：在时间区间 ［t _j （α _j ），t _j （α _j ）＋p _j ］ 中加工工件 j。

若所有 α _j ＝α ，则称算法2.5为 α -Conversion算法。

引理2.7 对于排序问题1｜ r _j ｜∑w _j C _j ，由算法2.5得到的排序，其工件 j（j＝1，2，…，n） 的完工时间

证明 工件 j 的完工时间等于工件 j 开始加工之前的空闲时间加上工件 j 的加工时间以及在工件 j 之前加工的所有工件的加工时间，由于工件按 α _j -点的非降序加工，工件 j 的完工时间之前的工件加工时间总和为

工件 j 开始加工之前的空闲时间可以表示为在LP序已存在的空闲时间 τ _j 与由算法2.5的步骤1产生的空闲时间之和。注意：算法2.5的步骤3不产生额外的空闲时间，这是因为收缩了相应的时间区间。每个不在工件 j 之后开始加工的工件 k ，即满足 α _k ≤ （α _j ） 的工件 k ，贡献了空闲时间 α _k p _k ，所有其他工件 k 贡献了空闲时间 （α _j ）p _k ，所以，工件 j 开始加工之前的总空闲时间为

因此，由算法2.5所得到的排序，其工件 j 的完工时间

定理2.9 对于排序问题1｜ r _j ｜∑w _j C _j ，对于其 （α _j ） -序，工件 j（j＝1，2，…，n） 的完工时间 C _j （α _j ） 满足

证明 根据引理2.7，由算法2.5构造的排序其工件 j 的完工时间 C _j 满足

所以，由算法2.5所构造的排序是排序问题 1｜r _j ｜∑w _j C _j 的可行序，又由于 （α _j ） -序与算法2.5构造的排序具有相同的次序，并且 （α _j ） -序是尽可能早地加工工件，所以

引理2.8 对于排序问题1｜ r _j ｜∑w _j C _j ，给定 α（0＜ α ≤1） 得到一 α -序，则对任意正则集 S ，成立

证明 为了方便证明，不妨假设正则集 S ＝｛1，2，…，l｝，并且 t ₁ （α）＜t ₂ （α）＜…＜ t _l （α）。

对任一固定的工件 j∈S ，由定理2.9得

设 R ＝｛ k∈J ｜ t _k （α）＜r _min （S） ｝，若 k∈R ，可得 α ≤ （ α ）。由于 S 是正则集，所以在LP序中， S 中工件在时间区间［ r _min （S），r _min （S）＋p（S） ］内是连续加工，因此满足 α ≤ （ α ）的工件 k 要么在 S 中，要么在 R 中。由 R 的定义，显然成立 ，即 ≤ 。将不等式 代入 C _j （α）≤t _j （ α ）＋ （1＋ α － （ α ）） p _k 得

同样，由于 S 中工件在时间区间 ［r _min （S），r _min （S）＋p（S）］ 上是连续加工，所以

由上述两个式子可得

这样得到

定理2.10 对于排序问题1｜ r _j ｜∑w _j C _j ，由给定的 α（0＜α≤1） 得到一 α -序，则成立

其中， 是线性规划（LP 2.10）的最优值。

证明 不妨假设工件按 的非增序标号，设 J _[i]: ＝｛1，2，…， i ｝，并设 J _[i] 的正则分解为｛ ，…， ｝，并令 ＝0，则成立

由引理2.8得

再由引理2.6得

当 α＝1/ 时， 取最小值，最小值为 1＋ 。所以，由定理2.10得到算法2.4是求解排序问题1｜ r _j ｜∑w _j C _j 的（1＋ ）-算法。

下面我们讨论随机化算法，根据（0，1］区间上所给定的适当的分布密度函数，随机选取｛ α _j ｜ j ＝1，2，…， n ｝，能得到求解排序问题1｜ r _j ｜ ∑w _j C _j 的性能比更好的近似算法。

定理2.11 设随机变量｛ α _j ｜ j ＝1，2，…， n ｝两两独立，并服从（0，1］区间上的均匀分布，则 （α _j ） -序的期望值不超过线性规划（LP 2.10）的最优值的2倍，即成立

其中， 是线性规划（LP 2.10）的最优值。

证明 对于任意固定的工件 j（j＝1，2，…，n） ，我们分析其完工时间的期望。

首先保持 α _j 固定，考虑条件期望 E ［ C _j （α _j ） ｜ α _j ］，由于对所有 k≠j ，随机变量 α _j 与 α _k 独立，由定理2.9得

再由前面所得到的等式 t _j （ α _j ）＝ τ _j ＋ ，得 ≤ t _j （α _j ） ，所以

因此

所以

为了得到更好的结果，我们进一步分析LP序的结构。假设所有工件已按 的非降序标号，对于任意工件 j（j＝1，2，…，n） ，假设在LP序中，工件 j 在时间 s 被中断加工，在时间 t 重新开始加工 （t＞s） ，则在时间区间 [s，t] 内加工的所有工件其标号都小于 j ，并且这些工件在时间区间 [s，t] 内完成加工，这样，在LP序中任意工件 j 的开始加工时间与完工时间之间机器被连续占用而没有空闲，交替加工工件 j 的一部分和加工完成所有标号都小于 j 的工件。另外，任意工件的加工如果在工件 j 的开始加工时间 t _j （0 ^＋ ） 被中断，则该工件只能等待，至少在工件 j 完工以后才能重新开始加工。为了下面的分析，对于固定的工件 j ，我们将工件集合 J ＼｛ j ｝分为两个集合 J ₁ 与 J ₂ ，J ₂ 包含所有在工件 j 的开始加工时间与完工时间之间进行加工的工件， J ₁ 包含其他剩余工件。

显然，当工件 k∈J ₁ 时， （α _j ） 是常数。对于工件 k∈J ₂ ，设 μ _k （0＜μ _k ＜1） 表示在工件 k 开始加工之前工件 j 已加工部分，则成立

这样我们可将

转变为下列式子

再将上式代入等式 得

又由于当工件 k∈J ₂ 时， α _k ≤ （α _j ） 等价于 α _j ＞μ _k ，这样，定理2.9的结果可写成

为了得到更好的结果，随机变量｛ α _j ｜ j ＝1，2，…， n ｝的概率分布的选取至关重要，必须处理两个矛盾的现象：一方面，若选取较小的 α _k ，将使（ 1＋α _k － （ α _j ））与（ 1＋α _k ）较小；另一方面，若选取较大的 α _k ，将使满足 α _k ≤ （ α _j ）的项数减少。

引理2.9 设 ，其中，常数 c ＞1，当 δ ＝ln 时， f（α） 是密度函数。

设 γ （ γ ≈0.467 5）是下列方程的唯一解：

定义 ，则满足δ= ，并且具有下列性质：

（1）当 η∈[0，1] 时，成立

（2）当 μ∈[0，1] 时，成立

证明 显然 f（α）≥0 ，又因为

所以 f（α） 是密度函数。

（1）下面证明　当 η∈[0，1] 时， 成立。

当 0≤η≤δ 时，

当 δ＜η≤1 时，

（2）下面证明　当 μ∈[0，1] 时， 成立。

当 μ∈（δ，1］ 时，

当 μ∈［0，δ］ 时，

由 δ ＝ln ，得（ c －1） e ^δ ＝ c ，由 δ ＝ γ ＋ln（1＋ γ ），得 ，再由 ，得到

因为 e ^μ－γ ≥1＋（μ－γ） ，所以

定理2.12 根据密度函数

随机选取 α ，其中 c 、 δ 的确定与引理2.9相同，构造排序问题1｜ r _j ｜ ∑w _j C _j 的 α -序，则工件 j 的完工时间 C _j （α） 的数学期望

证明 取 η＝1 ，由引理2.9的（1），或取 μ＝0 ，由引理2.9的（2）可得

由不等式

引理2.9以及 E ［ α ］≤ c －1得

定理2.13 对于排序问题1｜ r _j ｜∑w _j C _j ，最多有 n 个不同的 α -序，从而可得到排序问题1｜ r _j ｜∑w _j C _j 的1.745 1-近似算法。

证明 当 α 从0 ^＋ 增加到1时， α -序会发生改变仅当 α -点达到一工件 j 被中断的时刻，这样，不同的 α -序的个数不超过所有工件中断加工的次数。由于在LP序中仅当一个工件被释放时才可能发生一次工件中断加工，即所有工件中断加工的次数最多为 n－1 ，所以，所有不同的 α -序的个数不超过 n。

得到一 α -序的计算时间为 O（n） ，所以在时间 O（n ² ） 内可得到所有 α -序，这样上述随机化算法可以逆随机化，得到排序问题 1｜r _j ｜∑w _j C _j 的1.745 1-近似算法。

下面我们讨论 （α _j ） -序的情况。

引理2.10 设 ，其中，常数 c ＞1，当 δ ＝ln 时， g（α） 是密度函数。

设 γ （ γ ≈0.4835）是下列方程的唯一解：

定义 δ:＝ γ ＋ ln （2－ γ ）≈0.899 9， c :＝1＋ ＜1.685 3 ，则满足 δ ＝ln ，并且具有下列性质：

（1）当 η∈[0，1] 时，成立

（2）当 μ∈[0，1] 时，成立

证明 显然当 δ ＝ln 时， g（α） 是密度函数。

当 时，

（1）与引理2.9（1）的证明一致。

（2）首先计算

当 μ∈（δ，1］ 时，

所以

当 μ∈［0，δ］ 时，

又根据前面的定义 c ＝1＋ ， δ ＝ γ ＋ln（2－ γ ），得 δ （ c －1）＝ e ^－γ ，以及 e ^δ ＝（2－ γ ） e ^γ ，所以

定理2.14 根据密度函数

独立随机选取 α _j （j＝1，2，…，n） ，其中 c、δ 的确定与引理2.10相同，构造排序问题1｜ r _j ｜ ∑w _j C _j 的 （α _j ） -序，则工件 j 的完工时间 C _j （α _j ） 的数学期望

证明 对于固定的工件 j ，以及固定的值 α _j ，由不等式

以及引理2.10（1）得

再由引理2.10（2）得

独立随机选择 α _j （j＝1，2，…，n） ，则得到 （α _j ） -序是排序问题 1｜r _j ｜∑w _j C _j 的随机1.685 3-近似算法。下面将证明 （α _j ） -序可以有 2 ^{n － 1} 个，因此，不能通过列举所有不同的 （α _j ） -序将随机1.685 3-近似算法逆随机化。

引理2.11 对于排序问题1｜ r _j ｜∑w _j C _j ，最多有 2 ^{n － 1} 个不同的 （α _j ） -序。

证明 设 q _j （j＝1，2，…，n） 表示在LP序中工件 j 的不同加工时间段的个数，即 q _j 等于工件 j 加工被中断的次数加1，则不同的 （α _j ） -序个数为 s ＝ ，因为在LP序中标号为1的工件其加工不会被中断，所以 q ₁ ＝1 ，即 s ＝ 。

由于总加工中断次数最多为 n－1 ，所以 q _j ≤2n－1 ，即 q _j ≤2（n－1）。 由算术-几何平均不等式得到

下面所给出的例子说明等式 s＝2 ^{n － 1} 是可以得到的。

设工件 j（j＝1，2，…，n） 的加工时间为 p _j ＝2 ，权为 w _j ＝n－j＋1 ，就绪时间为 r _j ＝n－j ，则工件 j 不同加工时间段的个数 q _j ＝2（j＝2，…，n） ，即 s ＝ q _j ＝2 ^{n －1} 。

为了将随机1.685 3-近似算法逆随机化，Goemans et al.（2002）应用条件概率的方法（Motwani & Raghavan，1995）将上述随机化算法逆随机化。

定理2.15 排序问题1｜ r _j ｜∑w _j C _j 的随机1.685 3-近似算法可以逆随机化，在运行时间 O（n ² ） 内得到1.685 3-近似算法。

证明 对于任意向量 α ＝（α ₁ ，α ₂ ，…，α _n ） ，根据不等式

其相对应的 （α _j ） -序的目标函数值有一个上界，即

其中

由定理2.14我们已经证明

对于每个工件 j∈J ，对应于 α _j ，设 I _j ＝｛ I _j1 ，I _j2 ，…，I _{jq j} ｝是工件 j 在LP序中加工的 q _j 个时间区间段，所有工件按任意次序一个接一个考虑，假设为 j ＝1，2，…， n 。假设在逆随机化算法的第 j 步我们已经确定区间 ∈ I ₁ ，…， ∈ 满足

由条件期望，

由于 ，所以至少存在一个区间 满足

因此，可确定这样一个区间 ＝I _{j l} 满足上式，并得到结论

对所有工件 j∈J ，上述方法确定一个区间 ，并且对所有 α ∈ × ×…× 所得到的 （α _j ） -序是相同的，这一 （α _j ） -序的目标函数值成立

对所有工件 j∈J ，确定一区间 总共需要评估 O（n） 项，每一项的评估都可以在一个常数时间内计算完成，因为候选区间的总数 q _j ≤2n－1 ，因此，逆随机化算法的时间复杂性为 O（n ² ）。 bQWLFfQtv9mM6YuiW/rtrR8XJ1Cc0a6Xi7nJK6lR7B9mOS1F42TWaPBsEvuoG/JO