An exact algorithm for scheduling identical coupled tasks

被引：27

作者：

Ahr D. ^{[1
]}

Békési J. ^{[2
]}

Galambos G. ^{[2
]}

Oswald M. ^{[1
]}

Reinelt G. ^{[1
]}

机构：

[1] Institute of Computer Science, University of Heidelberg, D-69120 Heidelberg

[2] Department of Informatics, Juhász Gyula Teacher's Training College, University of Szeged, H-6720 Szeged

来源：

Mathematical Methods of Operations Research | 2004年 / 59卷 / 02期

关键词：

Coupled Tasks; Dynamic Programming; Scheduling;

D O I：

10.1007/s001860300328

中图分类号：

学科分类号：

摘要：

The coupled task problem is to schedule n jobs on one machine where each job consists of two subtasks with required delay time between them. The objective is to minimize the makespan. This problem was analyzed in depth by Orman and Potts [3]. They investigated the complexity of different cases depending on the lengths a i and b i of the two subtasks and the delay time L i . [InlineMediaObject not available: see fulltext.][InlineMediaObject not available: see fulltext.]-hardness proofs or polynomial algorithms were given for all cases except for the one where a i =a, b i =b and L i =L. In this paper we present an exact algorithm for this problem with time complexity O(nr 2L ) where [InlineMediaObject not available: see fulltext.] holds. Therefore the algorithm is linear in the number of jobs for fixed L. © Springer-Verlag 2004.

引用

页码：193 / 203

页数：10

共 5 条

[1]

Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, pp. 287-326, (1979)

[2]

Karp R.M., A characterization of the minimum cycle mean in a digraph, Discrete Mathematics, 23, pp. 309-311, (1978)

[3]

Orman A.J., Potts C.N., On the complexity of coupled-task scheduling, Discrete Applied Mathematics, 72, pp. 141-154, (1997)

[4]

Rinnooy Kan A.H.G., Machine Scheduling Problems, (1976)

[5]

Shapiro R.D., Scheduling coupled tasks, Naval Research Logistics Quarterly, 20, pp. 489-498, (1980)

← 1 →