带惩罚费用的多重任务排序问题∗

崔倩娜

（云南大学数学与统计学院 昆明 650000）

1 引言

长期以来，排序问题的近似算法研究都是算法理论领域研究的热点问题之一。受滑雪板租赁问题的启发，Bartal等［1］提出带惩罚费用的平行机排序问题 P∥Cmax+Σj∈Rwj，其定义如下：给定 m 台平行机和n项任务，每项任务的处理时间为 pj，惩罚费用为wj，一项任务要么被接受并在某台机器上处理，要么被拒绝并产生相应的惩罚费用。该问题的目标是寻找一个排序方案，使得机器的最大完工时间与被拒绝任务的惩罚费用之和最小。Bartal等［1］设计了一个运行时间为O(nlogn)的(2-1/m)-近似算法和一个运行时间为O((n3/ε)■■9ε2)的多项式时间近似方案（Polynomial Time Approximation Scheme，PTAS），推广了 Hochbaum和Shmoys［2］的结果。当机器数为固定常数时，Bartal等［1］还给出了一个运行时间为O(nm+1/εn)的全多项式时间近似方案（Fully Polynomial Time Approximation Scheme，FPTAS）。随后，带惩罚费用的机器排序问题及其变种迅速成为排序领域的热点问题之一。Ou等［3］给出 P∥Cmax+Σj∈Rwj问题的一个运行时间为O(nlogn+n/ε)的 (1.5+ε)-近似算法（这里 ε＞0为任 意 常 数）。 最 近 ，Ou和 Zhong［4］给 出P∥Cmax+Σj∈Rwj问题的一个运行时间为 O(mn2/ε2)的(4/3+ε)-近似算法。

Zhang和Lu［5］考虑了带就绪时间和惩罚费用的平行机排序问题 P ||rjCmax+Σj∈Rwj（这里 rj为任务的就绪时间），设计了一个运行时间为O(n2)的2-近似算法，当机器数为固定常数时，给出一个运行时间为 O(n2m+1/εm)的 FPTAS。随后，Zhong和 Ou［6］提出一个运行时间为 O(nlogn)的2-近似算法，一个运行时间为 O(nlogn+mO((log1/ε)/ε2))的 PTAS，和一个机器数为固定常数时运行时间为O(nlogn+1/ε3m+6)的 FPTAS，改进了 Zhang和 Lu［5］的结果。Zhong等［7］研究文献［4］中 m=2 的情况，给出一个运行时间为O((n/ε)2)的(1.5+ε)-近似算法。Li等［8］研究了惩罚费用受限的平行机排序问题 P ||Σj∈RwjCmax，设计了一个运行时间为 O(mn2)的2-近似算法，一个运行时间为O(nmO(1/ε2)+mn2)的PTAS和机器数为固定常数时的一个运行时间为O(1/ε2m+3+mn2)的FPTAS。Shabtay等［9］研究了处理时间相同时的带惩罚费用的双标准同类机排序问题。

当机器数为1时，Zhang等［10］证明了带就绪时间和惩罚费用的单机排序问题1 ||rj,rej Cmax+Σj∈Rwj是NP-难的，设计了一个运行时间为O(n2)的2-近似算法和一个运行时间为O(n3/ε)的FPTAS。Ou 等［11］提出一个运行时间为 O(nlogn)的2-近似算法和所有任务的加工时间相同时的一个运行时间为O(n2logn)的精确算法。Zhang等［12］证明了带就绪时间和惩罚费用受限的单机排序问题1|rj,Σj∈Rwj≤U |Cmax是 NP-难的，给出一个运行时间为 O(n3/ε)的FPTAS。Lu和Zhang［13］考虑了带生产费用和惩罚费用的单机排序问题。Shabtay等［14］研究了带惩罚费用和位置费用的双标准的单机排序问题，设计了多个最优算法或近似算法。He等［15］考虑了带就绪时间和惩罚费用的双标准的单机排序问题，对于最大完工时间与惩罚费用之和最小化问题，给出一个运行时间为O(nlogn)的4/5-近似算法；当最大完工时间受限时，设计了一个运行时间为O(n2/ε+n2logn)的FPTAS；当惩罚费用受限时，设计了一个运行时间为O(n2)的2-近似算法和一个运行时间为O(n2/ε+n2logn)的FPTAS，推广了 Gens和 Levner［16］的结果。

