Activity Insertion Problem in a RCPSP with Minimum and Maximum Time Lags

Christian Artigues (1) , Cyril Briand (1)

1 LAAS - Laboratoire d'analyse et d'architecture des systèmes

This chapter considers the RCPSP with minimum and maximum time lags. We focus on the problem of activity insertion in a schedule represented by a resource flow, which can occur in reactive scheduling (see next chapter) or as a component of a local search method. We show the problem is NP-hard and propose a polynomial algorithm when only minimum time lags are considered.

Mots clés: Resource-constrained project scheduling; time lags; activity insertion; complexity

Domaines: Recherche opérationnelle [math.OC]

Christian Artigues, Cyril Briand. Activity Insertion Problem in a RCPSP with Minimum and Maximum Time Lags. Christian Artigues, Sophie Demassey and Emmanuel Néron. Resource Constrained Project Scheduling. Models, Algorithms, Extensions and Applications., ISTE-WILEY, pp.171-190, 2008, Control Systems, Robotics and Manufacturing Series. ⟨hal-00271648⟩