Download or read book Approche alg brique de probl mes d ordonnancement de type flowshop avec contraintes de d lais written by Nhat Vinh Vo and published by . This book was released on 2015 with total page 153 pages. Available in PDF, EPUB and Kindle. Book excerpt: Nous abordons dans cette thèse des problèmes de flowshop de permutation soumis des contraintes de délais minimaux et maximaux avec deux types de travaux principaux : 1. Nous avons modélisé, en utilisant l'algèbre MaxPlus, des problèmes de flowshop de permutation m-machines soumis une famille de contraintes : de délais minimaux, de délais maximaux, de sans attente, de délais fixes, de temps de montage indé- pendant de la séquence, de temps de démontage indépendant de la séquence, de blocage, de dates de début au plus tæt ainsi que de durées de latence. Des matrices caractérisant complètement leurs travaux associés ont été élaborées. Nous avons fait apparaître un problème central soumis des contraintes de délais minimaux et maximaux. 2. Nous avons élaboré des bornes inférieures pour le makespan et pour la somme (pondérée ou non) des dates de fin. Ces bornes inférieures ont été incorporées dans des procédures par séparation et évaluation. Nous avons généralisé les bornes inférieures de Lageweg et al. pour des contraintes quelconques et amélioré une borne inférieure de la littérature. L'utilisation de chacune de ces bornes inférieures ainsi que de leurs combinaisons ont été testées. Une famille de bornes inférieures pour la somme (pondérée ou non) des dates de fin a été élaborée basée sur la résolution d'un problème une machine et sur la résolution d'un problème de voyageur de commerce. Une politique de sélection de bornes inférieures a été proposée pour combiner les bornes inférieures. Bien qu'il s'agisse d'un problème de NP-difficile, l'efficacité de ces bornes inférieures a été vérifiée l'aide de tests.
Download or read book Analyse Max Plus de probl mes d ordonnancement de type Flowshop written by Christophe Lenté and published by . This book was released on 2001 with total page 170 pages. Available in PDF, EPUB and Kindle. Book excerpt: Plusieurs problèmes d'ordonnancement de type flowshop se modélisent par un produit matriciel dans l'algèbre Max-Plus. L'étude de ce produit permet de redémontrer, unifier et généraliser une majorité de résultats connus sur les problèmes de flowshop à deux machines. L'approche matricielle prend en compte, quelque soit le nombre de machines, des contraintes telles que des temps de montage ou de démontage, des décalages temporels ou des groupements de travaux en sous-lots. De nombreuses bornes, heuristiques ou méthodes, issues de la littérature et souvent construites pour le flowshop sans contrainte, s'adaptent aisément au problèmes matriciel et donc à des flowshops soumis aux contraintes citées prédédemment. Plusieurs bornes sont étudiées en détail. De plus, l'écriture matricielle autorise la prise en compte des contraintes tout en nous dispensant de la manipulation explicite des variables qui les décrivent. En conséquence, la modélisation Max-Plus permet de s'abstraire du détail des calculs et de manipuler des objets mathématiques de plus haut niveau. Les problèmes sont mieux appréhendés, leurs analyses s'effectuent plus simplement et les concepts importants se dégagent naturellement. La minimisation du produit matriciel définit en elle même un problème que l'on peut qualifier de problème d'ordonnancement et qui est un sur-problème du problème d'ordonnancement de type flowshop. Pour le résoudre, une procédure par séparation et évaluation (PSE) est proposée, dont le schéma de séparation, original, s'appuie fortement sur l'associativité du produit matriciel. Cette PSE autorise indifféremment la résolution de problèmes de flowshop avec ou sans contraintes.
Download or read book M thodes exactes et heuristiques pour le flow shop de permutation written by Ismaïl Rebaï and published by . This book was released on 1996 with total page 120 pages. Available in PDF, EPUB and Kindle. Book excerpt: L'ordonnancement, qui est la programmation de l'exécution d'une réalisation en attribuant des ressources aux tâches et en fixant leurs dates d'exécution [CC88], est présent dans tous les domaines de l'économie. La théorie de l'ordonnancement traite aussi bien de modèles mathématiques que de la modélisation de situations réelles. C'est la synergie entre théorie et pratique qui fait apparaître de nouveaux modèles. Les problèmes d'atelier sont des problèmes d'ordonnancement d'aspect pratique extrêmement difficiles. Parmi les problèmes d'atelier, on distingue les job-shops et les flow-shops selon que les gammes dépendent des travaux - jobs - ou non. A l'origine, cette thèse a eu pour objectif de transposer des avancées récentes dans la résolution du job-shop à un problème plus particulier, le flow-shop de permutation. C'est ainsi que dans un premier temps, une première méthode basée sur les dates de disponibilité et les durées de latence a été élaborée. Des problèmes de grande taille en termes de travaux et d'opérations ont pu alors être résolus et ce, pour minimiser le makespan. Par la suite, nous avons généralisé ces dates de disponibilité et ces durées de latence aux machines associées aux tâches, et résolu des instances de flow-shops de très grande taille. Par ailleurs, quelques méthodes approchées ont été proposées et comparées à celles de la littérature. Puis, une méthode exacte a été mise au point pour l'optimisation des sommes de dates de fin d'exécution des travaux et de la somme pondérée de ces dates de fin. Une variante de cette méthode a elle aussi donné des résultats performants. Enfin, nous avons généralisé certaines de ces méthodes pour tenir compte des délais d'attente dus aux montagnes et démontages d'outils sur les machines, aux transports dans l'atelier ou aux décalages temporels. Nous avons également appliqué notre approche à un type particulier de flow-shop hybride &avec des contraintes d'ordre. Ceci montre la généralité de notre méthode.
Download or read book R solution exacte de probl mes d ordonnancement de type flowshop de permutation en pr sence de contraintes d carts temporels entre op rations written by Julien Fondrevelle and published by . This book was released on 2005 with total page 190 pages. Available in PDF, EPUB and Kindle. Book excerpt: Dans ce mémoire, nous nous intéressons à l'étude et la résolution de problèmes d'ordonnancement de type flowshop de permutation, en présence de contraintes d'écarts temporels (ou time lags), définies entre les couples d'opérations consécutives au sein des travaux. De telles contraintes généralisent les contraintes de précédence classiques et peuvent modéliser de nombreuses situations réelles. De nouveaux résultats de complexité sont démontrés et viennent compléter des résultats classiques tirés de la littérature. Nous présentons aussi un état de l'art assez détaillé sur les travaux concernant les problèmes d'ordonnancement avec time lags, qui met en évidence le manque d'attention reçu par ces problèmes. Nous développons ensuite un schéma générique de résolution exacte reposant sur une Procédure par Séparation et Evaluation et nous l'utilisons pour résoudre plusieurs problèmes de flowshop de permutation en présence de time lags. L'efficacité de cette approche de résolution est évaluée grâce à des séries d'expériences numériques. Enfin, des extensions permettant de prendre en compte des contraintes supplémentaires sont proposées.
Download or read book Flow shop deux machines avec des temps de latence written by and published by . This book was released on 2008 with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: Un ordonnancement est défini comme étant une allocation, dans le temps, des ressources (machines) disponibles aux différents travaux (tâches, jobs) à réaliser, dans le but d'optimiser un ou plusieurs objectifs. La richesse de la problématique de l'ordonnancement est due aux différentes interprétations que peuvent prendre les ressources et tâches. Ainsi, les ressources peuvent être des machines dans un atelier, des pistes de décollage et d'atterrissage dans un aéroport, des équipes dans un terrain de construction, des processeurs dans les ordinateurs, etc. Les tâches, quant à elles, peuvent être des opérations dans un processus de production, le décollage et l'atterrissage dans un aéroport, les étapes d'un projet de construction, l'exécution d'un programme informatique, etc. Les différentes tâches sont caractérisées par un degré de priorité et un temps d'exécution. Les ressources, quant à elles, sont caractérisées entre autres par une capacité, des temps de réglage, etc. Les problèmes d'ordonnancement sont généralement classés en deux modèles dépendamment du nombre d'opérations que requièrent les jobs: les modèles à une opération (modèle à machine unique et modèle à machines parallèles) et les modèles à plusieurs opérations dits modèles en ateliers (flow-shop, open-shop et job-shop). Bien entendu, il est également possible de trouver d'autres modèles, hybrides, qui sont des mélanges de ces deux modèles. Cette classification a permis, un tant soit peu, de mieux comprendre et cerner les problèmes d'ordonnancement réels. Toutefois, l'expérience a montré qu'il existe toujours un gouffre entre la théorie et ce qui se passe réellement dans les centres de production ou les prestations de services. Parmi les contraintes que la théorie d'ordonnancement n'a pas considérées jusqu'à un passé récent, nous pouvons citer les temps de latence des travaux, correspondant aux différents temps nécessaires devant s'écouler entre la fin d'une opération et le début de la prochaine opératio.
