Skæreopgave

Redeproblemet  er et NP-komplet optimeringsproblem , der i det væsentlige kan reduceres til et rygsækproblem . Problemet er et heltals lineært programmeringsproblem . Problemet opstår i mange områder af industrien. Forestil dig, at du arbejder i en papirmasse- og papirfabrik, og du har et antal papirruller med fast bredde, men forskellige kunder har brug for forskelligt antal ruller af forskellig bredde. Hvordan skærer man papir for at minimere spild?

Ifølge Confederation of European Paper Manufacturers [1] genererede 1.331 papirmaskiner i regionen i 2012 et gennemsnitligt spild på 56 millioner euro (ca. 73 millioner amerikanske dollars) hver. En besparelse på selv 1 % vil være meget betydelig.

Problemformulering og tilgange til løsning

Standardformuleringen af ​​indlejringsproblemet (men ikke den eneste) forudsætter en liste med m ordrer, hver ordre kræver stykker. Vi danner alle mulige nesting-kombinationer ("klippekort") og forbinder med hvert kort en positiv heltalsvariabel , der angiver, hvor mange gange kortet blev brugt. Lad os skrive det lineære programmeringsproblem ned:

hvor  - hvor mange gange ordren vises på kortet og  - prisen (ofte tabt) på kortet . Den præcise karakter af begrænsningerne kan føre til lidt forskellige matematiske karakteristika. De angivne grænser er minimumsgrænser ( mindst en given mængde skal produceres, men det er ikke udelukket, at der vil blive produceret mere). Hvis , er det nødvendigt at minimere antallet af afskårne stykker af kildematerialet. Hvis begrænsningerne fra uligheder erstattes af ligheder, kaldes problemet containerisering . I en mere generel formulering er begrænsningerne tosidede (og i dette tilfælde kan tabsminimeringsløsningen afvige fra løsningen med det mindste antal kildematerialestykker):

Denne problemformulering gælder ikke kun for det endimensionelle tilfælde. Mange variationer er mulige, for eksempel er målet ikke at minimere spild, men at maksimere det samlede antal producerede varer.

Generelt vokser antallet af mulige kort eksponentielt med m , antallet af ordrer. Efterhånden som antallet af ordrer stiger, er det muligvis ikke praktisk at angive mulige redemønstre.

Alternativt kan postgenerering bruges . Denne metode løser indlejringsproblemet ved at starte med et par kort. Metoden genererer nye kort, hvis det er nødvendigt, under løsningsprocessen. I det endimensionelle tilfælde dukker der nye kort op, når man løser et yderligere optimeringsproblem, rygsækproblemet , som bruger information om de dobbelte variable i et lineært programmeringsproblem . Rygsækproblemet har velkendte metoder til at løse det, såsom branch and bound-metoden og dynamisk programmering . Generering af doven kolonner kan være meget mere effektiv end den oprindelige tilgang, især når opgavens størrelse vokser. Forsinket kolonnegenerering som anvendt på redeproblemet blev første gang brugt af Gilmour og Gomory i en række artikler udgivet i 1960'erne [2] [3] . De viste, at denne tilgang med garanti vil føre til en (fraktionel) optimal løsning uden at skulle opregne alle mulige kort på forhånd.

Gilmour og Gomorys oprindelige metode var ikke heltal, så løsningen kunne indeholde fraktionerede komponenter, for eksempel skulle et bestemt kort bruges 3,67 gange. Afrunding til nærmeste heltal virker ofte ikke i den forstand, at det resulterer i en suboptimal løsning og underproduktion eller overproduktion for nogle ordrer (og mulig overtrædelse af begrænsninger, hvis de er tosidede). Denne mangel overvindes i nye algoritmer, der gør det muligt at finde optimale løsninger (i betydningen at finde en løsning med minimalt spild) af meget store problemer (generelt større end nødvendigt i praksis [4] [5] ).

Redeproblemet er ofte ekstremt degenereret, da et stort antal løsninger er mulige med samme mængde tab. Denne degeneration opstår fra evnen til at omarrangere dele, skabe nye redemønstre, men ikke ændre de resulterende tab. Dette giver en hel samling af relaterede opgaver, der opfylder de samme begrænsninger, såsom:

• Opgaven med at finde det mindste antal redekort: Find en løsning med et minimum af redekort blandt løsninger med minimale tab. Denne opgave er meget vanskelig, selvom tabene er kendte [6] [7] . Der er en formodning om, at ethvert ligningsbegrænset endimensionelt indlejringsproblem med n ordrer har mindst én minimumsspildløsning med n + 1 indlejringskort. Øvre grænser for antallet af redekort kendes ikke, selvom der kendes eksempler med n + 5.

• Minimumslagerets opgave: at finde en skæresekvens, så et stort antal delvist afsluttede ordrer ikke akkumuleres. Problemet var åbent indtil 2007, hvor en effektiv algoritme baseret på dynamisk programmering [8] blev offentliggjort .

• Problemet med det mindste antal knivskift (for et endimensionelt redeproblem): find rækkefølgen af ​​påføring af redekort for at minimere antallet af bevægelser af skæreknivene. Dette problem er et særligt tilfælde af det generelle problem med rejsende sælger .

En illustration af et endimensionelt skæreproblem

Papirmaskinen kan producere et ubegrænset antal ruller (emner), hver 5600 mm bred. Du skal have følgende 13 sidste ruller:

Løsning

Der er 308 mulige redemønstre til denne lille opgave. Den optimale løsning kræver 73 originale ruller og har 0,401 % spild. Det kan påvises, at minimumsantallet af reder for denne mængde affald er 10. Det kan også beregnes, at der findes 19 så forskellige løsninger, hver med 10 reder og 0,401 % affald. En sådan løsning er vist nedenfor og i figuren:

Klassifikation

Redeopgaver kan klassificeres på forskellige måder [9] . En måde er indlejringsdimensioner: Ovenstående eksempel illustrerer endimensionel indlejring (1D). Andre industrielle anvendelser til 1D-nesting er at skære rør, kabler og stålstænger. Todimensionelle problemer bruges i produktionen af ​​møbler, tøj og glas. Der er ikke mange 3D-nesting-applikationer, men relaterede 3D - pakningsproblemer har mange industrielle applikationer , især distribution af genstande i forsendelsescontainere ( se f.eks. Keplers hypotese .

Opgaven med at skære i papir-, film- og stålindustrien

En industriel anvendelse af redeproblemet til masseproduktionsanlæg opstår, når basismaterialet fremstilles i store ruller og derefter skæres i mindre stykker (se opskæring ). Dette sker for eksempel ved fremstilling af papir- og polymerfilm samt ved fremstilling af flade metalplader (jern eller bronze). Der er mange variationer og yderligere begrænsninger på grund af fremstillings- eller procesbegrænsninger, kundekrav og kvalitetsproblemer. Nogle eksempler:

• En to-trins proces, hvor rullen produceres i første fase og derefter bearbejdes igen på en anden maskine. For eksempel produceres alt kontorpapir (f.eks. A4 i Europa, Letter i USA) i denne proces. Vanskeligheder opstår, fordi maskinerne til den anden proces er smallere end maskinerne til den første. Effektiv brug af begge procestrin er vigtig (både med hensyn til materialebesparelser og energibesparelser), og det, der virker for det første trin, fungerer muligvis ikke for det andet, og et kompromis skal findes. Metalliseret film (bruges til fødevareemballage) og plastbelagt papir ( flydende emballagekarton , f.eks. juiceemballage) er andre eksempler på sådanne processer.

• Oprullere begrænser skæringen fysisk eller logisk: Generelle begrænsninger opstår som følge af, at kun et vist antal knive er tilladt, så skæreskemaet bør ikke indeholde mere end et vist antal knive. Da oprullere ikke er standardiserede, er der mange yderligere begrænsninger.

• Som en yderligere begrænsning kan der f.eks. gives en begrænsning af skæreretningen - forskellige kanter på pladen kan have stor tykkelsesforskel og nogle applikationer er meget følsomme over for dette.

• Et eksempel på indvirkningen af ​​kvalitetskrav er, når hovedrullen indeholder fejl, der bør skæres ud. Dyre materialer med høje krav til materialekvalitet, såsom fotografisk papir eller Tyvek , bør omhyggeligt optimeres for at minimere spild.

• Multimaskine opgaver opstår, når en ordre kan produceres på mere end én maskine, og disse maskiner har forskellige bredder. Grundlæggende reducerer tilgængeligheden af ​​flere kilderuller med forskellige bredder spild. I praksis skal der dog tages hensyn til en yderligere skærerækkefølge.

• Der er også problemer, når de resulterende ruller ikke behøver at have samme diameter, men kan være inden for et vist interval. Nogle gange kaldes dette problem for 1½ dimensionsproblemet . Denne variant optræder for eksempel ved fremstilling af bølgepap .

• I stålvalseindustrien er det et særkende, at de originale spoler hovedsageligt er forskellige i både bredde og længde. Der er således en lighed med multimaskinevarianten beskrevet ovenfor. I dette tilfælde kan spild forekomme både i bredden og i længden.

Indlejringssoftware til papirindustrien er leveret af ABB Group , Greycon , Honeywell og Tieto .

Indlejringsalgoritmen for stålindustrien blev formuleret af Robert Gongorra i 1998, og SONS (Steel Optimization Nesting Software) udviklede software til at forbedre stålpladeudnyttelsen og reducere spild.

Skæreproblem for glasindustrien

Opgaven med guillotineskæring  er opgaven med at skære glasplader i rektangler af specifikke dimensioner, ved kun at bruge snit, der løber langs hele arkets længde (eller bredde).

Sortimentsproblem

Det relaterede problem med at bestemme (for det endimensionelle tilfælde) den bedste størrelse af den originale rulle, der opfylder kravene; kendt som sortimentsproblemet [10] .

Historie

Skæreproblemet blev først formuleret af Kantorovich i 1939 [11] . I 1951, selv før computere blev bredt tilgængelige, foreslog L. V. Kantorovich og V. A. Zalgaller [12] en metode til at løse problemet med økonomisk brug af materiale under skæring ved hjælp af lineær programmering. Den foreslåede teknik blev senere kaldt Column Generation Method .

Software

Noter

1. ↑ Nøglestatistikker 2012 (ikke tilgængeligt link) . Sammenslutningen af ​​europæiske papirindustrier. Hentet 3. juli 2013. Arkiveret fra originalen 6. oktober 2014. (ubestemt) 
2. ↑ PC Gilmore, RE Gomory. En lineær programmeringstilgang til skærelagerproblemet // Operations Research. - 1961. - Nr. 9 . - S. 849-859 .
3. ↑ PC Gilmore, RE Gomory. En lineær programmeringstilgang til opskæringsproblemet - Del II // Operations Research. - 1963. - Nr. 11 . - S. 863-888 .
4. ↑ C. Goulimis. Optimale løsninger til problemet med opskæring af materiel // European Journal of Operational Research. - 1990. - Nr. 44 . - S. 197-208 .
5. ↑ V. de Carvalho. Præcis løsning af opskæringsproblemer ved brug af kolonnegenerering og branch-and-bound // Internationale Transaktioner i Operational Research. - 1998. - Nr. 5 . - S. 35-44 .
6. ↑ S. Umetani, M. Yagiura og T. Ibaraki. Et dimensionelt skærematerialeproblem for at minimere antallet af forskellige mønstre // European Journal of Operational Research. - 2003. - Nr. 146 . - S. 388-402 .
7. ↑ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk og S. Naidoo. Opsætning af minimerende forhold i trimtabsproblemet // European Journal of Operational Research. - 1996. - Nr. 95 . - S. 631-640 .
8. ↑ Maria Garcia de la Banda, PJ Stuckey. ynamisk programmering for at minimere det maksimale antal åbne stakke // INFORMERER Journal om computing. - 3007. - T. 19 , nr. 4 . - S. 607-617 .
9. ↑ G. Wäscher, H. Hausner, H. Schumann. En forbedret typologi af skære- og pakningsproblemer // European Journal of Operational Research. - T. 183 , nr. 3 . - S. 1109-1130 .
10. ↑ Raffensperger John F. The generalized assortment and best cutting stock length problems  // International Transactions in Operational Research. - 2010. - Januar ( bind 17 , nr. 1 ). - S. 35-49 . — ISSN 0969-6016 . - doi : 10.1111/j.1475-3995.2009.00724.x .
11. ↑ L. V. Kantorovich. Matematiske metoder til organisering og planlægning af produktion. – Leningrad State University.
12. ↑ Kantorovich L. V., Zalgaller V. A. Rationel skæring af industrielle materialer. - Novosibirsk: Nauka, 1971.

Litteratur

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

Links

• European Special Interest Group on Cutting & Packing
• En rudimentær brute-force algoritme til at skære materiel
• Bindingspakning og skærende lagerløseralgoritme