Lower bounds for resource-constrained project scheduling problems. (Q1399575)

The article treats a very general formulated scheduling problem, the so-called ``multi-mode resource-constrained project scheduling problem with minimal and maximal time-lags''. It handles with a combination of renewable (persons, machines) and non-renewable resources (money, energy), each activity can be processed in different modes (for each mode a duration is given resulting in an activity/duration matrix for each activity in each mode). Between the activities there are also minimal and maximal time-lags restricting the start-times of the activities dependent from the start times of other activities. The objective is to find a solution with minimal makespan fulfilling all restrictions concerning starting times and resources. The problem is known as an NP-hard problem. A small example illustrates all the constraints and input data. The main method (destructive) for generating lower bounds for the makespan is presented. There are two different approaches generating these bounds, namely proving infeasibility for a given threshold and a linear programming formulation of the problem. At the end numerical results for problems up to 100 activities are shown.