Bartal等［1］还对带惩罚费用的在线机器排序问题做了研究，所有任务的加工时间和惩罚费用都是未知的，给出一个竞争比为2.618的最优在线算法；当机器数为2时，设计了一个竞争比为1.618的最优在线算法。Seiden［17］研究了带惩罚费用的可中断平行机在线排序问题，给出一个竞争比为(4+)/3的在线算法，并指出任何在线算法的下界为 2.12。Gyorgy和 Imreh［18］提出带惩罚费用和机器费用的在线排序问题，设计了一个竞争比为(3+)/2 的最优在线算法。Epstein 和 Haider［19］研究了关于带惩罚费用的三台机器在线排序问题，当所有任务的处理时间为1，设计了一个竞争比1.839的最优在线算法。

由于在高性能计算环境中，用户提交的任务通常具有数量大且处理时间相同等特征，多重任务排序引起了学者的广泛关注［20～21］。另一方面，Goemans和 Rothvoß［22］给出多重物品装箱问题的一个最优算法。受文献［20～22］的启发，将任务或物品的类型视为用户，本文提出了带惩罚费用的多重任务排序问题（Multi-task Scheduling Problem with Rejection，MTSR），其定义如下：给定 n 个用户，每个用户 j提交tj项任务，任务集记为Tj，Tj中的每个任务具有相同的加工时间 pj和惩罚费用wj。每个用户提交的任务要么全部被接受，并被安排在m台机器上处理；要么全部被拒绝，并产生相应的惩罚费用。本文假定，一旦某项任务开始在某台机器上处理，则中间不被打断直到完工，而且所有任务的安排没有优先权。目标是寻找一个排序方案，使得机器的最大完工时间与所有被拒绝的任务的惩罚费用之和达到最小。

为更加清晰地描述问题，用xij表示被接受的用户 j提交的任务被安排在机器i上的数量，zj表示用户 j是否被接受，若被接受，则zj=1，否则，zj=0。MTSR问题的数学规划形式如下：

注意到，当每个用户提交的任务数量tj都为1时 ，MTSR 问 题 即 为 Bartal等［1］研 究 的 问 题P∥Cmax+Σj∈Rwj。因此，一种直观的想法是将所有任务的集合看作问题 P∥Cmax+Σj∈Rwj的任务集，从而使用［1］中的算法进行求解。但是，运行时间并不是关于输入长度的多项式函数。

2 MTSR问题的离线算法

2.1 2-近似算法

本节讨论一般情形下的MTSR问题，并给出一个2-近似算法H。算法H的主要思想是将用户集合U中一部分惩罚费用较小的用户都拒绝，这里 ||U=n；然后，将剩余用户提交的所有任务划分成m个集合；最后，把划分后的集合看作一个整体任务，并将其安排在m台机器上，接受一些加工时间较小的用户。

算法1 H

1）令 B={j|wj≤pj/m}，将集合 B中的所有用户都拒绝；

2）对U-B中的用户，以加工时间非减顺序排列；

3）将U-B中的每一个用户 j提交的所有任务分割成m个任务集合，即

这里 k=tj-

即Tj1,…,Tjk的每个集合中都含有用户 j所提交的个任务，Tj,k+1,…,Tjm中每个集合都含有用户 j所提交的个任务。计算每个被划分后的集合中总共的加工时间和惩罚费用，即

4）对每一个0≤h≤ ||U-B ，从U-B中选取的前h个用户，将这h个用户中的所有任务集（每个任务集视作一个任务，共hm个任务）用LS（List Scheduling）算法安排到m台机器上，然后将剩下的所有用户都拒绝，令这一调度方案为Sh。

5）在 ||U-B+1个可行方案中，选择目标函数值最小的方案Sh。

