Complete MCS-based search: application to resource constrained project scheduling

Abstract

This paper describes 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.