Improved analysis of an algorithm for the coupled task problem with UET jobs

被引：7

作者：

Bekesi, Jozsef ^{[2
]}

Galambos, Gabor ^{[2
]}

Oswald, Marcus ^{[1
]}

Reinelt, Gerhard ^{[1
]}

机构：

[1] Univ Heidelberg, Inst Informat, D-6900 Heidelberg, Germany

[2] Univ Szeged, Dept Informat, Fac Juhasz Gyula, Teachers Training Coll, Szeged, Hungary

来源：

OPERATIONS RESEARCH LETTERS | 2009年 / 37卷 / 02期

关键词：

Scheduling; Coupled tasks; Approximation algorithms; DELAYS;

D O I：

10.1016/j.orl.2008.11.002

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The coupled task problem is to schedule n jobs, each one consisting of two subtasks with exact delay times between them, on a single machine. We derive a new lower bound for the problem variant with unit execution times and correct a previously published analysis. (C) 2009 Published by Elsevier B.V.

引用

页码：93 / 96

页数：4

共 6 条

[1] Approximation algorithms for UET scheduling problems with exact delays [J].

Ageev, Alexander A. ;

Baburin, Alexei E. .

OPERATIONS RESEARCH LETTERS, 2007, 35 (04) :533-540

[2] An exact algorithm for scheduling identical coupled tasks [J].

Ahr D. ;

Békési J. ;

Galambos G. ;

Oswald M. ;

Reinelt G. .

Mathematical Methods of Operations Research, 2004, 59 (02) :193-203

[3]

BEKESI J, 2007, INTEGER PROGRAMMING

[4] On the complexity of coupled-task scheduling [J].

Orman, AJ ;

Potts, CN .

DISCRETE APPLIED MATHEMATICS, 1997, 72 (1-2) :141-154

[5]

SHAPIRO RD, 1980, NAV RES LOG, V20, P489

[6] Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard [J].

Yu, WC ;

Hoogeveen, H ;

Lenstra, JK .

JOURNAL OF SCHEDULING, 2004, 7 (05) :333-348

← 1 →