A note on the precedence-con strained class sequencing problem

Correa JR; Fiorini, S; Stier-Moses, NE

Abstract

We give a short proof of a result of Tovey [Non-approximability of precedence-constrained sequencing to minimize setups, Discrete Appl. Math. 134:351-360, 2004] on the inapproximability of a scheduling problem known as precedence-constrained class sequencing. In addition, we present an approximation algorithm with performance guarantee (c + 1) / 2, where c is the number of colors. This improves upon Tovey's c-approximation. © 2006 Elsevier B.V. All rights reserved.

Más información

Título según WOS: A note on the precedence-con strained class sequencing problem
Título según SCOPUS: A note on the precedence-constrained class sequencing problem
Título de la Revista: DISCRETE APPLIED MATHEMATICS
Volumen: 155
Número: 3
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2007
Página de inicio: 257
Página final: 259
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0166218X06002976
DOI:

10.1016/j.dam.2006.03.038

Notas: ISI, SCOPUS