带等时空载返程运输的双机Flow shop调度问题复杂性

摘要：

流水作业(Flow shop)问题是调度算法研究中经典问题模型之一,有两台处理机和一台运输机且运输机每次只运输一个工件的流水作业调度问题模型在现实中有着广泛的应用.同时考虑运输机去程(从机器M1到M2)与返程(从机器M2到M1)时间,在假定运输机去程运输时间及远程空载时间相等的情况下,通过把一个强NP-complete问题——3-PARTITION问题归约成一个研究问题的实例,来证明对这个问题求解是强NP-hard的.

关键词：Flow-shop问题、空载返程运输、调度、复杂性

所属期刊栏目：43

分类号：TP3-05(计算技术、计算机技术)

资助基金：国家自然科学在线背包问题的相关模型和算法分析11101065

在线出版日期：2016-10-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：18-22