Generazione di istanze a scarto nullo per il problema del 2D Multiple Bin Packing con tagli a ghigliottina

Il lavoro riguarda il problema del 2D Multiple Bin Packing con tagli a ghigliottina, nel quale pezzi rettangolari con domanda assegnata devono essere ricavati da pannelli di uno o più formati minimizzando il materiale impiegato. Il problema, ricorrente nel taglio industriale di pannelli, è NP-difficile in senso forte e si affronta di norma con metodi euristici, la cui distanza dall'ottimo resta in generale incognita. Per misurarla è stato sviluppato un generatore di istanze a scarto nullo. Costruendo l'istanza a partire da una suddivisione completa dei pannelli in pezzi, il generatore garantisce l'esistenza di una soluzione priva di scarto, cosicché lo scarto di qualunque soluzione coincide con la sua distanza dall'ottimo. Le istanze generate sono state impiegate per valutare un'euristica industriale per il taglio di pannelli in legno, con un disegno sperimentale fattoriale completo di 3072 combinazioni di caratteristiche dell'istanza e parametri dell'algoritmo, analizzato con strumenti statistici non parametrici. I risultati mostrano che la qualità delle soluzioni dipende soprattutto dalla domanda e che i parametri dell'algoritmo con l'effetto più ampio incidono principalmente sulle istanze a domanda bassa, le più difficili. Lo sforzo di ricerca maggiore recupera circa un quinto della distanza dall'ottimo a fronte di un tempo di calcolo circa venti volte superiore, mentre lo schema di taglio a due stadi comporta in mediana una perdita inferiore a un punto percentuale rispetto a quello a tre stadi. La sovraproduzione dei pezzi, infine, riduce lo scarto riportato dall'algoritmo ma aumenta il materiale impiegato: misurata con una metrica che tiene conto dei pezzi in eccesso, essa peggiora la qualità delle soluzioni.