Méthodologie

Méthodologie

Fondements mathématiques et implémentation technique

L'optimiseur de découpe Gomory implémente un algorithme de découpe guillotine two-stage combiné avec l'heuristique NFDH (Next Fit Decreasing Height), fournissant une approximation en temps polynomial pour le problème NP-difficile du bin packing 2D.

Fondements Mathématiques

Formulation de Programmation Linéaire

Définition du problème:

Variables de décision:

xijk = 1 si la pièce i est placée sur la planche j en position k

yj = 1 si la planche j est utilisée

sjk = position de début de la bande k sur la planche j

hjk = hauteur de la bande k sur la planche j

Fonctions objectif (selon le mode):

1. Minimiser les planches utilisées:

min z = Σj∈B yj

2. Minimiser les chutes (maximiser utilisation):

min w = Σj∈B yj · (W × H) - Σi∈P wi × hi

où W×H = surface planche, wi×hi = surface pièce i

3. Minimiser les coupes (objectif multi-critères):

min c = α · Σj∈B cutsj + β · Σj∈B yj

où α, β sont des poids de pondération

Contraintes du problème:

Contraintes générales:

1. Satisfaction de la demande:

Σj∈B Σk∈K xijk = qi ∀i ∈ P

Chaque pièce i doit être produite qi fois

2. Non-chevauchement horizontal:

xi + wi + kerf ≤ xi' ∨ xi' + wi' + kerf ≤ xi

Pour toutes pièces i, i' dans la même bande

3. Non-chevauchement vertical:

sjk + hjk + kerf ≤ sj(k+1) ∀j,k

Les bandes ne se chevauchent pas verticalement

4. Contraintes de guillotine (2-stage):

∀ coupe horizontale: traverse toute la largeur

∀ coupe verticale dans bande: de haut en bas de la bande

5. Contraintes de dimensions:

xi + wi ≤ W ∀i placée

yi + hi ≤ H ∀i placée

6. Rotation (si autorisée):

ri ∈ {0,1} où ri=1 ⟹ (wi, hi) ← (hi, wi)

Contraintes mode 2-colonnes:

Partitionnement vertical forcé:

∃ xsplit ∈ [min(wi), W - min(wi)]

∀i: xi + wi ≤ xsplit ∨ xi ≥ xsplit + kerf

Force exactement 2 colonnes avec position de split optimisée

Modes d'Optimisation

Mode Standard

Algorithme: NFDH modifié

Complexité: O(n log n)

Utilisation: 70-85%

Placement libre avec tri par hauteur décroissante

Mode 2-Colonnes

Algorithme: Split vertical + NFDH

Complexité: O(n² log n)

Utilisation: 60-80%

Optimise position du split pour minimiser les chutes

Mode Avancé V3 BETA

Algorithme: Multi-colonnes dynamiques

Complexité: O(n² × strategies)

Utilisation: 75-95%

Multi-start avec 5 stratégies de tri différentes

Algorithme V3 - Multi-Start Optimization

Stratégies de tri multi-start:

1. HEIGHT_DESC:

Sort by h descending, then w descending

Optimise pour bandes horizontales

2. WIDTH_DESC:

Sort by w descending, then h descending

Optimise pour colonnes verticales

3. AREA_DESC:

Sort by w×h descending

Place grandes pièces d'abord

4. MAX_DIM_DESC:

Sort by max(w,h) descending

Équilibre entre dimensions

5. RANDOM_SHUFFLE:

Random permutation with seed

Exploration stochastique de l'espace de solutions

Création dynamique de colonnes:

function createDynamicColumns(pieces, board):

columns = []

for piece in pieces:

bestColumn = findBestFit(columns, piece)

if not bestColumn:

newColumn = createColumn(piece.width)

columns.append(newColumn)

placePieceInColumn(piece, bestColumn)

return optimizeColumnWidths(columns)

Analyse de Complexité

Complexité Computationnelle

Tri initial: O(n log n)O(n log n)

Empilement NFDH par colonne: O(n)O(n)

2-colonnes (tous splits):O(n² log n)

V3 multi-start:O(s·n log n)

Complexité spatiale: O(n)O(n)

Garanties théoriques

Standard (NFDH):

U ≥ (1/2) · OPT - hmax/H

2-colonnes:

U ≥ (1/3) · OPT (pire cas avec split fixe)

V3 avancé:

E[U] ≥ maxs∈strategies(Us)

Détails de l'Algorithme

1

Étape 1: Prétraitement

Tri des pièces par hauteur décroissante (ou largeur si rotation activée)

pieces.sort((a,b) => max(b.h, b.w) - max(a.h, a.w))
2

Étape 2: Génération de Colonnes

Génération de colonnes verticales avec stratégie first-fit

Largeur colonne = max(piece.largeur) + trait_scie
C1
C2
C3
C4
3

Étape 3: Empilement en Étagères (NFDH)

Empilement des pièces en étagères horizontales dans chaque colonne

Si piece.hauteur > hauteur_restante_étagère: créer_nouvelle_étagère()
4

Étape 4: Optimisation

Application d'améliorations par recherche locale et optimisation de rotation

utilisation = Σ(surface_pièce) / (largeur_planche × hauteur_planche)

Implémentation

Structures de Données

Représentation des pièces:

interface PlacedPiece {
  id: string
  specId: string
  w: number
  h: number
  rotated: boolean
  x: number
  y: number
  boardIndex: number
  stripIndex: number
}

Disposition de la planche:

interface BoardLayout {
  index: number
  strips: Strip[]
  width: number
  height: number
  columnSplits?: number[]
  utilization: number
}

Strip (Bande horizontale):

interface Strip {
  x: number
  width: number
  y: number
  height: number
  pieces: PlacedPiece[]
  usedWidth: number
}

Configuration d'optimisation:

interface OptimizationConfig {
  boardWidth: number
  boardHeight: number
  kerf: number
  allowRotate: boolean
  forceTwoColumns: boolean
  useAdvancedOptimizer: boolean
  objective: 'waste' | 'cuts' | 'balanced'
}

Métriques de Performance

60-95%
Utilisation selon mode
<500ms
Temps moyen (V3: 2-5s)
O(n)
Utilisation mémoire: O(n) où n = nombre de pièces

Standard:

70-85% utilisation, rapide

2-colonnes:

60-80% utilisation, découpe simple

V3 avancé:

75-95% utilisation, plus lent

Améliorations Récentes (2025)

✓ Optimiseur V3 multi-colonnes

Création dynamique de colonnes avec multi-start pour exploration optimale

✓ Mode 2-colonnes intelligent

Optimisation automatique de la position du split vertical

✓ Historique de configurations

Sauvegarde locale des 10 dernières optimisations avec restauration

✓ Comptage amélioré des coupes

Détection des coupes inférieures pour pièces plus courtes que la bande

✓ Interface utilisateur enrichie

Cartes d'information au survol des pièces découpées avec détails complets

Références Académiques

[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]

Coffman Jr, E. G., Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1980). "Performance bounds for level-oriented two-dimensional packing algorithms". SIAM Journal on Computing, 9(4), 808-826.

[3]

Lodi, A., Martello, S., & Monaci, M. (2002). "Two-dimensional packing problems: A survey". European Journal of Operational Research, 141(2), 241-252.

[4]

Ntene, N., & van Vuuren, J. H. (2009). "A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem". Discrete Optimization, 6(2), 174-188.

[5]

Dyckhoff, H. (1990). "A typology of cutting and packing problems". European Journal of Operational Research, 44(2), 145-159.

Essayer l'optimiseur →