带等级约束的多重任务半在线调度问题

Multiple Tasks Semi-Online Scheduling Problem under a Grade of Service Provision

摘要: 在本文，我们研究两台平行机上带等级约束的多重任务调度问题，每个客户提交多个加工时间和等级相同的任务给机器加工。当低等级和高等级任务的加工时间之和分别已知时，本文提出了一个半在线算法，算法的竞争比为3/2。当低等级任务的加工时间之和已知时，本文也提出了一个半在线算法，算法的竞争比为3/2。

Abstract: In this paper, we study the multiple tasks semi-online scheduling problem with hierarchical con-straints on two parallel machines. Each customer submits multiple tasks with the same processing time and level to the machine. When the sum of processing time of low-level and high-level tasks is known respectively, this paper designs a semi-online algorithm with a competition ratio of 3/2. When the sum of processing time of low-level tasks is known, this paper also designs a semi-online algorithm with a competition ratio of 3/2.

1. 引言

带等级的调度问题由Hang等人在文 [1] 首次提出，由于在生产计划、工业设计、航班安排等中的广泛应用，等级调度问题得到了广泛的研究，并针对不同的目标设计了许多在线和半在线算法。等级约束在第三产业服务业应用较为广泛，服务机构将顾客分成不同的级别，例如级别较高的顾客被标记为金牌客户，级别较低的顾客被标记为银牌客户，等级越高的顾客享受越高的服务，并且服务机构只为服务等级不低于自己的顾客提供服务。

由于在实际生活中的广泛应用，半在线调度问题已经得到深入的研究。对于半在线算法，一般通过竞争比来衡量算法的性能。对于一个最小化问题，给定一个实例I，算法A的竞争比定义为最小的 $\gamma$，以满足 $C_{SEMI}\le \gamma C_{OPT}$， $C_{SEMI}$，表示半在线算法的输出值， $C_{OPT}$ 表示离线最优值。对于一个半在线问题，如果没有算法的竞争比小于 $\gamma$，则 $\gamma$ 是该问题的一个下界。如果一个算法的竞争比等于 $\gamma$，则该算法是一个最优半在线算法。

对于带等级约束的离线调度问题，Hang等人在文 [1] 设计了一个LG-LPT算法。当机器的台数 $m=2$ 时，他们设计了一个近似算法，算法的近似为5/4；当机器的台数 $m\ge 3$ 时，设计了一个 $2-1/\left(m-1\right)$ -近似算法。对于带等级约束的离线调度问题，Ou等人在文 [2] 设计了一个完全多项式时间近似方案(FPTAS)。Woeginger在文 [3] 也设计了两个类似的完全多项式时间近似方案。

对于带等级约束的在线调度问题，Park等人在 [4] 设计了一个竞争比为5/3的最优在线算法。Jiang等人在 [5] 也设计了一个竞争比为5/3的最优在线算法。当提前已知任务的加工时间之和时，Park等人在文 [4] 设计了一个竞争比为3/2的半在线算法。

对于半在线调度问题，Chen等人在文 [6] 设计了三个半在线算法：当低等级任务的加工时间之和已知时，设计了一个竞争比为3/2的最优半在线算法；当每个等级任务的加工时间之和已知时，设计了一个竞争比为4/3的半在线算法；当低等级任务的加工时间之和已知而且存在一个容量为K = 1的缓冲器时，设计了一个竞争比为4/3的最优半在线算法。Luo等人在 [7] 也设计了三个半在线算法：当低等级任务的加工时间之和已知时，设计了一个竞争比为3/2的最优半在线算法；当高等级任务的加工时间之和已知时，设计了一个竞争比为20/13的最优半在线算法；当每个等级任务的加工时间之和已知时，设计了一个竞争比为4/3的最优半在线算法。

在一般的调度中，任务总是一个接一个地到达，然后分配给机器加工。但在一些云计算问题中 [8] [9]，每个服务器提交一些要处理的相同任务给主机加工。这些工作启发我们研究两台平行机上带等级约束的多重任务调度问题。在本文，我们思考两台平行机上带等级约束的多重任务调度问题，设计了两个半在线算法。

