带约定时间的多维任务负载平衡问题

Multidimensional Task Load Balancing Problem with a Common Due Date

摘要: 本文研究了两台平行机上带约定时间的多维任务负载平衡问题，该问题是传统负载平衡问题的推广，目标是最大化机器的提前工作量。带有约定时间的多维任务负载平衡问题涉及到在多个维度上平衡任务的分配，同时满足任务的约定时间。这种问题在许多实际应用中都很常见，比如生产调度、交通规划、资源分配等领域。对于该问题，当任务的维数为 时，本文设计了一个在线算法，算法的竞争比为(√5-1)l，然后设计了一个动态规划算法以得到问题的最优解，最后在动态规划的基础上采用舍入取整技术设计了一个FPTAS。

Abstract: In this paper, we study multidimensional task loading problem on two parallel machines with a common due date. This problem is a generalization of the traditional load balancing problem, with the goal of maximizing the advance workload of machines. The multi-dimensional task load balanc-ing problem with a common due date involves balancing the distribution of tasks in multiple di-mensions while satisfying the due date time of tasks. This kind of problem is common in many prac-tical applications, such as production scheduling, transportation planning, resource allocation. For this problem, when the dimension of the task is l, we first designs an online algorithm with a com-petitive ratio of (√5-1)l , and the dynamic programming algorithm is designed to obtain the op-timal solution of the problem. Finally, on the basis of dynamic programming, the FPTAS is designed by rounding technique.

1. 引言

带约定时间的负载平衡问题是一类具有广泛的实际问题。该问题常常发生在生产贸易中，客户与工厂约定一个交货时间d，在d之前交付的商品，客户支付较高的价格，在d之后交付的商品，客户支付较低的价格。工厂为了最大化利润，需要制定生产计划，以使得在约定时间之前交付更多的商品。

对于带约定时间的两台平行机负载平衡问题，Chen等人在文 [1] 中设计了一个竞争比为 $\sqrt{5}-1$ 的最优在线算法。当所有工件总的加工时间已知时，Chen等人在文 [2] 中设计了一个竞争比为6/5的最优半在线算法。对于带约定时间和等级的两台平行机负载平衡问题，Xiao等人在文 [3] 中设计了三个半在线算法，当已知低等级或高等级工件的加工时间之和时，分别设计了一个竞争比为 $\sqrt{5}-1$ 的最优半在线算法，当已知低等级与高等级工件的加工时间之和时，设计了一个竞争比为6/5的最优半在线算法。

向量负载平衡问题是把n个l-维向量分配给m台机器加工以使得所有机器、所有维数的最大负载尽可能小。Graham等人在文 [4] 中创造性的工作，使得单维负载均衡问题被广泛的推广。Chekuri等人在文 [5] 首次提出离线多维向量负载平衡问题。当向量维数是任意常数时，Chekuri等人在文 [5] 设计了一个 $O\left({\ln }^{2}l\right)$ -近似算法。Meyerson等人在文 [6] 中设计了一个 $O\left(\log l\right)$ -近似算法。Im等人在文 [7] 设计了一个 $O\left(\log l/\log \log l\right)$ -近似算法。对于向量负载平衡问题，当向量维数l是固定常数时，Chekuri在文 [5] 首次给出多项式时间近似方案，算法的运行时间是 $n^{g\left(\epsilon ,l\right)}$ 。Bansal等人在文 [8] 设计了一个运行时间为 $\exp \left({\left(1/\epsilon \right)}^{O\left(l\log \log l\right)}\right)+nl$ 的 $\left(1+\epsilon \right)$ -近似算法。

Li等人在文 [9] 中第一次提出带惩罚费用的向量负载平衡问题，并证明了该问题是NP-hard。他们在多项式时间内设计了两个近似算法。Dai等人在文 [10] 中提出了两台平行机上带惩罚费用的多维任务负载平衡问题，设计了一个3-近似算法；在任务的维数为固定常数的情况下，在任务的维数l为固定常数的情况下，利用动态规划算法得到一个完全多项式时间近似方案；根据随机舍入方法，设计了一个近似算法，算法的近似比为2.54；在多维任务的信息未知时，设计了一个在线算法，在线算法的竞争比为2.618l。

