BL data set
Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems. 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(n2) “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 refined version of the “edge-finding” algorithm for cumulative resources which, despite its worst case complexity in O(n3) , performs very well on highly cumulative instances.
Keywords for this software
References in zbMATH (referenced in 21 articles )
Showing results 1 to 20 of 21.
Sorted by year (- Moukrim, Aziz; Quilliot, Alain; Toussaint, Hélène: An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal interval order enumeration (2015)
- Kameugne, Roger; Fotso, Laure Pauline; Scott, Joseph; Ngo-Kateu, Youcheu: A quadratic edge-finding filtering algorithm for cumulative resource constraints (2014)
- Heinz, Stefan; Schulz, Jens; Beck, J.Christopher: Using dual presolving reductions to reformulate cumulative constraints (2013)
- Kameugne, Roger; Fotso, Laure Pauline: A cumulative not-first/not-last filtering algorithm in $O(n^2 \log(n))$ (2013)
- Koné, Oumar; Artigues, Christian; Lopez, Pierre; Mongeau, Marcel: Event-based MILP models for resource-constrained project scheduling problems (2011)
- Schutt, Andreas; Feydy, Thibaut; Stuckey, Peter J.; Wallace, Mark G.: Explaining the cumulative propagator (2011)
- Lombardi, Michele; Milano, Michela: Allocation and scheduling of conditional task graphs (2010)
- Liess, Olivier; Michelon, Philippe: A constraint programming approach for the resource-constrained project scheduling problem (2008)
- Beldiceanu, Nicolas; Carlsson, Mats; Demassey, Sophie; Petit, Thierry: Global constraint catalogue: past, present and future (2007)
- Pedersen, C.R.; Rasmussen, R.V.; Andersen, K.A.: Solving a large-scale precedence constrained scheduling problem with elastic jobs using tabu search (2007)
- Simonis, Helmut: Models for global constraint applications (2007)
- de Givry, Simon; Jeannin, Laurent: A unified framework for partial and hybrid search methods in constraint programming (2006)
- Demassey, Sophie; Artigues, Christian; Michelon, Philippe: Constraint-propagation-based cutting planes: an application to the resource-constrained project scheduling problem (2005)
- Baptiste, Philippe; Demassey, Sophie: Tight LP bounds for resource constrained project scheduling (2004)
- Kovács, András; Váncza, József: Completable partial solutions in constraint programming and constraint-based scheduling (2004)
- Palpant, Mireille; Artigues, Christian; Michelon, Philippe: LSSPER: Solving the resource-constrained project scheduling problem with large neighbourhood search (2004)
- Artigues, Christian; Michelon, Philippe; Reusser, Stéphane: Insertion techniques for static and dynamic resource-constrained project scheduling. (2003)
- Carlier, J.; Néron, E.: On linear lower bounds for the resource constrained project scheduling problem. (2003)
- Baptiste, Philippe; LePape, Claude: Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems (2000)
- Carlier, Jacques; Néron, Emmanuel: A new LP-based lower bound for the cumulative scheduling problem (2000)