Combinatoire extrémale et optimisation de la diversité : des apports réciproques !

Mais la mise en œuvre d'une telle stratégie pose bien des difficultés en termes de gestion de production. Une production pour stock conduirait à des coûts de stockage de produits finis rédhibitoires alors qu'une gestion à la commande est souvent incompatible avec les exigences de délai des clients.

Une politique dite d'assemblage à la commande (on fabrique des modules ou produits semi-finis (PSF) sur stocks et on les assemble à la commande) est une politique qui permet d'offrir une forte diversité tout en réalisant un bon compromis entre les coûts de stockage des PSF et le délai d'obtention des produits finis. Pour la mettre en place un des problèmes clés est la définition des produits semi-finis à stocker.

Un exemple classique concerne les faisceaux électriques pour l'automobile

Questions et conjectures

Considérons un ensemble de produits finis réalisés à partir d'un ensemble d'options oi . Soit n le nombre d'options et V l'ensemble des options. Un produit fini est un sous-ensemble  d'options (il y ainsi 2n -1 produits finis possibles - on ne considère pas   un produit avec aucune option). On recherche des produits semi-finis qui sont des sous-ensembles non-vides particuliers de V. Soit k le nombre maximum de produits semi-finis disjoints autorisés à être assemblés pour former un produit fini (sans options inutiles). Ce nombre k peut être plus ou moins élevé selon le délai de livraison admis. Un générateur est un ensemble de PSF qui, par une union disjointe d'au plus k de ses PSF, permet de répondre exactement à n'importe quelle demande de produit finis. Il s'agit de trouver le générateur optimal c'est-à-dire un ensemble des produits semi-finis (de taille le plus faible possible pour minimiser les coûts de stockage) permettant de faire tous les produits finis dans le délai attendu. Plus précisément, la question de recherche est de : trouver un générateur optimal, c'est à dire de cardinal minimum (appelé opt(n,k)).

Une méthode permettant d'obtenir un générateur est la suivante : on partitionne l'ensemble des options en k paquets de taille aussi proches que possibles (la taille des paquets diffère d'au plus une option), et on met dans le générateur tous les sous-ensembles de chacun des paquets). On montre aisément que cette construction conduit effectivement à un générateur. Il faut alors montrer qu'il est de cardinalité minimum.

Plus formellement soit p = én/kù et r tel que n = pk - r avec 0 £ r < k. Si V1,...,Vk est une partition de V en r ensembles de taille (p-1) et (k-r) ensembles de taille p, alors les PSF  de la construction sont tous les éléments de P (Vi)   {Æ} pour i allant de 1 à k, où P (V) désigne l'ensemble des parties de V.  Le nombre de PSF de cette construction est :

constr(n,k) = r x (2p-1 - 1) + (k - r) (2p - 1).

La solution ainsi construite donne une borne supérieure sur le nombre de PSF d'un générateur optimal : opt(n,k) £ constr(n,k). Nous conjecturons que l'inégalité est en fait une égalité.

Conjecture faible. La construction est un générateur optimal.

Conjecture forte. La construction est l'unique générateur optimal dès que p 3.

Preuves pour des cas intéressants

Les travaux ont permis de démontrer la conjecture dans des cas intéressants.

Ce problème est une question typique de la combinatoire extrémale. Le cas optimal conjecturé fait maintenant partie d'un cercle de problèmes autour du «Théorème de Turán », célèbre théorème de base du domaine, dont la solution est similaire à notre construction.   

On obtient immédiatement une autre conjecture, équivalente à la conjecture faible : tout générateur optimal contient une option apparaissant dans 2p-1 PSF. C'est  sous cette forme là que les conjectures faibles et fortes ci-dessus ont été démontrées dans des cas particuliers importants. Les détails des preuves se trouvent dans (Frein et al, 2008). A ce jour on peut résumer les résultats dans le tableau ci-dessous:

Optimalité et unicité;

Optimalité et non unicité;

0ptimalité et ?

 

Conclusion

Ce travail a pu être réalisé grâce à la collaboration de membres de G-SCOP issus des mathématiques discrètes et de la gestion des systèmes de production. Il est intéressant de noter que la conjecture proposée, issue de réflexions sur un problème industriel, est en fait la généralisation d'une conjecture du mathématicien Erds (1993) qui portait sur l'analogue de opt(n, 2) quand les produits semi-définis ne sont pas nécessairement disjoints. Contacts: Yannick Frein, Benjamin Lévèque, András Sebo, laboratoire G-SCOP Publications:

• Y. Frein, Benjamin Lévèque, András Seb, Generating All Sets With Bounded Unions,Combinatorics Probability and Computing, vol. 17, 641-660, 2008.