direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 689-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Scheduling with AND/OR precedence constraints
A 2-page abstract appeared in Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00), 235-236.
not available
not available
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.
Download as [PDF] [ps.gz] [ps]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe