NDP约束下的最小化最大加权完工时间单机一致性在线排序问题研究

Online NDP-Constraint Scheduling of Jobs with Agreeable to Minimize the Maximum Weighted Completion Time

摘要: 本文在工件不能被强制推迟加工约束(即NDP约束)下研究最小化最大加权完工时间单台机器在线排序问题。每个工件J_j都具有一个释放时间r_j≥0，一个加工时间p_j≥0和一个权重w_j≥0。每两个工件J_i和J_j的释放时间与加工时间均具有一致性，即若r_i≥r_j，则有p_i≥p_j。我们首先利用对手法构造出该排序问题的下界是1.5，其次设计出一个在线算法SLF并采用最小反例法证明其争比是1.732。

Abstract: This paper studies the single-machine online schedule under the NDP-constraint to minimize the maximum weighted completion time. Each job J_j has a release time r_j≥0, a processing time p_j≥0 and a weight w_j≥0. Any two jobs J_i,J_j have agreeable release times and processing times (if r_i≥r_j, then p_i≥p_j). We first present a lower bound of 1.5 by the adversary method, and then design an online algorithm SLF with the competitive ratio of 1.732.

1. 引言

在线排序是现代排序领域中发展最为迅速的研究方向之一，并被广泛地应用于生产加工、货运物流、航班调度、医疗服务等众多领域。 在线排序中决策者在制定排序策略时只掌握当前已经被释放工件的信息(例如，释放时间、加工时间、权重等)，人们称这种在线为时间在线。列表在线、不可测在线是另外两种常见的在线排序模型 [1] [2] [3] [4]。

一般用竞争比来衡量一个在线算法关于对应在线排序问题的性能。我们称算法H的竞争比是 ${\rho }_H$ ，如果满足 ${\rho }_H={\sup }_{\forall I}\left\{H\left(I\right)/OPT\left(I\right):OPT\left(I\right)>0\right\}$ ，其中I是排序问题的工件实例， $H\left(I\right)$ 表示算法H关于I产生的目标值， $OPT\left(I\right)$ 表示离线最优算法产生的目标值。当一个排序问题在线算法的竞争比与排序问题的下界相吻合时，则称该算法是最优在线算法。

本文在NDP约束下研究最小化最大加权完工时间单机在线排序排序问题。NDP约束是指在任何机器出现空闲的时刻，如果有还没被安排加工的工件存在，则空闲机器必须立刻选择工件加工。换言之，工件不能被强制推迟加工。NDP约束是Li和Yuan在文献 [5] 中根据实际背景以及排序模型拓展提出的一种工件加工约束条件。该排序模型在实际生活中确有体现。例如市政服务大厅的办事窗口(抽象为机器)，当窗口开放并在给客户(抽象为工件)办理业务时，后面到达的客户就会自觉地取号排队等待服务，这些已到达还未办理业务的客户最不愿意看到窗口突然暂停服务的情况出现。因为每个客户都希望自己的满意度最大化都不愿意再去排队等待。这里将本文在NDP约束下所要研究的具体排序问题描述如下：

设I是一个工件集合(简称实例)包含n个工件 $J_1,J_2,\cdots ,J_n$。对每一个实例I中的工件 $J_i$ ，它具有一个释放时间(又称到达时间) $r_i\ge 0$ ，一个加工时间(又称长度) $p_i\ge 0$ ，一个权重 $w_i\ge 0$。要求实例I中任意两个工件 $J_i,J_k$ 的释放时间和加工时间之间满足：若 $r_i\ge r_k$ ，则有 $p_i\ge p_k$。通常称之为I中工件的释放时间和加工时间具有一致性。排序目标：确定一个工件不能被强制延迟加工(即满足NDP约束)的可行排序最小化所有工件的最大加权完工时间( $W{C}_{\max }$ )，其中 $W{C}_{\max }=\max \left\{w_i{C}_i:i=1,2,\cdots ,n\right\}$ ， $C_i$ 为工件 $J_i$ 的完工时间。方便起见，现将NDP约束下的工件的释放时间和加工时间具有一致性的最小化最大加权完工时间单机在线排序问题简记为(P)。用Graham等人在文献 [6] 中定义的三参数表示法，本文所研究的排序问题(P)可表示为：

