A linear programming and constraint propagation-based lower bound for the RCPSP

摘要

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.