Soutenance de these de Mohamed SIALA le 13 Mai 2015
Forum 'Annonces' - Sujet créé le 2015-05-06 par Christian Artigues
DOCTORAT DE L'UNIVERSITE DE TOULOUSE
Délivré par l'INSA
École Doctorale : EDSYS
Unité de recherche : LAAS-CNRS équipe ROC
Spécialité : Programmation par Contraintes
Titre :
Search, propagation, and learning in sequencing and scheduling problems
de
Mohamed SIALA (Equipe--- ROC)
E-mail : mohamed.siala@laas.fr
Date : 13 Mai 2015 à 10h00
Lieu : LAAS-CNRS - Salle de Conférences
7 avenue du Colo! nel Roche
31077 TOULOUSE Cedex 4
Composition du jury :
Fahiem BACCHUS, Professeur, Université de Toronto
Christian BESSIERE, Directeur de recherche, LIRMM-CNRS
Christine SOLNON, Professeur , LIRIS-CNRS
Hadrien CAMBAZARD, Maître de Conférences, G-SCOP; Grenoble INP
George KATSIRELOS, Chargé de recherche, INRA Toulouse
Christian ARTIGUES, Directeur de recherche, LAAS-CNRS
Emmanuel HEBRARD, Chargé de recherche, LAAS-CNRS, Toulouse
Résumé :
Les problèmes de séquencement et d'ordonnancement forment une famille de problèmes combinatoires qui implique la programmation dans le temps d'un ensemble d'opérations soumises à des contraintes de capacités et de ressources. Nous contribuons dans cette thèse à la résolution de ces problèmes dans un contexte de satisfaction de contraintes! et d'optimisation combinatoire. Nos propositions concer! nent trois aspects différents : comment choisir le prochain nœud à explorer (recherche) ? comment réduire efficacement l'espace de recherche (propagation) ? et que peut-on apprendre des échecs rencontrés lors de la recherche (apprentissage) ?
Nos contributions commencent par une étude approfondie des heuristiques de bran- chement pour le problème de séquencement de chaîne d'assemblage de voitures. Cette évaluation montre d'abord les paramètres clés de ce qui constitue une bonne heuristique pour ce problème. De plus, elle montre que la stratégie de branchement est aussi im- portante que la méthode de propagation. Deuxièmement, nous étudions les mécanismes de propagation pour une classe de contraintes de séquencement à travers la conception de plusieurs algorithmes de filtrage. En particulier, nous proposons un algorithme de filtrage complet pour un type de contrainte de séquence avec une complexité temporelle optimale dans le pire cas. Troisièmement, nous investiguons l'impact de l'apprentissage de clauses pour résoudre le problème de séquencement de véhicules à travers une nou- velle stratégie d'explication réduite pour le nouveau filtrage. L'éva! luation expérimentale montre l'importance de l'apprentissage de clauses pour ce problème. Ensuite, nous pro- posons une alternative pour la génération retardée de variables booléennes pour encoder les domaines. Finalement, nous revisitons les algorithmes d'analyse de conflits pour ré- soudre les problèmes d'ordonnancement disjonctifs. En particulier, nous introduisons une nouvelle procédure d'analyse de conflits dédiée pour cette famille de problèmes. La nouvelle méthode diffère des algorithmes traditionnels par l'apprentissage de clauses portant uniquement sur les variables booléennes de disjonctions. Enfin, nous présentons les résultats d'une large étude expérimentale qui démontre l'impact de ces nouveaux mécanismes d'apprentissage. En particulier, la nouvelle méthode d'analyse de conflits a permis de découvrir de nouvelle bornes inférieures pour des instances largement étudiées de la littérature
Ab! stract :
Sequencing and sc! heduling involve the organization in time of operations subject to capacity and resource constraints. We propose in this dissertation several improvements to the constraint satisfaction and combinatorial optimization methods for solving these problems. These contributions concern three different aspects: how to choose the next node to explore (search)? how much, and how efficiently, one can reduce the search space (propagation)? and what can be learnt from previous failures (learning)?
Our contributions start with an empirical study of search heuristics for the well known car-sequencing problem. This evaluation characterizes the key aspects of a good heuris- tic and shows that the search strategy is as important as the propagation aspect in this problem. Second, we carefully investigate the propagation aspect in a class of sequenc- ing problems. In particular, we propose an algorithm for filtering a type of sequence constraints which worst case time complexity is lower than the best known upper bound, and indeed optimal. Third, we investigate the impact of clause learning for solving the car-sequencing problem. In particular, we propose reduced explanations for the new filtering. The experimental evaluation shows compelling evidence supporting the impor- tance of clause learning for solving efficiently this problem. Next, we revisit the general approach of lazy generation for the Boolean variables encoding the domains. Our p! ropo- sition avoids a classical redundancy issue without computational overhead. Finally, we investigate conflict analysis algorithms for solving disjunctive scheduling problems. In particular, we introduce a novel learning procedure tailored to this family of problems. The new conflict analysis differs from conventional methods by learning clauses whose size are not function of the scheduling horizon. Our comprehensive experimental study with traditional academic benchmarks demonstrates the impact of the novel learning scheme that we propose. In particular, we find new lower bounds for a well known scheduling benchmark.
Délivré par l'INSA
École Doctorale : EDSYS
Unité de recherche : LAAS-CNRS équipe ROC
Spécialité : Programmation par Contraintes
Titre :
Search, propagation, and learning in sequencing and scheduling problems
de
Mohamed SIALA (Equipe--- ROC)
E-mail : mohamed.siala@laas.fr
Date : 13 Mai 2015 à 10h00
Lieu : LAAS-CNRS - Salle de Conférences
7 avenue du Colo! nel Roche
31077 TOULOUSE Cedex 4
Composition du jury :
Fahiem BACCHUS, Professeur, Université de Toronto
Christian BESSIERE, Directeur de recherche, LIRMM-CNRS
Christine SOLNON, Professeur , LIRIS-CNRS
Hadrien CAMBAZARD, Maître de Conférences, G-SCOP; Grenoble INP
George KATSIRELOS, Chargé de recherche, INRA Toulouse
Christian ARTIGUES, Directeur de recherche, LAAS-CNRS
Emmanuel HEBRARD, Chargé de recherche, LAAS-CNRS, Toulouse
Résumé :
Les problèmes de séquencement et d'ordonnancement forment une famille de problèmes combinatoires qui implique la programmation dans le temps d'un ensemble d'opérations soumises à des contraintes de capacités et de ressources. Nous contribuons dans cette thèse à la résolution de ces problèmes dans un contexte de satisfaction de contraintes! et d'optimisation combinatoire. Nos propositions concer! nent trois aspects différents : comment choisir le prochain nœud à explorer (recherche) ? comment réduire efficacement l'espace de recherche (propagation) ? et que peut-on apprendre des échecs rencontrés lors de la recherche (apprentissage) ?
Nos contributions commencent par une étude approfondie des heuristiques de bran- chement pour le problème de séquencement de chaîne d'assemblage de voitures. Cette évaluation montre d'abord les paramètres clés de ce qui constitue une bonne heuristique pour ce problème. De plus, elle montre que la stratégie de branchement est aussi im- portante que la méthode de propagation. Deuxièmement, nous étudions les mécanismes de propagation pour une classe de contraintes de séquencement à travers la conception de plusieurs algorithmes de filtrage. En particulier, nous proposons un algorithme de filtrage complet pour un type de contrainte de séquence avec une complexité temporelle optimale dans le pire cas. Troisièmement, nous investiguons l'impact de l'apprentissage de clauses pour résoudre le problème de séquencement de véhicules à travers une nou- velle stratégie d'explication réduite pour le nouveau filtrage. L'éva! luation expérimentale montre l'importance de l'apprentissage de clauses pour ce problème. Ensuite, nous pro- posons une alternative pour la génération retardée de variables booléennes pour encoder les domaines. Finalement, nous revisitons les algorithmes d'analyse de conflits pour ré- soudre les problèmes d'ordonnancement disjonctifs. En particulier, nous introduisons une nouvelle procédure d'analyse de conflits dédiée pour cette famille de problèmes. La nouvelle méthode diffère des algorithmes traditionnels par l'apprentissage de clauses portant uniquement sur les variables booléennes de disjonctions. Enfin, nous présentons les résultats d'une large étude expérimentale qui démontre l'impact de ces nouveaux mécanismes d'apprentissage. En particulier, la nouvelle méthode d'analyse de conflits a permis de découvrir de nouvelle bornes inférieures pour des instances largement étudiées de la littérature
Ab! stract :
Sequencing and sc! heduling involve the organization in time of operations subject to capacity and resource constraints. We propose in this dissertation several improvements to the constraint satisfaction and combinatorial optimization methods for solving these problems. These contributions concern three different aspects: how to choose the next node to explore (search)? how much, and how efficiently, one can reduce the search space (propagation)? and what can be learnt from previous failures (learning)?
Our contributions start with an empirical study of search heuristics for the well known car-sequencing problem. This evaluation characterizes the key aspects of a good heuris- tic and shows that the search strategy is as important as the propagation aspect in this problem. Second, we carefully investigate the propagation aspect in a class of sequenc- ing problems. In particular, we propose an algorithm for filtering a type of sequence constraints which worst case time complexity is lower than the best known upper bound, and indeed optimal. Third, we investigate the impact of clause learning for solving the car-sequencing problem. In particular, we propose reduced explanations for the new filtering. The experimental evaluation shows compelling evidence supporting the impor- tance of clause learning for solving efficiently this problem. Next, we revisit the general approach of lazy generation for the Boolean variables encoding the domains. Our p! ropo- sition avoids a classical redundancy issue without computational overhead. Finally, we investigate conflict analysis algorithms for solving disjunctive scheduling problems. In particular, we introduce a novel learning procedure tailored to this family of problems. The new conflict analysis differs from conventional methods by learning clauses whose size are not function of the scheduling horizon. Our comprehensive experimental study with traditional academic benchmarks demonstrates the impact of the novel learning scheme that we propose. In particular, we find new lower bounds for a well known scheduling benchmark.