$1|\text{online},r_i,\text{agreeable}\left(r_i,p_i\right),\text{NDP}|W{C}_{\text{max}}$ ，

其中“ $\text{agreeable}\left(r_i,p_i\right)$ ”表示关于问题(P)的任一实例中工件的释放时间和加工时间具有一致性。

关于无NDP约束的最小化最大加权完工时间单机在线排序问题，Chai等人在文献 [7] 中给出了一个2-竞争的最优在线算法。在NDP约束下，Li和Yuan在文献 [5] 中研究了该问题。他们首先给出问题的下界为2，其次设计出了一个竞争比为2.618的在线算法。关于最小化最大加权完工时间在线排序问题的其它相关文献可参见 [8] [9] [10] [11] [12]。

本文将在第二节构造出问题(P)的竞争比下界为1.5，在第三节中设计并证明该问的一个1.732-竞争的在线算法SLF。

2. 问题的下界

本节将通过构造特殊实例证明问题(P)的竞争比下界是1.5。用 $W{C}_{\text{on}}\left(I\right)$ 和 $W{C}_{\text{opt}}\left(I\right)$ 分别表示任一在线算法和离线最优算法关于实例I生成的排序所达到的目标函数值。

定理2.1对于问题 $1|\text{online},r_i,\text{agreeable}\left(r_i,p_i\right),\text{NDP}|W{C}_{\text{max}}$ ，不存在竞争比小于1.5的在线算法。

证明 设H是问题(P)的任意一个在线算法。令 $\epsilon$ 是一个任意小的正实数，K是一个充分大的正实数。下面用对手法构造的特殊实例I至多含有3个工件。

在0时刻，工件 $J_1$ 和 $J_2$ 被释放并且它们的加工时间和权重分别为 $p_1=1,w_1=1$ ， $p_2=1+\epsilon ,w_2=0$。由NDP约束可知，在线算法H必须在0时刻选择一个工件开工。如果算法H在0时刻选择加工 $J_2$ ，则之后不再有新工件被释放。此情形 $I=\left\{J_1,J_2\right\}$。易知在线算法H和离线最优算法OPT关于I生成的排序分别为 $\left(J_2,J_1\right)$ 和 $\left(J_1,J_2\right)$。于是可得 $C_{\text{on}}\left(I\right)=w_1\left(p_2+p_1\right)=2+\epsilon$ ， $C_{\text{opt}}\left(I\right)=w_1{p}_1=1$。进而可得

$\frac{W{C}_{\text{on}}\left(I\right)}{W{C}_{\text{opt}}\left(I\right)}=2+\epsilon >1.5$。

如果算法H在0时刻安排 $J_1$ 开工，则第三个工件 $J_3$ 将在 $1+\frac{1}{2}\epsilon$ 时刻被释放，其加工时间和权重分别

为 $p_3=1+\epsilon$ ， $w_3=K$。此情形 $I=\left\{J_1,J_2,J_3\right\}$。由NDP约束和 $r_3=1+0.5\epsilon >1$ 可知，算法H只能安排 $J_3$ 在继 $J_2$ 完工之后开工。于是可得 $C_{\text{on}}\left(I\right)=w_3\left(p_1+p_2+p_3\right)=K\left(3+2\epsilon \right)$。注意到，最优算法OPT则可以先安排 $J_2$ 在0时刻开工，然后安排 $J_3$ 在 $J_2$ 的完工时刻开工(可以这样安排的原因是 $r_3=1+0.5\epsilon <1+\epsilon$ )，最后安排 $J_1$ 在 $2+2\epsilon$ 时刻开工。可得离线最优序下的目标值为 $C_{\text{opt}}\left(I\right)=w_3\left(p_2+p_3\right)=K\left(2+2\epsilon \right)$。因此可以推得

$\frac{W{C}_{\text{on}}\left(I\right)}{W{C}_{\text{opt}}\left(I\right)}=\frac{3+2\epsilon }{2+2\epsilon }\to 1.5$ ，当 $K\to +\infty$ 时。

综上，定理2.1得证。 £

3. 在线算法及其竞争比分析

