带单服务器的自由作业排序问题的启发式算法

作者：时凌; 张琼; 时义梅; 魏代俊

来源：数学的实践与认识, 2019, 49(09): 198-203.

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

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

• 单位
  广州工商学院; 湖北民族大学