在实际问题中，一项任务可能需要多种资源来完成，因此需要用多维向量描述任务的需求。在本文中，每个多维任务都有一个共同的约定时间，算法需要把每个多维任务调度到一台机器上加工。基于此，本文研究两台平行机上带约定时间的多维任务提前工作量最大化负载平衡问题，该问题记作 $P_2|d_j=d,VC|\max \left(X\right)$ 。

2. 问题描述及符号说明

两台平行机上带约定时间的多维任务负载平衡问题可以描述为：给定一个实例 $I=\left(M,J,p,d\right)$ ，两台平行机构成的集合 $M=\left\{M_1,M_2\right\}$ ，n项任务构成的集合 $J=\left\{J_1,J_2,\cdots ,J_n\right\}$ ，一个共同的约定时间d。 $p_j={\left(p_{j1},p_{j2},\cdots ,p_{jl}\right)}^{\text{T}}$ 是对应于任务 $J_j\left(j=1,\cdots ,n\right)$ 的一个l-维向量。任务 $J_j$ 到达后，算法立刻分配给一台机器加工， $S_i\left(i=1,2\right)$ 表示分配给机器 $M_i$ 的任务集。

$L_{i\max }$ 表示机器 $M_i$ 负载向量的最大分量，

$L_{i\max }={\max }_k{\displaystyle {\sum }_{J_j\in S_i}{p}_{jk}}\left(k=1,2,\cdots ,l\right)$

对于两台平行机带约定时间的多维任务负载平衡问题，问题的目标是最大化X。

$X={\displaystyle \underset{i=1}{\overset{2}{\sum }}\min \left\{L_{i\max },d\right\}}$

下面给出问题 $P_2|d_j=d,VC|\max \left(X\right)$ 的一个实例：M₁、M₂表示两台平行机，表1给出3项任务对应的向量。在这里，任务维数 $l=3$ ，约定时间 $d=5$ 。根据目标函数的定义，该问题的最优解是把任务J₁和J₃分配给M₁，任务J₂分配给M₂，最优值目标函数值为8。

Table 1. Example of multidimensional task scheduling with a common due date

表1. 带约定时间的多维负载平衡实例

3. $\left(\sqrt{5}-1\right)l$ -在线算法

在这一部分，本文根据实例 $I=\left(M,J,p,d\right)$ ，设计了一个辅助实例 $\hat{I}=\left(M,J,\hat{p},d\right)$ 。对于实例I，任务 $J_j$ 用l-维向量 $p_j={\left(p_{j1},p_{j2},\cdots ,p_{jl}\right)}^{\text{T}}$ 描述。对于实例 $\hat{I}$ ，任务 $J_j$ 用1维向量 ${\hat{p}}_j={\displaystyle {\sum }_{k=1}^l{p}_{jk}}$ 描述。根据实

例I的目标函数定义，实例 $\hat{I}$ 目标函数是最大化 ${\displaystyle \underset{i=1}{\overset{2}{\sum }}\min \left\{{\displaystyle {\sum }_{j\in S_i}{\hat{p}}_j},d\right\}}$ 。

在线算法的设计策略如下：我们用EFF-LPT [1] 算法分配实例 $\hat{I}$ 中的任务，可得实例 $\hat{I}$ 的一个可行解 $\left(S_1,S_2\right)$ 。根据实例 $\hat{I}$ 和I的定义可知， $\left(S_1,S_2\right)$ 也是I的一个可行解。对于可行解 $\left(S_1,S_2\right)$ ，我们分别用 $OUT\left(\hat{I}\right)$ 、 $OUT\left(I\right)$ 表示实例 $\hat{I}$ 与I的输出值。 $OPT\left(\hat{I}\right)$ 与 $OPT\left(I\right)$ 则分别表示实例 $\hat{I}$ 与I的最优值。

MT-LPT在线算法

Step1：对于任意输入实例I，设计辅助实例 $\hat{I}$ ；

Step2：运用EFF-LPT [1] 算法求解实例I，可得实例I的一个可行解 $\left(S_1,S_2\right)$ ；

Step2.1：任务 $J_j\left(j=1,\cdots ,n\right)$ 到达时，根据 $p_j$ 构造 ${\hat{p}}_j$ 。

