3台平行机上带有2个服务等级的离线负载均衡  

Offline Load Balancing With Two Service Levels on Three Parallel Machines

作　　者：贾珊珊 嵇雯蕙 陈智斌[1] JIA Shan-shan;JI Wen-hui;CHEN Zhi-bin(College of Science,Kunming University of Science and Technology,Kunming 650500,China)

机构地区：[1]昆明理工大学理学院,云南昆明650500

出　　处：《软件导刊》2022年第2期97-100,共4页Software Guide

基　　金：国家自然科学基金项目(11761042)。

摘　　要：排序问题是一类重要的组合最优化问题,在生产计划、计算机控制等领域有着广泛应用,一直是理论界研究热点。对带服务等级的3台平行机排序问题进行研究,每台机器和每个工件都有等级标号,每个工件只能被某台服务等级不高于该工件等级的机器加工,目标是最小化最大机器的完工时间。运用新的算法思想解决离线状态等级约束下的3台机器负载均衡问题。对等级约束为1、2、2的3台平行机给出一个43-近似算法;对于等级约束为1、1、2的3台平行机给出一个2-近似算法。Scheduling problem is an important combinatorial optimization problem,which is widely used in production planning,computer control and other fields. Research on the scheduling problem of three parallel machines with service level,each machine and each job has a level label,each job can only be processed by a machine whose service level is not higher than that of the job. The goal is to minimize the maximum machine completion time. Use a new algorithm to solve the load balancing problem of three machines under the offline state level constraint. A 4/3 approximation algorithm is proposed for three parallel machines with level constraints of 1,2 and 2;For three parallel machines with level constraints of 1,1 and 2,a 2 approximation algorithm is proposed.

关 键 词：等级约束 排序问题 近似比 目标函数 

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