本节将设计关于问题(P)的在线算法SLF (加工策略“Shortest-length or Largest-weight Job First”的简称)并用最小反例法分析其竞争比至多为1.732。对于问题(P)的任意一个实例I，令 $\sigma$ 和 $\pi$ 分别表示在线算法SLF和离线最优算法OPT关于实例I生成的排序。令t表示当前时刻，下面的一系列记号将会在后面的讨论中被用到。

· $S_i\left(\sigma \right)$ ， $S_i\left(\pi \right)$ 分别表示I中工件 $J_i$ 在排序 $\sigma$ 和 $\pi$ 中的开工时间。

· $C_i\left(\sigma \right)$ ， $C_i\left(\pi \right)$ 分别表示I中工件 $J_i$ 在排序 $\sigma$ 和 $\pi$ 中的完工时间。

· $W{C}_{\max }\left(\sigma \right)$ ， $W{C}_{\max }\left(\pi \right)$ 分别表示排序 $\sigma$ 和 $\pi$ 关于实例I产生的目标值。

· $U\left(t\right)$ 表示在t时刻已经被释放但还没有被安排加工的工件构成的集合。

· $J_{\min }\left(t\right)$ 表示 $U\left(t\right)$ 中加工时间最小的工件。如果有多个这样的工件，则定义为最早被释放的工件。

· $J_w\left(t\right)$ 表示 $U\left(t\right)$ 中权重最大的工件。如果有多个这样的工件，则定义为最早被释放的工件。

· $p_i\left(t\right)$ 表示 $U\left(t\right)$ 中任一工件 $J_i$ 的长度。特别的，用 $p_{\min }\left(t\right)$ ， $p_w\left(t\right)$ 分别表示 $J_{\min }\left(t\right)$ 和 $J_w\left(t\right)$ 的长度。

设 $\lambda =\sqrt{3}-1$ ，在线算法SLF的具体执行步骤可描述如下：

在线算法SLF

第0步：置t等于I中工件的最早释放时间。不妨假设I中工件的最小释放时间为0，即置 $t:=0$。

第1步：若在t时刻 $U\left(t\right)\ne \varphi$ 且机器空闲，则执行第2步或第3步；否则重置t为下一个满足机器空闲且 $U\left(t\right)$ 非空的最早时刻。

第2步：若 $U\left(t\right)$ 只含有一个工件 $J_i$ ，则立刻加工 $J_i$ 并重置 $t:=t+p_i\left(t\right)$。转到第1步；否则， $U\left(t\right)$ 至少包含两个工件，则转到第3步。

第3步：若此时 $U\left(t\right)$ 中权重最大的工件 $J_w\left(t\right)$ 满足 $t\ge \lambda \cdot p_w\left(t\right)$ ，则立刻加工 $J_w\left(t\right)$ 并重置 $t:=t+p_w\left(t\right)$。转到第1步；否则，转到第4步。

第4步：此时 $U\left(t\right)$ 中权重最大的工件 $J_w\left(t\right)$ 满足 $t<\lambda \cdot p_w\left(t\right)$ ，则分以下两种情形，

(4.1)：若此时 $U\left(t\right)$ 中长度最小的工件 $J_{\min }\left(t\right)$ 满足 $t+p_{\min }\left(t\right)\le \lambda \cdot p_w\left(t\right)$ ，则立刻加工 $J_{\min }\left(t\right)$ 并重置 $t:=t+p_{\min }\left(t\right)$。转到第1步；否则，转到第4.2步。

(4.2)：可知 $U\left(t\right)$ 中任意一个工件 $J_i$ 的长度 $p_i\left(t\right)$ 满足 $t+p_i\left(t\right)>\lambda \cdot p_w\left(t\right)$ ，则立刻加工 $J_w\left(t\right)$ 并重置 $t:=t+p_w\left(t\right)$。转到第1步。

