Bonjour la communauté
J'ai une question sur le calepinage dans OPL. J'ai beau changer tous les paramètres je n'arrive à pas changer la proposition de calepinage qui ne me permet pas (je crois) d'optimiser mes chutes (longues).
Je poste la photo pour illustrer cette question.
Il me semble que le résultat de 2 planches débitées en 4xB et les deux dernières avec les 4 A (soit 3xA + 1A), laisse une chute plus importante que le calepinage proposé.
Bon j'ai essayée d'être claire, mais dites moi si je dois préciser.
Merci d'avance pour vos réponses
1 réponse
Ta remarque est justifiée. OCL utilise une méta-heuristique, une collection de stratégies pour résoudre le problème et choisi "la meilleure solution", pour calculer le calepinage 2D. L'algorithme reste cependant prévisible, dans la mesure où il livre toujours le même résultat sur n'importe quel ordinateur (rien n'est aléatoire, ni dans le temps, ni dans l'espace). Ces stratégies ont l'inconvénient d'être parfois trop gloutonnes, c'est-à-dire de vouloir remplir l'espace trop vite en passant à côté d'une solution qui pourrait être meilleure. La seule solution serait une recherche exhaustive de toutes les possibilités, mais ça exploserait nos ordinateurs assez vite et aucun utilisateur n'est prêt à attendre 24h que OCL aye fait son calepinage. On aurait pu implémenter un algorithme qui fait une recherche exhaustive pour un nombre de pièces < X, mais cela l'aurait rendu plus compliqué et que très rarement meilleur.
Pour ceux intéressé par la complexité, le problème du calepinage est NP-complet et même la vérification efficace d'une solution est un problème "exponentiel".
Pour le cas en 1D, j'ai utilisé une variante différente, d'ailleurs si tu configures tes planches en barre de section 200 x 26 avec 733 x 8 pièces et 827 x 4 pièces à placer dans une barre type de 3000, tu retrouveras la solution optimale que tu voulais obtenir, soit 2 barres avec les 8 pièces de 733, 1 barre avec 3 pièces de 827 et 1 barre avec une pièce de 827.
La variante la plus simple de ton problème est la suivante:
- 2 pièces de longeur 3
- 4 pièces de longeur 2
à placer dans une barre de longueur 7. On trouvera facilement que le placement [3, 2, 2] et [3, 2, 2] n'a besoin que de 2 barres. Si on trie les pièces par ordre décroissant et on les place dans les barres, on trouvera [3, 3] et [2, 2, 2] et [2], donc 3 barres, 1 de trop.
Le problème du calepinage en 1D est également NP-complet (du moins sa variante de décision).
Donc oui, il y a certainement plein de cas où le calepinage d'OCL ne trouve pas la solution optimale en terme de panneau ou de barre. Il y a des algorithmes OpenSource qui trouvent de très bonnes solutions, mais ils sont souvent basés sur des recherches exhaustives en limitant le temps de recherche ou sur des recherches aléatoires. Le calepinage d'OCL n'est jamais enregistré dans le modèle, donc nous devons garantir qu'il soit toujours le même, en passant d'une croûte d'ordi à la fusée du joueur.
Martin Müller Par curiosité, peux-tu nous en dire plus sur la définition de la "meilleure solution" que vous avez choisie en 1D et en 2D ? Quels sont les algos du coup ?
Après une telle explication, on est sans voix, et je n'ai rien à ajouter. De toute façon je n'avais pas d'avis sur la question. Merci Martin Müller pour ces précisions!
Pour le calepinage 1D, on a utilisé deux algorithmes:
- un algorithme de programmation dynamique qui résoud le problème de la somme des sous-ensembles lorsque le nombre de pièces est < 80 (valeur un peu arbitraire). Ce problème est assez similaire au Bin Packing 1D dans la mesure où on cherche à maximiser une somme de longueurs de pièces dans une barre de longueur donnée. Afin de ne pas être trop glouton, l'algorithme décide avoir trouvé une solution lorsqu'au moins 95% de la barre est pleine.
- lorsque le nombre de pièces est >= 80 et/ou après 5 secondes de temps de calcul, on passe à une heuristique First Fit Decreasing - FFD (trié par ordre descendant de longueur, puis assigné à la première barre possible). C'est avec cette variante qu'on trouvera la solution [3, 3], [2, 2, 2], [2] au problème mentionné dans ma première réponse.
La performance des algorithmes dépend du nombre de pièces et du nombre de pièces différentes et bien sûr aucune garantie de trouver la solution optimale. On sait que si OPT(L) est le nombre optimal de barres FFD trouvera une solution utilsant au maximum 11/9*OPT(L) + 6/9 de barre. Vous me direz que si OPT(L) = 1, alors la solution trouvée par FFD sera peut être 2, ce que représente le double (ou 100%). Ben oui! mais c'est pas moi qui les ai fait ces problèmes, c'est le bon Dieu!
Pour le calepinage, nous n'avons pas implémenté de préférence du style "regrouper toutes les pièces de même longueur sur une même barre" pour ne pas pénaliser la recherche d'une bonne solution.
Pour le calepinage 2D, on a utilisé plusieurs heuristiques pour résoudre un problème un peu plus restrictif que le calepinage 2D, car les coupes doivent être de type guillotine (de part en part d'une pièce, car pas de coupe à 90° au milieu d'un panneau possible avec une scie circulaire). Par rapport au programme disponible sur par ex. github, on a rajouté la possibilité d'utiliser des chutes et aussi de regrouper des pièces identiques en donnant la préférence à des coupes horizontales ou verticales (empiler les pièces). Il y a bien sûr aussi la notion de grain.
En choisissant un ordre de tri au départ, l'algorithme essaie de placer les pièces en commençant en haut à gauche et essayant une coupe horizontal d'abord, puis une verticale ou le contraire, ... en calculant 30 à 40 solutions possibles.
Une solution "optimale" est alors choisie parmi les solutions remplissant les critères suivants:
- minimum de pièces non placées,
- minimum de panneaux utilisés,
- chute la plus longue,
- chute la plus large,
- et finalement, le plus petit nombre de chutes (indicateur pour une meilleure coupe).
La solution est "souvent" très bonne, parfois moins bonne.
Pour la version 2.0 d'OCL, l'algorithme va changer un peu, on aura plus besoin de choisir l'ordre des pièces. Il y aura deux options d'optimization moyen et avancé, ainsi que le choix d'empiler les pièces, c'est tout! On calculera plusieurs ordre de pièces pour un total de 48 à 1152 solutions. La sélection de la meilleure solution ce fait sur la base de deux critères:
- une mesure de compacité (ou taux de remplissage), on cherche à éviter les trous dans le calepinage et à faire en sorte que les chutes se trouvent le plus à droite et le plus bas possible (si l'origine est en haut à gauche).
- le nombre de chutes minimale (moins c'est mieux, même si la surface est plus grande - on préfère en général une chute de 1m^2 plutôt que 9 chutes de 0.1m^2.
Licence
Pour suivre les réponses,
je me suis déjà confronté au problème, et je l'ai réglé manuellement (papier/crayon)