Leikkaustehtävä

Sisäkkäisongelma  on NP-täydellinen optimointiongelma , joka voidaan olennaisesti pelkistää reppuongelmaksi . Ongelma on lineaarinen kokonaislukuohjelmointiongelma . Ongelma ilmenee monilla teollisuuden aloilla. Kuvittele, että työskentelet sellu- ja paperitehtaalla ja sinulla on useita kiinteäleveisiä paperirullia, mutta eri asiakkaat tarvitsevat eri määrän eri levyisiä rullia. Kuinka leikata paperia jätteen minimoimiseksi?

European Paper Manufacturers Confederation [1] mukaan vuonna 2012 alueen 1 331 paperikonetta tuottaa kukin keskimäärin 56 miljoonan euron (noin 73 miljoonaa dollaria) jätettä. Jo 1 %:n säästö on erittäin merkittävää.

Ongelman muotoilu ja lähestymistavat ratkaisuun

Sisäkkäisongelman vakiomuotoilu (mutta ei ainoa) olettaa listan m tilauksesta, jokainen tilaus vaatii kappaletta. Muodostamme kaikki mahdolliset sisäkkäiset yhdistelmät ("leikkauskartat") ja liitämme jokaiseen karttaan positiivisen kokonaislukumuuttujan , joka osoittaa kuinka monta kertaa karttaa on käytetty. Kirjataan ylös lineaarisen ohjelmoinnin ongelma:

missä  - kuinka monta kertaa tilaus näkyy kortissa ja  - kortin hinta (usein kadonnut) . Rajoitusten tarkka luonne voi johtaa hieman erilaisiin matemaattisiin ominaisuuksiin. Annetut rajat ovat minimirajoja ( vähintään tietty määrä on tuotettava, mutta ei ole poissuljettua, että tuotetta tulee lisää). Jos , on tarpeen minimoida lähdemateriaalin leikattujen kappaleiden määrä. Jos epätasa-arvosta johtuvat rajoitukset korvataan yhtäläisyyksillä, ongelmaa kutsutaan konteiroimiseksi . Yleisemmässä muotoilussa rajoitukset ovat kaksipuolisia (ja tässä tapauksessa häviön minimointiratkaisu voi poiketa ratkaisusta, jossa on vähimmäismäärä lähdemateriaalikappaleita):

Tämä ongelman muotoilu ei sovellu vain yksiulotteiseen tapaukseen. Monia muunnelmia on mahdollista, esimerkiksi tavoitteena ei ole minimoida jätettä, vaan maksimoida tuotettujen tavaroiden kokonaismäärä.

Yleisesti ottaen mahdollisten korttien määrä kasvaa eksponentiaalisesti m :n kanssa, tilausten määrä. Tilausten määrän kasvaessa ei ehkä ole käytännöllistä luetella mahdollisia sisäkkäismalleja.

Vaihtoehtoisesti voidaan käyttää jälkigenerointia . Tämä menetelmä ratkaisee sisäkkäisongelman aloittamalla muutamalla kortilla. Menetelmä luo tarvittaessa uusia karttoja ratkaisuprosessin aikana. Yksiulotteisessa tapauksessa uudet kartat ilmestyvät, kun ratkaistaan ​​lisäoptimointitehtävä, selkärepputehtävä , joka käyttää tietoa lineaarisen ohjelmointitehtävän kaksoismuuttujista . Reppuongelman ratkaisemiseksi on tunnettuja menetelmiä, kuten haara ja sidottu menetelmä sekä dynaaminen ohjelmointi . Laiska sarakkeen luominen voi olla paljon tehokkaampaa kuin alkuperäinen lähestymistapa, varsinkin kun tehtävän koko kasvaa. Gilmour ja Gomory käyttivät ensimmäisen kerran 1960-luvulla julkaistuissa kirjoissa [2] [3] viivästettyä sarakkeiden luomista , jota käytettiin sisäkkäisongelmaan . He osoittivat, että tämä lähestymistapa johtaa taatusti (osittain) optimaaliseen ratkaisuun ilman, että kaikkia mahdollisia karttoja tarvitsee luetella etukäteen.

Gilmourin ja Gomoryn alkuperäinen menetelmä ei ollut kokonaisluku, joten ratkaisu saattoi sisältää murto-osia, esimerkiksi tiettyä karttaa piti käyttää 3,67 kertaa. Pyöristys lähimpään kokonaislukuun ei useinkaan toimi siinä mielessä, että se johtaa alioptimaaliseen ratkaisuun ja joidenkin tilausten ali- tai ylituotantoon (ja mahdolliseen rajoitusten rikkomiseen, jos se on kaksipuolista). Tämä puute on korjattu uusilla algoritmeilla, jotka mahdollistavat optimaalisen ratkaisun löytämisen (sillä mielessä, että ratkaisu löytyy mahdollisimman vähän hukkaa) erittäin suuriin ongelmiin (yleensä suurempiin kuin käytännössä tarvitaan [4] [5] ).

Pesäongelma on usein erittäin rappeutunut, koska suuri määrä ratkaisuja on mahdollista samalla häviöllä. Tämä rappeutuminen johtuu kyvystä järjestää osia uudelleen ja luoda uusia sisäkkäisiä kuvioita, mutta ei muuta tuloksena olevia menetyksiä. Tämä antaa koko joukon liittyviä tehtäviä, jotka täyttävät samat rajoitukset, kuten:

• Tehtävä löytää minimimäärä sisäkkäisiä karttoja: etsi ratkaisu, jossa on mahdollisimman vähän sisäkkäisiä karttoja, ratkaisujen joukosta, joissa häviöt ovat mahdollisimman pienet. Tämä tehtävä on erittäin vaikea, vaikka häviöt ovat tiedossa [6] [7] . Oletuksena on , että millä tahansa yhtälörajoitteisella yksiulotteisella sisäkkäisongelmalla, jossa on n kertalukua, on vähintään yksi hukkaratkaisu, jossa on n + 1 sisäkkäistä karttaa. Pesäkaavioiden lukumäärän ylärajoja ei tunneta, vaikka esimerkkejä n + 5 tunnetaan.

• Vähimmäisvaraston tehtävä: löytää leikkausjärjestys, jotta suuri määrä osittain valmiita tilauksia ei kerry. Ongelma oli avoinna vuoteen 2007 asti, jolloin julkaistiin tehokas dynaamiseen ohjelmointiin perustuva algoritmi [8] .

• Veitsen vaihtojen vähimmäismäärän ongelma (yksiulotteiselle sisäkkäisongelmalle): etsi sisäkkäisten karttojen käyttöjärjestys leikkausterien liikkeiden määrän minimoimiseksi. Tämä ongelma on erikoistapaus yleisestä matkustava myyjä - ongelmasta .

Esimerkki yksiulotteisesta leikkausongelmasta

Paperikoneella voidaan valmistaa rajattomasti 5600 mm leveitä teloja (aihioita). Sinun tulee saada seuraavat 13 viimeistä rullaa:

Ratkaisu

Tässä pienessä tehtävässä on 308 mahdollista sisäkkäismallia. Optimaalinen ratkaisu vaatii 73 alkuperäistä rullaa ja siinä on 0,401 % jätettä. Voidaan osoittaa, että tälle jätemäärälle vähimmäispesämäärä on 10. Voidaan myös laskea, että tällaisia ​​erilaisia ​​ratkaisuja on 19, kussakin 10 pesää ja 0,401 % jätettä. Yksi tällainen ratkaisu on esitetty alla ja kuvassa:

Luokitus

Sisäkkäistehtävät voidaan luokitella eri tavoin [9] . Yksi tapa on sisäkkäiset mitat: yllä oleva esimerkki havainnollistaa yksiulotteista sisäkkäisyyttä (1D). Muita teollisia käyttötarkoituksia 1D-pesälle ovat putkien, kaapelien ja terästankojen leikkaaminen. Kaksiulotteisia ongelmia käytetään huonekalujen, vaatteiden ja lasin tuotannossa. 3D-sisäkkäisiä sovelluksia ei ole paljon, mutta niihin liittyvillä 3D -pakkausongelmilla on monia teollisia sovelluksia, erityisesti esineiden jakamisessa kuljetuskontteihin ( katso esim. Keplerin hypoteesi .

Leikkauksen tehtävänä paperi-, filmi- ja terästeollisuudessa

Pesäongelman teollinen sovellus massatuotantolaitoksille syntyy, kun perusmateriaali valmistetaan suurissa rullissa ja leikataan sitten pienemmiksi paloiksi (katso leikkaus ). Tätä tapahtuu esimerkiksi paperi- ja polymeerikalvojen valmistuksessa sekä litteiden metallilevyjen (rauta- tai pronssilevyjen) valmistuksessa. On olemassa monia muunnelmia ja lisärajoituksia, jotka johtuvat valmistus- tai prosessirajoituksista, asiakkaiden vaatimuksista ja laatuongelmista. Joitain esimerkkejä:

• Kaksivaiheinen prosessi, jossa rulla valmistetaan ensimmäisessä vaiheessa ja käsitellään sitten uudelleen toisella koneella. Esimerkiksi kaikki toimistopaperi (esim . A4 Euroopassa, Letter Yhdysvalloissa) valmistetaan tällä prosessilla. Vaikeuksia syntyy, koska toisen prosessin koneet ovat kapeampia kuin ensimmäisen prosessin koneet. Molempien prosessivaiheiden tehokas käyttö on tärkeää (sekä materiaalinsäästön että energiansäästön kannalta), ja mikä toimii ensimmäisessä vaiheessa, ei välttämättä toimi toisessa, ja kompromissi on löydettävä. Metalloitu kalvo (käytetään elintarvikepakkauksiin) ja muovipäällysteinen paperi ( nestepakkauskartonki , esimerkiksi mehupakkaukset) ovat muita esimerkkejä tällaisista prosesseista.

• Leikkurit rajoittavat leikkaamista fyysisesti tai loogisesti: yleiset rajoitukset johtuvat siitä, että vain tietty määrä veitsiä on sallittu, joten leikkauskaaviossa ei saa olla enemmän kuin tietty määrä veitsiä. Koska kelauskoneita ei ole standardoitu, on olemassa monia lisärajoituksia.

• Lisärajoituksena voidaan antaa esimerkiksi leikkaussuunnan rajoitus - levyn eri reunoilla voi olla suuri paksuusero ja jotkut sovellukset ovat erittäin herkkiä tälle.

• Esimerkki laatuvaatimusten vaikutuksesta on se, kun päätelassa on puutteita, jotka tulisi leikata pois. Kalliit materiaalit, joilla on korkeat materiaalin laatuvaatimukset, kuten valokuvapaperi tai Tyvek , tulee optimoida huolellisesti jätteen minimoimiseksi.

• Monikonetehtävät syntyvät, kun tilaus voidaan valmistaa useammalla kuin yhdellä koneella ja nämä koneet ovat eri leveyksiä. Pohjimmiltaan useiden eri levyisten telojen saatavuus vähentää jätettä. Käytännössä on kuitenkin otettava huomioon lisäleikkausjärjestys.

• Ongelmia esiintyy myös silloin, kun syntyvien telojen ei tarvitse olla halkaisijaltaan samanlaisia, vaan ne voivat olla tietyn aikavälin sisällä. Joskus tätä ongelmaa kutsutaan 1½-ulottuvuuden ongelmaksi . Tämä muunnelma esiintyy esimerkiksi aaltopahvin tuotannossa .

• Teräsvalssausteollisuudessa erottuva piirre on, että alkuperäiset kelat eroavat pääasiassa toisistaan ​​sekä leveydeltään että pituudeltaan. Siten on olemassa samankaltaisuus edellä kuvatun usean koneen muunnelman kanssa. Tässä tapauksessa jätettä voi esiintyä sekä leveydeltään että pituudeltaan.

Paperiteollisuuden pesäohjelmistoja toimittaa ABB Group , Greycon , Honeywell ja Tieto .

Terästeollisuuden sisäkkäisalgoritmin muotoili Robert Gongorra vuonna 1998, ja SONS (Steel Optimization Nesting Software) kehitti ohjelmiston parantamaan teräslevyjen käyttöä ja vähentämään jätettä.

Lasiteollisuuden leikkausongelma

Giljotiinileikkauksen  tehtävänä on leikata lasilevyt tietynkokoisiksi suorakulmioiksi käyttämällä vain leikkauksia, jotka kulkevat levyn koko pituudelta (tai leveydeltä).

Lajitelmaongelma

Tähän liittyvä ongelma (yksiulotteiselle tapaukselle) parhaan vaatimukset täyttävän alkuperäisen rullan koon määrittämisessä; tunnetaan lajitelmaongelmana [10] .

Historia

Leikkausongelman muotoili ensimmäisen kerran Kantorovich vuonna 1939 [11] . Vuonna 1951, jo ennen tietokoneiden yleistymistä, L. V. Kantorovich ja V. A. Zalgaller ehdottivat [12] menetelmää materiaalin taloudellisen käytön ongelman ratkaisemiseksi leikkauksen aikana lineaarisen ohjelmoinnin avulla. Ehdotettua tekniikkaa kutsuttiin myöhemmin Column Generation Methodiksi .

Ohjelmisto

Muistiinpanot

1. ↑ Keskeiset tilastot 2012 (linkki ei saatavilla) . Euroopan paperiteollisuuden keskusliitto. Haettu 3. heinäkuuta 2013. Arkistoitu alkuperäisestä 6. lokakuuta 2014. (määrätön) 
2. ↑ PC Gilmore, RE Gomory. Lineaarinen ohjelmointi lähestymistapa raaka-aineongelmaan // Operations Research. - 1961. - Nro 9 . - S. 849-859 .
3. ↑ PC Gilmore, RE Gomory. Lineaarinen ohjelmointi lähestymistapa raaka-aineongelmaan - Osa II // Operaatiotutkimus. - 1963. - Nro 11 . - S. 863-888 .
4. ↑ C. Goulimis. Optimaalisia ratkaisuja hakkuumassaongelmaan // European Journal of Operational Research. - 1990. - Nro 44 . - S. 197-208 .
5. ↑ V. de Carvalho. Tarkka ratkaisu lastuamismassaongelmien pylväiden generointiin ja haarautumiseen // International Transactions in Operational Research. - 1998. - Nro 5 . - S. 35-44 .
6. ↑ S. Umetani, M. Yagiura ja T. Ibaraki. Yksiulotteinen leikkausmassaongelma eri kuvioiden määrän minimoimiseksi // European Journal of Operational Research. - 2003. - Nro 146 . - S. 388-402 .
7. ↑ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk ja S. Naidoo. Asenna minimointiolosuhteet trimmaushäviöongelmassa // European Journal of Operational Research. - 1996. - Nro 95 . - S. 631-640 .
8. ↑ Maria Garcia de la Banda, PJ Stuckey. dynaaminen ohjelmointi avoimien pinojen enimmäismäärän minimoimiseksi // INFORMS Journal on Computing. - 3007. - T. 19 , nro 4 . - S. 607-617 .
9. ↑ G. Wäscher, H. Haußner, H. Schumann. Parannettu leikkaus- ja pakkausongelmien typologia // European Journal of Operational Research. - T. 183 , nro 3 . - S. 1109-1130 .
10. ↑ Raffensperger John F. Yleinen valikoima ja paras leikkuumassan pituusongelmat  // International Transactions in Operational Research. - 2010. - tammikuu ( osa 17 , nro 1 ) - S. 35-49 . — ISSN 0969-6016 . - doi : 10.1111/j.1475-3995.2009.00724.x .
11. ↑ L. V. Kantorovich. Matemaattiset menetelmät tuotannon organisoinnissa ja suunnittelussa. – Leningradin valtionyliopisto.
12. ↑ Kantorovich L. V., Zalgaller V. A. Teollisten materiaalien järkevä leikkaus. - Novosibirsk: Nauka, 1971.

Kirjallisuus

• lineaarinen ohjelmointi. - W. H. Freeman, 1983. - ISBN 978-0-7167-1587-0 .
• Hatem Ben Amor, JM Valério de Carvalho. Pylvässukupolvi // Pylväiden syntymisen ongelmat / Guy Desaulniers, Jacques Desrosiers ja Marius M. Solomon. - Springer, 2005. - T. XVI. — ISBN 0-387-25485-4 .

Linkit

• Euroopan leikkaus- ja pakkaustyöryhmä
• Alkeellinen raakavoima-algoritmi materiaalin leikkaamiseen
• Säiliön pakkaus- ja leikkausvaraston ratkaisualgoritmi