Styckningslagerproblem

Inom operationsforskning är skärstocksproblemet problemet med att skära stycken av lagermaterial i standardstorlek, såsom pappersrullar eller plåt , i bitar av specificerade storlekar samtidigt som materialspillet minimeras. Det är ett optimeringsproblem inom matematik som uppstår från tillämpningar inom industrin. När det gäller beräkningskomplexitet är problemet ett NP-hårt problem som kan reduceras till ryggsäcksproblemet . Problemet kan formuleras som ett heltalslinjärt programmeringsproblem .

Illustration av ettdimensionellt styckningsproblem

En pappersmaskin kan producera ett obegränsat antal master (jumbo) rullar, var och en 5600 mm bred. Följande 13 föremål måste skäras, i tabellen nedan.

Det viktiga med denna typ av problem är att många olika produktenheter kan tillverkas av samma huvudrulle, och antalet möjliga kombinationer är i sig mycket stort, i allmänhet, och inte triviala att räkna upp.

Problemet är därför att hitta en optimal uppsättning mönster för att tillverka produktrullar från huvudvalsen, så att efterfrågan tillfredsställs och slöseri minimeras.

Bredd	#Artiklar
1380	22
1520	25
1560	12
1710	14
1820	18
1880	18
1930	20
2000	10
2050	12
2100	14
2140	16
2150	18
2200	20

Gränser och kontroller

En enkel nedre gräns erhålls genom att dividera den totala mängden produkt med storleken på varje huvudrulle. Den totala produkten som krävs är 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 mm. Varje huvudrulle är 5600 mm, vilket kräver minst 72,7 rullar, vilket innebär att 73 rullar eller fler krävs.

Lösning

En lösning för minimalt avfall, sekvenserad för att minimera knivbyten, visad som små vita cirklar

Det finns 308 möjliga mönster för denna lilla instans. Det optimala svaret kräver 73 huvudrullar och har 0,401 % spill; det kan visas beräkningsmässigt att i detta fall är det minsta antalet mönster med denna avfallsnivå 10. Det kan också beräknas att det finns 19 olika sådana lösningar, var och en med 10 mönster och ett slöseri på 0,401 %, varav en sådan lösning visas nedan och på bilden:

Upprepning	Innehåll
2	1820 + 1820 + 1820
3	1380 + 2150 + 1930
12	1380 + 2150 + 2050
7	1380 + 2100 + 2100
12	2200 + 1820 + 1560
8	2200 + 1520 + 1880
1	1520 + 1930 + 2150
16	1520 + 1930 + 2140
10	1710 + 2000 + 1880
2	1710 + 1710 + 2150
73

Klassificering

Styckningsproblem kan klassificeras på flera sätt. Ett sätt är skärningens dimensionalitet: exemplet ovan illustrerar ett endimensionellt (1D) problem; andra industriella tillämpningar av 1D förekommer vid kapning av rör, kablar och stålstänger. Tvådimensionella (2D) problem uppstår i möbler, kläder och glasproduktion. När antingen huvudartikeln eller de nödvändiga delarna är oregelbundna (en situation som ofta förekommer i läder-, textil-, metallindustrin) kallas detta häckningsproblem .

Inte många tredimensionella (3D) tillämpningar som involverar skärning är kända; det närbesläktade 3D- packningsproblemet har emellertid många industriella tillämpningar, såsom att packa föremål i fraktcontainrar (se t.ex. containerisering : det relaterade sfärförpackningsproblemet har studerats sedan 1600-talet ( Kepler-förmodan )).

Ansökningar

Industriella tillämpningar av styckningsproblem för höga produktionsvolymer uppstår särskilt när basmaterial produceras i stora rullar som skärs vidare till mindre enheter (se valsslitsning ). Detta görs t.ex. inom pappers- och plastfilmsindustrin men även vid produktion av platta metaller som stål eller mässing. Det finns många varianter och ytterligare begränsningar som härrör från speciella produktionsbegränsningar på grund av maskin- och processbegränsningar, kundkrav och kvalitetsfrågor; några exempel är:

Tvåsteg, där rullarna som produceras i det första steget sedan bearbetas en andra gång. Till exempel produceras alla kontorspapper (t.ex. A4 -storlek i Europa, Letter-storlek i USA) i en sådan process. Komplikationen uppstår eftersom maskineriet i det andra steget är smalare än det primära. Effektivt utnyttjande av båda produktionsstadierna är viktigt (ur ett energi- eller materialanvändningsperspektiv) och det som är effektivt för det primära steget kan vara ineffektivt för det sekundära, vilket leder till avvägningar. Metalliserad film (används vid förpackning av snacks) och plastextrudering på papper (används i vätskeförpackningar , t.ex. juicekartonger) är ytterligare exempel på en sådan process.
Winder-begränsningar där skärningsprocessen har fysiska eller logiska begränsningar: en mycket vanlig begränsning är att endast ett visst antal skärknivar är tillgängliga, så att möjliga mönster inte bör innehålla fler än ett maximalt antal rullar. Eftersom upprullningsmaskineri inte är standardiserat, stöter man på väldigt många andra begränsningar.
Ett exempel på ett kundkrav är när en viss order inte kan tillfredsställas från någon av de två kantpositionerna: detta beror på att kanterna på plåten tenderar att ha större variationer i tjocklek och vissa applikationer kan vara mycket känsliga för dessa.
Ett exempel på kvalitetsproblem är när masterrullen innehåller defekter som måste skäras runt. Dyra material med krävande kvalitetsegenskaper som fotopapper eller Tyvek måste noggrant optimeras så att slöseriområdet minimeras.
Flermaskinsproblem uppstår när beställningar kan produceras på mer än en maskin och dessa maskiner har olika bredd. I allmänhet förbättrar tillgängligheten av mer än en huvudvalsbredd avfallet avsevärt; i praktiken kan dock ytterligare orderuppdelningsbegränsningar behöva beaktas.
Det finns också ett semi-kontinuerligt problem, där de producerade rullarna inte behöver ha samma diameter, utan kan variera inom ett intervall. Detta inträffar vanligtvis med arkbeställningar. Detta är ibland känt som ett 1½-dimensionellt problem. Denna variant förekommer även vid tillverkning av wellpapp , där det något förvirrande kallas corrugator-schemaläggningsproblemet .
Eftersom vissa pappersmaskiner är relativt smala jämfört med de efterfrågade artiklarna, har vissa företag investerat i en sekundär process för skivning (även känd som en bansvetsning ), där två rullar (tillverkade genom att skära de första jumborullarna) sammanfogas sida vid- sida (med lite överlappning) för att göra en bredare rulle. Att producera smalare rullar i primärprocessen leder till lägre totalavfall.
Inom metallindustrin är en viktig skillnad att mastervalsarna vanligtvis tillverkas tidigare och i allmänhet skiljer sig från varandra (både vad gäller bredd och längd). Därför finns det likheter med multimaskinproblemet som nämns ovan. Förekomsten av längdvariationer skapar ett 2D-problem, eftersom avfall kan uppstå både på bredd och längd. ^{[ citat behövs ]}
Giljotinproblemet är ett annat 2D-problem med att skära ark i rektanglar av specificerade storlekar, men endast skärningar som fortsätter hela vägen över varje ark är tillåtna . Industriella tillämpningar av detta problem kan hittas inom glasindustrin.

Exempel på ett giljotinsnitt

Exempel på ett icke-giljotinsnitt

Styckningsbeståndsproblemet att bestämma, för det endimensionella fallet, den bästa huvudstorleken som kommer att möta en given efterfrågan kallas sortimentsproblemet .

Historia

Problemet med skärmaterial formulerades först av Kantorovich 1939. 1951 innan datorer blev allmänt tillgängliga föreslog LV Kantorovich och VA Zalgaller att man skulle lösa problemet med ekonomisk användning av material i skärstadiet med hjälp av linjär programmering. Den föreslagna tekniken kallades senare kolumngenereringsmetoden .

Matematisk formulering och lösningsmetoder

Standardformuleringen för styckningsbeståndsproblemet (men inte den enda) börjar med en lista med m beställningar, som var och en kräver $q_{j}$ bitar, där $j =1,\ldots ,m$ . Vi konstruerar sedan en lista över alla möjliga kombinationer av snitt (ofta kallade "mönster" eller "konfigurationer"). Låt $C$ vara antalet av dessa mönster. Vi associerar till varje mönster en positiv heltalsvariabel $x_{i}$ , som representerar hur många gånger mönster $i$ ska användas, där $i=1 ,\ldots ,C$ . Det linjära heltalsprogrammet är då:

\min \sum _{i=1}^{C}c_{i}x_{i}

{\text{st}}\sum _{i=1}^{C}a_{ij}x_{i}\geq q_{j},\quad \quad \forall j=1,\dots ,m

x_{i}\geq 0

, heltal

där $a_{ij}$ är antalet gånger order $j$ visas i mönstret $i$ och $c_{i}$ är kostnaden (ofta avfall) av mönster $i$ . Den exakta karaktären hos kvantitetsbegränsningarna kan leda till subtilt olika matematiska egenskaper. Ovanstående formulerings kvantitetsbegränsningar är minimibegränsningar (åtminstone den givna mängden av varje beställning måste produceras, men möjligen mer).