Step2.2： $i=1,i\le 2,i++$ ；

如果 $t\left(S_i^{j-1}\right)+{\hat{p}}_j\le \left(\sqrt{5}-1\right)l$ ，分配 $J_j$ 给机器 $M_i$ 。

Step2.3：否则，分配 $J_j$ 给负载小的机器。

Step3：对于 $\left(S_1,S_2\right)$ ，分别输出实例I与 $\hat{I}$ 的目标值 $OUT\left(I\right)$ 、 $OUT\left(\hat{I}\right)$ 。

定理1对于问题 $P_2|d_j=d,VC|\max \left(X\right)$ ，在线算法MT-LPT的竞争比为 $\left(\sqrt{5}-1\right)l$ 。

证明：我们由文 [1] 可得，平行机的台数为2时，用MT-LPT求解实例 $\hat{I}$ ，则有

$OPT\left(\hat{I}\right)\le \left(\sqrt{5}-1\right)OUT\left(\hat{I}\right)$ (1)

假设 $OUT\left(I\right)=\min \left\{L_{1\max },d\right\}+\min \left\{L_{2\max },d\right\}$ ，由实例I目标值的定义，则

$lOUT\left(I\right)\ge \min \left\{{\displaystyle {\sum }_{J_j\in S_1}{\displaystyle {\sum }_{k=1}^l{p}_{jk}}},d\right\}+\min \left\{{\displaystyle {\sum }_{J_j\in S_2}{\displaystyle {\sum }_{k=1}^l{p}_{jk}}},d\right\}$ (2)

由实例 $\hat{I}$ 目标值的定义，则

$OUT\left(\hat{I}\right)=\min \left\{{\displaystyle {\sum }_{J_j\in S_1}{\displaystyle {\sum }_{k=1}^l{p}_{jk}}},d\right\}+\min \left\{{\displaystyle {\sum }_{J_j\in S_2}{\displaystyle {\sum }_{k=1}^l{p}_{jk}}},d\right\}$ (3)

联立(2)和(3)式，则有

$OUT\left(\hat{I}\right)\le lOUT\left(I\right)$ (4)

接下来，本文用反证法证明 $OPT\left(I\right)\le OPT\left(\hat{I}\right)$ 成立。

假设 $OPT\left(I\right)>OPT\left(\hat{I}\right)$ 。

令 $\left(S_1^{*},S_2^{*}\right)$ 表示实例I的最优解。由实例I目标值的定义可知，

$\begin{array}{c}OPT\left(I\right)=\min \left\{L_{1\max },d\right\}+\min \left\{L_{2\max },d\right\}\\ \le \min \left\{{\displaystyle {\sum }_{J_j\in S_1^{*}}{\displaystyle {\sum }_{k=1}^l{p}_{jk}}},d\right\}+\min \left\{{\displaystyle {\sum }_{J_j\in S_2^{*}}{\displaystyle {\sum }_{k=1}^l{p}_{jk}}},d\right\}\\ \le OPT(\; I\; ^\; )\end{array}$

这与假设矛盾。因此，则有

$OPT\left(I\right)\le OPT\left(\hat{I}\right)$ (5)

由(1)、(4)、(5)式，则有

$OUT\left(I\right)\le \left(\sqrt{5}-1\right)lOPT\left(I\right)$ (6)

由以上证明可知，对于带约定时间的多维任务负载平衡问题，MT-LPT的竞争比为 $\left(\sqrt{5}-1\right)l$ 。

4. 问题 $P_2|d_j=d,VC|max\left(X\right)$ 的动态规划算法

我们设计了一个动态规划算法DY-AL求解问题 $P_2|d_j=d,VC|\max \left(X\right)$ 。算法思想如下：把n项任务所有的可行解尝试一遍，从而求出 $P_2|d_j=d,VC|\max \left(X\right)$ 的最优解。下面给出具体的算法步骤和一些符号说明。

${\epsilon }_i\left(i=1,2\right)$ 是第i列元素为1，其它的元素是0的 $l\times 2$ 维矩阵。我们定义一个新的运算，令 $p_j\otimes {\epsilon }_i$ 为列向量 $p_j$ 每个分量和 ${\epsilon }_i$ 的第i列元素对应相乘。