文章剩余部分被组织如下：在第二部分，介绍预备知识及问题的具体内容；在第三部分，当提前分别已知低等级任务和高等级任务的加工时间之和时，本文设计了一个竞争比为3/2的半在线算法；在第四部分，当提前已知低等级任务的加工时间之和时，本文设计了一个竞争比为3/2的半在线算法；在最后一部分，本文总结得到结论以及对未来研究方向的设想。

2. 预备知识

两台平行机上带等级约束的多重任务调度问题叙述如下：存在一个问题实例 $I=\left(M,N,J,a\right)$，集合M包含两台机器 $M_1,M_2$，集合N包含n个客户 $1,2,\cdots ,n$。客户j有 $a_j$ 个相同的任务，客户j的任务集可以表示成 $J_j=\left\{J_{j1},\cdots ,J_{j{a}_j}\right\}$。所有客户的任务集可以表示成 $J={\displaystyle {\cup }_{j=1}^n{J}_j}$。在这里， $p_j$ 表示客户j的每一个任务的加工时间。我们把客户分成金牌客户和银牌客户，金牌客户的任务等级较高，银牌客户的任务等级较低。对于 $j=1,2,\cdots ,n$，若客户j为银牌客户，则客户j的每一个任务只能在机器 $M_1$ 上加工；若客户j为金牌客户，则客户j的每一个任务可以在两台机器中的任意一台加工。 $S_i\left(i=1,2\right)$ 表示算法结束后分配给机器 $M_i$ 的任务集。 $t\left(S_i^j\right)\left(i=1,2\right)$ 表示分配完客户j的任务后机器 $M_i$ 的负载。 $t\left(S_i^n\right)$ 表示机器 $M_i$ 的完工时间，简记为 $t\left(S_n\right)$。 $T_1$ 表示银牌客户的任务加工时间之和， $T_2$ 表示金牌客户的任务加工时间之和。 $L_i^j$ 表示客户j的任务被调度后，分配给机器 $M_i$ 的金牌客户的任务加工时间之和。目标是寻找一个调度方案，使得机器的最大完工时间尽可能小。

为了便于理解两台平行机上的HSBT问题，下面给出一个实例。假设给定两个客户，两台机器 $M_1,M_2$，表1给出了每个客户包含的任务数量a以及每项任务的完工时间p和等级g。最优分配方案：客户1的1个任务分配给机器 $M_1$，2个任务分配给机器 $M_2$ ；客户2的所有任务分配给机器 $M_2$。可知该问题的最优目标值为8。

Table 1. Examples of multiple scheduling problems

表1. 多重调度问题实例

3. 半在线算法 $Semi-online-T_1-T_2$

在这一部分，假定已知银牌客户的任务加工时间总和为 $T_1$，金牌客户的任务加工时间总和为 $T_2$，本文设计了一个竞争比为3/2的半在线算法。。 $C_{SEMI}$ 表示半在线算法的输出值， $C_{OPT}$ 表示最优离线值。

为便于分析，令 $HT=\frac{1}{2}\left(T_1+T_2\right)$ 表示所有任务加工时间之和的一半。其中有，

$q_j=\lfloor \frac{\frac{3}{2}HT-T_1-L_1^{j-1}}{p_j}\rfloor$。

算法1： $Semi-online-T_1-T_2$

步骤1：如果 $T_2\le T_1$，分配银牌客户的任务给机器 $M_1$，分配金牌客户的任务给机器 $M_2$，算法结束。

步骤2：如果 $T_2>T_1$，令 $j=1$， $L_1^{j-1}=L_2^{j-1}=0$。

步骤2.1：如果客户j为银牌客户，分配客户j的 $a_j$ 个任务给机器 $M_1$ ；

步骤2.2：否则，分配客户j的 $q_j$ 个任务给机器 $M_1$，分配 $a_j-q_j$ 个任务给机器 $M_2$ ；

步骤3：如果有其他客户，令 $j=j+1$，转到步骤2.1。否则，结束算法。

引理1 由算法 $Semi-online-T_1-T_2$ 可知，若客户j是金牌客户而且有 $q_j<a_j$，可得 $\left(a_j-q_j\right)p_j\le HT$。

