Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | 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
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