摘要
研究带单服务器的自由作业排序问题,证明在只有两台机器且加工时间相同的情况下该问题是强NP-困难的,引入了求解该问题的启发式算法,证明该算法的紧界为5/4.在具有m台机器的情况下,给出相应的启发式算法,其紧界为2-3/(m+2).
The problem of two-machine open-shop scheduling with a single server and equal processing times is studied in this paper.This problem is proved NP-hard in the strong sense,a heuristic algorithm for this problem with worst-case ratio bound 5/4 is introduced.For m machines open-shop scheduling problem,a heuristic algorithm with worst-case ratio bound 2-3/(m+2)is presented.
作者
时凌
张琼
时义梅
魏代俊
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)
出处
《数学的实践与认识》
北大核心
2019年第9期198-203,共6页
Mathematics in Practice and Theory
基金
国家自然科学基金(61763009)
广州工商学院2018院级科研课题立项项目(KA201831)
关键词
自由作业排序问题
复杂性
单服务器
启发式算法
open-shop scheduling problem
complexity
single server
heuristic algorithm
