点击次数：

论文类型：期刊论文

发表时间：2016-01-01

发表刊物：INFORMATION PROCESSING LETTERS

收录刊物：SCIE

卷号：116

期号：1

页面范围：65-69

ISSN号：0020-0190

关键字：Analysis of algorithms; Flow shop; NP-hardness; Optimization

摘要：In this paper, we study a flow shop scheduling problem with an interstage transporter, in which there are a set of n jobs, two machines A and B, and one transporter located at machine A initially. Each job has to be processed on machine A first, then transported by a vehicle to machine B, finally processed on machine B. The interstage transporter can carry at most two jobs between the machines at a time. When the transporter carries items from machine A to machine B, it will take time tau; when it is back from machine B to machine A, it will take zero time. And there is an unlimited buffer on each machine to store jobs that will be processed. The objective is to minimize the completion time on machine B. The complexity of the problem is open in journal of Scheduling 2001 [5]. We prove the problem is NP-hard in the strong sense by 4-partition problem. (C) 2015 Elsevier B.V. All rights reserved.