zbMATH — the first resource for mathematics

Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. (English) Zbl 0941.90030
Summary: In recent years, constraint satisfaction techniques have been successfully applied to “disjunctive” scheduling problems, i.e., scheduling problems where each resource can execute at most one activity at a time. Less significant and less generally applicable results have been obtained in the area of “cumulative” scheduling. Multiple constraint propagation algorithms have been developed for cumulative resources but they tend to be less uniformly effective than their disjunctive counterparts. Different problems in the cumulative scheduling class seem to have different characteristics that make them either easy or hard to solve with a given technique. The aim of this paper is to investigate one particular dimension along which problems differ. Within the cumulative scheduling class, we distinguish between “highly disjunctive” and “highly cumulative” problems: a problem is highly disjunctive when many pairs of activities cannot execute in parallel, e.g., because many activities require more than half of the capacity of a resource; on the contrary, a problem is highly cumulative if many activities can effectively execute in parallel. New constraint propagation and problem decomposition techniques are introduced with this distinction in mind. This includes an \(O(n^2)\) “edge-finding” algorithm for cumulative resources where \(n\) is the number of activities requiring the same resource) and a problem decomposition scheme which applies well to highly disjunctive project scheduling problems. Experimental results confirm that the impact of these techniques varies from highly disjunctive to highly cumulative problems. In the end, we also propose a rufined version of the “edge-finding” algorithm for cumulative resources which, despite its worst case complexity in \(O(n^3)\), performs very well on highly cumulative instances.

90B35 Deterministic scheduling theory in operations research
BL data set; CLAIRE
Full Text: DOI