The impact of core precedences in a cyclic RCPSP with precedence delays

In this paper, we introduce a new kind of constraint, called a core precedence constraint, in a cyclic resource-constrained project scheduling problem (RCPSP) with precedence delays. We show, by an example, which kind of industrial constraints might be modeled by such core precedences in a periodic production setting. We then establish that these constraints can be quite easily added to an integer linear programming formulation of the cyclic RCPSP. Although core precedences seem to be very similar to classical precedence, they can induce infeasibility even without resource constraints. Moreover, we show that the feasibility checking problem is NP-complete in the strong sense, even assuming unit processing times and no resource constraints.