接下来，证明算法SLF关于问题(P)的竞争比 $\rho =\lambda +1=\sqrt{3}\approx 1.732$。反证法，假设存在一个包含工件数量最小的实例I满足 $W{C}_{\max }\left(\sigma \right)>\rho \cdot W{C}_{\max }\left(\pi \right)$ ，其中 $\sigma$ 和 $\pi$ 分别是在线算法SLF和离线最优算法OPT关于实例I生成的排序。通常称此实例为关于问题(P)的一个最小反例。由算法SLF的第0步，可以假设I中第一个工件在0时刻被释放并继续假设I中n个工件 $J_1,J_2,\cdots ,J_n$ 在 $\sigma$ 序下的开工时间分别满足 $S_1\left(\sigma \right)<S_2\left(\sigma \right)<\cdots <S_n\left(\sigma \right)$。可得 $S_1\left(\sigma \right)=0$ ， $C_n\left(\sigma \right)=C_{\max }\left(\sigma \right)$。设 $J_e,1\le e\le n$ 是I中第一个满足其加权完工时间等于目标值的工件，即满足 $w_e{C}_e\left(\sigma \right)=W{C}_{\max }\left(\sigma \right)$。下面给出两个重要引理。

引理3.1在排序 $\sigma$ 和 $\pi$ 中所有工件都是被连续加工的，即在0时刻与 $C_n\left(\sigma \right)$ 时刻之间机器没有空闲时间段。

证明 首先考虑排序 $\sigma$。如果在 $J_e$ 之前有工件 $J_a,2\le a\le e$ 满足 $C_{a-1}\left(\sigma \right)<S_a\left(\sigma \right)$ ，即 $\left[C_{a-1}\left(\sigma \right),S_a\left(\sigma \right)\right]$ 是空闲时间段，则令 $I^{\prime }=\left\{J_a,J_{a+1},\cdots ,J_n\right\}$。如果在 $J_e$ 之后有工件 $J_b,e\le b\le n-1$ 满足 $C_b\left(\sigma \right)<S_{b+1}\left(\sigma \right)$ ，即 $\left[C_b\left(\sigma \right),S_{b+1}\left(\sigma \right)\right]$ 是空闲时间段，则令 $I^{″}=\left\{J_1,J_1,\cdots ,J_b\right\}$。由算法SLF的执行策略可知，算法SLF关于实例I， $I^{\prime }$ 及 $I^{″}$ 产生的目标值相同。再由NDP约束和实例I是最小反例，可以推出 $I^{\prime }$ 或 $I^{″}$ 是更小的反例，与实例I是最小反例相矛盾。于是可得在排序 $\sigma$ 中所有工件被连续加工，即机器无空闲时间段。由NDP约束及I中工件在排序 $\sigma$ 中被连续加工，可知离线最优序 $\pi$ 中所有工件也是被连续加工的。 £

引理3.2 $w_i<w_e,i=e+1,e+2,\cdots ,n$。

证明 由 $W{C}_{\max }\left(\sigma \right)=w_e{C}_e\left(\sigma \right)$ 以及 $C_i\left(\sigma \right)>C_e\left(\sigma \right),e+1\le i\le n$ 可直接推出 $w_i<w_e,e+1\le i\le n$。 £

下面将分两种情形证明最小反例I不存在，进而得到算法SLF关于问题(P)的竞争比就是1.732。

情形1 $w_i\ge w_e,i=1,2,\cdots ,e$。则可得

$W{C}_{\max }\left(\sigma \right)=w_e{C}_e\left(\sigma \right)=w_e{\displaystyle {\sum }_{i=1}^e{p}_i}\le W{C}_{\max }\left(\pi \right)<\rho \cdot W{C}_{\max }\left(\pi \right)$。

显然与 $W{C}_{\max }\left(\sigma \right)>\rho \cdot W{C}_{\max }\left(\pi \right)$ 相矛盾。

情形2 $\left\{J_1,J_2,\cdots ,J_{e-1}\right\}$ 中存在权重小于 $w_e$ 的工件。则令 $k=\max \left\{i:w_i<w_e,i=1,2,\cdots ,e-1\right\}$。于是可得 $w_i\ge w_e,i=k+1,k+2,\cdots ,e$。令 $r_{\min }=\min \left\{r_i:k+1\le i\le e\right\}$。如果 $r_{\min }\le S_k\left(\sigma \right)$ ，表明 $\left\{J_{k+1},J_{k+2},\cdots ,J_e\right\}$ 中至少有一个工件在 $S_k\left(\sigma \right)$ 时刻或 $S_k\left(\sigma \right)$ 时刻之前到达。由于 $J_k$ 不是 $S_k\left(\sigma \right)$ 时刻已到达的工件中权重最大的工件而算法SLF选择在 $S_k\left(\sigma \right)$ 时刻加工 $J_k$ ，表明 $J_k$ 一定是加工时间最小的工件并且满足 $S_k\left(\sigma \right)+p_k\le \lambda \cdot p_w\left(S_k\left(\sigma \right)\right)$。根据引理3.2以及 $w_i\ge w_e,i=k+1,k+2,\cdots ,e$ ，可知 $S_k\left(\sigma \right)$ 时刻已到达的工件中权重最大的工件一定属于 $\left\{J_{k+1},J_{k+2},\cdots ,J_e\right\}$ ，即 $p_w\left(S_k\left(\sigma \right)\right)\in \left\{p_{k+1},p_{k+2},\cdots ,p_e\right\}$。因此可得

