Mémoires de Fin d’Etudes
Etablissement
Université de M’Sila - Mohamed Boudiaf
Affiliation
Institut d’Informatique
Auteur
HEMMAK, Allaoua
Directeur de thèse
BELOUADAH Hocine
Filière
Informatique:Programmation et Systéme
Diplôme
Magister
Titre
RESOLUTION D’UN PROBLEME D’ORDONNANCEMENT SUR UNE MACHINE AVEC DATE ECHUE COMMUNE PAR LA PROGRAMMATION DYNAMIQUE ET LA RELAXATION LAGRANGIENNE
Mots clés
Mots clés : Programmation Dynamique ; Ordonnancement sur une seule machine ; Date échue commune ; Coûts des avances et des retards ; Relaxation de l’espace des états posed. Key words: Dynamic Programming; Single machine Scheduling; Common Due Date; Earliness Tardiness Penalties; State Space Relaxation.
Résumé
RESUME L’objet de ce mémoire est l’implémentation de la méthode de la programmation dynamique appliquée à un problème d’ordonnancement intitulé : « minimisation de la somme des coûts des avances et des retards avec date échue commune sur une seule machine ». Vu le nombre exponentiel des états requis par cette méthode, on tente de développer une approche fondée sur la récursivité dynamique mais en tronquant certains états : la relaxation de l’espace des états pour trouver une solution approchée, et, dans certains cas, une solution optimale au problème posé. ABSTRACT The object of this memoir is the implementation of the dynamic programming method used to solving a scheduling problem : minimizing the sum of earliness and tardiness penalties with common due date on a single machine. Since the exponential number of states that the dynamic programming method requires, we try to develop an approach based on the dynamic recursion but by cutting some states: states space relaxation for getting near solution or, for some cases, exact solution to the problem posed
Date de soutenance
: 17/01/2007
Pagination
89
Format
pdf
Statut
Traitée