期刊文献+

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

Research for algorithm on the scheduling problem of three parallel machines with two GoS levels
下载PDF
导出
摘要 研究了带两个服务等级的平行机排序问题,其中等级为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.
作者 吴兆蕊 陈智斌 王扬 WU Zhao-rui;CHEN Zhi-bin;WANG Yang(Faculty of Science,Kunming University of Science and Technology,Kunming 650500,China)
出处 《陕西理工大学学报(自然科学版)》 2023年第1期67-72,共6页 Journal of Shaanxi University of Technology:Natural Science Edition
基金 国家自然科学基金项目(11761042)。
关键词 排序问题 服务等级 多项式时间算法 近似算法 scheduling problem grade of service polynomial-time algorithm approximate algorithm
  • 相关文献

参考文献2

二级参考文献5

  • 1范静,杨启帆.机器带准备时间的三台平行机排序问题的线性时间算法[J].浙江大学学报(理学版),2005,32(3):258-263. 被引量:12
  • 2HWANG H,CHANG S,LEE K.Parallel machine scheduling under a grade of service provision[J].Computers & Operations Research,2004,31:2055-2061.
  • 3GAREY M R,JOHNSON D S.Computers and Intractobility:A Guide to the Theory of NP-Completeness[M].New York:Freeman,1979.
  • 4COFFMAN E G,GAREY M R,JOHNSON D S.Anapplication of bin-packing to multi-processor scheduling[J].SIAM J on Comput,1978,7:1-17.
  • 5YUE M.On the exact upper bound for the Multifit processor scheduling algorithm[J].Annals of Oper Res,1990,24; 233-260.

共引文献6

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部