Indexed by:期刊论文

Date of Publication:2016-09-15

Journal:计算机科学

Included Journals:PKU、ISTIC、CSCD

Volume:43

Issue:9

Page Number:18-22

ISSN No.:1002-137X

Key Words:Flow-shop问题;空载返程运输;调度;复杂性

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