A linear programming and constraint propagation-based lower bound for the resource-constrained project scheduling problem

A linear programming and constraint propagation-based lower bound for the resource-constrained project scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20011790
Country: Netherlands
Volume: 127
Issue: 2
Start Page Number: 355
End Page Number: 362
Publication Date: Dec 2000
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: linear
Abstract:

A new destructive lower bound for the resource-constrained project scheduling problem (RCPSP) is presented. Given are n activities which have to be processed without preemptions. During the processing period of an activity constant amounts of renewable resources are needed where the available capacity of each resource type is limited. Furthermore, finish–start precedence relations between the activities are given. The objective is to determine a schedule with minimal makespan. The lower bound calculations are based on two methods for proving infeasibility of a given threshold value T for the makespan. The first uses constraint propagation techniques, while the second is based on a linear programming formulation. A column generation procedure is presented for the linear programming formulation and computational results are reported for an algorithm combining both concepts.

Reviews

Required fields are marked *. Your email address will not be published.