Ottimizzare produzione

[max81]

Un saluto a tutto il forum,
è da un po' che sto pensando ad un'applicazione di ottimizzazione in ambito industriale.
L'idea è la seguente, ipotizziamo di voler ottimizzare il taglio di profili, in modo da minimizzare la quantità di scarti prodotti, mi spiego meglio, diciamo che partiamo da una quantità di verghe di un profilato in acciaio da cui bisogna ricavare, tramite il taglio, alcuni pezzi di diversa lunghezza, quindi quello che vorrei fare, è utilizzare un algoritmo che partendo dalla dimensione delle verghe, dalla lista dei pezzi da tagliare e dalla lista delle sezioni del profilato difettose (cioè da scartare), mi calcola il layout migliore che produce il minimo scarto di materiale.
Il problema posto lavora a una dimensione, poi mi piacerebbe svilupparlo su 2 dimensioni (esempio ottimizzare il taglio di pezzi su lamiera).
Premetto che all'uni, ho visto qualche breve descrizione di algoritmi di ottimizzazione, ma non dal lato di vista dell'implementazione, quindi chiedo gentilmente se qualcuno può darmi una dritta su come potrei affrontare il problema, su che algoritmo utilizzare (Monte carlo, genetici, particle swarm), e se c'è del materiale interessante a riguardo (libri, tutorial, manuali, ecc...).
Grazie a tutti

[g.schgor]

Ti posso segnalare un mio articolo (di 40 anni fa) intitolato
Studio per l'ottimizzazione nel taglio a lunghezza delle billette
apparso in Automazione e Strumentazione (vol.XIX Febbraio 1971)
In cui vengono illustrate prime applicazioni di calcolatori
per questi problemi.
(se non lo trovi, posso vedere di farne copia elettronica)

[movlw]

Se non ricordo male, il problema dovrebbe essere del tipo NP-completo, da affrontare con la programmazione dinamica... ricordi abbastanza vecchi.

Credo dovresti cercare con la parola chiave "knapsack".

[max81]

Ringrazio per le risposte,
cercando su google "knapsack problem" ho trovato molto materiale accademico e non, e da quello che ho visto velocemente è il tipico algoritmo, con varie varianti, più utilizzato per questo tipo di problemi.
Ho scaricato un po' di materiale, appena ho un attimo di tempo provo a darci un'occhiata e poi vi farò sapere.

@Schgor
Vorrei chiederti gentilmente se potresti farmi avere una copia del tuo articolo.
Ringrazio per la disponibilità.

[g.schgor]

Trasmetto l'articolo in forma di immagini
(non avendo indirizzo a cui trasmetter i files)

bill1.GIF (222.52 KiB) Osservato 2655 volte

bill2.GIF (262.68 KiB) Osservato 2656 volte

bill3.GIF (225.74 KiB) Osservato 2654 volte

bill4.GIF (215.35 KiB) Osservato 2655 volte

bill5.GIF (221.2 KiB) Osservato 2654 volte

bill6.GIF (208.74 KiB) Osservato 2654 volte

Spero siano scaricabili per la stampa.

[max81]

Ciao Schgor,
ti ringrazio moltissimo per la disponibilità, leggo il tuo articolo e appena finisco un altro progetto a cui sto lavorando, provo a buttar giù un po' di codice, poi vi farò sapere.

Grazie e un saluto