文献类型：期刊文章

作　　者：时凌[1,2] 张琼[1] 时义梅[1] 魏代俊[2]

SHI Ling;ZHANH Qun;SHI Yi-mei;WEI Dai-jun(Basic Teaching Department,Guangzhou College of Technology and Business;School of Science,Hubei University for Nationalities)

机构地区：[1]广州工商学院基础教学部,广东广州510850 [2]湖北民族大学理学院,湖北恩施445000

出　　处：《数学的实践与认识》

基　　金：国家自然科学基金(61763009);广州工商学院2018院级科研课题立项项目(KA201831)

年　　份：2019

卷　　号：49

期　　号：9

起止页码：198-203

语　　种：中文

收录情况：BDHX、BDHX2017、MR、RCCSE、ZGKJHX、ZMATH、核心刊

摘　　要：研究带单服务器的自由作业排序问题,证明在只有两台机器且加工时间相同的情况下该问题是强NP-困难的,引入了求解该问题的启发式算法,证明该算法的紧界为5/4.在具有m台机器的情况下,给出相应的启发式算法,其紧界为2-3/(m+2).

关 键 词：自由作业排序问题  复杂性  单服务器  启发式算法

分 类 号：O223] TP18[数学类]