带单服务器的流水作业排序问题的复杂性

作者：时凌; 张琼; 龙彩燕

来源：延边大学学报(自然科学版), 2022, 48(04): 332-335.

DOI：10.16379/j.cnki.issn.1004-4353.2022.04.006

• 流水作业排序问题
• 总完工时间
• 单服务器
• 最坏性能比

研究了一个带单服务器且加工时间相等的两机流水作业排序问题，其目标函数是使总完工时间达到最小.研究表明，该流水作业排序问题是强NP-困难的.针对该流水作业排序问题构造了一种新的加工顺序，并证明该加工顺序的紧界为7/6.

• 单位
  教育学院; 广州工商学院