举个例子 $p_1\otimes {\epsilon }_1=\left(\begin{array}{c}{p}_{11}\\ p_{12}\\ ⋮\\ p_{1l}\end{array}\right)\otimes \left(\begin{array}{cc}1& 0\\ 1& 0\\ ⋮& ⋮\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}{p}_{11}& 0\\ p_{12}& 0\\ ⋮& ⋮\\ p_{1l}& 0\end{array}\right)$ 。

令 ${\Psi }_j\left(j=0,1,\cdots ,n\right)$ 表示加工完前j项任务后所有可能的负载矩阵构成的集合。

DY-AL动态规划算法

Step1：置 ${\Psi }_0=\left\{{\left(0\right)}_{l\times 2}\right\}$ ；

Step2：当任务 $J_j\left(j=1,\cdots ,n\right)$ 到达时，集合 ${\Psi }_j$ 可由 ${\Psi }_{j-1}$ 递推得到，计算方法如下：

${\Psi }_j={\Psi }_{j-1}+\left\{p_j\otimes {\epsilon }_i|i=1,2\right\}$ ；

Step3：对集合 ${\Psi }_n$ 所有的负载矩阵，提取第一列的最大值得到集合 $\left\{c_1,c_2,\cdots ,c_{\left|{\Psi }_n\right|}\right\}$ ，提取第二列的最大值得到集合 $\left\{{\tilde{c}}_1,{\tilde{c}}_2,\cdots ,{\tilde{c}}_{\left|{\Psi }_n\right|}\right\}$ ， $\left|{\Psi }_n\right|$ 表示空间 ${\Psi }_n$ 中负载矩阵的个数。令 $\alpha =\max \left\{c_1,c_2,\cdots ,c_{\left|{\Psi }_n\right|}\right\}$ ， $\beta =\max \left\{{\tilde{c}}_1,{\tilde{c}}_2,\cdots ,{\tilde{c}}_{\left|{\Psi }_n\right|}\right\}$ 。最后输出 $\min \left\{\alpha ,d\right\}+\min \left\{\beta ,d\right\}$ 。

由动态规划算法的步骤可知，问题 $P_2|d_j=d,VC|\max \left(X\right)$ 的最优解可由DY-AL得到。

5. 问题 $P_2|d_j=d,VC|max\left(X\right)$ 的完全多项式时间近似方案

当任务维数为给定常数时，在动态规划的基础上采用舍入取整技术，设计了一个全多项式时间近似方案(FPTAS)。

定理2 当l给定值时，问题 $P_2|d_j=d,VC|\max \left(X\right)$ 在 $O\left(n^{2l+1}{\left(\frac{l^2}{\epsilon }\right)}^{2l}\right)$ 时间内存在一个FPTAS。

证明：在这里，令L是MT-LPT处理实例I得到的输出值。由定理1可知，

$L\le OPT\left(I\right)\le \left(\sqrt{5}-1\right)lL$ (7)

根据实例 $I=\left(M,J,p,d\right)$ 设计辅助实例 $I^{\prime }=\left(M,J,p^{\prime },d\right)$ 。对于实例I来说，任务 $J_j$ 与向量 $p_j={\left(p_{j1},p_{j2},\cdots ,p_{jl}\right)}^{\text{T}}$ 对应。对于辅助实例 $I^{\prime }$ 来说，任务 $J_j$ 与向量 ${p^{\prime }}_j={\left({p^{\prime }}_{j1},{p^{\prime }}_{j2},\cdots ,{p^{\prime }}_{jl}\right)}^{\text{T}}$ 对应。我们令

$\alpha =\sqrt{5}-1$ ，而且令 ${p^{\prime }}_{jk}=\lfloor \frac{p_{jk}}{\epsilon L/\alpha nl}\rfloor \cdot \frac{\epsilon L}{\alpha nl}\left(k=1,2,\cdots ,l\right)$ 。由 ${p^{\prime }}_{jk}=\lfloor \frac{p_{jk}}{\epsilon L/\alpha nl}\rfloor \cdot \frac{\epsilon L}{\alpha nl}$ 的定义，我们可以得到 ${p^{\prime }}_{jk}\le p_{jk}\le {p^{\prime }}_{jk}+\frac{\epsilon L}{\alpha nl}$ 。

