Complete MCS-Based Search: Application to Resource Constrained Project
Scheduling

Exposé de Philippe Laborie (Ilog)

Abstract: I will describe a simple complete search for cumulative scheduling
based on the detection and resolution of minimal critical sets (MCS). The
heuristic for selecting MCSs relies on an estimation of the related
reduction of the search space. An extension of the search procedure using
self-adapting shaving is proposed. The approach was implemented on top of
classical constraint propagation algorithms and tested on resource
constrained project scheduling problems (RCPSP). We were able to close more
than 15% of the previously open problems of the PSPLIB [Kolisch and
Sprecher, 1996] and improve more than 31% of the best known lower bounds on
those heavily studied problems. Other new results on open-shop and
cumulative job-shop scheduling are reported.