Gomory⎯
Algorithme de découpe guillotine two-stage pour l'optimisation de matériaux.
Implémentation open source basée sur les travaux de Ralph E. Gomory (1958). Complexité O(n log n). Taux d'utilisation moyen: 70-85%.
IMPLÉMENTATION TECHNIQUE
Algorithme
tryOneBoardTwoColumns() ├─ Division en colonnes ├─ Empilement NFDH └─ Optimisation rotation
Performance
Temps: <100ms (n<1000) Espace: O(n) Coupes: 20-40 par planche Perte: 15-30%
Contraintes
• Coupes guillotine uniquement • Processus two-stage • Gestion du trait de scie • Support rotation 90°
FONCTIONNALITÉS PRINCIPALES
Optimisation guillotine two-stage
Partitionnement vertical en colonnes suivi d'un empilement horizontal dans chaque colonne. Réduit la complexité computationnelle tout en maintenant des ratios de perte acceptables.
Next Fit Decreasing Height (NFDH)
Algorithme d'empilement heuristique avec ratio d'approximation prouvé. Pièces triées par hauteur décroissante pour une utilisation optimale des étagères.
Compensation du trait de scie
Calcul automatique de l'espacement pour la largeur de lame. Valeurs de trait configurables de 0-10mm avec précision sub-millimétrique.
Export multi-format
Génération PDF avec jsPDF, rastérisation PNG via html2canvas, export SVG natif. Plans de découpe prêts pour la production avec annotations dimensionnelles.
STACK
RÉFÉRENCES
[1]
Gomory, R. E. (1958). "Outline of an algorithm for integer solutions to linear programs". Bulletin of the American Mathematical Society. 64 (5): 275–278.
[2]
Gilmore, P. C.; Gomory, R. E. (1961). "A Linear Programming Approach to the Cutting-Stock Problem". Operations Research. 9 (6): 849–859.
[3]
Lodi, A.; Martello, S.; Monaci, M. (2002). "Two-dimensional packing problems: A survey". European Journal of Operational Research. 141 (2): 241–252.
CONTRIBUER
$ git clone https://github.com/rmzlb/gomory.git $ cd gomory $ npm install $ npm run dev # Create feature branch $ git checkout -b feature/your-feature # Run tests $ npm test # Submit PR $ git push origin feature/your-feature
SUPPORT
Si ce projet vous est utile dans vos travaux ou production, vous pouvez soutenir son développement.