具有部分顶点覆盖约束的同型机排序问题  

Identical parallel machine scheduling problem with partial vertex cover constraint

作　　者：关莉 刘烘利 GUAN Li;LIU Hongli(School of Mathematics and Statistics,Yunnan University,Kunming 650500,China)

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

出　　处：《华中科技大学学报（自然科学版）》2024年第11期72-77,共6页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(12361066)。

摘　　要：针对具有部分顶点覆盖约束的同型机排序问题进行研究.给定赋权无向图,将无向图的部分顶点覆盖中的顶点视作工件放到m台同型机上进行加工,未被覆盖的边会产生一个惩罚费用,目标是机器的最大完工时间与所有未被覆盖的边的惩罚费用之和达到最小.基于局部比值法和列表排序(LS)算法,当机器数m不固定时,设计了一个近似比为(3+ε)的多项式时间算法,其中ε>0为任意小的固定常数;当机器数m固定时,设计了一个近似比为2的多项式时间算法.研究结果表明:基于局部比值法和LS算法,当机器数m不固定时,存在一个近似比为(3+ε)的多项式时间算法;当机器数m固定时,存在一个近似比为2的多项式时间算法.The identical parallel machine scheduling problem with partial vertex cover constraint was studied.Given a weighted undirected graph,the vertices in the partial vertex cover of the undirected graph were regarded as jobs and scheduled on m identical parallel machines,and uncovered edges would incur a penalty fee,and the goal was to minimize the sum of the maximum completion time of the machines and the penalty cost of all uncovered edges.Based on the local ratio method and the list scheduling(LS)algorithm,when m was not fixed,a polynomial time algorithm with an approximation ratio of(3+ε)was designed,whereε>0 was any small fixed constant.When m was fixed,a polynomial time algorithm with an approximation ratio of 2 was designed.Research results show that based on the local ratio method and the LS algorithm,whenmis not fixed,there is a polynomial time algorithm with an approximate ratio of(3+ε),and whenmis fixed,there is a polynomial time algorithm with an approximate ratio of 2.

关 键 词：部分顶点覆盖 同型机排序问题 近似算法 局部比值法 列表排序(LS)算法 

分 类 号：O224[理学—运筹学与控制论]