定理1 算法H是一个运行时间为O(n2logn)的2-近似算法。

证明 令A*，R*分别表示最优方案中被接受的用户集合和被拒绝的用户集合，A*T*和R*T*分别表示用户集合A*和R*对应的任务集合，Z*为最优方案的目标函数值。令UT表示用户集合U对应的任务集，A（或R）表示算法H的输出解中被接受（或被拒绝）的用户集合，AT（或RT）表示对应的任务集。令ZH表示算法H的输出解的目标函数值。对任意任务集T，令M(T)=∑j∈Tpjm和W(T)=∑j∈Twj分别表示任务集T中所有任务的平均负载和总惩罚费用。对任意用户集合X⊆U，令C(X)表示X中被接受用户提交的所有任务按LS算法安排在m台机器上之后，机器的最大完工时间。

假设算法第2）步中，用户集合U-B排序结果为1,…, ||U-B。如果最优方案拒绝U-B中所有用户，由B的定义知，拒绝B中所有用户也是最有的。因此，方案S0拒绝所有用户是最优的，即ZH=Z*。

否则，令l为在最优方案中从用户集合U-B中接受的最后一个用户。考虑算法H的输出解Sl，不失一般性，令 A={1,…,l}表示调度方案Sl所接受的用户集合，则l为所有被接受的用户里，任务加工时间最大的用户。由于用户集合A中的所有任务集合按LS方法安排在m台机器上。所以，调度方案Sl的机器的最大完工时间至多为

由于算法H的输出的目标函数值至多为方案Sl的目标函数值，则

因为集合 A不包含B中任何用户，所以，有M((AT{Tl,m})∩R*T*)≤W((AT{Tl,m})∩R*T*)。由 l的选择以及B的定义可知，A*∩(U-A)⊆B。这是由于U-A={l+1,…, ||U-B}∪B，而 l为 A*中从U-B中接受的最后一个用户，所以A*中不包含用户集合{l+1,…, ||U-B}中任意一个用户。从而，可以得到

W((UTAT)∩A*T*)≤M((UTAT)∩A*T*) 。 因此，上面的式（3）可以整理为

所以，算法H的近似比为2。

算法H的第一步选出属于集合B中的用户需要 O(n)时间，第二步给用户排序最多需要O(nlogn)时间，第三步将集合U-B中每个用户提交的所有任务划分成m个任务集最多需要O(m)时间，分割所有用户提交的所有任务最多需要O(nm)时间。计算每个集合的运行总时间和总惩罚费用最多可以在O(nm)内完成。第四步和第五步是选取方案Sh，使用了LS算法，所需要时间为O(nmlogm)。当n＞m时，算法的运行时间不会超过O(n2logn)。证毕。

2.2 机器数为固定常数时的一个FPTAS

当机器数m为固定常数时，在动态规划的基础上采用舍入取整技术，设计了一个FPTAS。

定理2 当机器数为固定常数时，MTSR问题可以在多项式时间O(n(tmaxZ*)m)内解决，其中tmax=max{t1,…,tn}，Z*是最优方案的目标函数值。

证明 采用动态规划方法。

令Li(i=1,2，…,m)为机器i的当前负载，对于每个L1,L2,…,Lm≤Z*，计算在这些负载下可以获得的总惩罚费用的最小值。在第 j个用户被安排或拒绝后，用Ej(L1,L2,…,Lm)来定义当前负载下可以获得的总惩罚费用的最小值。令aij为将用户 j提交的任务被安排在机器i上的数量。当Li＜0时，定义惩罚费用的最小值为∞。同时，可以在具有机器负载L1,L2,…,Lm的情况下可以计算出最后总花费 Z(L1,…,Lm)。对于L1,…,Lm≥0，这些值的计算可以用以下方式得出：

初始化：E0(0,…,0)=0；

定理3 对任意ε＞0，MTSR问题存在一个运行时间为O(()m(ntmax)m+1)的FPTAS。

