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

作     者：吴兆蕊 陈智斌 王扬 WU Zhao-rui;CHEN Zhi-bin;WANG Yang

作者机构：昆明理工大学理学院云南昆明650500 

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

出 版 物：《陕西理工大学学报（自然科学版）》 (Journal of Shaanxi University of Technology:Natural Science Edition)

年 卷 期：2023年第39卷第1期

页      码：67-72页

摘      要：研究了带两个服务等级的平行机排序问题,其中等级为1的机器有2台,等级为2的机器只有1台。每个工件和每台机器等级均为1或2,只有当工件等级不低于机器等级时,才能将工件安排到机器上加工,目标为极小化最大完工时间。针对该NP-难问题,设计了一个近似比严格小于3/2的新算法,改进了已知结果。同时,在加工时间满足2的幂次方条件下,设计了一个新算法,并证明了该算法总能得到一个最优分配。

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 08[工学] 070105[070105] 0701[理学-数学类] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1673-2944.2023.01.008

馆 藏 号：203118263...