Problema di partizionamento industriale

Question

Stiamo parlando della fabbrica di prodotti in metallo. C'è una macchina che taglia lunghe barre di ferro in parti più piccole che vengono successivamente utilizzate per creare vari prodotti.

Ad esempio, ho l'obbligo di produrre barre della seguente lunghezza e quantità: 2 pezzi di 248 mm, 5 di 1150mm, 6 di 2843mm, 3 di 3621mm.

Questo è l'output di partizionamento.

Sul lato input ho (sempre per esempio) 3 barre di 2500mm, 2 barre da 5000mm, 6 barre da 8000 mm e 3 barre di 10000 mm.

Dovrei trovare un modo per tagliare le barre di input in modo ottimale - il resto (le parti rimanenti che sono troppo piccole per essere utilizzate) dopo il taglio dovrebbero essere il più piccolo possibile.

Ho creato un algoritmo che crea semplicemente tutte le possibili combinazioni e poi ne scelgo una tra le migliori. Il codice funziona, ma non appena input e output sono leggermente più grandi, il calcolo può durare a lungo, quindi devo trovare un nuovo approccio al problema.

Hai qualche suggerimento?

Answer 1

Il tuo problema è piuttosto comune in Operations Research. Guarda a Riduzione del problema degli stock . Questo problema è essenzialmente NP-difficile come hai capito da solo. Non si adatta molto bene.

Come risolverlo? Dopo aver capito il modello, sarebbe meglio chiamare un risolutore di programmazione di numeri interi misti. In precedenza ho utilizzato LPSolve 5.5

Potrebbero esserci algoritmi più semplici che potresti codificare per affrontare questo problema in particolare. Il problema con questi algoritmi si pone di solito quando è necessario aggiungere alcuni vincoli collaterali a cui gli autori non hanno pensato. Il Risolutore MIP è uno strumento molto più generico.

Answer 2

Questo è chiamato problema di imballaggio del contenitore di dimensioni variabili . È NP difficile, il che significa che la tua soluzione fallirà invariabilmente per input di grandi dimensioni. Questo articolo, qui , che purtroppo non ho accesso anch'io, indirizzi questo problema e usa l'industria del taglio dei metalli come esempio.

Answer 3

La programmazione lineare è tua amica. Vedi http://en.wikipedia.org/wiki/Linear_programming in generale e, in particolare, , http://en.wikipedia.org/wiki/Linear_programming#Uses , < a href = "http://en.wikipedia.org/wiki/Linear_programming#Algorithms" rel = "nofollow noreferrer"> http://en.wikipedia.org/wiki/Linear_programming#Algorithms .

Answer 4

Sembra che sia simile al problema dello zaino (noto per essere davvero brutto) L'ho trovato su NIST DADS (riferimento pratico) più facile da raggiungere rispetto a ACM per i non membri Imballaggio bin