A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays

P. Schuurman

doi:10.1016/S0167-6377(98)00012-1

A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays

P. Schuurman

Combinatorische Optimalisering - EIDMA

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

2 Citaten (Scopus)

Samenvatting

We investigate a single-machine scheduling problem with precedence delays that have a simple structure: the corresponding tree has k leaves and only k+2 nodes. The objective is to minimize the makespan. We present a pseudo-polynomial algorithm for this problem, and we also give a fully polynomial approximation scheme.

Originele taal-2	Engels
Pagina's (van-tot)	9-11
Aantal pagina's	3
Tijdschrift	Operations Research Letters
Volume	23
Nummer van het tijdschrift	1-2
DOI's	https://doi.org/10.1016/S0167-6377(98)00012-1
Status	Gepubliceerd - 1998

Toegang tot document

10.1016/S0167-6377(98)00012-1

Vingerafdruk Duik in de onderzoeksthema's van 'A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays'. Samen vormen ze een unieke vingerafdruk.

Citeer dit

@article{8f3d321a8e7d47b3b69f8dd00f66eedd,

title = "A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays",

abstract = "We investigate a single-machine scheduling problem with precedence delays that have a simple structure: the corresponding tree has k leaves and only k+2 nodes. The objective is to minimize the makespan. We present a pseudo-polynomial algorithm for this problem, and we also give a fully polynomial approximation scheme.",

author = "P. Schuurman",

year = "1998",

doi = "10.1016/S0167-6377(98)00012-1",

language = "English",

volume = "23",

pages = "9--11",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1-2",

}

TY - JOUR

T1 - A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays

AU - Schuurman, P.

PY - 1998

Y1 - 1998

N2 - We investigate a single-machine scheduling problem with precedence delays that have a simple structure: the corresponding tree has k leaves and only k+2 nodes. The objective is to minimize the makespan. We present a pseudo-polynomial algorithm for this problem, and we also give a fully polynomial approximation scheme.

AB - We investigate a single-machine scheduling problem with precedence delays that have a simple structure: the corresponding tree has k leaves and only k+2 nodes. The objective is to minimize the makespan. We present a pseudo-polynomial algorithm for this problem, and we also give a fully polynomial approximation scheme.

U2 - 10.1016/S0167-6377(98)00012-1

DO - 10.1016/S0167-6377(98)00012-1

M3 - Article

VL - 23

SP - 9

EP - 11

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 1-2

ER -