证明 将所研究的实例I，通过舍入取整技术构造一个新的实例I′。每个用户 j提交tj个任务，这tj个任务有相同的加工时间pj′=和惩罚费用wj′=，其中，δ=εZH/2n(tmax)，这里ZH为通过算法H获得的目标函数值。采用定理2中的动态规划获得实例I'的一个最优排序方案，将此方案用在实例I上，获得实例I的一个近似方案。

通过上述方式获得的实例I的近似函数值Z(I)与最优函数值最多相差δntmax=εZH/2。由已经获得的最优函数值的下界Z*≥ZH/2，可以得到

由于实例I′的最优函数值与实例I的最优函数值满足 Z*≤Z*(I)/δ≤2ZH/δ，所以 Z*≤4ntmax/ε。定理2指出，实例I的最优解可以在时间O(n(tmaxZ*)m)内得到，故实例I′的最优解可以在多项式时间O((m(ntmax)m+1)内得到。证毕。

3 关于两台机器的在线算法

在离线问题中，所有用户提交的任务数量，每项任务的加工时间，以及被拒绝后的惩罚费用都是已知的。而要研究的在线问题，在上一个用户提交的所有任务被安排完之后，才会获得一个新用户的信息。当机器数为2时，设计了一个在线算法Aα，算法的设计思想是将惩罚费用较小的用户都拒绝，再将剩余用户提交的任务划分成两个任务集，把这两个任务集分别安排在两台机器上。

算法2 Aα

1）如果用户 j提交的所有任务的加工时间和惩罚费用满足wj≤αpj，则拒绝用户 j；

2）否则，将用户 j提交的所有任务分割成2个任 务 集 ，Tj=Tj1∪Tj2，其 中，而，计算两个被划分后的任务集中总共的加工时间和惩罚费用，即，且将两个集合依次安排在当前机器负载最小的机器上。

定理4 如果α满足不等式（6），则在线算法Aα的竞争比为1.618。

证明 分两种情况来证明：

1）若算法Aα拒绝了所有用户，则由算法输出的目标函数值

由于所有属于A*的用户都被算法拒绝，所以，对于每一个 j∈A*满足wj≤αpj。则A*提交的所有任务的惩罚费用之和满足W(A*T*)≤2αM(A*T*)。由条件（6）可将式（7）经整理得

2）否则，令l为最后一个被接受的用户，Tl2为Tl中最后一个被安排的任务集合。则所有被接受的用户提交的所有任务被安排到2台机器上之后，机器的最大完工时间为

由于算法Aα拒绝的用户集合R，其中每项任务的加工时间和惩罚费用满足wj≤αpj，则会有∑j∈Rtjwj≤2α∑j∈Rtjpj/2 ，所以算法输出的用户集合R提交的所有任务的惩罚费用之和满足：

由条件（6）可知，算法Aα输出的被接受的用户集合 A提交的任务满足w≥αp≥p，则集合 Ajjj提交的所有任务的平均负载小于总惩罚费用。从而会有

由条件（6）和（9）、（10）、（11）可以得到算法 Aα输出的目标函数值为

为证明竞争比，则需要讨论算法输出的被接受的最后一个用户l是否属于最优方案中被接受的用户集合，分成两种情况来说明：

1）如果用户l∈A*，由不等式（6）和等式

可以将上式转化为

2）如果用户l∈R*，但是算法输出用户l被接受，所以 w＞αp≥p，由条件（6），可将上面式lll（12）整理后可得

故，当 Aα满足不等式（6）时，在线算法 Aα的竞争比为。

当用户提交的任务数量都为1时，Bartal等［1］已证明不存在竞争比小于1.618的在线算法，所以，算法Aα为最优在线算法。证毕。

4 结语

本文提出一个带惩罚费用的多重任务排序问题，针对离线问题，设计了一个2-近似算法和一个FPTAS。对于在线问题，当机器数为2时，设计了一个竞争比为1.618的最优在线算法。

未来值得研究的问题有：利用Ou等［3］的算法思想设计MTSR问题的一个(1.5+ε)-的近似算法；设计MTSR问题的一个运行时间更低的FPTAS的；利用文献［22］中的算法思想设计一个用户数为固定常数时MTSR问题的一个最优算法。