证明：若客户j只包含一个任务，即 $a_j=1$，则有 $q_j=0$，因此 $\left(a_j-q_j\right)p_j\le HT$。如果 $a_j\ge 2$，我们下面分两种情况讨论 $a_j-q_j$ 的值：

第一种情况： $a_i-q_i\ge 2$

按照算法 $Semi-online-T_1-T_2$，则有

$t\left(S_1^j\right)=L_1^{j-1}+T_1+\left(q_j+1\right)p_j>\frac{3}{2}HT$ (1)

$t\left(S_1^j\right)+t\left(S_2^j\right)=L_1^{j-1}+T_1+L_2^{j-1}+a_j{p}_j\le 2HT$ (2)

由(2)式-(1)式，则有

$L_2^{j-1}+\left(a_j-q_j-1\right)p_j<\frac{1}{2}HT$ (3)

因为 $a_j-q_j\ge 2$，所以 $a_j-q_j-1\ge 1$，再结合(3)式，则有

$p_j\le L_2^{j-1}+\left(a_j-q_j-1\right)p_j<\frac{1}{2}HT$ (4)

结合(3)式和(4)式，则有

$\left(a_j-q_j\right)p_j\le L_2^{j-1}+\left(a_j-q_j\right)p_j<HT$。

第二种情况： $a_j-q_j=1$

根据此时 $a_j\ge 2$，则有

$\left(a_j-q_j\right)p_j=p_j\le \frac{a_j{p}_j}{2}=HT$。

由上面的推导过程可知，引理1成立。

定理1 $Semi-online-T_1-T_2$ 是一个竞争比为3/2的半在线算法。

证明：下面我们用反证法证明定理不成立，假设存在极小反例。对于极小反例(客户数最少的反例)，机器的最大完工时间在加工完最后一个客户(客户n)的任务后被确定，则有

$C_{SEMI}=\max \left\{t\left(S_1^n\right),t\left(S_2^n\right)\right\}>\frac{3}{2}{C}_{OPT}$

$\max \left\{t\left(S_1^{n-1}\right),t\left(S_2^{n-1}\right)\right\}\le \frac{3}{2}{C}_{OPT}$ (5)

下面我们分两种情况讨论客户n是金牌客户还是银牌客户：

第一种情况：客户n是金牌客户。

如果客户n的所有任务分配给机器 $M_1$ 加工，则有 $t\left(S_1^{n-1}\right)+a_n{p}_n\le \frac{3}{2}HT\le \frac{3}{2}{C}_{OPT}$。根据极小反例，则有 $C_{SEMI}=t\left(S_2^n\right)>\frac{3}{2}{C}_{OPT}$。又因为 $t\left(S_2^n\right)=t\left(S_2^{n-1}\right)$，这与(5)式矛盾。

因此客户n的部分任务一定被分配给机器 $M_2$ 加工。

根据 $Semi-online-T_1-T_2$，则有 $t\left(S_1^{n-1}\right)+a_n{p}_n>\frac{3}{2}HT$ 和 $C_{SEMI}=t\left(S_2^n\right)>\frac{3}{2}{C}_{OPT}$。因此，

$t\left(S_1^{n-1}\right)+a_n{p}_n+t\left(S_2^n\right)>\frac{3}{2}\left(C_{OPT}+HT\right)$。

根据算法 $Semi-online-T_1-T_2$，则有

$t\left(S_1^n\right)+\left(a_n-q_n\right)p_n+t\left(S_1^n\right)>\frac{3}{2}\left(C_{OPT}+HT\right)$。

又根据 $t\left(S_1^n\right)+t\left(S_2^n\right)=2HT$，则有

$\left(a_n-q_n\right)p_n>\frac{3}{2}{C}_{OPT}-\frac{1}{2}HT\ge C_{OPT}$

这与引理1矛盾。

第二种情况：客户n是银牌客户。

客户n是银牌客户，则客户n的全部任务都分配 $M_1$ 加工。由 $T_1<T_2$ 及算法可知， $t\left(S_1\right)=L_1^n+T_1\le \frac{3}{2}HT\le \frac{3}{2}{C}_{OPT}$，因此 $C_{SEMI}=t\left(S_2\right)>\frac{3}{2}{C}_{OPT}$，又因为 $t\left(S_2\right)=t\left(S_2^n\right)=t\left(S_2^{n-1}\right)$，这与(5)式矛盾。

