混合环上带惩罚费用的负载平衡问题  

A mixed ring loading problem with penalty cost

作　　者：关莉 冯彦雪 GUAN Li;FENG Yan-xue(School of Mathematics and Statistics,Yunnan University,Kunming 650500,China)

机构地区：[1]云南大学数学与统计学院

出　　处：《计算机工程与科学》2019年第11期1949-1953,共5页Computer Engineering & Science

基　　金：国家自然科学基金(11761078,11861075);云南省教育厅科学研究基金(2017ZZX235);云南省高校计算理论与应用科技创新团队建设项目(云教高[2018]134号);云南省科技厅-云南大学联合基金重点项目(2018FY001(-014))

摘　　要：在过去的20多年里,环负载平衡问题得到了广泛的研究。带惩罚费用的环负载平衡问题是环负载平衡问题的推广形式,在无向环和有向环上有一些研究结果。提出了带惩罚费用的混合环负载平衡问题,对于给定的混合环C和点对集,每1个点对r j都有1个流量d j和1个惩罚费用p j,当点对r j被接收时,其流量可以沿环上的顺时针路和逆时针路进行运输,点对r j也可以被拒绝,此时将产生惩罚费用p j,目标是使得环C上连接边的最大负载和惩罚费用之和达到最小。在流量可分的情况下,利用线性规划取整技巧,给出了1个2-近似算法,进一步地,利用随机取整技巧,得到1个更好的近似算法,近似比为1.58。类似地,在流量不可分的情况下,给出了1个3-近似算法和1个(1.58+ε)-近似算法,其中ε>0是一个固定的常数。In the past more than 20 years,the ring loading problem has been studied widely.The ring loading problem with penalty cost is the generalized form of the ring loading problem.There are some research results on undirected rings and directed rings.This paper proposes a mixed ring loading problem with penalty cost.Given a mixed ring C and a set of requests,each request r j has a demand d j and a penalty p j.When the request r j is accepted,its traffic can be transmitted along the ring clockwise and counter clockwise.When the request r j is rejected,the penalty p j is generated to minimize the sum of the maximum load among all links on the ring and the total penalty cost of the rejected requests.When the demand can be split,a 2-approximation algorithm is given by using the LP-rounding technique.Further,a 1.58-approximation algorithm is obtained by using the random rounding technique.Similarly,when the demand cannot be split,a 3-approximation algorithm and a(1.58+ε)-approximation algorithm are given,whereε>0 is a constant.

关 键 词：近似算法 混合环负载 惩罚费用 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]