带单服务器的自由作业排序问题的启发式算法
A Heuristic for Open-shop Scheduling Problems with a Single Server作者机构:广州工商学院基础教学部广东广州510850 湖北民族大学理学院湖北恩施445000
出 版 物:《数学的实践与认识》 (Mathematics in Practice and Theory)
年 卷 期:2019年第49卷第9期
页 面:198-203页
学科分类:12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 081104[工学-模式识别与智能系统] 08[工学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:国家自然科学基金(61763009) 广州工商学院2018院级科研课题立项项目(KA201831)
摘 要:研究带单服务器的自由作业排序问题,证明在只有两台机器且加工时间相同的情况下该问题是强NP-困难的,引入了求解该问题的启发式算法,证明该算法的紧界为5/4.在具有m台机器的情况下,给出相应的启发式算法,其紧界为2-3/(m+2).