Brevet FR3055718A1 — publié le 20180309

Arrière-plan de l'invention La présente invention se situe dans le domaine des procédés de découpe du verre et vise plus précisément une méthode et un dispositif permettant d'optimiser do telles découpes. La méthode et le procédé selon l'invention permettent notamment de réduire les pertes verrières lors de la création de lots de découpe en usine. On rappelle qu'un pian de découpe par guillotine d'un lot de pièces de verre rectangulaires doit prendre en compte le fait que les pièces sont destinées à être empilées sur un ou plusieurs chevalets, selon une séquence prédéterminée propre à chaque chevalet. Il n'existe pas, dans l'état actuel de la technique, de logiciel permettant d'optimiser la conception d'un plan de découpe permettant de respecter ces contraintes de placement, tout en minimisant les pertes verrières. En effet, les logiciels aujourd'hui utilisés à cet effet permettent de ne construire qu'un nombre limité de plans de découpe respectant les contraintes de placement, obligeant en pratique l'opérateur à utiliser plusieurs logiciels en parallèle, et à choisir parmi les plans de découpe générés par ces différents logiciels, celui qui minimise les pertes verrières. Objet et résumé de l'invention L'invention vise un procédé et un dispositif de détermination d'un plan de découpe qui ne présente pas les inconvénients précités. Plus précisément, et selon un premier aspect, l'invention concerne un procédé mis en oeuvre par ordinateur pour déterminer un plan optimisé de découpe par guillotine d'un lot de pièces de verre rectangulaires dans au moins un plateau de verre, les pièces étant destinées, après découpe, à être empilées sur un ou plusieurs chevalets, les pièces d'un chevalet devant être placées sur un plateau pour découpe selon une séquence prédéterminée pour ce chevalet, ledit procédé comportant - une étape de définition de contraintes de découpe et de contraintes de positionnement desdites pièces et d'un critère d'optimisation ; 3 0 5 5 7 1 8 2 - la création d'un arbre comprenant une racine, des feuilles représentant chacune un plan de découpe complet permettant de découper toutes les pièces du lot, chaque autre noeud de l'arbre représentant un plan de découpe partiel, le plan de découpe associé à un noeud de l'arbre étant 5 obtenu en ajoutant au plan de découpe partiel associé au noeud père de ce noeud, sous le respect de contraintes prédéterminées, la prochaine pièce d'un dit chevalet déterminée selon la séquence prédéterminée de ce chevalet ; et - une étape de sélection d'un plan de découpe complet associé à une 10 feuille de l'arbre en fonction dudit critère d'optimisation. Ainsi, et d'une façon gé.nérale, l'invention vise une méthode permettant de concevoir un nombre important de plans de découpe complets, y compris pour des lots complexes. Le procédé est remarquable en ce qu'il construit progressivement un arbre des plans de découpe 15 partiels en plaçant los pièces une par une dans le respect des contraintes. Ce procédé présente en outre l'avantage de pouvoir facilement être parallélisé. Le procédé facilite grandement la tâche de l'opérateur consistant essentiellement en la saisie des contraintes et du critère d'optimisation. 20 Ce critère d'optimisation peut viser à minimiser une surface totale de perte engendrée par la découpe. En variante, l'opérateur peut définir un autre critère d'optimisation, par exemple pour minimiser le nombre de plateaux de verre utilisés. Dans un mode particulier de réalisation, les contraintes de découpe 25 peuvent être choisies parmi: - un nombre maximum de niveaux de découpe ; - une largeur minimum des chutes, par exemple supérieure à deux fois l'épaisseur du plateau ; - une direction du premier rompage par exemple dans le sens de la 30 largeur du plateau, ou la largeur maximum d'un niveau de découpe par exemple trois mètres, en raison de contraintes de manipulation,. Dans un mode particulier de réalisation, les contraintes de positionnement peuvent être choisies parmi l'orientation des pièces dans un plateau, la position relative des pièces d'un même plateau en fonction 35 de leur niveau, le nombre maximum desdits au moins un plateau de verre. 3055718 Dans un mode particulier de réalisation, un noeud de l'arbre possède au maximum 9 fils, une nouvelle pièce ajoutée à un plan de découpe partiel pouvant être placée de neuf façons différentes horizontalement ou verticalement, au-dessus de la précédente, si les deux 5 pièces ont une assiette (bord parallèle à la longueur du plateau) de même longueur, à droite de la précédente dans le même niveau 2, au-dessus du niveau 2 précédent, à droite du niveau 1 précédent ou dans un nouveau plateau. Dans une variante optimisée de réalisation, la création de l'arbre 10 comporte : - une étape consistant à créer, sous la racine et pour chacun des chevalets un noeud associé à un plan de découpe partiel pour chacune des positions admissibles de la première pièce du chevalet sous le respect des contraintes ; et 15 - au moins une itération, chaque itération comportant : - une étape de sélection d'un noeud courant de l'arbre en fonction de caractéristiques du plan de découpe partiel représenté par ce noeud ; et - une étape de création d'au moins un noeud fils dudit noeud 20 courant, le plan de découpe associé audit noeud fils étant obtenu en ajoutant au plan de découpe partiel associé audit noeud courant, et sous le respect des contraintes, la prochaine pièce d'un chevalet prise selon la séquence prédéterminée de ce chevalet. 25 Cette variante est remarquable en ce qu'elle comporte, à chaque itération, une étape de sélection du noeud courant dont on créé les fils en fonction des caractéristiques du plan de découpe partiel représenté par ce noeud. Cette caractéristique permet de sélectionner le noeud courant le 30 plus prometteur pour arriver à la solution optimale, de sorte que le procédé arrive normalement plus vite à la solution optimale. Il est donc intéressant, dans un mode particulier de réalisation, que le procédé comporte une étape d'arrêt des itérations si la durée d'exécution du procédé est supérieure à une durée prédéfinie de manière 35 à permettre à l'opérateur de prendre connaissance d'une solution optimisée ou d'une bonne solution dans un délai raisonnable. 3055718 4 Dans un mode particulier de réalisation, le procédé permet à l'utilisateur de connaître la meilleure solution à tout moment tout en laissant le procédé s'exécuter pour découvrir éventuellement de meilleures solutions. 5 Dans un mode particulier de réalisation, le noeud courant est sélectionné - selon un premier critère dit « critère de chute minimum > consistant à sélectionner le noeud associé au plan de découpe pour lequel le rapport surface de perte / surface utile est minimal ; ou 10 - selon un deuxième critère dit « critère rie surface maximum » consistant à sélectionner le noeud associé au plan de découpe pour lequel la surface utile est la plus importante. Par exemple, le critère « critère de chute minimum » peut être utilisé jusqu'à atteindre un taux d'occupation de la mémoire vive de 15 l'ordinateur (environ 2 million de noeuds ouverts). Afin d'économiser de la place mémoire, dans un mode particulier de réalisation, seule la feuille associée au plan de découpe complet maximisant le critère d'optimisation est mémorisée, les autres feuilles étant supprimées. Autrement dit, la première feuille obtenue est 20 mémorisée, et lorsqu'on obtient une nouvelle feuille, on ne garde en mémoire que la feuille associé au meilleur plan de découpe complet. Dans un mode particulier de réalisation, le procédé comporte une étape de suppression des noeuds de l'arbre associés à des plans de découpe partiels pour lesquels la surface des chutes acquises est 25 supérieure à la surface de perte d'un plan de découpe complet associé à une dite feuille. Cette notion de « chutes acquises » est rappelée avec d'autres notions en référence à la figure 7 représentant un plan de découpe partiel PDP. 30 Dans ce plan partiel, il est connu de définir trois types de surface, à savoir la surface utile contenant des pièces portant sur cette figure le numéro du chevalet auquel elles sont destinées, les chutes acquises (hachurées), c'est-à-dire la surface inutilisée sur 35 laquelle on ne pourra ajouter aucune pièce ; et 3055718 - la surface (mouchetée) qui pourrait être utilisée pour placer des pièces supplémentaires à la suite (gris clair). Ainsi, dans un mode particulier de réalisation lorsqu'on détermine qu'un noeud de l'arbre est associé à un plan de découpe partiel dont la 5 surface des chutes acquises est déjà supérieure à la surface de perte d'un plan de découpe complet, on sait que ce noeud peut être supprimé car il ne peut en aucun cas être engendrer un plan de découpe complet offrant une meilleure solution. Ce mode particulier de réalisation permet d'élaguer l'arbre et de 10 diminuer considérablement la durée d'exécution du procédé. Dans un mode particulier de réalisation, le procédé d'optimisation selon l'invention évite ou minimise la création dans l'arbre de noeuds correspondants à des plans de découpe partiels isomorphes, à savoir des plans de découpe comportant les mêmes pièces et présentant la même 15 surface de chutes acquises. A titre d'exemple, les plans de découpe partiels PDPA et PDBP de la figure 9 sont isomorphes. Ainsi, dans un mode particulier de réalisation, lesdites contraintes de positionnement comportent au moins une contrainte lexicographique portant sur un numéro desdits chevalets pour éviter ou minimiser la 20 création de noeuds correspondants à des plans de découpe partiels isomorphes. Par exemple, les contraintes de positionnement peuvent comporter deux règles lexicographiques selon lesquelles : - Si on place la dernière pièce au-dessus de la précédente, le numéro 25 de chevalet de cette dernière pièce doit être inférieur au numéro de chevalet de la pièce précédente ; Si on place la dernière pièce à droite de la précédente, le numéro de chevalet de cette dernière pièce doit être supérieur ou égal au numéro de chevalet de la pièce précédente. 30 Dans un mode particulier de réalisation, à chaque création de noeud, on classe le noeud en fonction d'au moins une caractéristique du plan de découpe représenté par ce noeud, cette ou ces caractéristique(s) étant suffisantes pour sélectionner le plan de découpe complet optimisé. Cette caractéristique est préférentiellement la caractéristique 35 utilisée au cours de ladite étape de sélection du noeud courant de l'arbre dans la variante optimisée de réalisation. 3055718 6 Ce mode de réalisation permet d'éviter d'avoir à re-parcourir l'ensemble de l'arbre pour sélectionner le plan de découpe complet optimisé et pour sélectionner le noeud courant dans la variante optimisée de réalisation. 5 Dans un mode particulier de réalisation, les autres noeuds de l'arbre, y compris les feuilles, sont représentés en mémoire par le numéro de chevalet de la dernière pièce posée, et le sens dans lequel elle a été posée. Ce mode de réalisation permet un encombrement mémoire 10 minimum. L'invention vise aussi un dispositif de détermination d'un plan optimisé de découpe par guillotine d'un lot de pièces de verre rectangulaires dans au moins un plateau de verre, les pièces étant destinées, après découpe, à être empilées sur au moins un chevalet, les 15 pièces d'un chevalet devant être placées sur un plateau pour découpe selon une séquence prédéterminée pour ce chevalet, ledit dispositif comportant : - un module de définition de contraintes de découpe et de contraintes de positionnement des pièces et d'un critère d'optimisation ; 20 - un module de création d'un arbre comprenant une racine, des feuilles représentant chacune un plan de découpe complet permettant de découper toutes les pièces du lot, chaque autre noeud de l'arbre représentant un plan de découpe partiel, le plan de découpe associé à un noeud de l'arbre étant obtenu en ajoutant au plan de découpe partiel 25 associé au noeud père de ce noeud, sous le respect des contraintes, la prochaine pièce d'un chevalet déterminée selon la séquence prédéterminée de ce chevalet ; et - un module de sélection d'un plan de découpe complet associé à une feuille de l'arbre en fonction dudit critère d'optimisation. 30 Les plans de découpe obtenus par le procédé selon l'invention peuvent notamment être utilisés : - pour créer des lots de découpe optimisés en amont de la ligne de découpe ; lors de la découpe à proprement parler, la découpe consistant 35 principalement à propager des fissures sur le verre, suivant un ordre respectant le plan de découpe ; 3055718 7 en support pour l'opérateur lors du rompage du plateau de verre, pour l'obtention des pièces en vue de leur placement sur les différents chevalets. Par conséquent., l'invention vise aussi un procédé de découpe par 5 guillotine d'un lot de pièce de verres rectangulaires dans au moins un plateau de verre, caractérisé en ce qu'il comporte : la mise en oeuvre d'un procédé de détermination d'un plan optimisé de découpe tel que mentionné précédemment ; ledit plan optimisé étant utilisé au cours d'une phase de découpe 10 dudit plateau et au cours d'une phase de rompage dudit plateau. Dans un mode particulier de réalisation de ce procédé, le lot est lui-même déterminé par la mise en oeuvre d'un procédé de détermination d'un plan optimisé de découpe tel que décrit précédemment. Dans un mode particulier de réalisation, les différentes étapes du 15 procédé de détermination d'un plan optimisé de découpe selon l'invention sont déterminées par des instructions de programmes d'ordinateurs. En conséquence, l'invention vise aussi un programme d'ordinateur, sur un support d'informations, ce programme comportant des instructions adaptées à la mise en oeuvre des étapes d'un procédé de détermination 20 d'un plan optimisé de découpe selon l'invention. Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme 25 souhaitable. L'invention vise aussi un support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus. Le support d'informations peut être n'importe quelle entité ou 30 dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple un disque dur. D'autre part, le support d'informations peut être un support 35 transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres 3 0 5 5 71 8 8 moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. Brève description des dessins 10 D'autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent un exemple de réalisation dépourvu de tout caractère limitatif. Sur les figures : la figure 1 représente des chevalets comportant des pièces en 15 verre ; les figures 2A et 2B représentent des plans de découpe complets permettant de découper l'ensemble des pièces des chevalets de la figure 1; la figure 3 représente, sous forme d'organigramme, les principales 20 étapes d'un procédé de détermination conforme à un premier mode particulier de réalisation de l'invention ; et la figure 4 représente des plans partiels de découpe pouvant être obtenus par l'invention ; la figure 5 représente, sous forme d'organigramme, les principales 25 étapes d'un procédé de détermination conforme à un deuxième mode particulier de réalisation de l'invention la figure 6 représente, sous forme d'organigramme, les principales étapes d'une fonction d'optimisation mise en oeuvre par le procédé de détermination de la figure 5 ; 30 - la figure 7 déjà décrite représente un plan de découpe partiel ; - la figure 8 représente une mémoire tampon pour mémoriser les noeuds associés aux plans de découpe partiels dans un mode particulier de réalisation de l'invention ; - la figure 9 déjà décrite représente des plans de découpe partiels 35 isomorphes ; et 3055718 9 la figure 10 représente de façon schématique l'architecture matérielle d'un dispositif de détermination conforme à un mode particulier de réalisation de l'invention. Description détaillée d'un premier mode de réalisation de l'invention En référence à la figure 1, nous allons décrire un exemple de mise en oeuvre de l'invention dans un premier mode particulier de réalisation de l'invention pour déterminer un plan optimisé de découpe par guillotine 10 d'un lot de cinq pièces de verre rectangulaires P11, P12, P13, P21 et P22, devant être empilées sur deux chevalets C1 et C2, en respectant un certain nombre de contraintes, tout en minimisant les pertes de découpe. Ce procédé peut être mis en oeuvre par le dispositif 100 de détermination conforme à l'invention représenté à la figure 10. Ce 15 dispositif présente l'architecture matérielle d'un ordinateur. Il comporte notamment un processeur 101, une mémoire morte de type ROM 102, une mémoire vive de type RAM 103, un clavier 104, un écran 105 et un disque dur 106. La mémoire de type ROM 102 constitue un support au sens de 20 l'invention. Elle comporte un programme d'ordinateur PG comportant des instructions pour l'exécution des étapes du procédé de détermination d'un plan optimisé de découpe selon l'invention. Dans cet exemple, le programme PG contient des instructions pour permettre l'exécution des étapes représentées à la figure 3. 25 Ce programme permet de déterminer un plan optimisé de découpe par guillotine des pièces P11 à P22 dans au moins un plateau de verre. Ce programme comporte un module permettant à l'opérateur de fournir au dispositif 100 au clavier ou par tout autre moyen les contraintes de découpe et de contraintes de positionnement des pièces et un critère 30 d'optimisation. Ces données peuvent être mémorisées sur le disque dur 106. Ce programme comporte aussi un module de création d'un arbre comprenant une racine, des feuilles représentant chacune un plan de découpe complet permettant de découper toutes les pièces du lot, chaque 35 autre noeud de l'arbre représentant un plan de découpe partiel, le plan de découpe associé à un noeud de l'arbre étant obtenu en ajoutant au plan 3055718 10 de découpe partiel associé au noeud père de ce noeud, sous le respect desdites contraintes, la prochaine pièce d'un dit chevalet déterminée selon la séquence prédéterminée de ce chevalet. Dans le mode de réalisation décrit ici, les noeuds de l'arbre sont 5 mémorisés dans la mémoire vive 103. Le programme PG comporte également un module de sélection d'un plan de découpe complet associé à une feuille de l'arbre en fonction du critère d'optimisation mémorisé dans le disque dur 106. Dans le mode de réalisation décrit ici, les noeuds ouverts, 10 autrement dits les noeuds représentant les plans de découpe partiels dont on n'a pas étudié l'extension par une pièce, sont stockés dans un tampon en mémoire vive. Dans le mode de réalisation décrit ici, et comme représenté à la 15 figure 8, la mémoire tampon est organisée sous la forme d'un tableau MT à deux entrées dans lequel : - les lignes permettent de classer les noeuds selon le pourcentage de surface de perte du plan de découpe associé ; les colonnes permettent de classer les noeuds selon le pourcentage 20 de surface utile du plan de découpe associé. Dans l'exemple de la figure 8, le tableau comporte 20 lignes et 20 colonnes, autrement dit un pas de 5%. La valeur de ce pas est paramétrable et peut être différente pour les lignes et les colonnes. Ainsi, à titre d'exemple, un noeud associé à un plan de découpe 25 partiel présentant 91% de surface utile et 6% de surface de perte sera mémorisé dans la case Ti. Ce tableau est mis à jour à chaque création de noeud. Dans le mode de réalisation décrit ici, chaque noeud ouvert est caractérisé par : 30 -un tableau indiquant quelle est la prochaine pièce disponible dans chaque chevalet ; - les cotes à gauche et à droite du niveau de guillotine 1 le plus à droite, respectivement notées x11 et x1r à la figure 7 ; - les cotes en bas et en haut du niveau de guillotine 2 situé le plus haut, 35 respectivement y2f et y2c ;. - la cote à droite de la dernière pièce placée, x3 3055718 11 - la cote au-dessus de la dernière pièce placée, y4. Un noeud fermé est représenté en mémoire par le numéro de chevalet de la dernière pièce posée, et le sens dans lequel elle a été posée. 5 Dans l'exemple de mise en oeuvre décrit ici, les contraintes de positionnement imposent notamment : - que les pièces P11, P12 et P13 soient placées dans cet ordre sur le chevalet Cl; et que les pièces P21 et P22 soient placées dans cet ordre sur le 10 chevalet C2. Et les contraintes de découpe imposent : - au maximum 4 niveaux de découpes; - une largeur minimale des chutes ; - une largeur maximale des travers (ou niveaux). 15 Les figures 2A et 2B représentent deux plans de découpe PD1, PD2 admissibles, à savoir (Fig. 2A) un premier plan de découpe PD1 dans lesquelles toutes les pièces sont placées sur un même plateau PLF1, et un deuxième plan de découpe PD2 dans lesquelles les pièces sont placées sur deux plateaux PLF2, PLF3. 20 A titre d'exemple, dans le plan de découpe PD1 de la figure 2A, on reconnaît : - deux découpes de niveau 1 notées dl, d2 ; - deux découpes de niveau 2 notées d3, d4 - une découpe de niveau 3 notée d5. 25 Dans cet exemple, le plan de découpe PD1 de la figure 2A est préféré au plan de découpe PD2 de la figure 2B car il minimise la surface des chutes engendrées représentée en traits hachurés. La figure 3 représente les principales étapes d'un procédé d'optimisation de découpe de verre conforme à un premier mode de 30 réalisation de l'invention. En référence à cette figure, le procédé comporte une étape E5 de définition de contraintes de découpe et de contraintes de positionnement desdites pièces et d'un critère d'optimisation. Cette étape permet d'initialiser le procédé avec : 35 - le nombre de chevalets, en l'occurrence 2; - l'ordre des pièces P11-P13 et P21-P22 sur ces chevalets ; 3055718 12 la dimension de chacune des pièces ; la dimension des plateaux; le nombre maximum de niveaux de découpes maximum, 4 ; la largeur minimale des chutes ; 5 - la largeur maximum des travers ; et le critère d'optimisation. L'étape d'initialisation E10 est suivie par une étape ElO de création du premier étage L1 de l'arbre T des plans de découpe. On rappelle que conformément à l'invention, les plans de découpe 10 complets sont représentés par les feuilles de l'arbre, les noeuds pères d'une feuille représentant un plan de découpe complet représentant les plans de découpe partiels PDP permettant d'atteindre ce plan de découpe complet. Ainsi, conformément à l'invention,. à partir de la racine de l'arbre T, 15 chaque noeud (fils) est obtenu à partir du noeud précédent (père) en ajoutant au plan de découpe partiel représenté par ce père, une pièce supplémentaire dans le respect des contraintes de positionnement et de découpe. L'ensemble des plans partiels admissibles au premier étage Li de 20 l'arbre T est constitué par l'ensemble des plans partiels pouvant être obtenus en plaçant la première pièce de chacun des chevalets Cl, ou C2, à savoir la pièce P11 ou la pièce P21, dans un coin d'un plateau de verre. Comme représenté à la figure 4, on obtient ainsi quatre plans de découpe partiels PDP1 à PDP4 selon que l'on place la pièce P11 ou la 25 pièce P21 et selon que cette pièce est placée horizontalement ou verticalement. Au premier étage Li, chacun de ces plans de découpe partiels (représenté en traits pointillés) ne comporte qu'un plateau de verre PLF1 (représenté en trait plein). Au cours d'une étape E35, on créé les fils de chacun des noeuds de 30 l'étage L1, ces noeuds constituant un étage L2 de l'arbre T. Sur la figure 4, les fils PDP1/1 à PDP1./12 du noeud PDP1 ont été détaillés, les fils PDP2/1 à PDP4/12 des noeuds PDP2 à PDP4 seulement représentés. Les plans de découpe partiels PDP1/i sont obtenus à partir du plan 35 de découpe partiel PDP1 3055718 13 en considérant que les pièces placées dans le plan partiel PDP1 ont été dépilées des chevalets ; - en considérant tous les plans de découpe pouvant être obtenus en ajoutant au plan de découpe PDP1 chacune des pièces se trouvant 5 au-dessus des chevalets Cl, C2 ainsi considérés dans le respect des contraintes de positionnement et de découpe. Dans l'exemple de la figure 4, les pièces se trouvant au-dessus des chevalets Cl et C2 à l'issue du plan partiel de découpe PDP1 sont la pièce 12 pour le chevalet Cl et la pièce 21 pour le chevalet C2. Dans cet 10 exemple, les plans de découpe admissibles pouvant être obtenus à partir du plan partiel PDP1 en plaçant la pièce 12 ou la pièce 21 sont - le plan de découpe PDP1/1 obtenu en plaçant la pièce 12 à droite de la pièce 11 en position verticale, ce plan ne comportant qu'un seul plateau PLF1 ; 15 le plan de découpe PDP1/2 obtenu en plaçant la pièce 12 à droite de la pièce 11 en position horizontale, ce plan ne comportant qu'un seul plateau PLF1 ; le plan de découpe PDP1/3 obtenu en plaçant la pièce 12 sur la pièce 11 en position horizontale, ce plan ne comportant qu'un seul 20 plateau PLF1 ; le plan de découpe PDP1/4 obtenu en plaçant la pièce 12 sur la pièce 11 en position verticale, ce plan ne comportant qu'un seul plateau PLF1 ; le plan de découpe PDP1/5 obtenu en plaçant la pièce 21 à droite 25 de la pièce 11 en position horizontale, ce plan ne comportant qu'un seul plateau PLF1. ; - le plan de découpe PDP1/6 obtenu en plaçant la pièce 21 à droite de la pièce 11 en position verticale, ce plan ne comportant qu'un seul plateau PLF1; 30 - le plan de découpe PDP1/7 obtenu en plaçant la pièce 21 sur la pièce 11 en position horizontale, ce plan ne comportant qu'un seul plateau PLF1 ; le pian de découpe PDP1/8 obtenu en plaçant la pièce 12 sur la pièce 11 en position verticale, ce plan ne comportant qu'un seul 35 plateau PLF1 ; 3055718 14 le plan de découpe PDP1/9 obtenu en créant un nouveau plateau PLF2 comportant la pièce 12 en position verticale PLF ; le plan de découpe PDP111.0 obtenu en créant un nouveau plateau PLF2 comportant la pièce 12 en position horizontale; le plan de découpe PDP1/11 obtenu en créant un nouveau plateau PLF2 comportant la pièce 21 en position horizontale; le plan de découpe PDP1/12 obtenu en créant un nouveau plateau PLF2 comportant la pièce 21 en position verticale. 10 Dans cet exemple l'étage L2 comporte également : tous les plans de découpe partiels admissibles PDP2/1 à PDP2/12 pouvant être obtenus en ajoutant la pièce 12 ou 21 au plan de découpe partiel PDP2 ; - tous les plans de découpe partiels admissibles PDP3/1 à PDP3/12 15 pouvant être obtenus en ajoutant la pièce 11 ou 22 au plan de découpe partiel PDP3 ; tous les plans de découpe partiels admissibles PDP4/1 à PDP4/12 pouvant être obtenus en ajoutant la pièce 11 ou 22 au plan de découpe partiel PDP4. 20 En répétant ce processus de façon itérative jusqu'à vider entièrement les chevalets Cl et C2 de leurs pièces (test E90) on obtient un arbre T à 5 étages dont chacune des feuilles correspond à un plan de découpe complet vérifiant les contraintes de découpe et de placement. Les plans de découpe complets PD1 et PD2 des figures 2A et 2B font partie de 25 ces feuilles. Le procédé selon ce premier mode de réalisation comporte une étape E100 au cours de laquelle on sélectionne parmi toutes les feuilles de l'arbre T le plan de découpe complet qui minimise la surface de chutes. Ce plan de découpe permet d'optimiser la découpe de plateaux de 30 verre pour constituer les chevalets Cl et C2. Description détaillée d'un deuxième mode de réalisation Lorsque les lots sont complexes, le temps de calcul nécessaire pour 35 créer l'arbre T complet conformément au premier mode de réalisation de l'invention peut être excessivement long. 3055718 15 Dans un deuxième mode particulier de réalisation de l'invention, qui va maintenant être décrit en référence à la figure 5, on limite la durée totale d'exécution du procédé et on renonce à créer l'ensemble des noeuds de l'arbre en sélectionnant à chaque itération, parmi les noeuds de l'arbre 5 déjà créés, un noe.ud courant représentant un plan de découpe partiel prometteur dont on crée les fils. Ce procédé peut être mis en oeuvre par le dispositif 100 de détermination conforme à l'invention représenté à la figure 10, mais dans cet exemple, le programme PC contient des instructions pour permettre 10 l'exécution des étapes représentées à la figure 5. Dans le mode de réalisation décrit ici, chaque noeud ouvert est en outre caractérisé par : - le numéro du chevalet, le sens de placement et l'assiette de la dernière pièce placée ; 15 - le noeud parent, qui correspond au plan de découpe partiel sans la dernière pièce placée ; et - une série d'attributs secondaires mis à jour pour guider le parcours de l'arbre à savoir les chutes acquises, l'aire de plateau occupée, correspondant à la somme des aires des pièces du plan partiel pour les 20 pertes géométriques, le nombre de plateaux utilisés, sa position par rapport à la pièce précédente (à droite ou au-dessus). Dans le mode particulier de réalisation décrit ici, le procédé comporte deux critères de sélection pour sélectionner ce plan de découpe partiel prometteur, à savoir : 25 un critère dit « critère de chute minimum » consistant à sélectionner parmi tous les plans de découpe partiels déjà crées celui pour lequel le rapport surface de perte / surface utile est minimal ; - un critère dit « critère de surface maximum » consistant à 30 sélectionner parmi tous les plans de découpe partiels déjà crées celui pour lequel la surface utile est la plus importante. Dans le mode de réalisation décrit ici, après la création du premier étage L1 (voir étape E10 du premier mode de réalisation), on initialise le critère de sélection, au cours d'une étape E20, au « critère de chute 35 minimum ». Au cours de cette même étape E20, on initialise un compteur de temps à 0. 3055718 16 Dans le mode de réalisation décrit ici, chaque itération comporte une étape générale E25 au cours de laquelle on vérifie s'il convient de changer de critère de sélection. Cette étape est décrite en référence à la figure 6 dans un mode 5 particulier de réalisation de l'invention. Au cours d'une étape E251, on initialise une valeur TMAX en fonction du critère de sélection courant. Dans cet exemple, si le critère de sélection courant est « critère de chute minimum », TMAX égale 10s, et si le critère de sélection courant est « critère de surface maximum», TMAX 10 égale 20s. Au cours d'une étape E252, on vérifie si le compteur de temps t initialisé à l'étape [20 est supérieur à cette durée TMAX. Si tel n'est pas le cas, l'étape générale E25 se termine sans changement de critère de sélection ni réinitialisation du compteur de temps t. 15 Si le compteur de temps est supérieur à la durée TMAX, on détermine à l'étape E253 quel critère de sélection utiliser pour la sélection du prochain noeud dont on créera les fils. Dans le mode de réalisation décrit ici : - on retient (étape E254) le critère « critère de surface maximum » si 20 le critère courant est le critère « critère de chute minimum » ou si le nombre de noeuds de l'arbre T est supérieur à une valeur NMAX prédéfinie. A cet effet, on utilise dans ce mode de réalisation une variable globale nb_noeuds qui mémorise, dans la mémoire vive 103 le nombre de noeuds de l'arbre T, cette variable ayant, dans 25 cet exemple, la valeur 4 à l'issue de l'étape E10 de création du premier étage L1 ; - on retient (étape E255) le critère «critère de chute minimum » dans les autres cas. On réinitialise le compteur de temps t à 0 au cours d'une étape 30 E256 et l'étape générale [25 de changement de critère se termine. De retour à la figure 5, au cours d'une étape E30, on sélectionne parmi les noeuds de l'arbre déjà créés, un noeud courant en fonction du critère de sélection retenu à l'étape E25 : - si le critère de sélection est « critère de chute minimum », on 35 sélectionne le noeud de l'arbre représentant le plan de découpe pour lequel le rapport surface de perte / surface utile est minimal. 3055718 17 Dans le mode particulier de réalisation de la figure 8, cela revient à sélectionner un noeud mémorisé dans une case la plus haute du tableau. Si plusieurs possibilités se présentent, on choisit un noeud dans une case la plus à droite (pourcentage de surface utile 5 maximum) ; si le critère do sélection est « critère de surface maximum », on. sélectionne le noeud de l'arbre représentant le plan de découpe pour lequel la surface utile est la plus importante. Dans le mode particulier de réalisation de la figure 8, cela revient à sélectionner 10 un noeud mémorisé dans une case la plus à droite du tableau. Si plusieurs possibilités se présentent, on choisit un noeud dans une case la plus haute (pourcentage de surface de perte minimum). Au cours d'une étape E35, on créé les fils du noeud courant. Cette étape est identique à l'étape E35 décrite en référence à la figure 3. Au 15 cours de cette même étape, on calcule et on mémorise les attributs de chacun des noeuds créés et on met à jour la variable nb_noeuds représentative du nombre de noeuds de l'arbre. Dans ce mode de réalisation, au cours d'une étape E40, on supprime le noeud courant. 20 Au cours d'une étape E45, on vérifie si un ou plusieurs noeuds créés à l'étape E35 sont des feuilles de l'arbre, autrement dit s'ils contiennent l'ensemble des pièces des chevalets. Si tel est le cas, on conserve en mémoire, à l'étape E50, la feuille associée au plan de découpe complet correspondant à la meilleure 25 solution obtenue jusqu'alors, c'est-à-dire dans cet exemple minimisant la surface de chutes. Les autres feuilles peuvent être supprimées. Lorsqu'une première feuille est obtenue, cette feuille est gardée en mémoire. Au cours d'une étape E55, on vérifie si une feuille obtenue à l'étape E35 correspond à une solution améliorée, et si tel est le cas, on supprime 30 de l'arbre T, au cours d'une étape E60, tous les noeuds dont la surface des chutes acquises est supérieure à la surface de perte de cette feuille. Dans le mode de réalisation décrit ici, le procédé d'optimisation comporte une étape E65 au cours de laquelle on vérifie que in durée d'exécution totale du procédé ne dépasse pas une durée DMAX prédéfinie, 35 par exemple une heure. A cet effet on peut utiliser un compteur de temps global tps_calc initialisé à l'étape E5. 3055718 8 S'il est déterminé à l'étape E65 que la durée DMAX n'a pas été atteinte, le procédé se poursuit en bouclant sur l'étape E25 de détermination du critère de sélection du prochain noeud. Lorsqu'il est déterminé que la durée DN1AX a été atteinte, le procédé retourne à l'étape E70 le plan de découpe complet correspondant à la meilleure solution mémorisée à l'étape E50. Description die-taillée d'un troisième mode réalisation 10 Dans un mode particulier de réalisation, le procédé d'optimisation selon l'invention évite ou minimise la création dans l'arbre T de noeuds correspondants à des plans de découpe partiels isomorphes, à savoir des plans de découpe comportant les mêmes pièces, présentant la même surface de chutes acquises et les mêmes valeurs pour x11, x3, x1r, y2f, y4 15 et y2c. Dans ce troisième mode de réalisation décrit ici, à chaque étape de E35 de création d'un noeud, on s'assure avant de créer un noeud qu'il ne représente pas un plan de découpe partiel ou complet isomorphe d'un plan de découpe associé à un noeud déjà créé clans l'arbre. 20 Pour cela, dans le mode de réalisation décrit ici, on ajoute des règles lexicographiques aux contraintes de positionnement. Par exemple, on peut ajouter deux règles selon lesquelles : Si on place la dernière pièce au-dessus de la précédente, le numéro de chevalet de cette dernière pièce doit être inférieur au numéro de 25 chevalet de la pièce précédente ; Si on place la dernière pièce à droite de la précédente, le numéro de chevalet de cette dernière pièce doit être supérieur ou égal au numéro de chevalet de la pièce précédente. 30 Afin de réduire le risque de conserver des plans de découpe isomorphes, on peut aussi par exemple décider de n'ouvrir un nouveau niveau 1 que si au moins une des deux conditions suivantes est réunie : - Condition 1: les K niveaux 1 précédents comportent au moins une pièce devant être disposée sur un même chevalet. A titre d'exemple, dans le 35 contexte de la figure 2A, avec K=2, les pièces des deux niveaux 1 précédents sont respectivement {P11, P21, P22} et {P12, P13} ; chacun 3055718 19 de ces niveaux 1 comporte par conséquent au moins une pièce du chevalet Cl de sorte que la condition 1 est remplie ; - Condition 2 : l'ordre des chevalets de la dernière pièce posée pour les Q derniers niveaux 1 est croissant. A titre d'exemple., dans le contexte de la figure 2A, avec Q=2, les dernières pièces posées dans les deux derniers niveaux 1 sont respectivement P22 et P13; l'ordre des chevalets (C2, Cl) est décroissant de sorte que la condition 2 n'est pas remplie. REVENDICATIONS1. Procédé mis en oeuvre par ordinateur pour déterminer un plan 5 optimisé de découpe par guillotine d'un lot de pièces de verre rectangulaires dans au moins un plateau de verre, les pièces étant destinées, après découpe, à être empilées sur au moins un chevalet (Ci), les pièces d'un chevalet devant être placées sur ledit au moins un plateau pour découpe selon une séquence prédéterminée pour ce chevalet, ledit 10 procédé comportant : - une étape (E5) de définition de contraintes de découpe et de contraintes de positionnement desdites pièces et d'un critère d'optimisation ; - la création (E10, E35) d'un arbre (T) comprenant une racine, des feuilles représentant chacune un plan de découpe complet permettant de 15 découper toutes les pièces dudit lot, chaque autre noeud de l'arbre représentant un plan de découpe partiel, le plan de découpe associé à un noeud de l'arbre étant obtenu (E35) en ajoutant au plan de découpe partiel associé au noeud père de ce noeud, sous le respect desdites contraintes, la prochaine pièce d'un dit chevalet déterminée selon la 20 séquence prédéterminée de ce chevalet ; et - une étape (E100) de sélection d'un plan de découpe complet associé à une feuille de l'arbre en fonction dudit critère d'optimisation. 2. Procédé selon la revendication 1, dans lequel le critère 25 d'optimisation est choisi parmi : - un critère visant à minimiser le nombre de plateaux de verre utilisés ; - un critère visant à minimiser une surface totale de perte engendrée par la découpe. 30 3. Procédé selon la revendication 1 ou 2, dans lequel lesdites contraintes de découpe peuvent être choisies parmi: - un nombre maximum de niveaux de découpe ; - une largeur minimum des chutes; - une largeur maximum d'un niveau de découpe ; 35 - une direction du premier rompage. 3055718 21 4. Procédé selon l'une quelconque des revendications 1 à 3, dans lequel lesdites contraintes de positionnement peuvent être choisies parmi l'orientation des pièces dans un plateau, la position relative des pièces d'un même plateau en fonction de leur niveau, le nombre maximum desdits au moins un plateau de verre. 5. Procédé selon l'une quelconque des revendications 1 à 4 dans lequel ladite création de l'arbre comporte - une étape (E10) consistant à créer, sous ladite racine et pour chacun desdits chevalets (Cl, C2) un noeud associé à un plan de découpe partiel pour chacune des positions admissibles de la première pièce dudit chevalet sous le respect desdites contraintes ; et - au moins une itération, chaque itération comportant - une étape (E30) de sélection d'un noeud courant de l'arbre en fonction de caractéristiques du plan de découpe partiel représenté par ce noeud ; et - une étape (E35) de création d'au moins un noeud fils dudit noeud courant, le plan de découpe associé audit noeud fils étant obtenu (E35) en ajoutant au plan de découpe partiel associé audit noeud courant, et sous le respect desdites contraintes, la prochaine pièce d'un dit chevalet prise selon la séquence prédéterminée de ce chevalet. 6. Procédé selon la revendications 5, caractérisé en ce qu'il 25 comporte une étape (E60) d'arrêt desdites itérations si la durée d'exécution du procédé est supérieure à une durée (DMAX) prédéfinie. 7. Procédé selon la revendication 5 ou 6, caractérisé en ce que ledit noeud courant est sélectionné (E30) 30 - selon un premier critère dit « critère de chute minimum » consistant à sélectionner le noeud associé au plan de découpe pour lequel le rapport une surface de perte et la surface totale occupée par les pièces dudit plan est minimal ; ou selon un deuxième critère dit « critère de surface maximum » 35 consistant à sélectionner le noeud associé au plan de découpe pour lequel la surface utile est la plus importante. 3055718 22 8. Procédé selon l'une quelconque des revendications 1 à 7, dans lequel seule la feuille associée au plan de découpe complet maximisant ledit critère d'optimisation est mémorisée (E50), les autres feuilles étant supprimées. 9. Procédé selon l'une quelconque des revendications 1 à 8, caractérisé en ce qu'il comporte une étape (EGO) de suppression des noeuds de l'arbre associés à des plans de découpe partiels pour lesquels la 10 surface des chutes acquises est supérieure à la surface de perte d'un plan de découpe complet associé à une dite feuille. 10. Procédé selon l'une quelconque des revendications 1 à 9, caractérisé en ce que lesdites contraintes de positionnement comportent 15 au moins une contrainte lexicographique portant sur un numéro desdits chevalets pour éviter ou minimiser la création de noeuds correspondants à des plans de découpe partiels isomorphes. 20 11. Procédé selon l'une quelconque des revendications 1 à 10, dans lequel, à chaque création de noeud, on classe ledit noeud en fonction d'au moins une caractéristique du plan de découpe représenté par ce noeud, ladite au moins une caractéristique étant suffisante pour sélectionner ledit plan de découpe complet. 12. Procédé selon les revendications 5 et 11, dans lequel ladite au moins une caractéristique utilisée pour ledit classement est ladite au moins une caractéristique utilisée au cours de ladite étape de sélection du noeud courant de l'arbre. 13. Dispositif de détermination d'un plan optimisé de découpe par guillotine d'un lot de pièces de verre rectangulaires dans au moins un plateau de verre (PLF), les pièces étant destinées, après découpe, à être empilées sur au moins un chevalet (Ci), les pièces d'un chevalet devant être placées sur ledit au moins un plateau pour découpe selon une séquence prédéterminée pour ce chevalet, ledit dispositif comportant 3055718 23 - un module de définition de contraintes de découpe et de contraintes de positionnement desdites pièces et d'un critère d'optimisation ; - un module de création d'un arbre (T) comprenant une racine, des feuilles représentant chacune un plan de découpe complet permettant de 5 découper toutes les pièces dudit lot, chaque autre noeud de l'arbre représentant un plan de découpe partiel, le plan de découpe associé à un noeud de l'arbre étant obtenu (E35) en ajoutant au plan de découpe partiel associé au noeud père de ce noeud, sous le respect desdites contraintes, la prochaine pièce d'un dit chevalet déterminée selon la 10 séquence prédéterminée de ce chevalet ; et - un module de sélection d'un plan de découpe complet associé à une feuille de l'arbre en fonction dudit critère d'optimisation. 14. Programme d'ordinateur (PG) comportant des instructions pour 15 l'exécution des étapes du procédé de détermination d'un plan optimisé de découpe selon l'une quelconque des revendications 1 à 12 lorsque ledit programme est exécuté par un ordinateur. 15. Support d'enregistrement (103) lisible par un ordinateur (100) 20 sur lequel est enregistré un programme d'ordinateur (PG) comportant des instructions pour l'exécution des étapes du procédé de détermination d'un plan optimisé de découpe selon l'une quelconque des revendications 1 à 12. 25 16. Procédé de découpe par guillotine d'un lot de pièce de verres rectangulaires dans au moins un plateau de verre, caractérisé en ce qu'il comporte : - la mise en oeuvre d'un procédé de détermination d'un plan optimisé de découpe selon l'une quelconque des revendications 1 à 12 ; 30 - ledit plan optimisé étant utilisé au cours d'une phase de découpe dudit plateau et au cours d'une phase de rompage dudit plateau. 17. Procédé de découpe selon la revendication 16 dans lequel ledit lot est déterminé par la mise en oeuvre d'un procédé de détermination d'un 35 plan optimisé de découpe selon l'une quelconque des revendications 1 à 12.