När $c_{i}=1$ , minimerar målet antalet använda masterartiklar och, om begränsningen för den kvantitet som ska produceras ersätts med jämlikhet, kallas det för papperspackningsproblem .

Den mest allmänna formuleringen har tvåsidiga begränsningar (och i det här fallet kan en minimiavfallslösning förbruka mer än det minsta antalet huvudartiklar):

q_{j}\leq \sum _{i=1}^{n}a_{ij} x_{i}\leq Q_{j},\quad \quad \forall j=1,\dots ,m

Denna formulering gäller inte bara för endimensionella problem. Många varianter är möjliga, inklusive en där målet inte är att minimera avfallet, utan att maximera det totala värdet av de producerade föremålen, vilket gör att varje beställning får ett annat värde.

I allmänhet växer antalet möjliga mönster exponentiellt som en funktion av m , antalet order. I takt med att antalet beställningar ökar kan det därför bli opraktiskt att räkna upp möjliga skärmönster.

En alternativ metod använder fördröjd kolumngenerering . Denna metod löser styckningsproblemet genom att börja med bara några få mönster. Det genererar ytterligare mönster när de behövs. För det endimensionella fallet introduceras de nya mönstren genom att lösa ett extra optimeringsproblem som kallas ryggsäcksproblemet, med hjälp av dubbel variabel information från det linjära programmet . Ryggsäcksproblemet har välkända metoder för att lösa det, som förgrening och bunden och dynamisk programmering . Metoden för fördröjd kolumngenerering kan vara mycket effektivare än den ursprungliga metoden, särskilt när problemets storlek växer. Tillvägagångssättet för kolumngenerering som tillämpats på problemet med styckningsmaterial var pionjärer av Gilmore och Gomory i en serie artiklar publicerade på 1960-talet. Gilmore och Gomory visade att detta tillvägagångssätt garanterat konvergerar till den optimala (fraktionella) lösningen, utan att behöva räkna upp alla möjliga mönster i förväg.

En begränsning av den ursprungliga Gilmore and Gomory-metoden är att den inte hanterar integralitet, så lösningen kan innehålla fraktioner, t.ex. bör ett speciellt mönster produceras 3,67 gånger. Avrundning till närmaste heltal fungerar ofta inte, i den meningen att det kan leda till en suboptimal lösning och/eller under- eller överproduktion av några av beställningarna (och möjlig omöjlighet i närvaro av tvåsidiga efterfrågebegränsningar ). Denna begränsning övervinns i moderna algoritmer, som kan lösa till optimalitet (i betydelsen att hitta lösningar med minimalt slöseri) mycket stora instanser av problemet (i allmänhet större än vad som förekommer i praktiken).

Problemet med styckningslager är ofta mycket degenererat, eftersom flera lösningar med samma mängd avfall är möjliga. Denna degeneration uppstår eftersom det är möjligt att flytta runt föremål, skapa nya mönster, utan att påverka mängden avfall. Detta ger upphov till en hel samling relaterade problem som rör något annat kriterium, såsom följande:

Problemet med minsta antal mönster: att hitta en lösning med minsta antal mönster bland lösningarna för minsta avfall. Detta är ett mycket svårt problem, även när avfallet är känt. Det finns en gissning att alla likhetsbegränsade endimensionella instanser med n storlekar har minst en minsta avfallslösning med högst n + 1 mönster. Denna gissning motbevisades först i april 2020 med ett exempel med 9 storlekar som kräver 11 mönster.
Minsta stackproblem: detta handlar om sekvenseringen av mönstren för att inte ha för många delvis slutförda beställningar när som helst. Detta var ett öppet problem fram till 2007, då en effektiv algoritm baserad på dynamisk programmering publicerades.
Det minsta antalet knivbytensproblem (för det endimensionella problemet): detta handlar om sekvensering och permutering av mönstren för att minimera antalet gånger som skärknivarna måste flyttas. Detta är ett specialfall av det allmänna problemet med resande försäljare .

Se även

Vidare läsning

Chvátal, V. (1983). Linjär programmering . WH Freeman. ISBN 978-0-7167-1587-0 .
Hatem Ben Amor, JM Valério de Carvalho, Cutting Stock Problems in Column Generation, redigerad av Guy Desaulniers, Jacques Desrosiers och Marius M. Solomon, Springer, 2005, XVI, ISBN 0-387-25485-4
M. Delorme, M. Iori, S. Martello, Bin packing and cutting stock problems: Mathematical models and exact algorithms , European Journal of Operational Research 2016, 255, 1–20, doi : 10.1016/j.ejor.2016.04.030