A new O(n2 log n) not-first/not-last pruning algorithm for cumulative resource constraints

The recent success of the lazy clause generator (a hybrid of a FD and a SAT solver) on resource-constrained project scheduling problems (RCPSP) shows the importance of the global cumulative constraint to tackle these problems. A key for an efficient cumulative propagator is a fast and correct pruning of time-bounds. The not-first/not-last rule (which is not subsumed by other rules) detects activities that cannot be run at first/last regarding to an activity set and prunes their time bounds. This paper presents a new sound not-first/not-last pruning algorithm which runs in O(n2 log n), where n is the number of activities. It may not find the best adjustments in the first run, but after at most n iterations. This approach of iteration fits the setup of constraint propagation quite naturally offering the opportunity that a fixed point is reached more efficiently. Moreover, it uses a novel approach of generation of some "artificial" activities in the context of triggering p runing rules correctly. In experiments on RCPSP amongst others from the well-established PSPLib we show that the algorithm runs negligible more often than a complete algorithm while taking its advantage from the lower - to the best of our knowledge the lowest known - runtime complexity.