Programmation mathématique et grands problèmes combinatoires


Ordonnancement cyclique et lots de fabrication en production multiniveaux

De façon naturelle, le modèle " produit" d'une structure de production multiniveaux est représenté par un graphe " gozinto ". Pour formuler le problème d'ordonnancement des opérations sur les différentes machines de l'atelier, ce modèle peut être décomposé en " jobs". Chaque job est associé à un produit fini. Toutes les opérations qui le composent correspondent aux différentes étapes de sa fabrication. A toute opération non terminale correspond alors un couple de produits : (produit intermédiaire fabriqué, produit fini concerné). Connaissant les taux de demandes en produits finis, on en déduit alors les taux de traitement désirés pour les différentes opérations. On peut alors formuler le problème combiné de détermination des tailles de lots et d'ordonnancement de ces lots pour les différents produits [HP 99].

Sous l'hypothèse de taux de demande constants, lasolution du problème d'ordonnancement est cyclique. En utilisant l'approche par " cycle commun", ce problème a été formulé comme un problème d'optimisation conjointe des dates de fabrication et des quantités à fabriquer pour les différents produits. Nous avons montré que ce problème pouvait être résolu en deux étapes indépendantes [Hen 99b]:

L'ordonnancement cyclique est ensuite construit par calcul des dates sur la période de référence et répétition cyclique de l'ordonnancement ainsi obtenu.

La méthode de mise en oeuvre associée à cette technique de résolution est conçue pour s'adapter automatiquement à des variations des taux de demandes autour de leur valeur nominale [Hen 99c]. La méthode est rendue réactive

L'évaluation des performances de l'heuristique de mise en oeuvre adaptative a montré une très bonne qualité des solutions obtenues, particulièrement lorsque la modification de la longueur de la période de référence est autorisée [Hen 99c]
 
 

Résolution de problèmes opérationnels par optimisation en variables entières
 


De nombreux problèmes rencontrés dans l'Industrie et les Services, particulièrement les problèmes de logistique et d'allocation de ressources, donnent lieu à la formulation de problèmes de transport ou d'affectation généralisés en variables binaires ou entières. Dans ces problèmes, les nombres de variables et de contraintes sont souvent considérables, ce qui interdit numériquement l'exploration de tout le domaine des solutions admissibles. On observe cependant que la matrice des contraintes du problème de base, d'affectation ou de transport, est totalement unimodulaire, et donc que sa solution est naturellement entière. Cette propriété n'est pas conservée généralement en présence de contraintes supplémentaires venant compliquer la matrice des contraintes, et par là-même, générer de nouvelles faces limitant le polyèdre des solutions. Cependant, on peut l'utiliser soit dans des versions relaxées du problème, soit pour générer localement l'enveloppe des solutions entières, afin que la solution du problème continu redevienne " naturellement " entière. Les méthodes de relaxation et de génération de coupes dont s'inspire cette approche ne sont pas nouvelles, mais les outils logiciels récents en propagation logique de contraintes permettent de les rendre plus efficaces qu'auparavant. En outre, ces méthodes se révèlent particulièrement efficaces lorsqu'elles sont combinées à des méthodes heuristiques permettant de calculer de façon numériquement efficace des solutions sous-optimales à des problèmes de grande dimension [Hen 97a].
 


La sélection et la conduite de projets innovants de Recherche-Développement posent des problèmes de décision et de maîtrise dont l'enjeu est considérable pour l'Entreprise et pour la Société. Au sein d'une grande entreprise, par exemple dans le secteur aéronautique et spatial, de nombreux projets de recherche et développement apparaissent nécessaires à l'essor, au renforcement du savoir-faire et à la compétitivité de l'entreprise. Cependant, les ressources financières, temporelles et en personnel étant limitées, des choix s'imposent. Il est essentiel que ces choix soient faits sur des bases rationnelles. Quelles sont, à l'heure actuelle, les méthodologies permettant de sélectionner des sujets de recherche et de développement de façon à optimiser des critères économiques et des facteurs de risque? Comment doit-on ensuite conduire un projet innovant jusqu'au succès à travers une série de choix conjoncturels et stratégiques ?

Le problème de sélection de projets doit reposer d'une part sur le choix de paramètres pertinents permettant de caractériser les projets et de les comparer, d'autre part sur une approche multicritère d'aide à la décision.

La caractérisation d'un projet vise d'abord à quantifier ses paramètres internes : sa structure, ses composantes, sa faisabilité, sa gestion. Mais elle doit aussi intégrer le contexte et les enjeux, l'état des connaissances, du savoir-faire de l'entreprise et l'existence éventuelle d'autres projets dans les domaines concernés. La méthodologie de caractérisation doit permettre d'extraire des valeurs de paramètres pertinents à partir de ces données hétérogènes. Les méthodes de data mining et de Parameter Space Investigation. sont susceptibles de contribuer à cette caractérisation.

Plusieurs grilles d'évaluation peuvent ensuite être appliquées pour le traitement des données relatives aux projets et à leur caractérisation. Plusieurs analyses monocritères peuvent ainsi être menées, de façon à bien identifier les différents critères et leurs indicateurs. L'approche multicritère de l'aide à la décision s'efforce ensuite de combiner différents outils d'analyse et de génération de solutions : méthode DEA (data envelopment analysis), risk analysis, goal programming,....

Il s'agit aussi de développer une méthodologie d'aide au suivi et aux décisions stratégiques en cours de projet, en faisant évoluer les techniques classiques de gestion de projet, de planification et d'évaluation économique. Les spécificités du problème de pilotage de projets innovants dans l'Entreprise tiennent en particulier aux incertitudes sur l'évolution dynamique et aux facteurs de risque. Ainsi, le modèle doit permettre la représentation et le traitement de ces spécificités, en intégrant par exemple des alternatives et des remises en cause, sur la base d'expertises économiques et technologiques.

Références

(limitées à certaines contributions  de l'auteur et de ses co-auteurs)

[HRT 95] J.C.Hennet, W.Roux, P.Tchilinguirian,

A framework for off-line and on-line multi-site production assignment,

Proc. 9th International Working Seminar on Production Economics, Innsbruck (Autriche), 19-23 Février 1996, pp.445-452.

[Hen 96] J.C.Hennet,

Resource allocation in manufacturing systems,

1996 Advanced Summer Institute (ASI'96), Toulouse (France), 2-6 Juin 1996

[Hen 97a] J-C.Hennet

De l'allocation optimale aux règles d'allocation en temps réel,

Concepts et outils pour les systèmes de production, Cépaduès Editions, Coordination : JC.Hennet, N°ISBN 2-85428-437-2, 1997, Partie II - Chapitre 1, pp.69-85.

[Hen 99b] J-C.Hennet,

A decomposed resolution technique for the cyclic economic lot-sizing and scheduling problem, 7th IEEE International Conference on Emerging Tehnologies and Factory Automation (ETFA'99), Barcelone (Espagne), 18-21 Octobre 1999, pp.1117-1122.

[Hen 99c] J-C.Hennet,

A common cycle approach to lot scheduling in multistage manufacturing systems,

Rapport LAAS N°99242, Juin 1999, soumis à publication.

[HP 99] J.C.Hennet , C.A.S.Passos,

Lot-sizing and scheduling in multistage production systems,

15th International Conference on CAD/CAM Robotics and Factories of the Future (CARS & FOF'99), Aguas de Lindoia (Brésil), 1999, pp.MF2.13-MF2.18.


.