Algoritmen voor het oplossen van 2D en 3D onregelmatige snij- en verpakkingsproblemen gebruik makend van semi-discretisatie

Snij- en verpakkingsproblemen, zowel in 2D als in 3D, hebben betrekking op het plaatsen van een verzameling stukken zonder overlapping binnen een of meer containers. Deze problemen komen voor in een groot aantal industriële toepassingen, zoals het snijden van plaatmetaal en textiel, logistiek en additieve productie (additive manufacturing). Dit proefschrift bevat efficiënte optimalisatiemethoden voor zowel 2D als 3D onregelmatige snij- en verpakkingsproblemen gebruikmakend van een semi-discrete representatie van de stukken als de container.

We ontwikkelen een snel en schaalbaar algoritme voor het oplossen van 2D onregelmatige open dimensie snij- en verpakkingsproblemen, waarbij de horizontale lengte van de container geminimaliseerd wordt, terwijl rotatie van de stukken is toegestaan. 
De stukken en de container worden voorgesteld door een reeks equidistante verticale lijnsegmenten. Deze semi-discrete voorstelling wordt verkregen met behulp van een doorlooplijnalgoritme, gevolgd door een uitbreidingsalgoritme. Dit laatste genereert minimale maar volledige uitbreidingen van de lijnsegmenten van een stuk om ervoor te zorgen dat een niet-overlappende plaatsing van de lijnsegmenten, die twee stukken voorstellen, niet-overlappende stukken garandeert.
We implementeren een ‘links-onder-vullend’ plaatsingsprocedure, met een geoptimaliseerde volgorde van de segmentoverlaptesten. De kwaliteit van de oplossingen en de uitvoeringstijden zijn afhankelijk van R, de afstand tussen de verticale lijnsegmenten, en de uitvoeringstijd neemt minder dan lineair toe met R^(-1). Voor sommige benchmarkproblemen is dit ‘links-onder-vullend’-algoritme ongeveer twee grootte-ordes sneller dan een soortgelijk plaatsingsalgoritme in de literatuur, dat een continue representatie van de stukken gebruikt. Bovendien schaalt ons algoritme goed met een toenemend aantal stukken of met het aantal toegestane rotaties. 

Om de uitvoeringstijd te verminderen ontwikkelen we een parallelle versie van het algoritme. Wanneer voor elk stuk meerdere rotatiehoeken toegelaten zijn, wordt de berekening van de voorlopige plaatsing voor elke hoek parallel uitgevoerd. De versnelling is echter beperkt door een onevenwichtige belasting. Om de kwaliteit van de oplossing te verbeteren, ontwikkelen we een algoritme gebaseerd op deelverzamelingen van de stukken. De deelverzamelingen worden geplaatst met behulp van het ‘links-onder-vullend’-algoritme, terwijl een optimale volgorde van de stukken in elke deelverzameling wordt berekend. De vele mogelijke ordeningen van de stukken in een deelverzameling maken het mogelijk om veel taken te creëren die gelijktijdig kunnen worden uitgevoerd. Het parallelle algoritme met deelverzameling-grootte 3 leidt tot een kortere lengte van de container dan het originele links-onder-vullen-algoritme in een nog steeds korte uitvoeringstijd.

Voortbouwend op de efficiëntie van het 2D links-onder-vulend-algoritme met semi-discretisatie, breiden we deze aanpak uit om 3D onregelmatige snij- en verpakkingsproblemen op te lossen. De semi-discretisatie van de stukken en de container met behulp van een raster in twee dimensies resulteert in lijnsegmenten in de derde dimensie. De lijnsegmenten worden uitgebreid, volgens een gelijkaardige aanpak als in het 2D probleem, om overlapping van de stukken te voorkomen wanneer ze in de container geplaatst worden. We presenteren een `diepst-links-onder-vullend’ plaatsingsalgoritme voor ge-semi-discretiseerde stukken en container door iteratief gebruik te maken van het 2D-algoritme. Dit algoritme is schaalbaar met een toenemend aantal stukken en een toenemend aantal mogelijke rotatiehoeken. We tonen dat wanneer een voldoende aantal rotaties wordt toegestaan, dit algoritme gelijkaardige oplossingen vindt als deze verkregen met andere heuristieken en beschreven in de literatuur, maar het algoritme is grootte-ordes sneller. We introduceren een parallelle versie van het algoritme met dynamische taakverdeling om de uitvoeringstijd verder te verkorten en evalueren de prestaties op een `multicore processor’ met verschillende taakgroottes. We bepalen proefondervindelijk welke taakgrootte de snelheidsverhoging door parallellisatie maximaliseert. Om de oplossingskwaliteit verder te verbeteren, implementeren we een `hill-climbing’ algoritme op basis van het herschikken van de stukken bovenop het `diepst-links-onder-vullend’ algoritme. Tot slot vergelijken we de prestaties van het `diepst-links-onder-vullend’ algoritme met en zonder `hill-climbing’ met resultaten uit de literatuur voor enkele referentieproblemen: er wordt een vergelijkbare oplossingskwaliteit bereikt, maar de uitvoeringstijd is twee grootte-ordes korter.