Permutation schedules for a two-machine flow shop with storage

被引：14

作者：

Fung, Joey ^{[1
]}

Zinder, Yakov ^{[1
]}

机构：

[1] Univ Technol Sydney, Sch Math & Phys Sci, POB 123, Broadway, NSW 2007, Australia

来源：

OPERATIONS RESEARCH LETTERS | 2016年 / 44卷 / 02期

关键词：

Flow shop; Buffer; Permutation schedule; Makespan;

D O I：

10.1016/j.orl.2015.12.012

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper considers a two-machine flow shop problem with a buffer, arising in various applications, and addresses a fundamental question of the existence of an optimal permutation schedule. The paper proves that the problem of recognising whether an instance has an optimal permutation schedule is NP-complete in the strong sense, and estimates the deviation from the optimal makespan as a result of the restriction to permutation schedules only. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：153 / 157

页数：5

共 8 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

[Anonymous], 2004, Handbook of Scheduling: Algorithms, Models, and Performance Analysis

[3]

Brucker P., 2007, Scheduling Algorithms, V3, DOI DOI 10.1007/978-3-540-69516-5

[4] Quantity-based buffer-constrained two-machine flowshop problem: active and passive prefetch models for multimedia applications [J].

Kononov, Alexander ;

Hong, Jen-Shin ;

Kononova, Polina ;

Lin, Feng-Cheng .

JOURNAL OF SCHEDULING, 2012, 15 (04) :487-497

[5]

Kononova PA., 2013, J APPL IND MATH, V7, P54, DOI [DOI 10.1134/S1990478913010067, 10.1134/S1990478913010067]

[6] A two-machine flowshop problem with processing time-dependent buffer constraints-An application in multimedia presentations [J].

Lin, Feng-Cheng ;

Hong, Jen-Shin ;

Lin, Bertrand M. T. .

COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (04) :1158-1175

[7]

Pinedo ML, 2012, SCHEDULING: THEORY, ALGORITHMS, AND SYSTEMS, FOURTH EDITION, P1, DOI 10.1007/978-1-4614-2361-4

[8] PERMUTATION VS NON-PERMUTATION FLOW-SHOP SCHEDULES [J].

POTTS, CN ;

SHMOYS, DB ;

WILLIAMSON, DP .

OPERATIONS RESEARCH LETTERS, 1991, 10 (05) :281-284

← 1 →