带单机器人的流水作业排序问题的复杂性

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

来源：内蒙古民族大学学报(自然科学版), 2021, 36(06): 461-464.

DOI：10.14045/j.cnki.15-1220.2021.06.001

• 流水作业排序问题
• 复杂性
• 单机器人

研究n个工件在2台机器上加工的流水作业排序问题,目标函数是使完工时间达到最小.当一个工件在一台机器上完工后到下一台机器上加工之前的时间间隔,称之为运输时间的时间间隔,所有运输均由单运输机来完成,机器人在同一时间只运输一个工件,证明对于这种特殊的排序问题仍然是强NP-困难的.

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