Leikkuunoptimointiohjelman kehittäminen paperitehtaan tarpeisiin

Klaus Oehlandt

LEIKKUUNOPTIMOINTIOHJELMAN KEHITTÄMINEN

PAPERITEHTAAN TARPEISIIN

Diplomityö, joka on jätetty opin­

näytteenä tarkastettavaksi diplomi- insinöörin tutkintoa varten

Espoossa 27.9.198A

Työn valvoja apul.prof. Sampo Ruuth Työn ohjaaja DI Antti Kautto

/

TEKNILLINEN KORKEAKOULU TEKNILLISEN FYSIIKAN OSASTO

KIRJASTO

OTAKAARI 3 A 02150 ESPOO 15

.Tekijä ja lyön nimi : Klaus Oehlandt

Leikkuunoptimointiohjelman kehittäminen paperi tehtaan

tarpeisiin 1

Päivämäärä : 27.9 .1984 Sivumäärä : 90

Osasto :

Te k n i 1 1 isen f у s i i kan osasto

Professuuri :

0.02 sovellettu ma t ema ti i kka Työn valvoja :

Apul.prof. Sampo Ruu th Työn ohjaaja :

Dl Antti Kautto

Työn tarkoituksena oli kehittää tietokoneohjelma, joka so­

veltuisi paperitehtaan rullien 1eikkuunoptimointi- eli trrm- mi tysongelman ratkaisemiseen. -Käytännön trimmitysongelman tavoitteet ja rajoitukset kuvataan. Tärkeimmät tekijät ovat yleensä leikkaushäviö, leikkauskaavioiden lukumäärä, tuotan­

tomäärien poikkeamat tilatuista määristä sekä 1 e ikkauskaavi- olle asetetut rajoitukset. Paperitrimmityksen mene te >mi i h

luodusta, kirjall isuuskatsauksesta ei löytynyt menetelmää, jolla suoraan saavutettaisiin em. tekijöiden suhteen käypiä ja hyviä ra tka i su

peritehtai. si in. G nettu algoritmi, maalisia ratkaisu

a ja joka samalla soveltuisi erilaisiin, pa 1 то гe-Gото гy n menetelmä o n tehokkain tun — olla saavutetaan 1 e ikkaushäv iöltään opti — _ a .. Ratkaisujen leikkauskaavioiden lukumää­

rä on kuitenkin pääsääntöisesti sama kuin lähtöaineiston eri ti 1 au s 1 eveyk s.i en lukumäärä, ja menetelmään liittyvä pyöris­

tys aiheuttaa 1 ei. kkaussuunni tel maan poikkeamia tilatuista mää гistä. Paketo i ntiheuri sti ika 1 1 a voidaan leikkauskaavioi­

den lukumäärää vähentää . Pyöri stysheuristi i k a 1 la kyetään helpottamaan määrä toleransseissa pysymistä. Trimmitysohj el ma keh i tetäänkin yhdistämällä Gi1more-Gomoryn menetelmä pake-

° ' n a Pyöristysheuristi ikkaan. G i 1 more-Gomoryn menetel­

mässä apup rob1eemana syntyvää 1 e i kkau skaavion generointi- ongelmaa ei voida kuten yleensä ratkaista tavallisella knap­

sack-algoritm il Ia, kun leikkauskaaviol le on asetettu ] i sä­

ra joi tuks ia. Tämä kokonais 1ukuonge1 ma ratkaistaan Martello- Tothin algoritmilla KP2, joka modifioidaan sopivaksi ja jon­

ka pieni virhe korjataan. Testi- ja vertailua joissa modifi­

oitu. K P 2 - a 1. gori tmi sekä koko kehitetty trimmi tysohj elmisto havaitaan käyttökelpoiseksi ja kilpailukykyiseksi.

Työni valvoja apul.prof. Sampo Ruuth innosti minua

kirjoittamaan diplomityöni tästä aiheesta, joka kehittyi työn ohjaajan DI Antti Kauton tarjoamista haastavista

työtehtävistä Oy Avanced Forest Automation Ab (AFORA) :ssa.

Arvokkaita virikkeitä työhöni olen saanut etenkin maisteri Seppo Peltoselta. Tekn.lis. Leena Aittoniemen kanssa olen käynyt rakentavia keskusteluja ja saanut häneltä myös mer­

kittävän osan käyttämästäni kirjallisuusaineistosta.

Heille kaikille haluan esittää parhaimmat kiitokseni.

Vanhempiani kiitän kannustuksesta ja myötäelämisen kyvystä.

Erityisesti haluan vielä kiittää Eevaani lämpimästä tuesta ja hyödyllisestä avusta.

Espoossa 27. syyskuuta 1984

Klaus Oehlandt

TIIVISTELMÄ ALKUSANAT

1 JOHDANTO 1

2 PAPERITEHTAAN TRIMMITYSONGELMA 4

2.1 Ongelman yleiskuvaus ja trimmitykseen liittyvien

käsitteiden määrittely 4

2.2 Taloudellinen merkitys 6

2.3 Trimmitys tuotannonsuunnittelun osana 6 2.4 Trimmityksen tavoitteet ja rajoitukset 8 2.5 Ongelman matemaattinen esitysmuoto 12

3 YLEISKATSAUS PAPERITRIMMITYKSEN MENETELMIIN 16

3.1 Käsintrimmitys ja trimmitysohjelmien tarve 16

3.2 Gi 1more-Gomoryn menetelmä 17

3.3 Lineaarinen ohjelmointi ja etukäteen valitut

leikkauskaaviot 21

3.4 Heuristiset ohjelmat 22

4 TRIMMITYSOHJELMAN KEHITTÄMINEN YHDISTÄMÄLLÄ GILMORE-GOMORYN MENETELMÄ PAKETOINTI- JA

PYÖRISTYSHEUR1STIIKKAAN 27

4.1 Lähestymistavan perustelu ja yleiskuvaus 27 4.2 Gilmore-Gomoryn menetelmä minimoitaessa

kokonaishukkaa 28

4.3.3 Toteutetun paketointiheuristiikan kuvaus 36 4.3.4 Esimerkki paketoinnista 39 4.3.5 MuuttomääriItään pienten asetteiden

poistaminen 42

4.4 Tilaustoleransseissa pysyminen 42

4.4.1 Yleistä 42

4.4.2 Poikkeamien minimointi 43

5 MARTELLO-TOTHIN KNAPSACK-ALGORITMIN KP2 MUUNTAMINEN

TRIMMITYSOHJELMAAN SOPIVAKSI 48

5.1 Yleistä 48

5.2 KP2:n yleiskuvaus 50

5.3 KP2:n virhe ja sen korjaus 54

5.4 Trimmitysajon lopussa syntyvän knapsack-ongelman

vaikeudesta 59

5.5 Lisärajoitetun asetteengenerointiongelman

matemaattinen esitysmuoto 61

5.6 Lisärajoitetun asetteengenerointiongelman

ratkaiseminen 63

5.6.1 Yleistä 63

5.6.2 Terärajoitus ja jälkikäsittelyrajoitus 64 5.6.3 Mi n imi trimmileveys- ja terämekaniikka-

rajoitus 64

5.6.4 Tavoitteellinen minimimuuttomäärä 64 5.6.5 Mahdollisista muista lisärajoituksista 65 5.7 Reduktioalgoritmien käyttömahdollisuudesta 66

6.2 Algoritmimuutokset ja -lisäykset 68

7 TOTEUTUS 69

7.1 Mikrotietokoneeseen sopivan ohjelman

kehittämisen perustelu 69

7.2 ATK-toteutuksesta 69

7.3 Ohjelmien TRIM ja ROUND ympäristö 71

7.4 Ohjelmien käyttö 73

8 TESTIAJOT JA TULOSTEN TARKASTELU 76

8.1 Yleistä 76

8.2 Trimmitysohjelmiston testiajot ja niiden

tarkastelu 76

8.3 Modifioidun KP2-algoritmin testitulosten

analysointi 82

9 YHTEENVETO 85

10 KIRJALLISUUSVIITTEET 87

LIITTEET

1 JOHDANTO

Suurtuotannosta saavutettavan hyödyn takia kannattaa val­

mistaa tuotteita suurissa erissä, ja aivan vastaavasti on edullista tuottaa materiaaleja isoina standardikokoina ku­

ten esimerkiksi paperia, kartonkia tai kankaita leveinä rullina ja lasia tai aaltopahvia suurina levyinä. Standar­

dikokoja on myöhemmin leikattava mahdollisimman taloudelli­

sesti asiakkaiden tarpeiden mukaisiksi paloiksi: leikkuu- eli trimmitysongelma (engl. cutting-stock problem, trim problem; saks. Verschnittproblem) on syntynyt.

Trimmitysongelmat voidaan karkeasti jakaa yksi-, kaksi- ja kolmiulotteisiin /19/: Paperirullien, teräskelojen ja -palkkien leikkaus, television mainonta-ajan hyväksikäyttö sekä työkuormitusongelma ovat esimerkkejä yksiulotteisista probleemoista. Kaksiulotteisia ongelmia syntyy metal 1ilevy­

jä, lasia, lastulevyjä tai mattoja leikattaessa. Laatikoi­

den tai konttien pakkaaminen on kolmiulotteinen ongelma.

Tässä diplomityössä keskitytään yksiulotteiseen paperiteh­

taan rullien leikkuuongelmaan.

Leikkuuongelmia on perinteisesti ratkaistu käsin ammatti­

taidon ja kokemuksen avulla. Myöhemmin ovat algoritmeihin tai heuristiikkoihin perustuvat tietokoneohjelmat yleisty­

neet. Algoritmien kehittäjinä ovat uraauurtavaa työtä teh­

neet Gilmore ja Gomory, jotka 1960-luvun alussa julkaisivat neljä kirjoitusta (/5/, /6/, /7/, /8/) menetelmästään, sen edelleen kehittämisestä ja sovellutuksista yksi- ja useam­

piulotteisiin tapauksiin. Heidän algoritminsa onkin yhä te­

hokkain käytettävissä oleva, mutta se soveltuu suoraan vain tapaukseen, jossa ainoana tavoitteena on leikattaessa huk­

kaan menevän materiaalin eli trimmihylyn (myös: trimmihu- kan) minimointi. Käytännössä esiintyy usein ristikkäisenä

tavoitteena leikkuun vaivaton sujuminen. Tällöin on usein jouduttu turvautumaan heuristiikkoihin, joista tunnetuimpia on Haesslerin vuonna 1971 julkaisema ja myöhemmin

edelleenkehittämä menetelmä (/10/). Hinxmanin /11/ mukaan tämänkin hetkinen tilanne on se, että jokaisen trimmityson- gelman kanssa tekemisiin joutuvan on (ellei Gilmore-Gomoryn menetelmä ole käypä) kehitettävä oma menetelmänsä, jonka on lähes pakko olla heuristinen. Trimmitysongelmia ei siis voida katsoa vielä lopullisesti ratkaistuiksi. Gilmoren ja Gomoryn jälkeen on trimmitysongelmia käsitteleviä julkaisu­

ja ilmestynyt yli 50 kappaletta /19/, kun sivuavien alojen kuten esimerkiksi knapsack-funktioiden teorian julkaisuja ei lasketa mukaan. Julkaisujen määrä on Madsenin /19/ mukaan viime vuosina kasvanut eksponentiaalisesti kaksinkertais- tumisajan ollessa noin viisi vuotta. Lisäksi on useita malleja, menetelmiä ja ohjelmia kehitetty kaupallisesti, mutta ne ovat yleensä pysyneet liikesalaisuuksina /10/.

Diplomityön tavoitteena oli kehittää paperitehtaan rulla- trimmitysongelman ratkaisemiseen soveltuva tietokoneohjelma Oy Advanced Forest Automation AB (AFORA): n tuotteeksi.

AFORA on metsäalan automaatiojärjestelmiä tuottava yritys, josta puolet omistaa Nokia ja puolet Kymi-Stömberg. Sillä on tytäryhtiö Yhdysvalloissa ja Keski-Euroopassa. Trimmitys- ohjelmat kuuluvat paperiosaston järjestelmäjaoksen tuot­

teisiin. AFORA pyrkii nykyään tekemään mikrotietokoneissa toimivia trimmitysohjelmia, joita voidaan myydä asiakkaille koneineen. Ennestään AFORA:11a oli kaksi mikrotietokoneessa toimivaa ohjelmaa: puhtaasti Gilmore-Gomoryn menetelmään perustuva ohjelma sekä hienopaperitehtaan trimmitykseen so­

veltuva, täysin heuristinen ohjelma. Lisäksi on käytössä (Nokia laskentakeskuksen) H-66 tietokoneessa toimiva, Gilmore-Gomoryn menetelmään ja heuristiikkaan perustuva NOPTRIM-ohjelma, jota on myyty useille asiakkaille ositus- käyttöversiona. NOPTRIM-ohjelman siirto pientietokoneeseen (PDP 11) ei konekapasiteetti syistä ollut onnistunut.

NOPTRIM-ohjelma ei myöskään kykene ottamaan huomioon

tiettyjä käytännössä esiintyviä lisärajoituksia. Täten pää­

tettiin kehittää uusi GiImore-Gomoryn menetelmään ja heu­

ristiikkaan perustuva, paperitehtaan käytännön lisärajoi­

tukset huomioonottava, mikrotietokoneeseen sopiva rulla- trimmitysohjelma. Ohjelman tuli erityisesti sopia yhden asiakkaan, ruotsalaisen hienopaperi tehtaan, tarpeisiin.

Paperitehtaan trimmitysongelmaa ja sen liittymistä tehtaan tuotannonsuunnitteluun selvitetään tarkemmin luvussa 2. Lu­

vussa 3 luodaan lyhyt yleiskatsaus paperitrimmityksen mene­

telmiin. Valittu lähestymistapa, GiImore-Gomoryn menetelmän yhdistäminen paketointi- ja pyöristysheuristiikkaan, selos­

tetaan luvussa 4. GiImore-Gomoryn menetelmässä syntyvän osaongelman ratkaisemiseen tarvitaan knapsack-algoritmia, joksi on valittu Martel 1o-Tothin algoritmi KP2 (/21/).

Martello-Tothin algoritmin muuntaminen trimmitysohjelmaan sopivaksi esitetään luvussa 5. Luvuissa 2-5 on selkeyden vuoksi käsitelty trimmitysongelmaa yhden paperirata!eveyden tapauksena; luvussa 6 esitellään tilannetta, jossa

trimmitettävänä on yhden paperi kone leveyden lisäksi useita varastoleveyksiä. Ohjelmiston toteutusta ja käyttöä kuva­

taan lyhyesti luvussa 7. Luvussa 8 analysoidaan testiajoja:

mm. verrataan kehitetyn ohjelman toimintaa Martti Kuutin tekemään NOPTRIM-ohjelmaan ja heuristiseen ohjelmaan. Trim­

mi tysohjelman modifioidun knapsack-algoritmin toiminta tes­

tataan myös erikseen ja sitä verrataan yleiseen kokonaislu- kualgoritmiin perustuvaan ohjelmaan. Yhteenveto on esitetty luvussa 9 ja käytetyt kirjallisuuslähteet luvussa 10.

2 PAPERITEHTAAN TRIMMITYSONGELMA

2.1 Ongelman yleiskuvaus ja trimmitykseen liittyvien käsitteiden määrittely

Paperikone tuettaan paperia leveänä konerullana eli nk.

tampuurina. Tampuurin leveydestä käytetään nimitystä kone- tai rataleveys. Paperikoneen jälkeen ei ole välivarastoin- titilaa kuin muutamalle konerullalle, joten lähes välittö­

mästi valmistumisen jälkeen rulla siirretään pituus leikku­

rille. Pituusieikkuri11 a konerullasta leikataan tiettyä te­

rien asetusta eli asetetta (leikkauskaaviota) käyttäen ka­

peampia asiakasrullia. Jos asetteen asiakasleveyksien summa (=trimmileveys) on alle koneleveyden, jää osa konerullan paperista käyttämättä eli syntyy leikkaushäviötä, nk.

tri mmihylkyä tai -hukkaa. Trimmihylky ei sinänsä mene täy­

sin hukkaan vaan se voidaan käyttää uudestaan massana» Seu- raava kuva, jossa Wpt ovat asiakasrullien leveyksiä,

havainnollistaa edellä selostettuja käsitteitä:

Koneleveys

KUVA 1 Konerull a ja tri nimityksen käsitteitä

Asi ak asrul lilla, jotka leikataan yhdessä on kaikilla sama pituus, ns. muuttopituus. Samaa asetetta käytetään yleensä moneen kertaan peräkkäin, eli sillä leikataan useita

muuttoja. Yhdestä konerullasta saadaan tavallisesti muutama muutto.

Paperikoneella tuotetaan paperia yleensä samanaikaisesti useaan eri tilaukseen. Jokainen tilaus voi myös koostua mo­

nesta eri rullaleveydestä ja -määrästä. Ongelmana on suun­

nitella pituus!eikkurin käyttö s.e. tuotantotekniset rajoi­

tukset otetaan huomioon, asiakkaiden tilaukset täytetään kauppatol eranss ien sallimissa rajoissa ja paperia hukataan mahdollisimman vähän. Tätä leikkaussuunnitelman tekoa kut­

sutaan trimmitykseksi. Trimmityksen lähtöaineiston muodos­

tavat rj^Rääi e1 i yhdessä trimmitettävät tilaukset. Leik- kaussuunnitelmassa määritetään asetteet ja niillä ajettavat muuttomäärät. Leikkaussuunnitelmaan kuuluu myös tilaus- ja leveyskohtainen yhteenveto, jossa on eriteltynä kunkin asi­

akas ru 11 atyyp in tilattu määrä, tuotettava määrä sekä edel­

listen erotuksena määräpoikkeama (ylitys tai alitus).

Jos paperitehdas tuottaa rullien lisäksi myös arkkeja, on rul1atrimmityksen ohella suoritettava myös arkkitrimmitys.

Tällöin on kyse kaksivaiheisesta ongelmasta: pituusleikku- rilla on leikattava sellaisia rullia, joita voidaan tehok­

kaasti jatkokäsitel1ä arkki leikkureilla. Arkkileikkuri pys­

tyy samanaikaisesti leikkaamaan muutamaa (myös eri le­

vyistä) rullaa rinnan arkeiksi, ja leikattavia paperiratoja saa olla myös useampi päällekkäin. Arkkitrimmityksessä arkkileikkureiden tehokas hyväksikäyttö on tärkeä tavoite trimmihylyn minimoinnin rinnalla. Arkkitrimmitys on vielä rullatrimmitystä monimutkaisempi ongelma. Tässä diplomi­

työssä rajoitutaan jatkossa rullatrimmitykseen, jossa sii­

näkin riittää kehittämistä.

2.2 Taloudellinen merkitys

Trimmitysongelman optimaaliseen ratkaisemiseen sisältyy varsin merkittävä rahallinen potentiaali. Trimmihylky ai­

heuttaa tuotannonmenetyksen, jonka arvo normaalitilanteessa on menetetty kate ja vajaakuormitusti1 anteessakin menetetyt muuttuvat kustannukset (raaka-ainekustannuksia

lukuunottamatta). Tilannetta havainnollistaa seuraava esi­

merkkilaskelma (oletettu täyskuormitus):

Trimmihylky on paperitehtaalla tyypillisesti luokkaa 1-3 prosenttia. Valmiin korkealaatuisen painopaperin tonnihinta on noin 2000 markkaa. Koska trimmihylky voidaan käyttää uu­

delleen raaka-aineeksi ja massan hinta on noin 1000

mk/tonni, voidaan hylyksi menevän paperin aiheuttamaksi me­

netykseksi arvioida karkeasti 1000 mk/tonni. Kolmen prosen­

tin trimmihylky vastaisi ison paperitehtaan 350 000 tonnin vuosikapasiteetin tasolla runsaan 10 tonnin hyikymäärää eli 10 miljoonaa markkaa. Trimmihylyn täydellinen eliminoiminen ei käytännössä trimmitysohjelman avullakaan ole mahdollis­

ta, mutta esimerkiksi puolen prosenttiyksikön vähennys hylyn määrässä merkitsisi tässä n. 1,5 miljoonan markan vuotuista 1isäansiota.

2.3 Trimmitys tuotannonsuunnittelun osana

Paperitehtaan tuotannonsuunnittelun tavoitteena on koko tuotantokapasiteetin tehokas hyväksikäyttö.

Suunnittelutehtävä on monimutkaisuutensa takia jouduttu ja­

kamaan osatehtäviin, joista trimmitys on yksi. Ennen kuin trimmitys voidaan suorittaa, on tilauskannasta valittava ti­

laukset, jotka trimmitetään yhdessä. Tilauksien

yhdistämistä suuremmiksi, kerrallaan ajettaviksi kokonai­

suuksiksi eli ryppäiksi kutsutaan rypästelyksi. Samaan ryp- pääseen valittavilla tilauksilla on oltava määrätyissä ra­

joissa sama laatu, neliöpaino, rullapituus (tai rulla- halkaisija) sekä hylsyn ulkoläpimitta. Rypästelyssä on otet­

tava myös tilausten toimitusajat huomioon, jotka eivät saa merkittävästi poiketa toisistaan. Liian aikaisin valmistu­

vat tilaukset kasvattavat varastoja aiheuttaen pääomien si­

toutumista, ja vastaavasti liian myöhään valmistuvat ti­

laukset voivat johta myöhästymiskorvauksiin tai jopa toimi­

tusten peruuntumisiin /23/.

Tuotannonsuunnittelun osatehtäviin kuuluu myös ryppäiden ajojärjestyksen laadinta eli sekvensointi. Sekvensoinnissa pyritään minimoiman laadunvaihto- ja varastointikustannus- ten summa toimitusaikojen sallimissa rajoissa. Laadunvaihto aiheuttaa tuotannossa tyhjäkäyntiä, jonka kustannuksina täyskuormitusti1 anteessa voidaan pitää menetettyä katetta /14/. Tehtävä ratkaistaan käytännössä yleensä

järjestelemällä ryppäät siten, että keskeisten 1aatusuureit- ten (neliöpaino, tuhkapitoisuus, vaaleus) muutokset peräk­

käin valmistettavien ryppäiden välillä jäävät niin pieniksi kuin toimitusaikojen puitteissa on mahdollista.

Jos paperitehtaalla samaa laatua voidaan valmistaa usealla koneella, joudutaan ratkaisemaan myös konesijotteiuongelma eli on päätettävä, millä koneella rypäs tai yksittäinen ti­

laus ajetaan. Tällöin on mm. seuraavat tekijät otettava huomioon /23/: paperin tekniset ominaisuudet, paperikonei­

den kokonaiskuormitustilanne sekä koneiden suhteelliset tuotantotehokkuudet ko. pintapainolla. Jos koneleveydet poikkeavat toisistaan, vaikuttaa sijoittelu myös trimmityk- seen (vrt. luku 6: trimmitys usean rataleveyden

tapauksessa). Rypäs trimmitetään käytännössä kuitenkin vain harvoin usealle koneelle samanaikaisesti, koska tällöin ti­

laus saattaisi hajautua eri paperikoneille, mikä vai­

keuttaisi jälkikäsittelyä.

Kuten konesijoittelun yhteydessä jo kävi ilmi paperitehtaan tuotannonsuunnittelun osatehtävät ovat kytkeytyneet toi­

siinsa, mikä hankaloittaa kokonaisuuden kannalta parhaan ratkaisun löytämistä. Kytkeytyminen näkyy trimmityksen ja rypästelyn välillä selvästi: Jos jonkin ryppään trimmitys tuottaa suuren hylkyprosentin, voidaan joutua muuttamaan rypästä. Trimmityksen kannalta huonosti ryppääseen sopiva tilaus saatetaan jättää pois ja siirtää toiseen ryppääseen.

Sopivia tilauksia voidaan myös etsiä lähiviikkojen

tuotanto-ohjelmista tai tiedustella suoraan Finnpapista (metsäteollisuuden markkinointijärjestö). Joskus on mahdol­

lista käyttää myös nk. sivuratatilauksia, joiden laatu- ja toimitusaikavaatimukset eivät ole tiukkoja.

2.4 Trimmityksen tavoitteet ja rajoitukset

Leikkaussuunnitelma pyritään tekemään tuotantotekniset ra­

joitukset huomioon ottaen siten, että asiakkaiden tilaukset saadaan täytettyä ja paperia hukataan mahdollisimman vähän.

Seuraavassa trimmitykseen liittyviä tavoitteita ja rajoi­

tuksia esitellään tarkemmin.

1) Trimmihylky

Saavutettavissa oleva pienin trimmikylkyprosentti määräytyy pääasiassa tilauskannan ja koneleveyden mutta osaksi myös hylyn ohella huomioon otettavien lisärajoitusten ja

-tavoitteiden vaikutuksesta.

Mikäli trimmitettävässä ryppäässä on vain muutamia tilaus- leveyksiä, on myös pituusleikkaukseen periaatteessa

käytettävissä olevien asetteiden (leikkauskaavioiden) lukumäärä pieni. Tällöin on yleensä helppoa valita edulli­

simmat asetteet, mutta trimmihylky saattaa jäädä suureksi, koska harvoista tilausleveyksistä ei aina ole muodostetta­

vissa paperiradan tehokkaasti käyttävää kombinaatiota.

Jos rypäs sen sijaan sisältää paljon eri tilausleveyksiä, on mahdollista päästä alhaiseen trimmihylkyyn. Mahdollisia leikkauskaavioita on erittäin paljon, jolloin parhaiden kaa vioiden valinta on ongelmallista. Tri mmihylyn pienentämisen ja muiden trimmityksen tavoitteiden välillä syntyy risti­

riitoja tällöin helpommin kuin harvojen tilausleveyksien tapauksessa.

2) Asetteiden lukumäärä

Pituusi eikkuriter ien siirtäminen ja asettaminen vie aikaa.

Pituusleikkurilla on kuitenkin pystyttävä leikkaamaan kone- rullia vähintään samassa tahdissa kuin paperikone tuottaa niitä. Tämän takia käytettävien asetteiden lukumäärä ei saa kasvaa liian suureksi. Paperikoneen ja pituusleikkurin vä­

liseen puskurivarastoon mahtuu vain muutama konerulla. Jos siis pituusleikkurista muodostuu tuotannon pullonkaula, joudutaan valmis paperi ajamaan suoraan massaksi, tai kone on pysäytettävä.

Asetteen vaihtoon kuluva aika riippuu pituusleikkurin te­

rien asetusmekanismin kehittyneisyydestä. Teränsiirto- automatiikalla asetteen vaihto vie keskimäärin noin 2 minuuttia, kun taas terien siirtoon käsin kuluu yleensä noin 10 minuuttia. Vastaavat pelkät muutonvaihtoajat ovat automatisoidusti 1 minuutti ja käsin keskimäärin 5 minuuttia Asetteen vaihto kuluttaa pelkkään muuton vaihtoon verrattu­

na si in noin kaksi kertaa enemmän aikaa. Teränsiirto- automatiikka vähentää asetteiden vaihdon kriittisyyttä.

3) Tilausten määrätoleranssit

Vaikka ostaja tilaa määrätyn rullamäärän paperia, mahdol­

listavat kauppasäännöt yleensä toimituksen pienen poikkea­

misen tilatuista määristä.

Rullatrimmityksessä käytetään vakiomuuttopituuksia. Koska asetteessa voi samaa tilausleveyttä olla useita rullia rin­

nan ja asetteella leikataan aina vain kokonaisia muuttoja, saattaa tuotettava rullamäärä poiketa tilatusta määrästä muutamalla rullalla. Jos tilatut määrät ovat useita kymmeniä tai satoja rullia, määrätoleransseissa pysytään vielä helposti. Jos tilaus sen sijaan käsittää vain muuta­

man rullan, ei ylityksiä tai alituksia sallita. Tällainen tilanne esiintyy usein Keski-Euroopan paperitehtailla, joi­

den tilauskannat sisältävät paljon pieniä tilauksia.

Markkinatilanteen mukaan tilausten rul 1amääriä saatetaan myös tarkoituksellisesti pyrkiä ylittämään tai alittamaan.

4) Minimimuuttomäärät

Jos joillakin asetteilla ajetaan vain harvoja muuttoja, jou­

dutaan pituusleikkurin teriä siirtelemään useaan kertaan lyhyen ajan sisällä, mikä em. pienen puskurivarastoti 1 an takia saattaa aiheuttaa vaikeuksia. Pienet muuttomäärät ja lyhyessä aikavälissä muuttuvat asetteet ovat haitallisia myös rullien jälkikäsittelyn kuten esimerkiksi pakkauksen kannalta. Ideaalitapaus olisi, että kaikki muuttomäärät oiisisvat saman suuruisia. Käytännössä esitetään usein toi­

vomus minimimuuttomäärästä, jota ei minkään asetteen muut- tomäärän tulisi alittaa.

5) Tilauksen valmistuksen hajautuminen

Trimmitettäessä yhdessä useita tilauksia ja ti laus leveyksiä saattaa pieneen tr immihyi kyyn pyrkiminen johtaa siihen, että saman tilauksen rullia valmistetaan ajallisesti kauka­

na toisistaan. Tämä voi aiheuttaa vaikeuksia pakkaamisessa, varastoinnissa ja toimitusaikojen täyttämisessä, ja se on tällöin otettava huomioon yhdessä trimmitettäviä tilauksia ja asetteiden ajojärjestystä valittaessa.

6) Terärajoitus (ratapaikkojen lkm)

Pituusleikkurissa on käytettävissä vain rajallinen määrä teriä. Asetteella voidaan samanaikaisesti leikata korkein­

taan terien lkm + 1 rullaa (kun mahdollisia reunateriä ei lasketa mukaan).

7) Jä1 kikäsitte1yrajoitus (eri leveyksien lkm)

Automaattinen pakkaus!inja saattaa aiheuttaa sen, että sa­

massa asetteessa saa olla korkeintaan tietty määrä eri leveyksiä (tilauksia).

8) Minimitrimmileveys

Jos pituusleikkurilla syntyvää reunahylkyrul1 aa eli nk. nu­

ti kk aa ei pystytä jälkikäsittelemään, on se jo leikattaessa imaistava pulpperiin, jotta hylky voidaan käyttää uudes­

taan massana. Imuri ei kykene imemään kuin korkeintaan tie­

tyn levyistä reunanauhaa. Tämä asettaa alarajan trimmin (=koneleveys-leikkaushäviö) leveydelle.

9) Terämekaniikkarajoitus

Pituusleikkurin mekaniikka saattaa rajoittaa asetteen muo­

toa, esimerkiksi siten, että jokaisessa asetteessa on olta­

va toisessa reunassa vähintään tietyn levyinen rulla, jotta asetteella kyetään leikkaamaan.

Viitteessä /23/ kuvataan myös seuraavanlainen terämekanii­

kan aiheuttama rajoitus: Leikkausteriä pyörittävien mootto­

reiden koko ratkaisee, mitä kapeampaa leveyttä ei saa esiintyä asetteessa tiettyä määrää enempää, sillä mootto­

reista osa joudutaan asettamaan perät vastakkain.

Tässä työssä käsitellään trimmitysohjelmaa kehitettäessä kaikkia edellä lueteltuja tekijöitä tilauksen valmistuksen hajautumista (tekijä 5) lukuunottamatta. Tilauksen valmis­

tuksen hajautumisen hallitsemista ovat tutkineet esimerkiksi Madsen /19/ ja Suomessa Raimo Voutilainen /27/.

2.5 Ongelman matemaattinen esitysmuoto

Edellä kuvattu trimmitysongelma voidaan matemaattisesti esittää seuraavana rajoitettuna, diskreettinä

minimointiongelmana:

- MINIMOITAVANA KOHDEFUNKTIONA kokonaistrirmiihylky:

n m

min ^ (L aijWj) Xj (2.1)

xj»aij J=1 i=1

- RAJOITUSEHTOINA:

- suurin sallittu asetteiden lukumäärä

n

- tilausmäärät toieransseineen (eli ala- ja ylämäärät)

n

1 i 4

У

- asetteen leveys ei saa ylittää koneleveyttä

m

a-jj Wj 4 L j = (2.4)

i=l

- minimimuuttomäärä

Xj > Sj q j = (2.5)

- terärajoitus (ratapaikkojen lkm)

m

aij < N j =l,...,n (2.6) i=l

- jälkikäsittelyrajoitus (maksimilkm eri leveyksiä asetteessa)

m

sij 4 M j = l,...,n (2.7)

i=l

- min imitrimmileveys

m

ai j wi ^ Lm-¡ n j = 1»...» n (2.8) i=1

- terämekaniikkarajoitus (vähintään 1 leveys yli tietyn leveyden)

m

Tl

^{^1}

⁼¹

(2.9)

missa

Xj

>,

a ij > 0 ja kokonaisluku

1 jos Xj > 0

k0 muuten

... flj

’ij ~

jos aij > 0

0 muuten

Л

1 jos Wi

У/

J) muuten

m n xj aij Wi L S li Ui q N

M Lmin

tilausleveyksien lkm

mahdollisten asetteiden lkm

asetteella j ajettavien muuttojen lkm lkm leveyttä i asetteessa j (leveyden i kerta!uku asetteessa j)

asiakasrullaieveys i koneleveys (rataleveys) sallittu asetteiden lkm

leveyttä i tehtävien rullien lkm:n alaraja leveyttä i tehtävien rullien 1 km:n yläraja minimimuuttomäärä

ratapaikkojen lkm (= leikkausterien lkm + 1, jos ei reu nateri ä)

suurin sallittu lkm eri leveyksiä asetteessa minimitrimmileveys

Edellä selitettyjä merkintöjä käytetään tässä työssä myös jatkossa.

Tuntemattomia ovat asetteet (eli siis a^j:t) ja niillä ajettavat muuttomäärät Xj. Ongelman ratkaisua hankaloitta­

vat muuttujien kokonais!ukuvaatimukset, epälineaariset ra- joitusehdot sekä mahdollisten eri asetteiden suuri lkm

(n on iso). Mikäli leikattavia eri leveyksiä on m kpl ja yhteen asetteeseen mahtuu rinnakkain keskimäärin k rullaa, saadaan erilaisten mahdollisten asetteiden lukumäärä n 1ikimäärin kaa­

vasta /25/:

n ~ /m+k-l\ (m+k-1) ! (järjestämätön otos V k / k! (m-1)! takaisinpanolla)

Hienopaperitehtaassa m saattaa olla esim. 20 ja k tyypilli­

sesti 15, jolloin n:n arvioksi saadaan 1,8 x 109.

Lisärajoitukset kuten jälkikäsittely-, minimitrimmileveys- tai terämekaniikkarajoitus luonnollisesti pienentävät mah­

dollisten asetteiden määrää.

3 YLEISKATSAUS PAPERITRIMMITYKSEN MENETELMIIN

3.1 Käs intrimmi tys ja trimmitysohjelmien tarve

Perinteisesti trimmitysongelma on ratkaistu käsin.

Ammattitaitoiset ja kokeneet trimmittäjät pystyvätkin yleensä tekemään varsin hyviä leikkaussuunnitelmia, varsin­

kin jos ryppäät ovat yksinkertaisia (vain harvoja eri leveyksiä) tai säilyvät suurin piirtein vakioina eikä eri- koisrajoituksia ole paljon. Trimmittäjät kykenevät impli­

siittisesti ottamaan epälineaariset rajoitukset sekä keske­

nään ristiriitaiset tavoitteet (esim. pieni trimmihyi ky ja asetteiden määrä) huomioon ja löytämään täten tehtaan ti­

lanteeseen hyvin sopivan, tasapainoisen ratkaisun.

Käsin trimmitettäessä noudatetaan yleensä seuraavanlaista menettelytapaa:

- kootaan "hyvältä tuntuva" asete

- asetteen muuttomäärä valitaan s.e. vähintään yhden leveyden tilausmäärä saadaan täysin täytetyksi

- vähennetään asetteella valmistuvat määrät ryppään tilausmääristä

- kootaan uusi "hyvältä tuntuva" asete - jne. kunnes kaikki ryppään tilaukset on

trimmitetty

Ongelmia saattaa syntyä, kun on laaja, paljon pieniä ti­

lauksia sisältävä, vaihteleva tilauskanta tai kun trimmitys on suoritettava nopeasti (esim. alunperin tehtyä leikkaus- suunnitelmaa ei tuotantohäiriöiden takia voidakaan

noudattaa). Useat tuotantotekniset rajoitukset saattavat myös siinä määrin monimutkaistaa leikkaussuunnitelman teko- a, että trimmihylky jää toissijaiseksi. Tällöin trimmitys- ohjelmia tarvitaan parempien ratkaisujen löytämiseksi.

Haesslerin /10/ mukaan tarvetta on lisäksi seuraavien teki­

jöiden takia:

- trimmityksen virhemahdollisuuksien minimointi - tilauksen saapumisen ja tuotantomääräyksen

antamisen välillä olevan aikaviiveen pienentä­

minen

- viimehetken muutosten käsittelymahdollisuuk­

sien paraneminen

3.2 Gilmore-Gomoryn menetelmä

Gilmore ja Gomory ovat julkaisseet menetelmänsä perusversion vuonna 1961 (/5/). Menetelmässä käytetään hyväksi lineaa­

rista ohjelmointia eli tarkemmin revised-simplexiä.

Gilmore-Gomoryn menetelmän (jatkossa käytetään lyhennettä GGM) suurin etu on se, ettei kaikkia mahdollisia asetteita tarvitse muodostaa etukäteen vaan niitä generoidaan

knapsack-algoritmin avulla tarvittaessa. GGM:n perusversio soveltuu seuraavan pelkistetyn trimmitysongelman

ratkaisemiseen. Merkinnät ovat samat kuin edellä (kohta 2.5). Lisäksi: d-¡ = leveyttä i tilattu määrä.

n min

Xj j = l

n

i = 1

,... ,m

m

j = 1 ,..., n i = l

j = 1 Xj > 0

Minimoitavana kohdefunktiona on siis kokonaismuuttomäärä.

Muuttojen Xj kokonais!ukuvaatimuksesia on luovuttu, joten saatava ratkaisu on vielä pyöristettävä.

Revised-simplexin 1ähtökannaksi voidaan valita m asetetta s.e. asetteessa j on vain yksi leveys wj eli a-¡j=l kun i=j ja 0 muuten. Tällöin x-,*=di kun i=l,...,m.

Tämän jälkeen vuorottelevat revised-simplex- ja knapsack- kierrokset niin, että aina kun revised-simplexi1 la on haet­

tu optimiratkaisu mukana olevalle asetejoukolle, knapsack- algoritmi1 la etsitään asete, jolla ratkaisua voitaisiin yhä parantaa. Optimiin on päästy, kun knapsack-algoritmi ei löydä enää parantavaa asetetta.

Lineaarisen ohjelmoinnin teorian perusteella sarake (eli tässä asete) on mi nimoi ntitapauksessa edullinen, jos sen nk. redusoitu kustannus (zj-cj) on positiivinen eli:

m

Zj-Cj =

УУВ-1)!

1=1

missä CT on kantaa vastaavien hintojen c-j muodostama vektori ja B_1 on kannan käänteismatriisi.

Merkitään pj = (cTß-l)i.

Kerroin pi tunnetaan myös rajoitusehtoon (eli tässä tilaukseen) i liittyvänä nk. varjohintana tai

simplex-kertoimena.

Kun etsitään kohdefunktion arvoa (ainakin lyhyellä

tähtäimellä) eniten parantavaa asetetta k, joudutaan apu- probleemana ratkaisemaan seuraava knapsack-ongelma, jossa wi on tilaus leveys i ja L on rataleveys:

max aik

aik

m (3.2)

Xj aik * L i=l

aik ^ O ja kokonaisluku i = 1,...,m

Kun ongelmasta ratkaistuille a-¡|<: lie pätee, että

Zj - Cj 4 0 , ei kohdefunktion arvoa voida enää paran­

taa, ja (pelkistetty) trimmitysongelma on ratkaistu.

Vuoden 1963 artikkelissaan /6/ Gilmore ja Gomory julkaisi­

vat varsin tehokkaan ja trimmitysohjelmissa usein käytetyn, leksikograafisen knaps ack-al goritmin, jolla myös terärajoi­

tus kyetään ottamaan huomioon. Artikkelissa esitetään myös kaksi parannusehdostusta GGM:n nopeuttamiseksi. Jos ennen knapsack-kierrosta havaitaan, että ti laus leveyksin e w-¡ ja

Wj pätee w-j < wj ja p-j > pj, voidaan leveys wj jättää suo­

raan pois. Knapsack-ongelmien koko pienenee tällöin varsin­

kin tapauksissa, joissa hukka on suuri. Tällainen knapsack- ongelman pienentäneen ei kuitenkaan enää onnistu, kun tie­

tyt lisärajoitukset kuten esim. minimitrimmileveys joudu­

taan ottamaan huomioon. Toisessa parannusehdotuksessa ra­

joitutaan joka toisella knapsack-kierroksen a etsimään edullista asetetta vain niiden tilaus!eveyksien joukosta, joiden tilausmäärät ylittävät kaikkien tilausmäärien mediaanin. Ideana on, että kun asetteessa on mukana vain suurimääräisiä ti laus leveyksiä, niin asetetta ainakin peri­

aatteessa voitaisiin käyttää paljon. Tällöin kohdefunktion arvo saattaa parantua absoluuttisesti enemmän kuin aset-

teel la, jossa olevien simplex-kertoimien summa ehkä on suu­

rempi mutta mukana on vähän tilattuja leveyksiä. Simplex- kertoimet eli varjohinnathan kuvaavat vain kohdefunktion suhteellista muutosnopeutta.

Artikkelissaan /6/ Gilmore ja Gomory esittävät lisäksi ta­

van, jolla tilausmäärien toleransseja voidaan heidän mene­

telmässään jo optimointivaiheessa käyttää. Kokonaismuutto- määrän sijasta minimoidaan suhteellista hukkaa eli ratio­

naalisena kohdefunktiona z on:

n m n

Diplomityön luvussa 4.2 näytetään kuitenkin, miten määrä- toleransseja voidaan hyödyntää joutumatta minimoimaan rationaalifunktiota.

Knapsack-funktioiden teoriaa ja laskentaa käsittelevässä vuonna 1966 julkaistussa artikkelissa /8/ Gilmore ja Gomory selvittävät knapsack-funktioiden jaksollisuusominaisuuksia ja hiovat knapsack-algoritmejaan aikaa ja muistitilaa säästäviksi. Mielenkiintoista tämän diplomityön kannalta on, että he mainitsevat käytännön lisärajoituksina terära- joituksen lisäksi myös "eri leveyksiä asetteessa"

-rajoituksen sekä mahdolliset ylärajat kunkin leveyden mää­

rälle asetteessa. He määrittelevät myös dynaamisen ohjel­

moinnin funktionaalisen yhtälön 1isärajoitetun knapsack- ongelman ratkaisemista varten.

Yhteenvetona GGM:stä voidaan todeta, että /11/ se on tehok­

kain käytettävissä oleva algoritminen menetelmä olettaen, että knapsack-apuprobleeman ratkaisemiseen käytetään paras­

ta saatavissa olevaa menetelmää. GGM soveltuu suoraan kui­

tenkin vain tapauksiin, joissa mahdollisimman pieni trimmi- hukka on ainoa tavoite. Jos asetteiden määrä on pidettävä

pienenä, joudutaan GGM:n yhteydessä käyttämään

heuristiikkaa. GGM tuottaa nimittäin yhtä monta asetetta kuin mitä ongelmassa on eri tilausleveyksiä, jos simplex- ratkaisu ei ole degeneroitunut. Myös eräiden käytännön lisä- rajoitusten huomioon ottaminen saattaa knapsack-algoritmissa olla hankalaa.

3.3 Lineaarinen ohjelmointi ja etukäteen valitut leikkauskaaviot

Tilanteissa, joissa yhdessä trimmitettäviä eri

tilausleveyksiä on vähän ja asetteiden muotoa rajoittavat useat tekijät, on mahdollista soveltaa lineaarista ohjel­

mointia suoraan siten, että LP-matriisiin on etukäteen va­

littu ^hyväV leikkeuskaaviot. Tällaista lähestymistapaa on sovellettu esim. aaltopahvitehtaita varten kehitetyissä trimmitysohjelmissa, jollaisia Stovicek vuoden 1977 kirjoi- tuksesaan (/26/) kuvaa. Stovicek käsittelee myös asetteiden lukumäärään liittyvää ongelmaa, joka on lineaarista ohjel­

mointia käytettäessä sama generointiinpa asetteet etukä­

teen tai vasta tarvittaessa kuten GGM:ssä.

Lähestymistavan ongelmana on usein kuitenkin hyvien aset­

teiden määrittäminen. Kriteereinä käytetään trimmileveyttä ja muuttomäärää, joka asetteella on mahdollista ajaa. Asete hyväksytään siis vain, jos sen trimmileveys ylittää tietyn minimileveyden ja sillä on mahdollista ajaa vähintään tiet­

ty minimimäärä muuttoja. Leikkauskaavion on tietysti myös täytettävä mahdolliset käytännön lisärajoitukset kuten esim. rajoitus kaaviossa sallituille eri tilausleveyksille.

Sellaisten asetteiden hylkääminen, joiden hukkaleveys on suuri, saattaa estää joskus hyvän tai ainakin parhaan rat­

kaisun löytämisen. Jonkin epäedullisen asetteen mukaanotto saattaa kannattaa, koska se voi toisaalta mahdollistaa use­

an hyvän asetteen käytön. Tilanne on luonnollisesti toinen, jos minimitrimmileveysvaatimus on teknisten syiden takia ehdoton.

Stovicekin /26/ käsittelemässä aaltopahvi tehtaassa löydet­

tiin yleensä 20-30 hyvää asetetta, kun til aus leveyksiä oli 10 kappaletta, mutta 70:n tilausleveyden tapauksissa aset­

teiden lukumäärä oli noin 900, jolloin siis ratkaistavan LP-matriisin koko oli jo 70 x 900.

3.4 Heuristiset ohjelmat

Lineaarisen ohjelmoinnin avulla ei pystytä aina tuottamaan käytäntöön soveltuvia ratkaisuja leikkuunoptimointiongel- miin liittyvien epälineaaristen tekijöiden takia. Koska epälineaarisen trimmitysongelman optimaalisesti ratkaisevia ja riittävän tehokkaita algoritmeja ei tunneta, on jouduttu kehittämään myös täysin heuristisia ohjelmia. Seuraavassa käsitellään yleisimmin käytettyä nk. sekventiaalista lähes­

tymistapaa. Sekventiaalisessa lähestymistavassa ratkaisuun otetaan asete kerrallaan mukaan muuttamatta ratkaisussa jo olevien, aikaisemmin generoitujen asetteiden ajomääriä.

Tilausmääristä poistetaan aina uudella asetteella valmistu­

vat tilausmäärät, joten ongelman koko pienenee askeleit­

tain. Tässä onkin suurin periaatteellinen ero lineaarisen ohjelmoinnin käyttöön verrattuna: siinähän ratkaisun asete- joukkoa käsitellään samanaikaisesti kokonaisuutena eli kaikkien asetteiden ajomäärät muuttuvat, kun uusi asete tu­

lee ratkaisuun mukaan.

Haessler on tehnyt uraauurtavaa työtä heurististen ohjel­

mien kehittäjänä. Hän käsittelee julkaisussaan /10/ trimmi- tysongelmaa, jossa on minimoitava trimmihylyn ja asetteiden vaihdon aiheuttamien kustannusten summa, ja esittää sek- ventaalisen ratkaisumenetelmän. Menetelmässä lasketaan ryp­

pään vielä trimmiitämättä olevalle osalle kaksi tunnus- 1ukua:

- arvio vielä tarvittavasta kokonaismuuttomäärästä

m

A = d'i w-j /L i=l

(L = rataleveys, Wj = tilausleveys i)

- yhdestä muutosta keskimäärin saatava asiakasrul1 ien määrä

В

Merkinnällä dj tarkoitetaan til aus leveyttä i vielä

trimmittämättä olevaa määrää. Alussa ennen kuin ensimmäinen asete on generoitu, dj on siis yhtä kuin leveyden i

tilausmäärä.

Näitä tunnuslukuja käytetään hyväksi, kun seuraavaksi va­

littavalle asetteelle määritetään tavoitetaso eli tietyt rajoitusehdot, jotka valittavan asetteen on täytettävä:

- m in imitrimmileveys

z

1=1

aij wi ^ Lmin

- asetteessa rinnan mukana olevien rullien minimi- ja maksimilukumäärä

m

MINR < < MAXR i = l

jossa MAXR määräytyy yleensä leikkausterien määrän perus­

teella ja MINR asetetaan tyypillisesti B-l:ksi.

- minimimuu 11 omää r ä

d'i / а-jj > MINU kaikille aij > 0

jossa MINU = 0,5...0,9 x A. Osuutta kasvatetaan, kun A eli vielä tarvittava kokon aismuuttomäärä pienenee.

Edellä kuvatut rajoitusehdot täyttävän asetteen hakemista varten til aus leveydet järjestetään d'-j-arvojen mukaan laske­

vaan järjestykseen. Haku suoritetaan generoimalla asetteita leksikograafisessa järjestyksessä kunnes sopiva asete, jos­

sa d-j-arvoltaan suurin tilausleveys on mukana löytyy. Jos ei yhtään käypää asetetta löydy, pienennetään minimimuuttomää- rän MINU arvoa ja yritetään uudestaan. Jos haku epäonnistuu kaikilla MINU:n yli ykkösen olevilla arvoilla, asetetaan MINU ykköseksi ja valitaan mukaan trimmihukaltaan pienin asete.

Valitulla uudella asetteella ajetaan niin monta muuttoa kuin mahdollista, siten että mitään tilattua määrä ei kui­

tenkaan ylitetä. Tämän jälkeen määritetään ryppään vielä trimmittämättä jäänyt osa, lasketaan sille uudet tunnuslu­

vut jne.

Asetteenvaibiokustannusten ja trimmihylyn hinnan keski­

näistä suhdetta ei menetelmässä tarvinnut eksplisiittisesti määritellä, vaan saatava ratkaisu määräytyy minimitrimmi-

1eveys-parametrin arvon perusteella. Tällä parametrilla on kokeiltava eri arvoja, jos halutaan asete- ja hylkymääril- tään tietynlaisia ratkaisuja.

Haesslerin suoraviivainen menetelmä sopii parhaiten tilan­

teisiin, joissa on paljon eri tilausleveyksiä ja tilausle- veydet ovat kapeita verrattuna koneleveyteen (leveyksien yhdistelymahdollisuudet suuret). Tällöin saadaan yleensä hylkyprosenteiltaan hyviä ratkaisuja, joiden asetemäärät ovat selvästi pienemmät kuin GGM: 11 ä saavutettujen

ratkaisujen. Tilausmäärät saadaan myös tarkasti täytettyä, sillä menetelmässä ei tarvita pyöristyksiä. Kun tilausleve- yksien ja koneleveyden suhde muuttuu epäedullisemmaksi,

huononevat Haesslerin menetelmällä saadut ratkaisut sekä hyikyprosentiltaan että asetemääriItään huomattavasti.

Johnston /15/ kuvaa kirjoituksessaan puumaista ratkaisupol- kua etenevää menetelmää, jossa hyödynnetään Haesslerin kehittämää heuristiikkaa. Johnstonin menetelmässä ei

välttämättä tyydytä ensimmäiseen löydettyyn kokonaisratkai­

suun, vaan etsitään vielä parempia ratkaisuja

11 takai s insei aus "-askel eita (edellisen asetteen poisto) käyttäen. "Так ai s insei aus"-askel ta käytetään myös esimer­

kiksi jouduttaessa tilanteeseen, jossa huomataan muodostu­

van ratkaisun jäävän väistämättä huonommaksi kuin siihen mennessä löydetty paras ratkaisu tai asetteiden määrän kas­

vavan liian suureksi. Johnston on kehittänyt erilaisia rat- kaisukandidaateille laskettavia ala- ja ylärajoja, joilla jo aikaisessa vaiheessa voidaan havaita mahdollisen

"takai s insei aus"-askeleen tarve.

Hinxmanin /11/ mukaan heuristiset ohjelmat eivät ole yleis­

käyttöisiä, sillä niissä joudutaan käyttämään ongelmien erityispiirteitä hyväksi. Heuristisella ohjelmalla saate­

taan joskus jäädä kauas optimista sovellettaessa sitä pe­

riaatteessa "oikeankin" tyyppiseen ongelmaan. Heuristiset menetelmät tuottavat yleensä loppuvaiheessa asetteita, joil­

la ajettavat muuttomäärät jäävät pieniksi ja trimmileveydet huonoiksi.

4 TRIMMITYSOHJELMAN KEHITTÄMINEN YHDISTÄMÄLLÄ GILMORE-GOMORYN MENETELMÄ PAKETOINTI- JA PYÖRISTYSHEURISTIIKKAAN

4.1 Lähestymistavan perustelu ja yleiskuvaus

Tavoitteena oli kehittää mikrotietokoneessa tehokkaasti toimiva, yleiskäyttöinen rullatrimmitysohjelma, jolla myös kyettäisiin ottamaan huomioon käytännön lisärajoitukset (erityisesti yhden ruotsalaisen hienopaperitehtaan).

Heuristinen, sekventiaaliseen menetelmään perustuva ohjelma soveltuu periaatteessa hyvin hienopaperi tri nimitykseen, sillä hienopaperi tehtaiden ryppäät koostuvat yleensä monista pienistä tilauksista ja koneleveyteen nähden ka­

peista ti 1ausleveyksistä. Asetteiden määrä saataisiin pidettyä pienenä, joskin osittain trimmihylyn

kustannuksella. Tarkasteltavan hienopaperitehtaan pituus- leikkurilla on teränsiirtoautomatiikka, joten asetteiden määrä ei ole kriittinen, vaan päätavoitteena on pieni trimmihyi ky. Asetteen muotoon liittyvät rajoitukset ovat tehtaalla ehdottomia, esimerkiksi minimitrirrmileveys- vaatimus on täytettävä, mikä aiheuttaisi vaikeuksia lop­

puvaiheessa huonoja asetteita tuottavalle sekventiaalisel- le menetelmälle. Heuristinen ohjelma ei myöskään olisi yleiskäyttöinen.

GGM:n toiminta ei ole riippuvainen "sopivasta" trimmiryp­

päästä, vaan menetelmä takaa minimaalisen trimmihukan, mut­

ta takuita käytäntöön soveltuvista leikkaussuunnitelmista ei ole. Asetteiden määrää pitäisi yleiskäyttöisyyttä aja­

tellen voida vähentää. Leikkaussuunnitelman tuotantomäärien poikkeamat tilatuista määristä saattavat aiheuttaa vaikeuk­

sia, jos ryppäässä on pieniä tilauksia. Poikkeamat liitty­

vät GGM:n yhteydessä suoritettavaan pyöristykseen. Asettei­

den määriin ja poikkeamiin voidaan vaikuttaa liittämällä GGM:ään paketointi- ja pyöristysheuristiikkaa.

Paketointi- ja pyöristysheuristiikan käytöstä GGMrään perus­

tuvissa trimmitysohjelmissa on hyviä kokemuksia. Martti Kuutilla on NOPTRIM-ohjelmassaan pitkälle kehitetty pake- tointiheurist iikka, joskin se ainakin mikrotietokoneversi- oon on turhan raskas. Seppo Peltosella on arkkitrinmitysoh- jelmassaan sekä paketointi- että pyöristysheuristiikkaa, ja hänen ohjelmallaan on Kymi-Strömberg Oy:n Kuusankosken teh­

tailla saavutettu hyviä tuloksia. Edelleenkehitettäviä ide­

oita oli siis olemassa.

Jotta mikrotietokoneeseen kehitettävä trimmitysohjelma oli­

si mahdollisimman tehokas, päätettiin GGMrään liittyvänä knapsack-algoritmina käyttää Martel lon ja Tothin knapsack- algor i tmi a KP2 (/21/), joka on nopeimpia tunnettuja algo­

ritmeja rajoitetulle knapsack-problemmal le. Algoritmia on modifioitava asetteiden muotoon liittyvien rajoitusten ta­

kia. Knapsack-algoritmin muuttamista ja sovittamista trim- mitysohjelmaan käsitellään luvussa 5.

4.2 Gilmore-Gomoryn menetelmä minimoitaessa kokonaishukkaa

GGM esitetään (kuten kohdassa 3.2) yleensä s.e. minimoita­

vana kohdefunktiona on kokonaismuuttomäärä eli kulutettava kokonaispaperimäärä. Tämä kohdefunktion valinta ei kuiten­

kaan ole sopiva, kun tilauksille jo LP-vaiheessa sallitaan toleranssit, sillä se painaisi kaikki tuotantomäärät

alarajoilleen. Gilmore ja Gomory esittävätkin toisena koh­

def unktiomahdol 1 isuutena suhteellisen hukan minimoinnin (vrt. kohta 3.2) ja selvittävät, kuinka tämän rationaali- funktion minimi löydetään.

Rationaal ifunktioita ei kuitenkaan tarvitse ottaa kohde- funktioksi, jos toleranssit ovat pienet. Tällöin nimittäin kokonaismuuttomäärä on eri kohdefunktioita käyttäen saavu­

tetuissa optimiratkaisuissa lähes vakio, ja KOKONAISHUKAN minimointi johtaa siis myös suhteellisen hukan minimiin.

Kokonaishukka on muutamissa julkaisuissa (esim. /9/) välit-

tu kohdefunktioksi, mutta tästä aiheutuvaa muutosta

knapsack-ongelman kohdefunktion päätösmuuttujien kertoimiin ei ole otettu huomioon!

Seuraavassa esitetään ongelman formulointi GGMrää varten, kun minimoidaan kokonaishukkaa sallien tilauksille

toleranssit. Tilausmäärään i liittyvää slack-muuttujaa on merkitty xsi, muut merkinnät ovat samat kuin edellä.

nm n

m1n Z (L " Wi) XJ = Z CJ XJ

J=1 i=l j=l

n

Zj ай XJ + xsi ^ ui i = 1...m j=l

xsi < Ui - Ij i = 1,...,m (4.1)

m

Wi < L j = l,...,n

i=l

xj > 0 j = 1... n

xsi ^ 0 i = 1,...,m

Kohdefunktion arvoa parantavaa asetetta etsittäessä maksi­

moitava redusoitu kustannus on:

(CT в-l), ,y

m

i=l

Muuttujaan xj eli uuteen asetteeseen j liittyvä kohdefunk- tion kerroin cj on tässä trimmihukkareuna eli saadaan:

- c-

m m

У

У

i=l i=l

m

У

Koska L on yhden koneleveyden tapauksessa vakio kaikille asetteille, se voidaan lupaavinta asetetta etsittäessä jättää pois. Muodostuvan knapsack-ongelman kohdefunktion kertoimet ovat siis simplex-kertoimien pj ja leveyksien Wj summia (vrt. myös probleema 3.2):

m

max (Pi + wi) aij aij

(4.2)

aij > 0 ja kokonaisluku i = 1,... ,m

j on kiinnitetty

Lopetusehdoksi saadaan eli kohdefunktion arvoa parantavaa asetetta ei enää löydy, jos knapsack-ongelman optimaalisen ratkaisun avilie pätee:

m

(Pi + wi) aij 4 L i=l

4.3 Asetteiden vähentäminen

4.3.1 Yleistä

Edellä on jo selvitetty asetteiden lukumäärän merkitys.

GGM:n tuottaman ratkaisun asetteiden määrä on pääsääntöi­

sesti sama kuin trimmityksessä mukana olevien eri tilausle- veyksien määrä. Mikäli simplex-ratkaisu sattumalta on dege­

neroitunut eli jonkun tai joidenkin kannassa olevien muut­

tujien arvo on nolla, voi asetteita olla yksi tai muutama vähemmän. Kuitenkin asetteita saattaa olla liikaa toteutta­

miskelpoiseen leikkaussunnitelmaan, varsinkin jos tehtaalla ei ole teränsiirtoautomatiikkaa.

4.3.2 Ratkaisuvaihtoehtojen kuvaus ja arviointi

Asetteiden vähentämiseen GGM:n yhteydessä on yleensä käy­

tetty seuraavia keinoja:

1) Leveyksien yhdistely

Johnston esittelee julkaisussaan /15/ seuraavanlaisen

menettelytavan: Haetaan ensin ratkaisu GGM: 11ä. Sen jälkeen yhdistellään kapeita leveyksiä leveämpi en kanssa s.e.

leveämpiä leveyksiä valitaan kapeampien "peiteleveyksiksi"

samalla kuitenkin pitäen GGM:n ratkaisun asetteet käypinä (koneleveyttä ei saa ylittää). Näin saatu redusoitu ongelma ratkaistaan taas GGM:11ä, minkä jälkeen ratkaisun yhdistel­

lyt leveydet puretaan auki s.e. purkamisesta syntyy mahdol­

lisimman vähän uusia asetteita. Asetteiden määrän vähenty­

misen onnistumisesta ei kuitenkaan ole varmuutta, eikä menetelmää päästä käyttämään ollenkaan, jos ensimmäinen GGM-kierros tuottaa nollahukkaratkaisun (tällöin ei voida valita peite!eveyksiä s.e. asetteet säilyvät käypinä).

Gilmore ja Gomory esittävät artikkelissaan /7/ leveyksien yhdistelyn (ryhmittelyn) asetteiden vähentämiskeinona kak­

sivaiheisessa trimmityksessä.

Seppo Peltonen onkin soveltanut leveyksien yhdistelyä hyvällä menestyksellä arkkitrimmitysohjelluistossaan.

Arkkitrimmityksessä yhdisteltyjä leveyksiä sisältäviä aset­

teita ei pituusleikkurilla tarvitse purkaa auki erillisiksi asetteiksi, vaan asia hoidetaan arkkileikkurilla leikkaa­

malla eri levyistä reunanauhaa.

Rullatrimmitykseen menetelmä ei em. syistä kovin hyvin so­

vellu, joten sitä ei jatkossa enempää käsitellä.

2) Asetteiden poistaminen

Asetteiden poistaminen GGM:n ratkaisusta on suoraviivaisin menetelmä asetteiden vähentämiseksi. Näin trimmittäjät usein käsin jäi kikäsittelevät GGM: 11ä saatua ratkaisua.

Tästä menettelytavasta myös Könönen kirjoittaa Pro Gradu­

työssään /17/.

Asetteita ei kuitenkaan voida poistaa yleensä kuin korkein­

taan muutama, ilman että määräpoikkeamat muodostuvat niin pahoiksi, ettei niitä jäljelle jääneiden asetteiden

muuttomääriä lisäämällä saada kompensoitua. Muuttomääril­

taan pienten asetteiden poistaminen sopii hyvin ratkaisun jälkikäsittelyn eli pyöristyksen yhteyteen, joten se kan­

nattaa ottaa 1isäkeinona ratkaisumenetelmään mukaan.

3) Keinotekoisen degeneroitumisen aiheuttaminen

Keinotekoisen degeneroitumisen aiheuttamista optimaaliseen simplexmatriisiin on käytetty GGM:n sekä myös etukäteen va­

littujen leikkauskaavioiden + tavallisen s impi ex in yhtey­

dessä. Ensinmainitusta tapauksesta kirjoittaa Holmberg (/12/) ja jälkimmäisestä Stovicek (/26/).

Stovicek kuvaa menetemää laskennallisesti varsin raskaaksi, joten siihen ei tässä yhteydessä tarkemmin paneuduta

etsittäessä mikrotietokoneen resursseihin soveltuvia ratkaisumenetelmiä.

4) Martti Kuutin leveyksien paketointi /16/

Paketoimalla leveyksiä yhteen vähenee eri leveyksien määrä ja siten myös GGM-ratkaisun asetteiden määrä. Martti

Kuutin NOPTRIM-ohjelmassa etsitään lopullista ratkaisua branch-and-bound-menetelmän luonteisesti ratkaisupuun haa­

roja pitkin solmusta (1 ratkaisusta) seuraavan tason sol­

muun edeten. Ideana on, että aina seuraavan alemman tason solmuun siirryttäessä otetaan yksi uusi nk. makro (= eri leveyksien lkm:ää yhdellä vähentävä pakettikombinaatio) lisää käyttöön ja asetteet vähenevät näin yleensä yhdellä edelliseen solmuun verrattuna. Käyttäjä valitsee haarautu- missolmun, josta ratkaisun hakua jatketaan eteenpäin. Uusia makroja otetaan käyttöön niille laskettujen hyvyys!ukujen perusteella. Sama leveys voi esiintyä useammassa paketissa eli osamakrossa. Kuutin mukaan makro on kuitenkin yleensä sitä parempi mitä yksinkertaisempi se on (osamakrojen lkm ja leveys). Muuta hän ei makrojensa hyvyysluvuista

mainitsekaan.

Koska asetteita vähennetään vain yksi kerrallaan, joudutaan käytännön ongelmaa ratkottaessa ratkaisemaan jopa kymmeniä trimmiongelmia GGM:llä, ennenkuin tyydyttävä 1eikkaussuuni- telma on löytynyt: joka solmusta haarauduttaessa NOPTRIM kokeilee eri makroja ja ratkaisee niihin liittyvät trimmi- tysongelmat. Kun jatkokäsittelysolmu valitaan esimerkiksi pienimmän trimmihukan mukaan, saatetaan helposti joutua um­

pikujaan eli asetteiden lukumäärää ei lopulta saadakaan riittävän pieneksi siedettävällä trirnmihukalla. Tällöin olisi aloitettava lähes alusta ja kokeiltava toista solmua jne.

Kuutin menetelmä on siis erittäin hidas, kun sitä yritetään soveltaa tilanteeseen, jossa asetteita on vähennettävä tuntuvasti. Vaikka NOPTRIM :iä käytetäänkin monessa paperi­

tehtaassa, on käytäntö osoittanut, etteivät trimmittäjät yleensä ole osanneet (tai viitsineet) käyttää sitä kunnolla hyväksi vaan tyytyneet perusratkaisuun.

Koska tässä etsitään mikrotietokoneen laskenta- ja muisti- kapasiteettiin soveltuvaa menetelmää, oli siis kehitettävä suoraviivaisempi paketointi heuristiikka.

5) Toteutettu paketointiheuristiikka

Tässä työssä kehitetyssä paketointiheuristiikassa on sovel- letettu ideoita, joihin Seppo Peltoselta on saatu hyviä virikkeitä.

Menetelmässä muodostetaan yhdellä kertaa tarvittava määrä paketteja, s.e. eri leveyksien määrä ei paketoinnin jälkeen ylitä käyttäjän syöttämää maksimiasetemäärää. Näin saadaan heti asetemääriItään käypiä ratkaisuja. Lisäksi voidaan ha­

kea kokonaisuuden kannalta sakkolukujen perusteella paras (tai parhaimpiin kuuluva) pakettiyhdistelmä, joka harvoin on sama kombinaatio kuin mikä saadaan ottamalla yksi ker­

rallaan paras paketti käyttöön. Paketit ovat toisiaan osittain poissulkevia. Sama tilausleveys saa esiintyä vain yhdessä paketissa, millä saadaan aikaan yksinkertaisia pa­

ketteja (jotka edellä on todettu parhaiksi).

Paketointia ohjataan parametreillä, jotka vaikuttavat pake­

teille laskettavien sakkolukujen komponenttien painotuk­

siin. Samalla pyritään suoraan sulkemaan pois huonoja pa­

ketteja ehdottomilla testeillä: esimerkiksi toleranssira- joitukset otetaan ehdottomina huomioon, paketointi ei saa aiheuttaa 1isäpoikkeamia.

Tällaiseen paketointiheuristiikkaan perustuvalla ohjelmalla joudutaan joskus suorittamaan muutamia ajoja, ennenkuin parhaimman tuloksen antava parametrikombinaatio on

löydetty. Ongelman koko on kuitenkin paketoinnin ansiosta yleensä niin pieni, että ajot sujuvat nopeasti.

4.3.3 Toteutetun paketointiheuristiikan kuvaus

Seuraavassa kuvataan paketointimenetelmää askeleittain.

Seuraavia uusia merkintöjä käytetään:

JA i j = alajakomäärä JYij = yläjakomäärä

J = hyväksyttyjen jakomääräparien joukko S = asetteiden maksimimäärä

wmin = pienin tilausleveys

Io Haetaan jokaisen tilausleveyden ala- ja ylämäärien (l-¡ ja u-j) jakomäärät käyttäen jakajina numeroita 1-5 ja pyöristä­

en kokonaisluvuksi s.e. toleranssirajat eivät laajene:

JAij = Hi/jl j = 1,...,5 ; i = l,...,m Jyij = hi/jJ

Jos alajakomäärä on suurempi kuin yläjakomäärä, niin ko.

jakomääräpari hylätään. Jakomääräpari hylätään myös, jos yläjakomäärä on alle minimimuuttomäärän tai jos jakajalla j

kerrottu leveys ylittää koneleveyden ja kapeimman tilaus- leveyden erotuksen. Hyväksytyt jakomääräparit muodostavat si is joukon J:

^ = f^Aij» ^Yij)

!

2 ° Järjestetään jakomääräparit aiajakomäärien perusteella nou­

sevaan järjestykseen.

3° Järjestetyn jakomääräjoukon perusteella aletaan muodostaa paketteja. Joukon ensimmäinen jakomääräpari valitaan ensim­

mäisen potentiaalisen paketin perustajaksi, jolle haetaan sopivia "kumppaneita" joukon toisesta alkiosta lähtien.

Kumppaninhaku ko. perustajalle lopetetaan, kun kumppanieh­

dokkaan aiajakomäärä ylittää perustajan yläjakomäärän.

Tällöin valitaan joukon toinen jakomäärä perustajaksi jne.

kunnes joukon viimeistä lukuunottamatta jokainen jakomäärä­

pari on saanut toimia potentiaalisena paketin perustajana.

Samaan pakettiin paketoidaan korkeintaan viiden eri leveyden jakomäärät. Potentiaalisen paketin on läpäistävä alla ku­

vattavat hyväksymistarkistukset ja sen sakko!uvun on kuu­

luttava r:n (esim. 50:n) pienimmän joukkoon, jotta paketti (ainakin väliaikaisesti) hyväksyttäisi in järjestettyyn pakettijoukkoon. Lopulliseen pakettijoukkoon hyväksytään vain r sakkoluvultaan parasta pakettia (mahdollisten paket­

tien määrää on mahdotonta ennustaa ja muistitilaa ei haluta tuhlata!).

Hyväksymistarkistukset:

- kumppaninehdokkaan aiajakomäärä < perustajan yläjakomäärä - ehdokkaaseen liittyvä tilausleveys ei saa vielä esiintyä

paketissa

- paketissa rinnan olevien rullien lkm (jakajien j summa)

< N (terärajoitus) - paketin leveys < L

- paketissa olevien eri leveyksien lkm < M ( jälkikäsittelyn joi tus)

Sakko!uvui11 a pyritään kuvaamaan paketin potentiaalisesti aiheuttamaa !isätrimmihukkaa. Hukkaa lisäävästi vaikuttavia tekijöitä ovat:

- paketin leveys

- pois paketoidut kapeat leveydet - pakettia tarvittava määrä

Em. tekijät otetaan huomioon laskettaessa yksittäisen pa­

ketin sakkoa. Tavoitteena on siis paketoida tilausmääril­

tään pieniä, suhteellisen kapeita leveyksiä ja jättää ti­

lausmääriltään suuria, kapeita leveyksiä paketoimatta.

Jos paketti sisältää esimerkiksi 4 eri leveyttä, niin sen asetteita vähentävä vaikutus on kolme, kun taas vain 2 eri leveyttä sisältävä paketti vähentää asetteita vain yhdellä.

Tämä "tehoero" otetaan implisiittisesti huomioon paketti- kombinaatioita muodostettaessa (seuraava askel), joten sitä ei tarvitse sisällyttää sakko!ukuihin. Kuitenkin jotta useita eri leveyksiä sisältävä, hyvä paketti saadaan mukaan järjestettyyn pakettijoukkoon (jonne vain r parasta

hyväksyttiin!) potentiaalisesti oikealle paikalleen, pake­

tin sakkoluku jaetaan paketin sisältämien eri leveyksien määrällä. Pakettikombinaation kokonaissakkoa seuraavassa askeleessa laskettaessa palautetaan paketin "oikea" sakko kertomalla edellä jakajana käytetyllä luvulla.

4° Etsitään paketti kombinaatio, joka mahdollistaa n eri ti­

laus leveyden tilauskannan esittämisen S (= asetteiden suu­

rin sallittu lkm) eri leveyden avulla ja jonka kokonaissak- ko on mahdollisimman pieni. Pakettikombinaation kokonais- sakko on siihen kuuluvien pakettien sakkojen summa. Paket- tikombinaatiota muodostettaessa on otettava huomioon, että paketit ovat osittain toisiaan poissulkevia: sama tilausle- veys ei saa esiintyä kuin yhdessä kombinaation paketissa.

Absoluuttisesti parhaan kombinaation löytäminen ei ole helppoa, kyseessä on kombinatorinen optimointiongelma. Sak-

kojen heuristisen luonteen takia ei ole perusteltua yrittää väkisin löytää kokonaissakon minimin antava, käypä

yhdistelmä jollakin optimointialgoritmilla, vaan riittää, kun löydetään hyvä kombinaatio.

Hyvän kombinaation etsimisessä käytetään neljää strategiaa:

1) Pakettijoukkoa käydään sakkojärjestyksessä läpi alusta loppuun, s.e. kukin paketti vuorollaan toimii kombinaation perustajana ja kumppaneita etsitään perustajan jälkeisistä alkioista.

2) Sama kuin 1) paitsi, että kumppaneita etsitään aina joukon ensimmäisestä alkiosta lähtien.

3) Pakettijoukkoa käydään läpi laskevan yhteensopi- vuusindeksin (= luku, joka ilmoittaa kuinka mo­

nen paketin kanssa ko. paketti sopii yhteen) mu­

kaisessa järjestyksessä. Kumppaneita etsitään perustajan jälkeisistä alkioista.

4) Sama kuin 3) paitsi, että kumppaneita etsitään joukon ensimmäisestä alkiosta lähtien.

Paras löydetty kombinaatio valitaan.

Näin saadut leveyspaketit ja paketoimatta jääneet leveydet muodostavat GGM:n lähtöaineiston.

4.3.4 Esimerkki paketoinnista

Seuraava esimerkki paketoinnista perustuu kehitetyllä trim- mitysohjelmalla suoritettuun ajoon. Lähtöaineistona on käy­

tetty todellista, ranskalaisen Arjornarin hienopaperi tehtaan yhtä trimmitettävää rypästä. Tehtaalla käytetään

peukalosääntönä sitä, että asetteiden lukumäärä saa olla korkeintaan noin 2/3 eri tilausleveyksien määrästä.

Rypäs koostuu 16 tilausleveydestä:

Leveys [mm] al at i 1ausmäärä [kpl] ylätilausmäärä [kpl]

470 523 587

510 36 41

540 34 39

610 73 84

630 381 417

640 72 80

650 149 169

700 85 95

710 38 44

740 76 88

770 78 87

800 51 59

860 69 78

880 179 199

900 20 23

920 149 169

Tehtaan koneleveys on 3880 mm.

Trimmitettäessä rypäs GGM:llä, saadaan nollahukkaratkaisu, jossa asetteita on 16. Kun maksimiasetemääräksi sallitaan vain 10, muodostaa paketointiheuristiikka yllä esitetyn ryppään pohjalta seuraavan vain 10 eri leveyttä sisältävän joukon, jonka viisi ensimmäistä leveyttä ovat paketteja:

Leveys aiamäärä ylämäärä paketin koostumus

1760 38 39 1 x 510, 1 x 540,

1820 21 23 1 x 900, 1 x 920

1440 85 88 1 x 700, 1 x 740

1380 78 84 1 x 610, 1 x 770

1500 72 78 1 x 640, 1 x 860

470 523 587 ^-

630 381 417 ^-

650 149 169 ^-

800 51 59 ^-

880 179 199

Kuten havaitaan heuristiikka on tässä esimerkissä onnistu­

nut muodostamaan yksinkertaisia paketteja: jokaisessa pake­

tissa samaa leveyttä on vain yksi rinnan. Paljon tilatut ja kapeat leveydet ovat jääneet paketoimatta.

Pakettien ala- ja ylämäärät on laskettu siten, että puret­

taessa pakettia auki ei minkään siihen sisältyvän leveyden toleranssiraja ylity. Listan ensimmäisen paketin (1760 mm), ala- ja ylämäärä on esimerkiksi laskettu seuraavasti:

aiamäärä = max (36, 34, 38) = 38

ylämäärä = min (41, 39, 44) = 39

Kun "paketoitu rypäs" trimmitetään GGM:llä saavutetaan rat­

kaisu, jonka hukkaprosentti on 0,14 ja asetteiden lukumäärä on 10.

Soveltamalla esimerkkiongelmaan seuraavassa luvussa kuvatta­

vaa pyöritysheuristiikkaa saadaan ratkaisusta poistettua vielä yksi yhden muuton asete hukkaprosentin pysyessä ennallaan.

4.3.5 MuuttomääriItään pienten asetteiden poistaminen

Paketoinnilla ei asetteita voida vähentää mielivaltaisen paljon, tilausryppäästä riippuen yleensä korkeintaan 50-60

%

(eri tilausleveyksien lukumäärästä). Paketoinnin mahdolli­

suuksien äärirajoilla toimittaessa yleensä myös hukkapro­

sentti nousee jyrkästi. Tämän takia paketointiin on hyvä liittää toinen asetteiden vähentämiskeino, muuttomääriItään pienten asetteiden poistaminen. Pienet muuttomäärät ovat myös sinänsä haitallisia, ne hankaloittavat rullien jälkikäsittelyä (vrt. minimimuuttovaatimus).

Asetteiden poistaminen liittyy kiinteästi kohdassa 4.4 kä­

siteltävään tilaustoleransseissa pysymiseen. Vain vähän käytetyn asetteenkin poistaminen leikkaussuunnitelmasta ai­

heuttaa tuotantomäärien poikkeamista tilausmääristä, mikä on pyrittävä kompensoimaan muiden asetteiden käyttöä lisää­

mällä. Tätä ja muutenkin tilaustoleransseissa pysymistä varten on kehitetty erillinen työkalu, jälkikäsittelyohjel­

ma (pyöristysheuristiikka), jossa suorahakumenetelmää käyt­

täen minimoidaan sakkofunktioita. Sakkofunktio koostuu poikkeaminen perusteella laskettavista sakoista ja asettei­

den poistosta saatavista hyvityksistä (kts. lähemmin kohta 4.4).

4.4 Tilaustoleransseissa pysyminen

4.4.1 Yleistä

GGM:ssä poistetaan optimoinnin ajaksi muuttojen xj koko- naislukuvaatimus, joten saatu ratkaisu on pyöristettävä.

Vaikka tilausmäärät olisivat suuria ja niille olisi sallit­

tu normaalitoleranssit, saattaa pyöristyksestä johtuvilla poikkeamilla olla merkitystä, kun toleransseja on jo LP-vaiheessa (kohdassa 4.2 kuvatulla tavalla) käytetty hyväksi. LP:n murto!ukuratkaisu saattaa jo ennestään olla joillakin toleranssirajoilla, jolloin pyöristys johtaa näi-

den toieranssirajojen ulkopuolelle. Huomattavasti hankalam­

maksi tilanne muodostuu vielä, kun jotain leveyttä on ti­

lattu vain muutama rulla. Jos nämä rullat sattuvat vielä rinnakkain johonkin asetteeseen, niin pieni pyöristys alas­

päin voi aiheuttaa 100 %:n poikkeaman eli ko. asiakas jäisi täysin ilman (mitä ei pidettäisi hyvänä asiakaspalveluna).

Pyöristysnäkökohta on siis myös jo asetteen generointivai- heessa otettava huomioon. Vähän tilattua leveyttä ei salli­

ta asetteessa rinnan kuin korkeintaan max (1, t-¡/qtav )>

missä qtav = tavoitteellinen minimimuuttomäärä ja t-¡ levey­

den i tilausmäärä rullissa.

4.4.2 Poikkeamien minimointi

Muodostetaan sakkofunktio, jonka muuttujina ovat GGM:n tuottamien asetteiden muuttomäärät. Tavoitteena on hakea optimaaliset muuttomäärät, joilla sakkofunktion arvo

minimoituu. Poikkeamat kasvattavat sakkoa, pienten muutto- määrien saamisesta nollaan (asetteiden poistosta) hyvite­

tään (sakkofunktion arvo pienenee). Minimoitaessa absoluut­

tisia poikkeamia toleranssirajoista ongelma voidaan kir­

joittaa seuraavaan muotoon:

min Ci max (O, 1^ - xj

n

У~! aijxj) + j=l

C2 max(0, ajjXj j=l

ui) - CgSj (4.3)

m

/ . aij “i> Xj i=l

n m

< ^ aij Wi)xj + d j=l i=l

missä

1 kun Xj = O

O muuten

ja uudet merkinnät:

Ci = alitussakko C2 = ylityssakko

C3 = bonus asetteen poistamisesta

xj = GGM:n ratkaisun muuttomäärä lähimpään kokonaislukuun pyöristettynä

d = maksimilisähukka, joka sallitaan

Probleeman 4.3 kohdefunktion absoluuttisen minimin löytävää optimointialgoritmia ei keksitty vaan turvauduttiin suoraha-

kumenetelmän käyttöön, jolla tosin saatetaan jäädä (vain) lokaaliin minimiin. Alla esitetyssä menetelmässä käyttäjä valitsee parametrit СЬ C2 ja C3. Käyttäjä päättää myös, käytetäänkö kohdefunktiossa absoluuttisia poikkeamia (A) vai suhteellisia neliöpoikkeamia (S). Rajoitusehtoa 2 ei

eksplisiittisesti oteta huomioon, vaan lopussa tarkiste­

taan, onko hukka kasvanut liian suureksi (jos näin on käy­

nyt, on valittava toiset parametrit). Menetelmä on siis seuraava:

Io Lasketaan lähtötilanteen leveyskohtaiset

- alitukset: RL-j = lj i — 1,...,m

- ylitykset: RUi i — 1,...,m

sekä "redusoidut" muuttomäärät: RMj = 1-xj j = l,...,n

ja näihin liittyvä lähtösakko S°

m m

joko (A): S° = Ci max (0, RL-¡) + C2 max (0, RU-¡)

i=l i=l

m

tai (S):S°=Ci

У

+

m

C2 ^[max(0,RUi)]2/t i=l

missä ti = tilausleveyttä i tilattu määrä

(lähtötilanteessa on mukana vain asetteita, joiden muutto- määrät >0, joten RMj:t eivät vaikuta lähtösakkoon!).