4. 半在线算法 $Semi-online-T_1$

在这一部分，假定银牌客户的任务加工时间总和 $T_1$ 已知，下面提出一个竞争比为3/2的半在线算法。当客户j到达时，如果 $g_j=1$，则分配客户j的 $a_j$ 个任务给机器 $M_1$ ；如果 $g_j=2$，则分配客户j的 $q_j$ 个任务给机器 $M_1$，分配 $a_j-q_j$ 个任务给机器 $M_2$。其中有

$q_j=\lfloor \frac{L_1^{j-1}+T_1+a_j{q}_j-L_2^{j-1}}{2p_j}\rfloor .$ (6)

算法2： $Semi-online-T_1$

步骤1：令 $j=1$ ； $L_1^{j-1}=L_2^{j-1}=0$ ；

步骤2：如果客户j为银牌客户，分配客户j的 $a_j$ 个任务给机器 $M_1$ ；

步骤3：否则，分配客户j的 $q_j$ 个任务给机器 $M_2$，分配 $a_j-q_j$ 个任务给机器 $M_1$ ；

步骤4：如果有其他客户，令 $j=j+1$，转到步骤2。否则，结束算法。

引理2 若金牌客户j的部分任务分配给机器 $M_1$，根据 $q_j$ 的定义可知，则 $t\left(S_2^j\right)\le t\left(S_1^j\right)$。

证明：由公式(6)可知， $q_j\le \frac{L_1^{j-1}+T_1+a_j{q}_j-L_2^{j-1}}{2p_j}$，因此

$t\left(S_2^{j-1}\right)+q_j{p}_j\le L_1^{j-1}+T_1+\left(a_j-q_j\right)p_j$

即 $t\left(S_2^j\right)\le t\left(S_1^j\right)$。

定理2 $Semi-online-T_1$ 是一个竞争比为3/2的半在线算法。

证明：由引理2和算法 $Semi-online-T_1$ 可知， $t\left(S_2\right)\le t\left(S_1\right)$。

假设 $t\left(S_1\right)>\frac{3}{2}{C}_{OPT}$，则有 $t\left(S_2\right)<\frac{1}{2}{C}_{OPT}$。

由 $t\left(S_1\right)>\frac{3}{2}{C}_{OPT}>\frac{3}{2}{T}_1>T_1$，则有至少一个等级为2的任务把任务分配给机器 $M_1$。

设k是最后一个把部分任务分配给 $M_1$ 等级为2的客户。

当客户k到达时，有

$t\left(S_2^k\right)=t\left(S_2^{k-1}\right)+q_k{p}_k\le t\left(S_2\right)<\frac{1}{2}{C}_{OPT}$ (7)

根据 $q_k$ 的定义可知，

$t\left(S_2^{k-1}\right)+q_k{p}_k+p_k\ge t\left(S_1^{k-1}\right)+T_1+\left(a_k-q_k\right)p_k$

又因为 $t\left(S_1\right)=t\left(S_1^{k-1}\right)+T_1+\left(a_k-q_k\right)p_k>\frac{3}{2}{C}_{OPT}$，则有

$t\left(S_2^{k-1}\right)+q_k{p}_k+p_k>\frac{3}{2}{C}_{OPT}$，

又因为 $p_k\le C_{OPT}$，则有

$t\left(S_2\right)=t\left(S_2^{k-1}\right)+q_k{p}_k>\frac{1}{2}{C}_{OPT}$，

与公式(7)矛盾。

5. 结束语

本文提出了两台平行机带等级约束的多重调度问题，当分别已知银牌客户和金牌客户的任务加工时间之和时，本文提出了一个竞争比为3/2的半在线算法。当已知银牌客户任务的加工时间之和时，本文提出了一个竞争比为3/2半在线算法。下一步，当已知金牌客户任务的加工时间之和时，我们希望给出一个半在线算法。

基金项目

楚雄师范学院研究项目(XJYB2004)资助。