direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 702-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Branch-and-Bound Algorithms for Stochastic Resource-Constrained Project Scheduling
This is a journal version which extends the Report 613/1998.
not available
not available
We study branch-and-bound algorithms for resource-constrained project scheduling where processing times of jobs are random. The objective is to find a so-called scheduling policy which minimizes the project makespan in expectation. The proposed procedures are based upon four classes of scheduling policies which differ considerably with respect to their computational tractability as well as with respect to the optimum costs that can be achieved within the respective class. The purpose of the paper is twofold. First, we establish results on the trade-off between computational efficiency and solution quality for each of the considered classes of policies and evaluate their practical applicability for scheduling stochastic resource-constrained projects. Second, we develop and apply various ingredients such as dominance rules and lower bounds that turn out to be useful within the computation. In order to comprehensively study these issues we have implemented five different branch-and-bound algorithms and explore their computational behavior on 1440 test instances.
Download as [PDF] [ps]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe