Ai2

Tesina di Applicazioni di Intelligenza Artificiale Di Elisa Benetti

Scopo progetto: Dati in ingresso un numero variabile di ordini di pezzi di stoffa, il compito del programma dev’essere quello della gestione dei ritagli su rotoli di lunghezza prefissata.

Spiegazione Programma: Dopo la lettura degli ordini e la loro memorizzazione in una lista Lrich, viene calcolata la lunghezza di questa lista e di conseguenza sono create varie liste di questa stessa lunghezza (la lunghezza è la stessa sia nel caso si stiano trattando gli ordini, sia nel caso si trattino i rotoli da tagliare in quanto , nel caso peggiore, si userà al massimo 1 rotolo per ogni ordine): Ordini: Per ogni ordine viene segnalato in quale rotolo verrà tagliato Lung: Lunghezze dei vari ordini OrdiniRotoli: Lista di liste. A tutti gli effetti è una ‘matrice’ in cui ogni elemento può assumere valore 0 o 1. Se il valore i-esimo della j-esima listaè 1, allora l’ordine iesimo verrà tagliato dal rotolo j-esimo, altrimenti no. LungRot: Stessa struttura di OrdiniRotoli ma ogni elemento che nella lista precedente ha valore 1, avrà qui la corrispondente lunghezza dell’ordine. Vengono poi inizializzate la lista con gli identificativi dei rotoli e quella delle lunghezze con i giusti valori, definiti i domini ed infine i vincoli.

Minimizzazione in schedulingSfrido.ecl: La minimizzazione viene fatta sulla somma degli sfridi, ovvero della stoffa rimanente, da ciascun rotolo. Per fare questo dapprima mi creo una lista RotScelti che conterrà per ogni rotolo un 1 o uno zero a seconda che il rotolo sia o meno utilizzato. Questo è stato ottenuto scorrendo la lista di liste OrdiniRotoli e per ogni lista si mette in rotScelti il suo valore massimo: ovvero se almeno 1 ordine sarà tagliato in quel rotolo avremo un 1, altrimenti uno zero. Si scorre infine la lista di liste LungRot e per ognuna si esegue la seguente operazione: si somma la lista di lunghezze tagliate dal rotolo, la si detrae dalla lunghezza totale del rotolo e tutto questo si moltiplica per l’elemento corrispondente a quel rotolo nella lista RotScelti che quindi porterà il valore a zero se il rotolo non è usato e al valore trovato se il rotlo è usato. Avremo così la nostra lista ListaSfridi con, per ogni rotolo utilizzato, la quantità di stoffa da esso avanzata. Minimizzando la somma di questi valori avremo raggiunto il nostro obiettivo. La quantità di operazioni da eseguire è notevole, visto inoltre che con questo metodo viene eseguita per ogni rotolo anche se questo non è in effetti utilizzato. All’aumentare del numero di ordini l’aumento delle permutazioni possibili dei valori nel labeling cresce con andamento esponenziale, se consideriamo che per ognuna di queste possibilita si avranno lunghe tempistiche a causa dei calcoli sopra spiegati, l’andamento esponenziale verrà maggiormente accentuato dando tempi eccessivamente lunghi già a 7-8 ordini.

Minimizzazione in schedulingMinimizeRot.ecl: Ho quindi ragionato sul fatto che la minimizzazione dello sfrido totale è equivalente alla minimizzazione del numero di rotoli utilizzati, a meno delle informazioni sulla stoffa rimanente, che nel secondo caso non verranno espresse. E’stato quindi eseguito semplicemente un minimize sulla somma dei valori della lista RotScelti, diminuendo notevolmente le tempistiche di esecuzione. I valori scelti nei due casi risultano effettivamente gli stessi:

Ma l’inizio della crescita esponenziale nel caso degli sfridi si nota gia in un numero di ordini minore rispetto al caso della minimizzazione dei rotoli:

E come il grafico della crescita delle tempistiche degli sfridi sia molto piu ‘ripido’ rispetto all’altro caso si nota visualizzando un maggiore numero di esempi: