direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 693-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

On the Representation of Resource Constraints in Project Scheduling
not available
Project scheduling, resource constraints, forbidden sets, threshold hypergraphs, threshold dimension, minmal cover inequalities
In project scheduling, resource constraints are usually defined via resource consumption and -availability. Many algorithmic approaches, however, are based on the concept of minimal forbidden sets to represent the resource constraints. Jobs of a forbidden set can be scheduled simultaneously with respect to the precedence constraints, however, they consume more resources than available. Forbidden sets are usually not given explicitly, and by definition even the number of inclusion-minimal forbidden sets may be exponential in the number of jobs. In this paper, we propose a simple branch-and-bound type algorithm to efficiently compute and represent all minimal forbidden sets for a given instance. We evaluate the algorithm on well established test sets of the project scheduling problem library PSPLIB. In addition, we exhibit intimite relations between the different representations of resource constraints and threshold hypergraphs.
Download as [PDF] [ps]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe