Displaying similar documents to “Généralisation max-plus des bornes de Lageweg, Lenstra et Rinnooy Kan”

Méthode heuristique pour le problème de flow shop hybride avec machines dédiées

Najoua Dridi, Hatem Hadda, Sonia Hajri-Gabouj (2009)

RAIRO - Operations Research

Similarity:

Dans ce papier, nous traitons le problème de minimisation du makespan dans un flow shop hybride à deux étages avec machines dédiées. En premier lieu, nous présentons des propriétés de base, un ensemble de bornes inférieures et deux cas polynomiaux. En second lieu, nous proposons une nouvelle heuristique qui exploite ces propriétés, et cherche à placer les jobs, en tenant compte pour chaque instance du problème, de la valeur de la borne inférieure. La dernière partie de ce travail présente...

Une nouvelle transformation des réseaux de Petri généralisés : l’abstraction généralisée

Christophe Haro, Patrick Martineau, Christian Proust (2004)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Cet article introduit une nouvelle transformation des réseaux de Petri généralisés appelée l’abstraction généralisée. C’est une réduction dont nous montrons qu’elle conserve les invariants du réseau de départ et les propriétés structurelles les plus importantes. Une fonction de transformation de marquages nous permet d’introduire l’étude de la conservation des propriétés comportementales.

Une procédure de purification pour les problèmes de complémentarité linéaire, monotones

Abderrahim Kadiri, Adnan Yassine (2004)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Dans cet article, nous proposons une nouvelle méthode de purification pour les problèmes de complémentarité linéaire, monotones. Cette méthode associe à chaque itéré de la suite, générée par une méthode de points intérieurs, une base non nécessairement réalisable. Nous montrons que, sous les hypothèses de complémentarité stricte et de non dégénérescence, la suite des bases converge en un nombre fini d’itérations vers une base optimale qui donne une solution exacte du problème. Le procédé...

Configuration des lignes d'usinage à boîtiers multibroches : une approche mixte

Olga Guschinskaya, Alexandre Dolgui (2009)

RAIRO - Operations Research

Similarity:

Ce travail porte sur l'optimisation des lignes d'usinage pour la grande série. Une telle ligne comporte plusieurs postes de travail, chacun étant équipé avec boîtiers multibroches. Un boîtier multibroche exécute plusieurs opérations en parallèle. Lors de la conception en avant-projet, il est nécessaire d'affecter toutes les opérations à des boîtiers et des postes de travail de sorte à minimiser le nombre de postes et de boîtiers utilisés. Pour ce nouveau problème d'équilibrage des...

La méthode de Cholesky

Claude Brezinski (2005)

Revue d'histoire des mathématiques

Similarity:

L’objet de cet article est de présenter le manuscrit original, jusqu’alors inconnu, de Cholesky où il explique sa méthode de résolution des systèmes d’équations linéaires. Le contexte historique est précisé après une brève biographie. La méthode des moindres carrés et son application à la topographie, ainsi que les diverses méthodes directes de résolution des systèmes linéaires sont discutées. Ensuite, la diffusion de la méthode de Cholesky est retracée et l’on donne une analyse détaillée...

Un problème d’approximation matricielle : quelle est la matrice bistochastique la plus proche d’une matrice donnée ?

Pawoumodom L. Takouda (2005)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Nous nous intéressons dans ce travail au problème d’approximation d’une matrice donnée par une matrice bistochastique. Des instances de ce problème peuvent apparaître dans différents domaines : en recherche opérationnelle dans un problème d’agrégation de préférence, en calcul de variations et optimisation de forme entre autres. Nous en proposons dans cet article une étude directe via le théorème de projection et une résolution numérique inspirée par la méthode de projections alternées...

Les effets de l’exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs

Adama Coulibaly, Jean-Pierre Crouzeix (2003)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Les méthodes de points intérieurs en programmation linéaire connaissent un grand succès depuis l’introduction de l’algorithme de Karmarkar. La convergence de l’algorithme repose sur une fonction potentielle qui, sous sa forme multiplicative, fait apparaître un exposant p . Cet exposant est, de façon générale, choisi supérieur au nombre de variables n du problème. Nous montrons dans cet article que l’on peut utiliser des valeurs de p plus petites que n . Ceci permet d’améliorer le conditionnement...

Éditorial

Jean-Charles Billaut, Emmanuel Néron (2007)

RAIRO - Operations Research

Similarity:

Des explications pour reconnaître et exploiter les structures cachées d’un problème combinatoire

Hadrien Cambazard, Narendra Jussien (2006)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

L’identification de structures propres à un problème est souvent une étape clef pour la conception d’heuristiques de recherche comme pour la compréhension de la complexité du problème. De nombreuses approches en Recherche Opérationnelle emploient des stratégies de relaxation ou de décomposition dès lors que certaines struc- tures idoines ont été identifiées. L’étape suivante est la conception d’algorithmes de résolution qui puissent intégrer à la volée, pendant la résolution, ce type...

The periodic Vehicle routing problem: classification and heuristic

M. Mourgaya, F. Vanderbeck (2006)

RAIRO - Operations Research

Similarity:

The Periodic Vehicle Routing Problem (PVRP) consists in assigning customer visits to vehicle routes in some periods of a time horizon so as to satisfy some service level requirements that can take the form of frequency of visit, constraint on time lag between visits, or pre-defined visit patterns. We present different variants of this problem and propose a classification. Then, we consider a model for tactical planning for which we propose a heuristic: we optimise the planning...