摘要:
在过去的20多年里,环负载平衡问题得到了广泛的研究。带惩罚费用的环负载平衡问题是环负载平衡问题的推广形式,在无向环和有向环上有一些研究结果。
提出了带惩罚费用的混合环负载平衡问题,对于给定的混合环C和点对集,每1个点对rj都有1个流量dj和1个惩罚费用pj,当点对rj被接收时,其流量可以沿环上的顺时针路和逆时针路进行运输,点对rj也可以被拒绝,此时将产生惩罚费用pj,目标是使得环C上连接边的最大负载和惩罚费用之和达到最小。在流量可分的情况下,利用线性规划取整技巧,给出了1个2-近似算法,进一步地,利用随机取整技巧,得到1个更好的近似算法,近似比为1.58。类似地,在流量不可分的情况下,给出了1个3-近似算法和1个(1.58+ε)-近似算法,其中ε>0是一个固定的常数。
关莉,冯彦雪. 混合环上带惩罚费用的负载平衡问题[J]. 计算机工程与科学.
GUAN Li,FENG Yan-xue. A mixed ring loading problem with penalty cost[J]. Computer Engineering & Science.