三台带两个服务等级的平行机排序问题算法研究  

Research for algorithm on the scheduling problem of three parallel machines with two GoS levels

作　　者：吴兆蕊 陈智斌[1] 王扬 WU Zhao-rui;CHEN Zhi-bin;WANG Yang(Faculty of Science,Kunming University of Science and Technology,Kunming 650500,China)

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

出　　处：《陕西理工大学学报（自然科学版）》2023年第1期67-72,共6页Journal of Shaanxi University of Technology:Natural Science Edition

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

摘　　要：研究了带两个服务等级的平行机排序问题,其中等级为1的机器有2台,等级为2的机器只有1台。每个工件和每台机器等级均为1或2,只有当工件等级不低于机器等级时,才能将工件安排到机器上加工,目标为极小化最大完工时间。针对该NP-难问题,设计了一个近似比严格小于3/2的新算法,改进了已知结果。同时,在加工时间满足2的幂次方条件下,设计了一个新算法,并证明了该算法总能得到一个最优分配。The problem of scheduling parallel machines with two grades of service(GoS) is investigated. Given are three machines and independent jobs, each job and machine assigned the GoS levels of 1 or 2. The processing rule is that the job is allowed to be processed on some particular machines only when the GoS level of the job is no less than that of the machine, the objective is to minimize the makespan. For this problem, a new algorithm with an approximation ratio strictly less than 3/2 is proposed, which is better than the previous algorithm. Moreover, a new algorithm is obtained for the problem of processing time satisfying a power of 2 condition for the scheduling problem with GoS levels, and it is shown that the algorithm always obtains an optimal assignment.

关 键 词：排序问题 服务等级 多项式时间算法 近似算法 

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