Horizontally Elastic Not-First/Not-Last Filtering Algorithm for Cumulative Resource Constraint

摘要

Fast and powerful propagators are the main key to the success of constraint programming on scheduling problems. It is, for example, the case with the CUMULATIVE constraint, which is used to model tasks sharing a resource of discrete capacity. In this paper, we propose a new not-firstot-last rule, which we call the horizontally elastic not-firstot-last, based on strong relaxation of the earliest completion time of a set of tasks. This computation is obtained when scheduling the tasks in a horizontally elastic way. We prove that the new rule is sound and is able to perform additional adjustments missed by the classic not-firstot-last rule. We use the new data structure called Profile to propose a O(n~3) filtering algorithm for a relaxed variant of the new rule where n is the number of tasks sharing the resource. We prove that the proposed algorithm still dominates the classic not-firstot-last algorithm. Experimental results on highly cumulative instances of resource constrained project scheduling problems (RCPSP) show that using this new algorithm can substantially improve the solving process of instances with an occasional and marginal increase of running time.