Calcolo di una lista di taglio con la minima quantità di scarti di taglio

Question

Sto lavorando ad un progetto in cui produco una lista di taglio per l'estrusione di alluminio.

Le estrusioni di alluminio sono disponibili in lunghezze di 5 m.

Ho un elenco di lunghezze più piccole che devono essere tagliate dalle lunghezze di 5 m di estrusioni di alluminio.

I pezzi più piccoli devono essere tagliati nell'ordine che produce la minor quantità di scarti tagliati dalle lunghezze di 5 m degli estrusi di alluminio.

Attualmente ordino la lista di taglio in modo tale che generalmente la lunghezza più lunga tra quelle più piccole venga tagliata per prima e quella più corta tra le lunghezze più piccole venga tagliata per ultima.L'eccezione a questa regola è che ogni volta che un pezzo più corto non si adatta a ciò che resta dei 5 m di estrusione di alluminio, utilizzo il pezzo più corto più lungo che si adatta.

Questo sembra produrre un elenco di taglio molto efficiente (con pochissimi scarti di taglio) e non richiede molto tempo per essere calcolato.Immagino, tuttavia, che anche se la lista di taglio lo sia molto efficiente, non è necessariamente il maggior parte efficiente.

Qualcuno conosce un modo per calcolare la lista di taglio più efficiente che possa essere calcolata in un lasso di tempo ragionevole?

MODIFICARE:Grazie per le risposte, continuerò a utilizzare l'approccio "avido" poiché sembra che stia facendo un ottimo lavoro (supera qualsiasi tentativo umano di creare una lista di taglio efficiente) ed è molto veloce.

Answer 1

Questo è un problema classico e difficile da risolvere in modo efficiente.L'algoritmo che descrivi suona come a Algoritmo goloso.Dai un'occhiata a questo articolo di Wikipedia per ulteriori informazioni: Il problema del materiale da taglio

Answer 2

Temo che non ci siano idee specifiche su questo problema, ma potresti esaminare un "algoritmo genetico' (che sarebbe andato qualcosa come questo)...

Posiziona le lunghezze da tagliare in ordine casuale e assegna a quell'ordine un punteggio in base alla corrispondenza con la tua soluzione ideale (0% di scarto, presumibilmente).

Quindi, apporta in modo iterativo modifiche casuali all'ordine e riesegui il punteggio.Se il punteggio è più alto, abbandona il risultato.Se il punteggio è inferiore, conservalo e usalo come base per il tuo prossimo calcolo.Continua finché non raggiungi il punteggio entro limiti accettabili.

Answer 3

Ciò che hai descritto è effettivamente classificato come a Taglio delle scorte problema, come Impennata menzionato, e non a Imballaggio del contenitore problema perché si cerca di minimizzare gli scarti (somma degli avanzi) piuttosto che il numero di estrusioni utilizzate.

Entrambi questi problemi possono essere molto difficili da risolvere, ma è probabile che l'algoritmo di "adattamento migliore" che hai menzionato (utilizzando la "lunghezza ridotta" più lunga che si adatta all'estrusione corrente) fornisca ottime risposte con una complessità molto bassa.

Answer 4

In realtà, poiché la dimensione del materiale è fissa, ma le richieste no, è un problema di bin packaging.

Ancora, Wikipedia in soccorso!

(Qualcosa che potrei dover esaminare anche per lavoro, quindi evviva!)

Answer 5

Questo è un problema interessante perché suppongo dipenda dalla quantità di ciascuna lunghezza che stai producendo.Se sono tutti la stessa quantità e puoi ottenere ciascuna lunghezza diversa su un'estrusione di 5 m, allora hai la soluzione ottimale.

Tuttavia, se non si adattano tutti a un'estrusione, il problema è maggiore.Per mantenere la stessa quantità di tagli per ciascuna lunghezza è necessario calcolare quante lunghezze (non necessariamente in ordine) possono adattarsi a un'estrusione e quindi passare in ordine attraverso ciascuna estrusione.

Answer 6

Anche qui ho lottato con questo problema esatto (la lunghezza per il mio problema è di 6 m).

La soluzione su cui sto lavorando è un po' brutta, ma non mi accontento della tua soluzione.Lasciatemi spiegare:

Dimensioni delle scorte 5 metri

Deve essere tagliato in dimensioni (1 di ciascuno):

**3,5

1

1,5**

La tua soluzione:

3,5 | 1 con uno scarto di 0,5

1,5 con un residuo di 3,5

Vedi il problema?

La soluzione su cui sto lavorando -> Forza bruta

1 - Testare ogni possibile soluzione

2 - Ordina la soluzione in base ai rifiuti

3 - Scegli la soluzione migliore

4 - Rimuovere gli elementi presenti nella soluzione dall'"Universo"

5 - Vai a 1

So che richiede tempo (ma ci metto 1 ora e 30 minuti per pranzare...COSÌ...:))

Ho davvero bisogno della soluzione ottimale (eseguo manualmente una soluzione quasi ottimale (+-) in Excel) non solo perché sono ossessivo, ma anche perché il prodotto non è economico.

Se qualcuno avesse una soluzione semplice e migliore, mi farebbe molto piacere