假设 $\left({S^{\prime }}_1,{S^{\prime }}_2\right)$ 是算法DY-AL求解实例 $I^{\prime }=\left(M,J,p^{\prime },d\right)$ 的最优解，则最优值

$OPT\left(I^{\prime }\right)=\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_1}{\sum }{p^{\prime }}_{jk}},d\right\}+\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_2}{\sum }{p^{\prime }}_{jk}},d\right\}$ 。

假设实例I的最优解是 $\left(O_1,O_2\right)$ ，则最优值

$OPT\left(I\right)=\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in O_1}{\sum }{p^{\prime }}_{jk}},d\right\}+\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in O_2}{\sum }{p^{\prime }}_{jk}},d\right\}$ 。

依据实例 $I^{\prime }$ 的最优解 $\left({S^{\prime }}_1,{S^{\prime }}_2\right)$ 调度实例I，则有

$\begin{array}{l}\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_1}{\sum }{p^{\prime }}_{jk}},d\right\}+\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_2}{\sum }{p^{\prime }}_{jk}},d\right\}\\ \le \min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_1}{\sum }\left({p^{\prime }}_{jk}+\frac{\epsilon L}{\alpha nl}\right)},d\right\}+\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_2}{\sum }\left({p^{\prime }}_{jk}+\frac{\epsilon L}{\alpha nl}\right)},d\right\}\\ \le \min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_1}{\sum }{p^{\prime }}_{jk}},d\right\}+\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_2}{\sum }{p^{\prime }}_{jk}},d\right\}+n\frac{\epsilon L}{\alpha nl}\\ =\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_1}{\sum }{p^{\prime }}_{jk}},d\right\}+\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in {S^{\prime }}_2}{\sum }{p^{\prime }}_{jk}},d\right\}+\frac{\epsilon L}{\alpha l}\end{array}$

$\begin{array}{l}\le \min \left\{\underset{k}{\max }{\displaystyle \underset{j\in O_1}{\sum }{p^{\prime }}_{jk}},d\right\}+\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in O_2}{\sum }{p^{\prime }}_{jk}},d\right\}+\frac{\epsilon L}{\alpha l}\\ \le \min \left\{\underset{k}{\max }{\displaystyle \underset{j\in O_1}{\sum }{p}_{jk}},d\right\}+\min \left\{\underset{k}{\max }{\displaystyle \underset{j\in O_2}{\sum }{p}_{jk}},d\right\}+\frac{\epsilon L}{\alpha l}\\ \le OPT\left(I\right)+\epsilon OPT\left(I\right)\\ =\left(1+\epsilon \right)OPT(\; I\; )\end{array}$

下面分析算法的运行时间，由定理2中的(7)式可知， $OPT\left(I^{\prime }\right)\le OPT\left(I\right)\le \alpha lL$ ，所以算法DY-AL求

解实例 $I^{\prime }$ 时，只计算负载分量不超过 $\alpha lL$ 的可行解，而且机器的各负载分量又是 $\frac{\epsilon L}{\alpha nl}$ 的整数倍，则机器负载最多有 $\alpha lL/\frac{\epsilon L}{\alpha nl}+1=\frac{{\alpha }^{2}n{l}^2}{\epsilon }+1$ 种可能。又因为每个负载矩阵的元素个数为2l，而且任务总个数为n，所以实例 $I^{\prime }$ 能够在 $O\left(n{\left(\frac{{\alpha }^{2}n{l}^2}{\epsilon }+1\right)}^{2l}\right)=O\left(n^{2l+1}{\left(\frac{l^2}{\epsilon }\right)}^{2l}\right)$ 时间找到最优解。

6. 结论

本文研究了两台平行机上带约定时间的多维任务负载平衡问题，设计了一个在线算法，算法的竞争比为 $\left(\sqrt{5}-1\right)l$ ，然后给出该问题的一个FPTAS。对于带约定时间的多维任务负载平衡问题，以后我们希望设计一个近似算法。

基金项目

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

NOTES

^*通讯作者。