91documents trouvés
Amélioration par apprentissage de la recherche à divergences limitées
W.KAROUI, M.J.HUGUET, P.LOPEZ, W.NAANAA
Tunis, MOGISA, Monastir
Manifestations avec acte à diffusion limitée : Journées Francophones de Programmation par Contraintes (JFPC'2005), Lens (France), 8-10 Juin 2005, pp.109-117 , N° 05108
Lien : http://hal.inria.fr/inria-00000051
Diffusable
Plus d'informations
Résumé
Dans le cadre de la résolution des problèmes de satisfaction de contraintes, nous présentons une nouvelle méthode complète basée sur des améliorations de " Limited Discrepancy Search " [Harvey & Ginsberg 1995]. Cette méthode, intitulée " Minimal Discrepancy Search " ( DS), peut être considérée comme la fusion de deux nouvelles variantes de LDS ; celles-ci mettent en oeuvre des techniques d'apprentissage au cours de la recherche : - " Permuted Limited Discrepancy Search " qui exploite les échecs rencontrés lors de l'exploration de l'arbre de recherche et en déduit un ordre sur les variables. Cet ordre minimise le nombre de divergences et accélère la résolution dans le cas d'un problème soluble. - " Restricted Discrepancy Search ", méthode permettant de déterminer, sans pour autant réaliser toutes les itérations de LDS, si le problème est sur-contraint. Dans ce cas, on abandonne la recherche prématurément (et avantageusement). Les performances de ces méthodes sont évaluées suivant le temps nécessaire pour aboutir à une solution, ou à la preuve de l'absence d'une solution, et le nombre de noeuds générés dans l'arbre de recherche correspondant. Pour attester de l'efficacité de DS, des comparaisons avec d'autres méthodes ont été menées, suivant la taille et le taux de contraintes des problèmes testés. " Forward Checking " est ainsi utilisé pour des problèmes de taille réduite et relativement peu contraints ; pour des problèmes de grande taille et plus fortement contraints, nous utilisons « mac3cache ", proposé par [Zhang et al. 2004]. Dans tous les cas, DS s'avère très performante et surclasse les autres méthodes.
Recherche par montée de divergences (CDS) guidées par heuristique de retour pour le job-shop flexible
A.BEN HMIDA, M.J.HUGUET, P.LOPEZ
MOGISA, La Marsa
Manifestations avec acte à diffusion limitée : 4ème Conférence Internationale en Recherche Opérationnelle (CIRO'05), Marrakech (Maroc), 23-26 Mai 2005, 2p. (Résumé) , N° 05137
Diffusable
104606Recherche à divergences limitées guidées par heuristique pour le job-shop flexible
A.BEN HMIDA, M.J.HUGUET, P.LOPEZ
Tunis, MOGISA
Manifestations avec acte à diffusion limitée : 6ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'05), Tours (France), 14-16 Février 2005, pp.100-102 (Résumé) , N° 04450
Diffusable
103258Approches par contraintes pour l'ordonnancement robuste
C.BRIAND, M.J.HUGUET, H.T.LA, P.LOPEZ
MOGISA
Ouvrage (contribution) : Flexibilité et robustesse en ordonnancement, Traité IC2 Informatique et Systèmes d'Information, Hermes Science, N°ISBN 2-7462-1028-2, 2005, Chapitre 9, pp.191-218 , N° 04355
Diffusable
103476A limited discrepancy search method for solving disjunctive scheduling problems with resource flexibility
M.J.HUGUET, P.LOPEZ, A.BEN H'MIDA
MOGISA, SOI2E
Manifestations avec acte à diffusion limitée : 9th International Workshop on Project Management and Scheduling (PMS'2004), Nancy (France), 26-28 Avril 2004, pp.299-302 , N° 03511
Lien : http://hal.archives-ouvertes.fr/hal-00138200
Diffusable
Plus d'informations
Abstract
In this paper we are concerned with shop scheduling problems with resource flexibility. We propose to solve both problems, scheduling and allocation, in an integrated approach based on an adaptation of Limited Discrepancy Search (LDS) (Harvey and Ginsberg (1995)) to prune dramatically the search tree while ensuring good performances.
An LDS-based approach for shop scheduling problems with resource flexibility
M.J.HUGUET, P.LOPEZ, A.BEN H'MIDA
MOGISA, SOI2E
Rapport LAAS N°03479, Octobre 2003, 7p.
Diffusable
101421Constraint propagation techniques for mixed scheduling and allocation problems
M.J.HUGUET, P.LOPEZ
MOGISA
Rapport LAAS N°03285, Juin 2003, 34p.
Diffusable
100932Résolution intégrée d'ordonnancement et d'affectation : adaptation d'une méthode de recherche à divergence limitée à une approche fondée sur les réseaux de Petri et la logique linéaire
C.MANCEL, M.J.HUGUET, P.LOPEZ, M.MEDJOUDJ, R.VALETTE
OCSD, MOGISA, OLC
Manifestation avec acte : 4ème Conférence Francophone de MOdélisation et SIMulation (MOSIM'03), Toulouse (France), 23-25 Avril 2003, pp.293-298 , N° 02546
Diffusable
100711Dynamic task sequencing in temporal problems with uncertainty
M.J.HUGUET, P.LOPEZ, T.VIDAL
OCSD, LGP-ENIT, MOGISA
Manifestations avec acte à diffusion limitée : Workshop on On-Line Planning and Scheduling, Toulouse (France), 24 Avril 2002, pp.41-48 , N° 02073
Diffusable
51620A constraint-based procedure for scheduling and allocation with unrelated machines
M.J.HUGUET, P.LOPEZ
OCSD, MOGISA
Manifestations avec acte à diffusion limitée : 8th International Workshop on Project Management and Scheduling (PMS'2002), Valence (Espagne), 3-5 Avril 2002, pp.190-193 , N° 01460
Diffusable
104166