$\begin{array}{c}W{C}_{\max }\left(\sigma \right)=w_e\left(S_k\left(\sigma \right)+p_k+{\displaystyle {\sum }_{i=k+1}^e{p}_i}\right)\le w_e\left(\lambda \cdot p_k\left(S_k\left(\sigma \right)\right)+{\displaystyle {\sum }_{i=k+1}^e{p}_i}\right)\\ \le \left(1+\lambda \right)w_e{\displaystyle {\sum }_{i=k+1}^e{p}_i}\le \rho \cdot W{C}_{\max }\left(\pi \right).\end{array}$

这显然与I是最小反例相矛盾。

如果 $r_{\min }>S_k\left(\sigma \right)$ ，即 $r_i\ge S_k\left(\sigma \right)\ge r_k,i=k+1,k+2,\cdots ,e$ ，则有 $W{C}_{\max }\left(\pi \right)\ge w_e\left(S_k\left(\sigma \right)+{\displaystyle {\sum }_{i=k+1}^e{p}_i}\right)$。由于I中工件的释放时间与加工时间具有一致性，可知 $p_i\ge p_k,i=k+1,k+2,\cdots ,e$。若 $S_k\left(\sigma \right)\ge 0.5\lambda \cdot p_k$ ，则可得

$\begin{array}{c}\frac{W{C}_{\max }\left(\sigma \right)}{W{C}_{\max }\left(\pi \right)}=\frac{w_e\left(S_k\left(\sigma \right)+p_k+{\displaystyle {\sum }_{i=k+1}^e{p}_i}\right)}{w_e\left(S_k\left(\sigma \right)+{\displaystyle {\sum }_{i=k+1}^e{p}_i}\right)}\\ \le \frac{S_k\left(\sigma \right)+\left(e-k+1\right)p_k}{S_k\left(\sigma \right)+\left(e-k\right)p_k}\\ \le \frac{0.5\lambda \cdot p_k+\left(e-k+1\right)p_k}{0.5\lambda \cdot p_k+\left(e-k\right)p_k}\\ \le \frac{\lambda +4}{\lambda +2}\\ =\rho .\end{array}$

结论与 $W{C}_{\max }\left(\sigma \right)>\rho \cdot W{C}_{\max }\left(\pi \right)$ 相矛盾。

不妨假设 $S_k\left(\sigma \right)<0.5\lambda \cdot p_k$。如果在 $S_k\left(\sigma \right)$ 时刻只有一个工件 $J_k$ ，由NDP约束和引理3.1，可知在离线最优序 $\pi$ 中 $J_k$ 一定排在 $\left\{J_{k+1},J_{k+2},\cdots ,J_e\right\}$ 中工件之前加工。于是可得 $\min \left\{S_i\left(\pi \right):k+1\le i\le e\right\}\ge C_k\left(\pi \right)\ge p_k$。进而可得

$\begin{array}{c}\frac{W{C}_{\max }\left(\sigma \right)}{W{C}_{\max }\left(\pi \right)}=\frac{w_e\left(S_k\left(\sigma \right)+p_k+{\displaystyle {\sum }_{i=k+1}^e{p}_i}\right)}{w_e\left(\min \left\{S_i\left(\pi \right):k+1\le i\le e\right\}+{\displaystyle {\sum }_{i=k+1}^e{p}_i}\right)}\\ \le \frac{S_k\left(\sigma \right)+\left(e-k+1\right)p_k}{\min \left\{S_i\left(\pi \right):k+1\le i\le e\right\}+\left(e-k\right)p_k}\\ \le \frac{0.5\lambda \cdot p_k+\left(e-k+1\right)p_k}{p_k+\left(e-k\right)p_k}\\ \le \frac{\lambda +4}{4}\\ <\rho .\end{array}$

