Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Moehring, Rolf H.
Skutella, Martin
Stork, Frederik

dblp
dblp
dblp

Not MPG Author(s):

Moehring, Rolf H.
Stork, Frederik

BibTeX cite key*:

MoehringSkutellaStork2004

Title

Title*:

Scheduling with AND/OR Precedence Constraints

Journal

Journal Title*:

SIAM Journal on Computing

Journal's URL:

http://www.siam.org/journals/sicomp/sicomp.htm

Download URL
for the article:

http://epubs.siam.org/sam-bin/dbq/article/37727

Language:

English

Publisher

Publisher's
Name:

SIAM

Publisher's URL:

http://www.siam.org/

Publisher's
Address:

Philadelphia, USA

ISSN:

0097-5397

Vol, No, pp, Date

Volume*:

33

Number:

2

Publishing Date:

February 2004

Pages*:

393-415

Number of
VG Pages:

30

Page Start:

393

Page End:

415

Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

In many scheduling applications it is required that the processing
of some job must be postponed until some other job, which can be
chosen from a pre-given set of alternatives, has been completed. The
traditional concept of precedence constraints fails to model such
restrictions. Therefore, the concept has been generalized to
so-called AND/OR precedence constraints which can cope with
this kind of requirement.

In the context of traditional precedence constraints, feasibility,
transitivity, as well as the computation of earliest start times for
jobs are fundamental, well-studied problems. The purpose of this
paper is to provide efficient algorithms for these tasks for the
more general and complex model of AND/OR precedence constraints. We
show that feasibility as well as many questions related to
transitivity can be solved by applying essentially the same
linear-time algorithm. In order to compute earliest start times we
propose two polynomial-time algorithms to cope with different
classes of time distances between jobs.

URL for the Abstract:


Categories,
Keywords:

project scheduling, AND/OR precedence constraints, earliest start schedule, mean payoff games

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

MPG Subsubunit:

Combinatorial Optimization Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{MoehringSkutellaStork2004,
AUTHOR = {Moehring, Rolf H. and Skutella, Martin and Stork, Frederik},
TITLE = {Scheduling with AND/OR Precedence Constraints},
JOURNAL = {SIAM Journal on Computing},
PUBLISHER = {SIAM},
YEAR = {2004},
NUMBER = {2},
VOLUME = {33},
PAGES = {393--415},
ADDRESS = {Philadelphia, USA},
MONTH = {February},
ISBN = {0097-5397},
}


Entry last modified by Anja Becker, 06/09/2005
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Martin Skutella
Created
02/27/2004 12:49:56 PM
Revisions
3.
2.
1.
0.
Editor(s)
Anja Becker
Christine Kiesel
Martin Skutella
Martin Skutella
Edit Dates
09.06.2005 09:19:07
30.05.2005 15:48:49
04.05.2004 16:13:04
27.02.2004 12:49:56