Conference Agenda

The project scheduling problem without resource constraints arises as subproblem in lower-bound computations such as lagrangian relaxation and column generation for resource-constrained project scheduling problems. Due to this relevance the structure of time-indexed integer programming formulations has been studied extensively for the classical single-mode case. However, for more general multi-mode problems such results are missing. This work contributes to closing this gap by generalizing the following two results to the multi-mode setting: The multi-mode project scheduling problem (i) possesses the integrality property and (ii) is solvable in polynomial time. We prove these results by a transformation into a stable set problem in a perfect graph.

We study the Resource-Constrained Project Scheduling Problem (RCPSP) which has remained one of the most computationally challenging scheduling problems to solve in practice over the last decades. A powerful state-of-the-art method to address this problem is lazy clause generation in combination with energetic propagators to quickly prune variable assignments in which a certain amount of jobs cannot be scheduled within a given time interval. Most energetic approaches from the literature however work only on one resource at a time while the RCPSP considers multiple resources simultaneously. In this talk, we will present an approach to compute additional stronger resources that originate from a dual LP formulation that incorporates the multi-dimensional nature of the resource constraints. We include such “redundant” resources into the energetic propagators to generate stronger lazy constraints. We implemented this method into our constraint programming solver LazyCP and will present insightful results on the RCPSP instances of the classical PSPLIB.

A single-item or small-series production environment can be represented as a project consisting of a set of precedence-related activities that require time and resources to be performed. The resources represent, for example, production personnel. We present a mixed binary linear program for minimizing the makespan subject to workload balancing constraints.