BL data set swMATH ID: 8330 Software Authors: Philippe Baptiste, Claude Le Pape Description: 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. Homepage: http://rd.springer.com/article/10.1023%2FA%3A1009822502231 Related Software: PSPLIB; CHIP; CLAIRE; MiniSat; Gecode; Zinc; ILOG SCHEDULE; LSSPER; JOBSHOP; Oz Explorer; OscaR; Oz; TSPLIB; MIPLIB; Essence; MiniZinc; SCIP; Chaff; JaCoP; HIBISCUS Cited in: 26 Publications all top 5 Cited by 58 Authors 4 Artigues, Christian 4 Michelon, Philippe Yves Paul 3 Demassey, Sophie 2 Baptiste, Philippe 2 Carlier, Jacques G. 2 Fotso, Laure Pauline 2 Kameugne, Roger 2 Lombardi, Michele 2 Lopez, Pierre 2 Néron, Emmanuel 1 Andersen, Kim Allan 1 Arkhipov, Dmitriĭ Igorevich 1 Battaïa, Olga 1 Beck, J. Christopher 1 Beldiceanu, Nicolas 1 Carlsson, Mats 1 Crawford, Broderick 1 de Azevedo, Guilherme Henrique Ismael 1 de Givry, Simon 1 Fahimi, Hamed 1 Feydy, Thibaut 1 Heinz, Stefan 1 Jeannin, Laurent 1 Johnson, Franklin 1 Koné, Oumar 1 Kovács, András 1 Lazarev, Aleksander Alekseevich 1 Le Pape, Claude 1 Liess, Olivier 1 Milano, Michela 1 Mongeau, Marcel 1 Moukrim, Aziz 1 Ngo-Kateu, Youcheu 1 Niklander, Stefanie 1 Olguín, Eduardo 1 Olivares, Rodrigo 1 Ouellet, Yanick 1 Palpant, Mireille 1 Paredes, Fernando 1 Pedersen, Christian Roed 1 Pessoa, Artur Alves 1 Petit, Thierry 1 Quilliot, Alain 1 Quimper, Claude-Guy 1 Rasmussen, Rasmus V. 1 Reusser, Stéphane 1 Schaus, Pierre 1 Schulz, Jens 1 Schütt, Andreas 1 Simonis, Helmut 1 Soto, Ricardo Lorenzo 1 Stuckey, Peter James 1 Subramanian, Anand Prabhu 1 Torres, Philippe 1 Toussaint, Hélène 1 Van Cauwelaert, Sascha 1 Váncza, József 1 Wallace, Mark G. all top 5 Cited in 9 Serials 8 Constraints 7 European Journal of Operational Research 3 Computers & Operations Research 2 Annals of Operations Research 1 Artificial Intelligence 1 Indian Journal of Pure & Applied Mathematics 1 INFORMS Journal on Computing 1 OR Spectrum 1 Natural Computing Cited in 2 Fields 24 Operations research, mathematical programming (90-XX) 8 Computer science (68-XX) Citations by Year