如果在 $S_k\left(\sigma \right)$ 时刻至少有两个工件(包括 $J_k$ )已经到达，即集合 $U\left(S_k\left(\sigma \right)\right)$ 中工件数大于等于2。注意到 $r_{\min }>S_k\left(\sigma \right)$ ，再根据引理3.1，可知在离线最优序 $\pi$ 下 $U\left(S_k\left(\sigma \right)\right)$ 至少有一个工件一定被排在 $\left\{J_{k+1},J_{k+2},\cdots ,J_e\right\}$ 中工件之前加工。于是可得 $\min \left\{S_i\left(\pi \right):k+1\le i\le e\right\}\ge \min \left\{p_x:J_x\in U\left(S_k\left(\sigma \right)\right)\right\}$。由算法SLF的执行策略可知，在 $S_k\left(\sigma \right)$ 时刻 $J_k$ 要么是一个长度最小的工件，要么是一个权重最大的工件。若 $J_k$ 是一个长度最小的工件，则有 $\min \left\{S_i\left(\pi \right):k+1\le i\le e\right\}\ge \min \left\{p_x:J_x\in U\left(S_k\left(\sigma \right)\right)\right\}=p_k$。用上面式子的分析形式可直接推出 $W{C}_{\max }\left(\sigma \right)<\rho \cdot W{C}_{\max }\left(\pi \right)$。

若 $J_k$ 是一个权重最大的工件，则根据算法SLF的第4.2步可知集合 $U\left(S_k\left(\sigma \right)\right)$ 中的工件满足， $\forall J_x\in U\left(S_k\left(\sigma \right)\right)$ ， $S_k\left(\sigma \right)+p_x>\lambda \cdot p_k$。注意到 $S_k\left(\sigma \right)<0.5\lambda \cdot p_k$。于是可得

$\forall J_x\in U\left(S_k\left(\sigma \right)\right),p_x>0.5\lambda \cdot p_k$。

再根据 $r_{\min }>S_k\left(\sigma \right)$ 以及根据引理3.1，可推得

$\min \left\{S_i\left(\pi \right):k+1\le i\le e\right\}\ge \min \left\{p_x:J_x\in U\left(S_k\left(\sigma \right)\right)\right\}>0.5\lambda \cdot p_k$。

因此可得

$\begin{array}{c}\frac{W{C}_{\max }\left(\sigma \right)}{W{C}_{\max }\left(\pi \right)}=\frac{w_e\left(S_k\left(\sigma \right)+p_k+{\displaystyle {\sum }_{i=k+1}^e{p}_i}\right)}{w_e\left(\min \left\{S_i\left(\pi \right):k+1\le i\le e\right\}+{\displaystyle {\sum }_{i=k+1}^e{p}_i}\right)}\\ \le \frac{S_k\left(\sigma \right)+\left(e-k+1\right)p_k}{\min \left\{S_i\left(\pi \right):k+1\le i\le e\right\}+\left(e-k\right)p_k}\\ \le \frac{0.5\lambda \cdot p_k+\left(e-k+1\right)p_k}{0.5\lambda \cdot p_k+\left(e-k\right)p_k}\\ \le \frac{\lambda +4}{\lambda +2}\\ =\rho .\end{array}$

综上可知，满足 $W{C}_{\max }\left(\sigma \right)>\rho \cdot W{C}_{\max }\left(\pi \right)$ 的最小反例I不存在。表明对每个关于问题(P)的实例都有

$W{C}_{\max }\left(\sigma \right)\le \rho \cdot W{C}_{\max }\left(\pi \right)$ 恒成立。于是得到本文的主要结论如下：

定理3.3 对于问题 $1|\text{online},r_i,\text{agreeable}\left(r_i,p_i\right),\text{NDP}|W{C}_{\text{max}}$ ，在线算法SLF的竞争比是1.732。 £

基金项目

河南省自然科学基金项目( 222300420503)，河南省高校重点科研项目(22A110015)，河南省高校青年骨干教师培养计划项目(2019GGJS202，2018XJGGJS-10)。