Nel problema del cutting stock bidimensionale, dato uno stock rettangolare di materia prima di dimensioni (L, W ), e dato un insieme P di pezzi rettangolari desiderati, a cia-scuno dei quali è associato un valore di profitto ed una coppia di dimensioni (l, w), bisogna trovare l’insieme Sopt di pezzi, sottoinsieme di P, estraibile dallo stock che mas-simizzi la somma dei profitti dei pezzi in esso contenuti.
Un insieme S di pezzi estraibile è definito in letteratura come “feasible pattern”. Un esempio di pezzi non estrai-bile, nel caso di stock con dimensioni (5, 5) è S = {(3, 3), (4, 4)}. Se più pezzi sono identici, sia nelle dimensioni che nel profitto, essi costituiscono un “tipo” di pezzo ed il numero ne rappresenta la domanda.
In molte applicazioni di questo problema è necessario ottenere i pezzi dividendo lo stock iniziale ed i conseguenti sottorettangoli soltanto con tagli a ghigliottina, vale a dire tagli che cominciano e terminano su punti perimetrali.
I tagli a ghigliottina paralleli realizzati sullo stock iniziali sono definiti di primo livello. Quelli ad essi per-pendicolari e realizzati sui rettangoli ottenuti sono definiti di secondo livello e così via.
I metodi di soluzione proposti in letteratura sono molteplici e fanno riferimento a schemi di programmazione dinamica (Gilmore and Gomory, 1966), metaeuristici (Alvarez-Vades, 2002), di programmazione lineare (Lodi and Monaci, 2003). La maggior parte di essi sono però approcci ad hoc e possono essere distinti in tre classi: top-down, bottom-up e strip heuristics.
Gli approcci top-down (figura 1a) dividono ricorsivamente lo stock iniziale ed i conseguenti sottorettangoli in due parti fino ad ottenere i pezzi finali (Christofides and Whitlock, 1977; Hifi and Zissimopoulos, 1997).
Gli approcci bottom-up (figura 1b) hanno una strategia opposta, fondendo ricorsivamente coppie di rettangoli (chiamati builds) contenenti pezzi e generando perciò rettangoli sempre maggiori fino al riempimento dello stock.
I rettangoli di partenza sono quelli equivalenti a ciascun tipo di pezzi. La fusione di due rettangoli avviene aggiungendo un taglio di separazione orizzontale o verticale. (Wang, 1983; Hifi, 1997; G et al., 2003).
Gli approcci strip heuristics (figura 1c) generano soluzioni identificate dai livelli di taglio, in genere non più di quattro (Fayard et al., 1998; Hifi and M’Hallah, 2006).
Recentemente Russo and Sforza (2007) hanno proposto un metodo ibrido, definito di boundary disposition, che sceglie gruppi di pezzi da disporre lungo il lato inferiore e sinistro del rettangolo corrente (figura 2a), aggiungendo poi i tagli (disposition cuts) coerenti con tale disposizione (figura 2b).
Per il taglio del vetro piano si utilizzano solo tagli a ghigliottina. Esso prevede anche altre considerazioni particolari, principalmente legate alla delicatezza con cui è necessario trattare il vetro, in contrapposizione al fatto che le lastre (gli stock) di vetro hanno dimensioni notevoli, in genere sei metri per trecentoventuno centimetri. Ne consegue che il problema del taglio del vetro è molto interessante e si accenna nel seguito sia alle cause fisico-tecnologiche che agli spunti per le tecniche di ottimizzazione proposte per tenerne conto.
La necessità di tagli a ghigliottina, nel caso del vetro, è dovuta alla tecnica generalmente utilizzata per l’estrazione dei pezzi. Essa prevede due fasi, la prima di “incisione” e la seconda di “apertura”. L’incisione consiste nel realizzare una ferita nel vetro lungo la linea del taglio e per una profondità molto ridotta rispetto al suo spessore totale.
L’incisione è realizzata generalmente tramite punte diamantate in dotazione ai macchinari che la eseguono. La fase di apertura è realizzata con il supporto di apposite barre di legno o plastica, incastonate nel tavolo di lavoro.
Gli operatori, sfruttando getti d’aria continui, distribuiti sul tavolo e che alleggeriscono la lastra, spostano la lastra stessa in modo che la linea del taglio da aprire si sovrapponga ad una delle barre, che viene poi repentinamente alzata attraverso comandi meccanici, a pedale o con pulsanti.
L’innalzamento della barra determina una spinta sul vetro verso l’alto lungo la linea dell’incisione ed il peso delle due parti che si trovano ai lati opposti dell’incisione determina una leva meccanica con fulcro sulla barra, facendo così realizzare il taglio (figura 3). Quando il rettangolo da tagliare è di dimensioni ridotte, l’apertura può essere realizzata con il solo ausilio delle mani.
Dato che le incisioni non richiedono l’intervento degli operatori, in genere sono prima realizzate tutte le incisioni su un tavolo e poi su un secondo tavolo avvengono le aperture. La presenza di due tavoli permette di ottimizzare il lavoro poiché l’apertura dei tagli su una lastra può avvenire contemporaneamente alle incisioni dei tagli su una lastra successiva.
Questo aspetto determina due fatti da tenere in considerazione nella soluzione del problema. Il primo aspetto da tenere in considerazione circa la realizzazione di tutte le incisioni prima di tutte le aperture è legato al fenomeno chiamato in gergo “raffreddamento” del taglio. Esso si manifesta in particolar modo per vetri di spessore elevato, almeno otto-dieci millimetri, e consiste nel dover realizzare l’apertura senza far passare troppo tempo dall’incisione.
Addirittura non sarebbe possibile eseguire nuovamente l’incisione poiché questo avrebbe effetti ancora peggiori, tanto che gli operatori in gergo usano dire che il taglio in tal caso si “chiude”. Il rischio determinato dal fenomeno descritto diventa rilevante quando, da lastre di spessore sufficientemente elevato, si deve estrarre un insieme di pezzi che richiede un numero eccessivo di tagli.
Tale aspetto è affrontabile con una fase di post-ottimizzazione il cui obiettivo è ottenere una partizione dell’insieme dei tagli a ghigliottina associati alla soluzione scelta, così da eseguirne un solo sottoinsieme per volta.
L’obiettivo è ottenere il minimo numero di sottoinsiemi soddisfacendo vincoli di tempo per ciascuno di essi, sulla base di modelli sperimentali per la valutazione dei tempi necessari alla realizzazione di ciascuna apertura e dei tempi di raffreddamento dei tagli.
Il secondo aspetto da tenere in considerazione circa la realizzazione di tutte le incisioni prima di tutte le aperture è che, quando si esegue l’apertura di un taglio T, vi possono essere ulteriori incisioni su ciascuno dei due sottorettangoli che se ne ottengono. Se una di tali incisioni, indicata con I, è parallela al taglio T che si sta aprendo ed è sufficientemente vicino ad esso, c’è il rischio che l’operazione di apertura possa far “aprire” anche quest’altra incisione.
Il problema nasce quando quest’ultima ha almeno uno dei due estremi in punti che non sono sul perimetro del rettangolo che si sta correntemente spezzando in due attraverso T. Se questo avviene, l’apertura indesiderata si allunga seguendo direzioni casuali ed anche curvilinee.
In gergo tale fenomeno è definito “finta” e può danneggiare zone della lastra associate a molti dei pezzi del pattern scelto.
Per quanto detto il rischio è concreto quando il suddetto taglio T passa su un lato di un piccolo scarto B, sempre rettangolare, che ha l’altro suo lato parallelo a T e sufficientemente vicino ad esso, con relativa incisione I, come nell’esempio di figura 4.
Anche la questione delle “finte” è affrontata con una fase di post-ottimizzazione. A partire dalla soluzione scelta nella fase di ottimizzazione principale, si riposizionano, se necessario, i pezzi del pattern scelto. Spesso il rischio di finte è evitabile semplicemente spostando il suddetto scarto B, scambiando la sua posizione con il pezzo che si trova dal lato opposto di I. In certi casi non è possibile annullare del tutto il rischio ed allora se ne segnala la presenza agli operatori che operano conseguentemente con maggiore attenzione. Nella fase di post-ottimizzazione si può tener conto del fatto che la direzione della finta, per quanto casuale, assume raggi di curvatura limitati secondo lo spessore del vetro, con valori minimi ottenibili sperimentalmente. Ciò vuol dire che in alcuni casi è certo che l’eventuale finta danneggi solo zone della lastra destinate allo scarto. Nell’esempio di figura è raffigurata una incisione in rosso ed in blu la relativa finta.
Tornando sulla realizzazione di un taglio, c’è da dire che nella fase di apertura è necessario realizzare un effettivo meccanismo di leva meccanica, cosa purtroppo non sempre
possibile. Se infatti l’incisione è troppo vicina al (più vicino) bordo (parallelo) del rettangolo da tagliare, l’apertura risulta impossibile o, per vetri di spessore ridotto, realizzabile solo manualmente tramite pinze, da utilizzare un po’ per volta lungo tutta l’incisione, con risultati di bassa qualità del taglio ed elevati tempi di esecuzione.
I tagli devono dunque essere sufficientemente distanti dai bordi e si parla in gergo di “rifilo” minimo (o minimum trim). La figura 6 riporta un caso in cui si suppone che l’incisione sia troppo vicina al bordo. Tale parametro aumenta all’aumentare dello spessore del vetro, come si può capire dalla precedente descrizione della fase di apertura.
Inoltre esso può essere considerato variabile con la lunghezza del taglio stesso, poiché per tagli più corti è accettabile una distanza minore a patto di fare comunque più attenzione nell’apertura.
La presenza del rifilo minimo non comporta di per sé particolari problemi nell’applicazione dei metodi risolutivi classici, per lo più di tipo branch and bound, ma è opportuno che alla riduzione dell’insieme di soluzioni fattibili corrispondano migliori upper and lower bounds. Il legame fra rifilo minimo e lunghezza dei tagli rappresenta un ulteriore elemento di complessità per la conseguente correlazione che nasce fra il posizionamento dei pezzi e la scelta dei tagli utili ad ottenerne l’estrazione.
Al rifilo minimo si combina ancora un altro aspetto che è quello delle tolleranze dimensionali. Salvo che per casi particolari, come quello in cui i pezzi di vetro sono destinati a lavorazioni di sigillatura per la realizzazione di vetri camera, è possibile che i pezzi abbiano dimensioni diverse da quelle richieste, in genere con differenze che non superino il millimetro.
Sfruttando le tolleranze, a volte è possibile ridurre le dimensioni di un gruppo di pezzi, così da riuscire a posizionarlo in un rettangolo le cui dimensioni sarebbero state sforate se si fossero utilizzate le dimensioni non ridotte.
Ad esempio da un vetro con una dimensione pari a 100 sarebbe impossibile estrarre due pezzi con una dimensione di 51. Se però entrambi godono di una tolleranza di 1, allora è possibile restringerli ed ottenerli con una dimensione pari a 50. Altre volte è invece possibile aumentare le dimensioni così da riempire tutto il rettangolo ed evitare il problema del rifilo minimo. Se nel precedente esempio, ipotizzando un rifilo minimo pari a 5, i pezzi devono avere una dimensione di 49, ma godono di tolleranza 1, allora li si può allungare a 50.
Un modo per tener conto delle tolleranze è, durante il processo di costruzione delle soluzioni, associare dimensioni non fisse ai sottorettangoli dello stock, ma variabili entro un’unione di intervalli (disgiunti) di valori. Tali intervalli sono identificati dai gruppi di pezzi posizionati nei corrispondenti sottorettangoli. Questo metodo si sposa molto bene con le tecniche che puntano sulla scelta dei pezzi, escludendo dunque le tecniche top-down che realizzano invece tecniche di ricerca ad albero con branching sulle sole coordinate dei tagli.
Talvolta, nonostante l’utilizzo delle tolleranze, non si riesce a superare il problema del rifilo minimo. Si supponga ad esempio di voler estrarre un pezzo con una dimensione pari a 98, con tolleranza 1, da un rettangolo con una dimensione pari a 100. Se il rifilo minimo vale 4, il pezzo non può essere estratto poiché, pur sfruttando la massima riduzione, si può usare una dimensione di 97 con scarto di dimensione 3, minore del rifilo minimo. Analogamente, sfruttando il massimo aumento, si può usare una dimensione di 99, senza però raggiungere il pieno valore di 100.
In casi come questi si può sfruttare una caratteristica del processo di produzione del vetro. Spesso, per necessità tecnologiche come nel caso in cui un pezzo di vetro debba essere temprato in un apposito forno, o per le finalità stesse cui esso è destinato, vi è la necessità di realizzare una fase di levigatura dei bordi perimetrali del pezzo che prende il nome di “arrotatura”. Tale operazione è realizzata consumando il pezzo di vetro lungo il suo perimetro (figura 7), asportandone di fatto la cornice più esterna, per una dimensione minima di pochi millimetri.
Detta dimensione aumenta con l’aumentare dello spessore del vetro poiché con lo spessore aumenta l’irregolarità dei bordi, a causa delle modalità precedentemente spiegate con cui è realizzata la fase di apertura (figure 8a ed 8b).
La caratteristica fondamentale dell’arrotatura, in relazione al problema del taglio, è che la minima arrotatura realizzabile è inferiore al rifilo minimo. Se nell’esempio precedente si suppone un’arrotatura minima di valore pari a 3, allora si può pensare di non realizzare alcun taglio, per poi ottenere il pezzo con dimensione 97, a partire dalla dimensione di 100, proprio grazie all’arrotatura.
Lo svantaggio consiste nella necessità di una ulteriore fase produttiva, con conseguente aumento dei costi. Tale svantaggio è annullato nel caso in cui il pezzo era già predestinato a subire tale fase, con conseguente aumento delle dimensioni dei pezzi da realizzare con il taglio. In tal caso l’effetto finale è nell’aumento delle tolleranze sfruttabili nel problema di taglio, in relazione al fatto che la dimensione asportabile con l’arrotatura è a sua volta variabile entro un determinato range.
L’elemento più interessante che lega l’arrotatura al cutting stock risiede però nelle due seguenti considerazioni. Innanzitutto, se dei pezzi identici non necessitano di per sé di una fase di arrotatura, allora si può scegliere di estrarne alcuni facendovi ricorso ed altri senza. In termini di modello del problema di taglio, ciò vuol dire che vanno considerati due distinti tipi di pezzo, diversi nel profitto ma con domanda condivisa. Al secondo tipo sarà infatti associato un profitto inferiore, legato all’aumento dei costi di produzione.
fa corrispondere un tipo di pezzo, con profitto decrescente all’aumentare di tale numero. A ciascun tipo sono associate tolleranze che, al contrario del profitto, sono crescenti. L’insieme di tali tipi di pezzo costituisce una sorta di classe, con domanda totale condivisa. Si sottolinea infine che il numero massimo di cicli di arrotatura è dovuto al rapporto fra rifilo minimo e massima dimensione asportabile con l’arrotatura stessa. Se, come nell’esempio precedente, il rifilo minimo è 11 e l’arrotatura ha valore massimo 3, allora il massimo numero di cicli è 4.
Si descrivono ora gli effetti che altre importanti considerazioni sul ciclo produttivo del vetro hanno sul problema di taglio. In particolare si accenna alle dipendenze con la schedulazione delle attività produttive e con il problema dello stoccaggio dei vetri sui carrelli fra una lavorazione e l’altra. Questi effetti sorgono nel momento in cui non si considera più l’ottimizzazione di una sola lastra, ma di una serie di lastre, con l’obiettivo di estrarre tutti i pezzi desiderati. Tale problema è noto in letteratura come bin packing.
Se si suppone che la schedulazione delle attività sia già stata realizzata, nel problema del taglio si associano profitti maggiori ai pezzi che, appartenendo ad uno specifico lotto di produzione, devono subire ulteriori lavorazioni prima possibile. Se inoltre questo è vero per più gruppi di pezzi e per ciascun gruppo è importante che siano stati tutti già estratti, sorge allora un problema di raggruppamento.
Infatti, ipotizzando che sia tagliata una lastra per volta, ne consegue che non è importante estrarre i pezzi di tutti tali gruppi prima degli altri, ma piuttosto che essi siano estratti in una sequenza tale che i pezzi dello stesso gruppo siano estratti in modo ravvicinato (figura 9).
Se, come caso estremo, si suppone che tutti i gruppi hanno uguale priorità ed essi devono essere estratti da un elevato numero di lastre, è auspicabile non estrarre dall’ultima lastra l’ultimo pezzo di ciascun gruppo. E’ invece opportuno che il primo e l’ultimo pezzo estratto di ciascun gruppo siano posizionati su lastre vicine nella sequenza di taglio.
La questione del raggruppamento sorge anche in relazione alla necessità di stoccare i vetri, fra un lavorazione e l’altra, su carrelli mobili. Le modalità con cui i vetri possono essere appoggiati l’uno sull’altro sono tali da dover rispettare vincoli dovuti alla delicatezza con cui trattare il vetro, per evitarne il danneggiamento. In alcuni casi, i vincoli sono tali per cui il raggruppamento dei vetri da associare a ciascun carrello deve necessariamente prescindere dalla soluzione del problema di taglio. In altri casi è invece possibile operare la scelta a valle del problema di taglio, quando ad esempio i pezzi da estrarre sono molto simili in termini di dimensioni. In generale può sorgere la necessità di risolvere insieme i due problemi, con fasi di loop-back fra l’uno e l’altro.
In ogni caso, analogamente alla schedulazione delle attività, il problema del taglio può dover tener conto della necessità di raggruppare i pezzi. Se così non fosse, si rischierebbe che prima di terminare il taglio di tutte le lastre, più carrelli potrebbero essere solo parzialmente riempiti, con conseguente ingombro fisico nei pressi dell’isola di taglio (figura 10). Questo produrrebbe un aumento dei tempi di posizionamento dei pezzi sui carrelli stessi ed un aumento dei rischi di danneggiamento dei pezzi stessi.
L’introduzione dei gruppi di pezzi può essere trattata in due modi. Il primo è adatto ai metodi di soluzione che puntano sulla scelta dei pezzi e prevede l’associazione di profitti dinamici ai pezzi non ancora aggiunti alla soluzione parziale costruita, sulla base dell’insieme dei pezzi già aggiunti. Un seconda tecnica consiste in primo luogo in una fase di postottimizzazione che, a partire dall’insieme delle lastre, ciascuna con la sua soluzione, determini la sequenza ottima delle lastre stesse. Si parla perciò di problema di Sequencing (Becceneri et al., 2004). Questa post-ottimizzazione, da sola, potrebbe però risentire di situazioni sfortunate in cui ciascun gruppo di pezzi è distribuito fra troppe lastre. Può allora nascere la necessità di operare fasi di loop-back, riottimizzando alcune o tutte le lastre ed associando un profitto alterato ai pezzi, analogamente
a quanto proposto per problemi di packing da Perboli et al. (2006).
Dall’insieme di considerazioni fatte si può concludere che il problema del cutting stock nell’industria del vetro risulta alquanto articolato, date le molteplici sfaccettature. Si tenga conto del fatto che ulteriori questioni si aprono per il taglio di vetri fisicamente più strutturati, come nel caso dei vetri laminati che, al centro del proprio spessore, hanno uno strato plastico (figura 11). Per essi, come per altri di cui non si fa cenno per brevità, sorgono ulteriori vincoli tecnologici con ricadute sul modello del relativo problema.
Le tecniche proposte dagli autori per ciascuno dei dettagli descritti sono state applicate con successo in una delle più grandi industrie di trasformazione del vetro del Sud Italia, la Mexall Glass, sita in Scafati (SA) con un soddisfacente guadagno in termini di riduzione dei costi e di aumento della competitività. Detta azienda ha puntato molto da un lato su strumenti matematici di ottimizzazione dei problemi e dall’altro su strumenti tecnologici originali per il controllo e l’ottimizzazione della gestione aziendale, raggiungendo ragguardevoli standard di qualità e servizio.
Salvatore Prete
Uniplan Software & Mexall Glass
Via Oberdan 52, 84018 Scafati (Sa), Italy
sprete@uniplan.it
Mauro Russo, Antonio Sforza, Claudio Sterle
Dipartimento di Informatica e Sistemistica
Università degli Studi di Napoli “Federico II”
Via Claudio 21, 80125 Napoli, Italy
sforza@unina.it , ma.russo@unina.it
Bibliografia
Alvarez-Valdés R., Parajon A., Tamarit J.M. (2002) A tabu search
algorithm for large-scale guillotine (un)constrained two-dimensional
cutting problems. Computers and Operations Research
29, 925-947.
Becceneri J.C., Yanasse H.H., Soma N.Y. (2004) A method for
solving the minimization of the maximum number of open stacks
problem whitin a cutting process. Computers and Operations Re-search
31, 2315-2332.
Christofides N., Withlock C. (1977) An algorithm for two-dimensional
cutting problems. Operations Research 25, 30-44.
Fayard D., Hifi M., Zissimopoulos V. (1998) An efficient approach
for large-scale two-dimensional guillotine cutting stock problems.
Journal of the Operational Research Society 49, 1270-1277.
G Y.-G., Seong Y.-J., Kang M.K.. (2003) A best-first branch and
bound algorithm for unconstrained two-dimensional cutting prob-lems.
Operations Letters 31, 301-307.
Gilmore P.C., Gomory R.E.. (1966) The theory and computation of
knapsack functions. Operations Research 14, 1045-1074.
Hifi M. (1997) An improvement of Viswanathan and Bagchi’s ex-act
algorithm for constrained two-dimensional cutting stock.Com-puters
& Operations Research 24, 727-736.
Hifi M., M’Hallah R. (2006) A hybrid algorithm for the two-dimensional
layout problem: the cases of regular and irregular
shapes. Int. Tr In Operational Research 10, 915-216.
Hifi M., Zissimopoulos V. (1997) Constrained two-dimensional
cutting: An improvement of Christofides and Withlock’s exact al-gorithm.
Journal of the Operational Research Society 48, 324-331.
Lodi A., Monaci M. (2003) Integer linear programming model for
2-staged two-dimensional knapsack problems. Mathematical pro-gramming
94, 257-278.
Perboli G., Crainic T.G., Tadei R. (2006) UniPack: a new heuristic
framework for Multi-Dimensional Packing Problems, in Proceed-ings
of AIRO, 27, Cesena (FC), Italy.
Russo M., Sforza A. (2007) A boundary disposition heuristic for the
two-dimensional cutting stock problem. Submitted to European
Journal of Operational Research.
Wang P. Y. (1983) Two algorithms for constrained two-dimensional
cutting stock problems. Operations Research 31, 573-586.