Réseaux de contraintes temporels satisfaction de contraintes, ordonnancement des tâches / Saïd Belhadji ; sous la dir. de Gérard Plateau

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 1998

Format : 125 p.

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Plateau, Gérard (1946-....) (Directeur de thèse / thesis advisor)

Université Sorbonne Paris Nord (Bobigny, Villetaneuse, Seine-Saint-Denis ; 1970-....) (Organisme de soutenance / degree-grantor)

Résumé / Abstract : NOTRE TRAVAIL S'INSCRIT DANS LE CADRE DE LA RESOLUTION DE PROBLEMES D'ORDONNANCEMENT DE TACHES PAR DES TECHNIQUES DE SATISFACTION DE CONTRAINTES TEMPORELLES (TCSP) ET DISCRETES (CSP BINAIRES). PLUS PRECISEMENT, IL CONCERNE L'ETUDE DE DEUX PROBLEMES CLASSIQUES D'ORDONNANCEMENT DE TACHES : LE JOB SHOP ET LES PROBLEMES A FENETRES DE TEMPS FIXES (FSP). AUSSI APRES AVOIR EVOQUE QUELQUES MODELES ET TECHNIQUES DE RESOLUTION DE CES PROBLEMES NOUS PROPOSONS UNE MODELISATION DE CONTRAINTES DISJONCTIVES ET LA SITUONS PAR RAPPORT A D'AUTRES MODELES DE LA LITTERATURE (PARTIE 1). NOUS DEFINISSONS DANS LA PARTIE 2 UNE RESTRICTION DES TCSP SUFFISAMMENT EXPRESSIVE POUR MODELISER TOUT PROBLEME D'ORDONNANCEMENT D'ATELIERS ET PROPOSONS UN ALGORITHME ORIGINAL DE RESOLUTION DU JOB SHOP. LA PARTIE 3 CONCERNE L'ETUDE DU PROBLEME D'ORDONNANCEMENT DE TACHES A FENETRES DE TEMPS FIXES (FSP). NOUS LE MODELISONS EN UN PROBLEME DE SATISFACTION DE CONTRAINTES BINAIRES (AU SENS CSP CLASSIQUE). SA RESOLUTION EST FAITE PAR UN ALGORITHME QUI HYBRIDE LES TECHNIQUES DE CSP AVEC LA RECHERCHE DE STABLES DANS LES GRAPHES. DES EXPERIENCES REALISEES SUR DES INSTANCES CLASSIQUES DE LA LITTERATURE VALIDENT L'ENSEMBLE DES ALGORITHMES PROPOSES.