Aller au contenu

Problèmes d’ordonnancement sur plusieurs machines

Objectifs et prérequis du TP sur l'ordonnancement sur plusieurs machines Objectifs Ce TP a pour but d'apprendre à résoudre des problèmes d'ordonnancement sur plusieurs machines. À l'issue de ce TP, vous serez capable de : Comprendre les différents types de machines et leurs caractéristiques. Appliquer des algorithmes d'ordonnancement tels que l'algorithme de Johnson.

D'après le document Problèmes d’ordonnancement sur plusieurs machines

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source

Problèmes d’ordonnancement sur plusieurs machines

Industrial Engineering · PDF · 45 pages · 2021

Afficher l'aperçu du document

Consulter le document original →

Objectifs et prérequis du TP sur l'ordonnancement sur plusieurs machines

Objectifs

Ce TP a pour but d'apprendre à résoudre des problèmes d'ordonnancement sur plusieurs machines. À l'issue de ce TP, vous serez capable de :

  • Comprendre les différents types de machines et leurs caractéristiques.
  • Appliquer des algorithmes d'ordonnancement tels que l'algorithme de Johnson.
  • Optimiser l'affectation des tâches sur les machines.
  • Identifier et corriger les erreurs fréquentes dans l'ordonnancement.

Prérequis

Pour réaliser ce TP, il est nécessaire de disposer des éléments suivants :

  • Connaissances de base en optimisation et en programmation.
  • Logiciels de simulation ou d'optimisation tels que Lekin et Cplex.
  • Matériel informatique adéquat pour exécuter les simulations.

Procédure d'ordonnancement sur plusieurs machines

Introduction aux problèmes d'ordonnancement

Dans ce TP, nous allons aborder les problèmes d'ordonnancement sur plusieurs machines. Nous avons m machines pour effectuer n tâches. L'objectif est d'optimiser un critère 𝛾 choisi tout en respectant les contraintes 𝛽 imposées.

Étape 1 : Compréhension des types de machines

Il existe trois types de machines :

  • Machines identiques (Pm) : La durée d'exécution est la même pour toutes les machines et toutes les tâches.
  • Machines uniformes (Qm) : Chaque machine a une vitesse d'exécution propre et constante.
  • Machines indépendantes (Rm) : La vitesse d'exécution est différente pour chaque machine et pour chaque travail.

Étape 2 : Application de la règle LPT

Pour le problème Pm||Cmax, un ordonnancement est optimal si les tâches sont rangées dans l'ordre décroissant de Pi (LPT : Longest Processing Time). Voici comment procéder :


1. Classer les tâches par temps d'exécution décroissant.
2. Affecter la tâche ayant le plus long temps d'exécution à la première machine disponible.

Étape 3 : Utilisation de l'algorithme de Mac Naughton

Pour le problème Pm|prmp|Cmax, la solution optimale est obtenue avec l'algorithme de Mac Naughton. Voici les étapes :


1. Mettre les tâches sur la première machine selon un ordre quelconque.
2. Découper la séquence au niveau de M* et placer les tâches en aval de M* sur la machine suivante.
3. Répéter jusqu'à ce que toutes les tâches soient ordonnancées.

Résultats attendus de l'ordonnancement

Après avoir appliqué les méthodes d'ordonnancement, vous devriez observer les résultats suivants :

  • Pour Pm||Cmax, le temps d'achèvement maximal Cmax doit être minimisé.
  • Les tâches doivent être exécutées dans l'ordre optimal pour réduire le temps total.
  • Les valeurs de Cmax doivent être vérifiées pour s'assurer qu'elles correspondent aux attentes.

Erreurs fréquentes avec l'ordonnancement sur plusieurs machines

Lors de la mise en œuvre des algorithmes d'ordonnancement, certaines erreurs peuvent survenir :

  • Ne pas respecter l'ordre de priorité des tâches lors de l'affectation.
  • Oublier de vérifier la disponibilité des machines avant d'affecter une tâche.
  • Confondre les types de machines, ce qui peut mener à des résultats sous-optimaux.

Questions fréquentes

Qu'est-ce que l'ordonnancement sur plusieurs machines ?

L'ordonnancement sur plusieurs machines consiste à affecter des tâches à différentes machines tout en optimisant un critère spécifique, comme le temps d'achèvement maximal.

Quels sont les types de machines en ordonnancement ?

Il existe trois types de machines : identiques, uniformes et indépendantes, chacune ayant des caractéristiques spécifiques qui influencent l'ordonnancement.

Comment appliquer l'algorithme de Johnson ?

L'algorithme de Johnson est utilisé pour minimiser le temps d'achèvement dans les problèmes à deux machines. Il nécessite de classer les tâches selon des règles spécifiques basées sur leurs temps d'exécution.

Quelles sont les erreurs courantes en ordonnancement ?

Les erreurs courantes incluent le non-respect de l'ordre de priorité des tâches, l'oubli de vérifier la disponibilité des machines, et la confusion entre les types de machines.

Comment optimiser l'ordonnancement dans un job shop ?

Pour optimiser l'ordonnancement dans un job shop, il est essentiel d'utiliser des algorithmes adaptés, comme celui de Jackson, qui permet de gérer efficacement les tâches sur différentes machines.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions