Skärningsuppgift

Häckningsproblemet  är ett NP-komplett optimeringsproblem , som i huvudsak kan reduceras till ett ryggsäcksproblem . Problemet är ett heltalslinjärt programmeringsproblem . Problemet uppstår inom många branscher. Föreställ dig att du arbetar i ett massa- och pappersbruk och du har ett antal pappersrullar med fast bredd, men olika kunder behöver olika många rullar av olika bredd. Hur skär man papper för att minimera avfallet?

Enligt Confederation of European Paper Manufacturers [1] genererade 1 331 pappersmaskiner i regionen 2012 ett genomsnittligt avfall på 56 miljoner euro (cirka 73 miljoner US-dollar) vardera. Att spara till och med 1% kommer att vara mycket betydande.

Problemformulering och tillvägagångssätt för lösning

Standardformuleringen av kapslingsproblemet (men inte det enda) förutsätter en lista med m beställningar, varje beställning kräver bitar. Vi bildar alla möjliga kapslingskombinationer (”klippkartor”) och associerar till varje karta en positiv heltalsvariabel , som anger hur många gånger kartan användes. Låt oss skriva ner det linjära programmeringsproblemet:

var  - hur många gånger beställningen förekommer på kortet och  - priset (ofta förlorat) på kortet . Den exakta karaktären av begränsningarna kan leda till något annorlunda matematiska egenskaper. De angivna gränserna är minimigränser ( minst en given mängd måste produceras, men det är inte uteslutet att mer kommer att produceras). Om , det krävs för att minimera antalet skurna bitar av källmaterialet. Om begränsningarna från ojämlikheter ersätts av jämlikheter, kallas problemet containerizing . I en mer allmän formulering är begränsningarna tvåsidiga (och i det här fallet kan lösningen för förlustminimering skilja sig från lösningen med det minsta antalet källmaterialdelar):

Denna formulering av problemet är inte bara tillämplig på det endimensionella fallet. Många variationer är möjliga, till exempel är målet inte att minimera avfallet, utan att maximera det totala antalet producerade varor.

I allmänhet växer antalet möjliga kort exponentiellt med m , antalet order. När antalet beställningar ökar kan det inte vara praktiskt att lista möjliga häckningsmönster.

Alternativt kan postgenerering användas . Denna metod löser kapslingsproblemet genom att börja med några kort. Metoden genererar nya kartor vid behov under lösningsprocessen. I det endimensionella fallet dyker nya kartor upp när man löser ett ytterligare optimeringsproblem, ryggsäcksproblemet , som använder information om de dubbla variablerna i ett linjärt programmeringsproblem . Ryggsäcksproblemet har välkända metoder för att lösa det, som gren- och bindningsmetoden och dynamisk programmering . Generering av lata kolumner kan vara mycket effektivare än det ursprungliga tillvägagångssättet, särskilt när uppgiften blir större. Fördröjd kolumngenerering som tillämpats på häckningsproblemet användes först av Gilmour och Gomory i en serie artiklar publicerade på 1960-talet [2] [3] . De visade att detta tillvägagångssätt garanterat leder till en (fraktionell) optimal lösning utan att behöva räkna upp alla möjliga kartor i förväg.

Gilmour och Gomorys ursprungliga metod var inte heltal, så lösningen kunde innehålla bråkdelar, till exempel måste en viss karta användas 3,67 gånger. Avrundning till närmaste heltal fungerar ofta inte, i den meningen att det resulterar i en suboptimal lösning och underproduktion eller överproduktion för vissa beställningar (och eventuellt överträdelse av begränsningar om tvåsidigt). Denna brist övervinns i nya algoritmer som gör det möjligt att hitta optimala lösningar (i betydelsen att hitta en lösning med minimalt slöseri) av mycket stora problem (i allmänhet större än vad som behövs i praktiken [4] [5] ).

Häckningsproblemet är ofta extremt degenererat, eftersom ett stort antal lösningar är möjliga med samma mängd förluster. Denna degeneration uppstår från förmågan att ordna om delar, skapa nya häckningsmönster, men inte förändra de resulterande förlusterna. Detta ger en hel samling relaterade uppgifter som uppfyller samma begränsningar, såsom:

• Uppgiften att hitta det minsta antalet häckningskartor: hitta en lösning med ett minsta antal häckningskartor bland lösningar med minimala förluster. Denna uppgift är mycket svår, även om förlusterna är kända [6] [7] . Det finns en gissning att varje ekvationsbegränsat endimensionellt kapslingsproblem med n beställningar har minst en minsta avfallslösning med n + 1 kapslingskartor. Övre gränser för antalet häckningsdiagram är inte kända, även om exempel med n + 5 är kända.

• Minimilagrets uppgift: att hitta en skärsekvens så att ett stort antal delvis slutförda beställningar inte ackumuleras. Problemet var öppet fram till 2007, då en effektiv algoritm baserad på dynamisk programmering [8] publicerades .

• Problemet med det minsta antalet knivbyten (för ett endimensionellt häckningsproblem): hitta sekvensen för att applicera häckningskartor för att minimera antalet rörelser av skärknivarna. Detta problem är ett specialfall av det generella problemet med resande försäljare .

En illustration av ett endimensionellt skärproblem

Pappersmaskinen kan producera ett obegränsat antal rullar (ämnen), var och en 5600 mm bred. Du måste få följande 13 slutrullar:

Lösning

Det finns 308 möjliga häckningsmönster för denna lilla uppgift. Den optimala lösningen kräver 73 originalrullar och har 0,401 % spill. Det kan visas att minsta antal bon för denna mängd avfall är 10. Man kan också räkna ut att det finns 19 så olika lösningar, var och en med 10 bon och 0,401 % avfall. En sådan lösning visas nedan och i figuren:

Klassificering

Häckningsuppgifter kan klassificeras på olika sätt [9] . Ett sätt är kapslingsdimensioner: exemplet ovan illustrerar endimensionell kapsling (1D). Andra industriella användningsområden för 1D-kapning är att skära rör, kablar och stålstänger. Tvådimensionella problem används vid tillverkning av möbler, kläder och glas. Det finns inte många 3D-kapslingstillämpningar, men relaterade 3D- packningsproblem har många industriella tillämpningar, särskilt distributionen av föremål i fraktcontainrar ( se t.ex. Keplers hypotes .

Uppgiften att skära i pappers-, film- och stålindustrin

En industriell tillämpning av häckningsproblemet för massproduktionsanläggningar uppstår när basmaterialet produceras i stora rullar och sedan skärs i mindre bitar (se skärning ). Detta sker till exempel vid tillverkning av papper och polymerfilmer, såväl som vid tillverkning av platta metallplåtar (järn eller brons). Det finns många variationer och ytterligare begränsningar på grund av tillverknings- eller processbegränsningar, kundkrav och kvalitetsproblem. Några exempel:

• En tvåstegsprocess där rullen tillverkas i det första steget och sedan bearbetas igen på en annan maskin. Till exempel produceras allt kontorspapper (t.ex. A4 i Europa, Letter i USA) i denna process. Svårigheter uppstår eftersom maskinerna för den andra processen är smalare än maskinerna för den första. Effektiv användning av båda processtegen är viktigt (både när det gäller materialbesparingar och energibesparingar) och det som fungerar för det första steget kanske inte fungerar för det andra, och en kompromiss måste hittas. Metalliserad film (används för livsmedelsförpackningar) och plastbelagt papper ( vätskeförpackningskartong , till exempel juiceförpackningar) är andra exempel på sådana processer.

• Winders begränsar skärningen fysiskt eller logiskt: allmänna begränsningar uppstår av att endast ett visst antal knivar är tillåtna, så skärtabellen bör inte innehålla mer än ett visst antal knivar. Eftersom rullmaskiner inte är standardiserade finns det många ytterligare begränsningar.

• Som en ytterligare begränsning kan till exempel en begränsning av skärriktningen ges - olika kanter på plåten kan ha stor skillnad i tjocklek och vissa applikationer är mycket känsliga för detta.

• Ett exempel på inverkan av kvalitetskrav är när huvudrullen innehåller defekter som bör skäras bort. Dyra material med höga krav på materialkvalitet, som fotopapper eller Tyvek , bör noggrant optimeras för att minimera avfallet.

• Flermaskinsuppgifter uppstår när en order kan produceras på mer än en maskin och dessa maskiner har olika bredd. I grund och botten minskar tillgången på flera källrullar med olika bredder avfallet. I praktiken måste dock en ytterligare styckningsordning beaktas.

• Det finns också problem när de resulterande rullarna inte behöver ha samma diameter, utan kan vara inom ett visst intervall. Ibland kallas detta problem för 1½ dimensionsproblemet . Denna variant förekommer till exempel vid tillverkning av wellpapp .

• Inom stålvalsindustrin är ett utmärkande drag att originalrullarna huvudsakligen skiljer sig åt i både bredd och längd. Det finns alltså en likhet med multimaskinvarianten som beskrivs ovan. I detta fall kan avfall uppstå både på bredden och på längden.

Kapslingsprogramvara för pappersindustrin levereras av ABB Group , Greycon , Honeywell och Tieto .

Kapslingsalgoritmen för stålindustrin formulerades av Robert Gongorra 1998 och SONS (Steel Optimization Nesting Software) utvecklade mjukvara för att förbättra användningen av stålplåt och minska avfallet.

Skärningsproblem för glasindustrin

Uppgiften med giljotinskärning  är uppgiften att skära glasskivor till rektanglar med specifika dimensioner, med endast snitt som löper längs hela längden (eller bredden) av skivan.

Sortimentproblem

Det relaterade problemet med att bestämma (för det endimensionella fallet) den bästa storleken på originalrullen som uppfyller kraven; känt som sortimentsproblemet [10] .

Historik

Skärproblemet formulerades först av Kantorovich 1939 [11] . 1951, även innan datorer blev allmänt tillgängliga, föreslog L. V. Kantorovich och V. A. Zalgaller [12] en metod för att lösa problemet med ekonomisk användning av material under skärning med linjär programmering. Den föreslagna tekniken kallades senare Column Generation Method .

Programvara

Anteckningar

1. ↑ Nyckelstatistik 2012 (inte tillgänglig länk) . Confederation of European Paper Industries. Hämtad 3 juli 2013. Arkiverad från originalet 6 oktober 2014. (obestämd) 
2. ↑ PC Gilmore, RE Gomory. En linjär programmeringsmetod för stycklagerproblemet // Operations Research. - 1961. - Nr 9 . - S. 849-859 .
3. ↑ PC Gilmore, RE Gomory. En linjär programmeringsmetod för styckningsbeståndsproblemet - Del II // Operations Research. - 1963. - Nr 11 . - S. 863-888 .
4. ↑ C. Goulimis. Optimala lösningar för styckningsbeståndsproblemet // European Journal of Operational Research. - 1990. - Nr 44 . - S. 197-208 .
5. ↑ V. de Carvalho. Exakt lösning av styckningsproblem med hjälp av kolumngenerering och branch-and-bound // Internationella transaktioner inom operationell forskning. - 1998. - Nr 5 . - S. 35-44 .
6. ↑ S. Umetani, M. Yagiura och T. Ibaraki. Endimensionellt styckningsproblem för att minimera antalet olika mönster // European Journal of Operational Research. - 2003. - Nr 146 . - S. 388-402 .
7. ↑ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk och S. Naidoo. Konfigurera minimerande förhållanden i trimförlustproblemet // European Journal of Operational Research. - 1996. - Nr 95 . - S. 631-640 .
8. ↑ Maria Garcia de la Banda, PJ Stuckey. ynamisk programmering för att minimera det maximala antalet öppna stackar // INFORMERAR journal om datoranvändning. - 3007. - T. 19 , nr 4 . - S. 607-617 .
9. ↑ G. Wäscher, H. Hausner, H. Schumann. En förbättrad typologi för skär- och packningsproblem // European Journal of Operational Research. - T. 183 , nr 3 . - S. 1109-1130 .
10. ↑ Raffensperger John F. Det generaliserade sortimentet och problemen med bästa skärstockslängd  // International Transactions in Operational Research. - 2010. - Januari ( vol. 17 , nr 1 ). - S. 35-49 . — ISSN 0969-6016 . - doi : 10.1111/j.1475-3995.2009.00724.x .
11. ↑ L. V. Kantorovich. Matematiska metoder för att organisera och planera produktionen. – Leningrad State University.
12. ↑ Kantorovich L. V., Zalgaller V. A. Rationell skärning av industrimaterial. - Novosibirsk: Nauka, 1971.

Litteratur

• linjär programmering. - W. H. Freeman, 1983. - ISBN 978-0-7167-1587-0 .
• Hatem Ben Amor, JM Valério de Carvalho. Kolumngenerering // Cutting Stock Problems in Column Generation / Guy Desaulniers, Jacques Desrosiers och Marius M. Solomon. - Springer, 2005. - T. XVI. — ISBN 0-387-25485-4 .

Länkar

• Europeisk specialintressegrupp för skärning och packning
• En rudimentär brute-force-algoritm för att skära lager
• Bin Packing och Cutting Stock Solver Algoritm