Ordonnancement sur machines parall
Forum 'Emplois' - Sujet créé le 2004-06-14
Les problèmes d'ordonnancement en ateliers spécialisés relèvent de la problématique de la régulation à court terme de l'entreprise, et plus particulièrement de celle du contrôle et de l'utilisation de la main d'oeuvre et des équipements productifs. Elles complètent donc les techniques de gestion des stocks qui assurent
le contrôle de matières. L'ordonnancement de la production est l'un des modes d'organisation des systèmes productifs les plus répandus, c'est sans doute l'un de ceux qui posent le plus de problèmes.
Une grande partie de la théorie d'ordonnancement suppose que les machines sont disponibles à tout instant. Cependant, cette supposition n'est pas toujours vérifiée. En effet, la réalité industrielle prévoit des périodes d'indisponibilité des machines pour la maintenance préventive par exemple (modèle déterministe), ou tout simplement à cause des pannes (modèle stochastique). Notre étude prend en compte cette situation, en considérant le
cas déterministe.
La motivation de l'étude du problème avec contrainte d'indisponibilité déterministe, vient de la pratique en matière de production. En effet, une machine peut être conçue pour être
examinée, réapprovisionnée en combustible ou maintenue après avoir travaillé pendant une période donnée. Une machine peut également être programmée pour effectuer un autre travail
particulier dans certains intervalles de temps et devient ainsi indisponible. Ces situations sont fréquemment observées dans les industries où des périodes de maintenance préventives sont
planifiées automatiquement en même temps que le programme des travaux. Nous pouvons citer comme exemple les industries alimentaires.
Le problème que l'on propose d'étudier est le problème d'ordonnancement sur machines parallèles identiques avec une période d'indisponibilité sur chaque machine. L'objectif est la minimisation des encours. Cet objectif se traduit par la minimisation du flot moyen (temps de séjour moyen des produits dans l'atelier). Le critère de minimisation du flot est une mesure de performance souvent rencontrée en pratique. La
minimisation des encours permet de raccourcir le temps de cycle du produit et ainsi maîtriser sa date de sortie de l'atelier. Elle permet également de diminuer le volume des stocks et les coûts de possession.
Deux cas sont à traiter :
- la date et la durée de chaque période sont connues et sont fixes ;
- la durée de chaque période d'indisponibilité est connue et fixe, par contre la date de chaque maintenance est connue avec une "incertitude" et la date précise fait partie des variables de
décision.
Plusieurs études dans la littérature ont traité le premier cas en considérant certaines hypothèses ou certaines variétés du problème. Des heuristiques à performances garantie ainsi que des méthodes exactes ont été proposées. Le but de cette étude est de faire un tour d'horizon des méthodes proposées dans la littérature pour la résolution des problèmes d'ordonnancement sur machines parallèles avec périodes d'indisponibilité en considérant les deux cas présentés ci-dessus. Ensuite, des méthodes de résolution du problèmes sur machines parallèles identiques seront proposées :
- algorithmes d'approximation ;
- analyse du "pire cas" ;
- méthodes exactes avec développement des propriétés de dominance et des bornes inférieures.
Mots clés : ordonnancement, indisponibilité, heuristique, analyse du pire cas, méthodes exactes, propriétés de
dominance, bornes inférieures.
Responsables : Chérif Sadfi et Chengbin Chu.
Laboratoire : ISTIT (Institut des Sciences et des Techniques de l'Information de Troyes).
Equipe : OSI (Optimisation des Systèmes Industriels).
Profil du projet : ordonnancement, recherche opérationnelle.
Compétences souhaitées : recherche opérationnelle, programmation en C.
Candidature :
Envoi d'un CV détaillé, des notes obtenues en DEA en décrivant les enseignements suivis pendant le DEA, d'une lettre de motivation et éventuellement prendre contact avec les responsables de la thèse.
Les dossiers sont à envoyer à : sadfi@utt.fr
le contrôle de matières. L'ordonnancement de la production est l'un des modes d'organisation des systèmes productifs les plus répandus, c'est sans doute l'un de ceux qui posent le plus de problèmes.
Une grande partie de la théorie d'ordonnancement suppose que les machines sont disponibles à tout instant. Cependant, cette supposition n'est pas toujours vérifiée. En effet, la réalité industrielle prévoit des périodes d'indisponibilité des machines pour la maintenance préventive par exemple (modèle déterministe), ou tout simplement à cause des pannes (modèle stochastique). Notre étude prend en compte cette situation, en considérant le
cas déterministe.
La motivation de l'étude du problème avec contrainte d'indisponibilité déterministe, vient de la pratique en matière de production. En effet, une machine peut être conçue pour être
examinée, réapprovisionnée en combustible ou maintenue après avoir travaillé pendant une période donnée. Une machine peut également être programmée pour effectuer un autre travail
particulier dans certains intervalles de temps et devient ainsi indisponible. Ces situations sont fréquemment observées dans les industries où des périodes de maintenance préventives sont
planifiées automatiquement en même temps que le programme des travaux. Nous pouvons citer comme exemple les industries alimentaires.
Le problème que l'on propose d'étudier est le problème d'ordonnancement sur machines parallèles identiques avec une période d'indisponibilité sur chaque machine. L'objectif est la minimisation des encours. Cet objectif se traduit par la minimisation du flot moyen (temps de séjour moyen des produits dans l'atelier). Le critère de minimisation du flot est une mesure de performance souvent rencontrée en pratique. La
minimisation des encours permet de raccourcir le temps de cycle du produit et ainsi maîtriser sa date de sortie de l'atelier. Elle permet également de diminuer le volume des stocks et les coûts de possession.
Deux cas sont à traiter :
- la date et la durée de chaque période sont connues et sont fixes ;
- la durée de chaque période d'indisponibilité est connue et fixe, par contre la date de chaque maintenance est connue avec une "incertitude" et la date précise fait partie des variables de
décision.
Plusieurs études dans la littérature ont traité le premier cas en considérant certaines hypothèses ou certaines variétés du problème. Des heuristiques à performances garantie ainsi que des méthodes exactes ont été proposées. Le but de cette étude est de faire un tour d'horizon des méthodes proposées dans la littérature pour la résolution des problèmes d'ordonnancement sur machines parallèles avec périodes d'indisponibilité en considérant les deux cas présentés ci-dessus. Ensuite, des méthodes de résolution du problèmes sur machines parallèles identiques seront proposées :
- algorithmes d'approximation ;
- analyse du "pire cas" ;
- méthodes exactes avec développement des propriétés de dominance et des bornes inférieures.
Mots clés : ordonnancement, indisponibilité, heuristique, analyse du pire cas, méthodes exactes, propriétés de
dominance, bornes inférieures.
Responsables : Chérif Sadfi et Chengbin Chu.
Laboratoire : ISTIT (Institut des Sciences et des Techniques de l'Information de Troyes).
Equipe : OSI (Optimisation des Systèmes Industriels).
Profil du projet : ordonnancement, recherche opérationnelle.
Compétences souhaitées : recherche opérationnelle, programmation en C.
Candidature :
Envoi d'un CV détaillé, des notes obtenues en DEA en décrivant les enseignements suivis pendant le DEA, d'une lettre de motivation et éventuellement prendre contact avec les responsables de la thèse.
Les dossiers sont à envoyer à : sadfi@utt.fr