TEKNIU.INEN KORKEAKOULU
Teknillisen Fysiikan ia Matematiikan Osasto
Olli Stenlund
Talonrakennuksen aikataulun optimointi
____ TEKNILLINEN KORKEAKOULU
t TEKNILLISEN FYSIIKAN JA MATEMATIIKAN KIRJASTO
Diplomi-insinöörin tutkintoa varten tarkastettavaksi jätetty diplomityö Espoo, 26.6.2007
Työn valvoja: professori Harri Ehtamo Työn ohjaaja: KTM Olli Seppänen
Teknillinen korkeakoulu Diplomityön tiivistelmä
Tekijä Olli Stenlund
Osasto Teknillisen fysiikan ja matematiikan osasto Pääaine Systeemi-ja operaatiotutkimus
Sivuaine Ohjelmistojärjestelmät
Työn nimi Talonrakennuksen aikataulun optimointi Title in English Optimization of Construction Project Schedule Professuurin koodi
ja nimi
Mat-2 Sovellettu matematiikka Työn valvoja Professori Harri Ehtamo Työn ohjaaja KTM Olli Seppänen
Tiivistelmä Talonrakennushankkeiden aikatauluttamisessa on siirrytty tietokonepohjaisen rakennushankkeille suunnitellun ohjelmiston käyttöön. Rakennushankkeet ovat usein niin suuria, että niiden aikatauluja on vaikea hallita käsin paperilla tai edes yleisellä aikataulun suunnitteluohjelmalla. Vico Softwaren Control- ohjelmisto on suunniteltu juuri rakennushankkeiden aikatauluttamisen helpottamiseen. Tähän ohjelmistoon toteutetaan lisäosana aikataulun optimointisovellus, jossa käytetään tässä diplomityössä kuvattua optimointialgoritmia.
Talonrakennushankkeet koostuvat eri paikoissa suoritettavista tehtävistä, joita suoritetaan erilaisilla resursseilla. Aikatauluttamisessa päätetään mm. missä paikkajärjestyksessä, millä resursseilla ja nopeudella tehtävät suoritetaan. Rajoituksia tehtävien suoritukselle asettavat mm. resurssien yhtäaikaiset ja tehtäväkohtaiset käyttörajoitukset ja tehtävien mahdolliset suoritusjärjestykset. Aikataulun optimoinnissa pyritään minimoimaan aikataulun kustannukset. Kustannuksia syntyy mm. resurssien käytöstä ja niiden kuljettamisesta työmaalle. Tyypillisten rakennusprojektien tehtävien ja paikkojen suuren määrän takia optimoinnissa joudutaan käyttämään satunnaisuuteen pohjautuvaa algoritmia, koska kaikkia ratkaisuja ei voida ajan puutteen takia käydä läpi. Tähän valitaan geneettinen algoritmi, koska se soveltuu hyvin ongelmiin, joissa ratkaisuavaruus on hyvin suuri ja epätasainen ja joissa optimaalista ratkaisua ei tarvitse löytää, vaan riittävän hyvä ratkaisu riittää
Tässä diplomityössä toteutetaan rakennushankkeen aikataulun optimointiin mahdollisimman tehokas algoritmi ja viritetään se mahdollisimman hyväksi estimoimalla sen joitakin oleellisimpia parametreja.
Parametrit estimoidaan testaamalla algoritmia kahdella testiongelmalla, joista toinen vastaa normaalia rakennushanketta ja toinen on yksinkertaisempi. Lopuksi testataan algoritmin suorituskykyä eli kuinka lähelle optimia ne pääsevät testiongelmissa. Optimoinnin lisäkeinoina käytetään mm. resurssien tahdistusta
¡a älykästä alustusta. Resurssien tahdistuksessa resurssien määrä pyritään arvioimaan sopivaksi edeltävien tehtävien perusteella. Älykkäässä alustuksessa yksilöt alustetaan älykkäästi jo ennen optimoinnin alkua.
Testien perusteella resurssien tahdistuksesta ei todettu olevan testiongelmissa hyötyä, mutta älykäs alustus sen sijaan paransi tehokkaasti tuloksia jo ennen varsinaisen optimoinnin alkua. Suorituskykytesteissä algoritmi pääsi yksinkertaisemmassa testiongelmassa optimiin, mutta toisessa monimutkaisemmassa testiongelmassa optimin lähelle ei päästy testiongelman suuruuden takia. Kuitenkin jo pelkkä älykäs alustuskin optimoi testiongelmia tehokkaasti.
Sivumäärä 85 Avainsanat Optimointi, rakennushanke, geneettiset algoritmit
Täytetään osastolla
Hyväksytty Kirjasto
Helsinki University of Technology Abstract of Master’s Thesis
Author Olli Stenlund
Department Department of Engineering Physics and Mathematics Major subject Systems and Operations Research
Minor subject Software Systems
Title Optimization of Construction Project Schedule Title in Finnish Talonrakennuksen aikataulun optimointi Chair Mat-2 Applied Mathematics
Supervisor Professor Harri Ehtamo Instructor EM Olli Seppänen
Abstract Nowadays scheduling of construction projects is done with computer programs developed especially for construction projects. Construction projects are often so huge that their schedules are hard to control if they are made in paper or with general computer scheduling applications. Vico Software’s Control application is made especially for scheduling construction projects. Optimization algorithm described in this Master’s thesis is being used in the additional optimization application developed to Control.
Construction projects contain many different tasks, which are carried out with different resources. Scheduling means deciding location order, resource usage and working pace of different tasks. Constraints in carrying out tasks are for example simultaneous and task specific usage constraints of resources and possible location orders of different tasks. Schedule optimization means minimizing costs, which result for example from resource usage and from their mobilization. Optimization has to be done using an algorithm based on randomness, because of the huge amount of tasks and locations in typical construction projects. Whole solution space can’t be checked in a short enough period of time. Genetic algorithm is used in this optimization problem, because it works well in this kind of problems, where the solution space is huge, not smooth, there is not much information about it and where optimal solution doesn’t have to be found, but solution good enough is sufficient.
The aim of this Master’s thesis is to create an algorithm as effective as possible for construction project schedule optimization and to tune it by estimating the most important parameters. Parameters are estimated by testing the algorithm with two test problems, from which the other one is simpler and the other one equals a typical construction project. Finally algorithm performance in the test problems is tested. In optimization for example resource synchronizing and intelligent initialization are used as additional optimization methods.
Resource synchronizing means that resource usage in tasks is estimated based on the predecessor tasks.
Intelligent initialization creates solutions with intelligent starting values before the optimization starts.
Based on the tests, resource synchronizing was not useful in this optimization problem. But intelligent initialization created good solutions even before the optimization started. In performance tests optimum solution was reached in the simpler test problem. But because of the huge size of the second test problem, the algorithm didn’t find solutions near the optimum in the second problem. Anyway the intelligent initialization alone optimized the test problems very efficiently.
Number of pages 85 Keywords Optimization, construction project, genetic
algorithms Department fills
Approved Library code
Alkusanat
Tämä diplomityö on tehty Vico Software Oy:lle. Haluan kiittää Olli Seppästä ohjauksesta ja mahdollisuudesta tehdä tämä diplomityö. Kiitos myös Vico Software!le taloudellisesta
tuesta, Ilkka Pelkoselle työn lukemisesta ja Harri Ehtamolle työn valvomisesta.
Kiitos kaikille kavereille ja vanhemmille kannustuksesta ja tuesta työn teon aikana. Kiitos myös ennenkaikkea Jumalalle sopivan diplomityön aiheen ja paikan antamisesta.
Helsingissä, 26.6.2007
Olli Stenlund
Sisällysluettelo
1 Johdanto...7
1.1 Taustaa...7
1.2 Työn tavoitteet... 8
2 Rakennushankkeen teoriaa... 10
2.1 Paikat... 10
2.2 Määrät ja resurssit...11
2.3 Tehtävän osat... 12
2.4 Aikataulujen esitysmuotoja... 16
2.5 Riippuvuudet... 17
2.5.1 Riippuvuustyypit...17
2.5.2 Riippuvuuksien käyttö... 18
2.6 Osatehtävien ajoitus... 21
2.7 Kustannukset...24
3 Rakennushankkeen aikataulun optimointiongelma...29
3.1 Ongelman kuvaus... 29
3.2 Optimointikeinot... 29
3.3 Rajoitukset... 34
4 Ongelman ratkaisualgoritmi...36
4.1 Sopivan ratkaisutavan valinta...36
4.2 Geneettiset algoritmit... 37
4.3 Koodaus... 39
4.4 Geneettisen algoritmin osat... 39
4.4.1 Alkupopulaation luonti...39
4.4.2 Lopetusehto... 40
4.4.3 Valinta... 40
4.4.4 Risteytys...42
4.4.5 Mutaatio...43
4.5 Parametrien valinta... 43
5 Ratkaisualgoritmin toteutus...45
5.1 Koodaus... 45
5.2 Ratkaisualgoritmin osat...48
5.2.1 Parametrit ja niiden asetus... 49
5.2.2 Alkupopulaation alustus... 50
5.2.3 Valinta... 53
5.2.4 Risteytys... 53
5.2.5 Mutaatio... 53
5.2.6 Dekoodaus...54
5.2.7 Pisteytys... 61
5.2.8 Takaisinsijoitus... 61
5.2.9 Aikataulun siirto ohjelmaan... 61
6 Algoritmin testaus...64
6.1 Tavoite... 64
6.2 Parametrien vaikutus algoritmin toimintaan... 64
6.2.1 Tutkittavat parametrit ja niiden vaikutus algoritmin toimintaan...64
6.2.2 Muiden parametrien valinta ja vaikutus optimointiin...66
6.2.3 Älykkään alustuksen vaikutus optimointiin... 68
6.3 Parametrien testattavat arvot... 69
6.4 Testausuunnitelma... 71
7 Tulokset...74
7.1 Risteytys- ja mutaatiotestien tulokset...74
7.2 Työryhmien lukumäärä-testin tulokset... 75
7.3 Älykäs alustus-testin tulokset... 76
7.4 Suorituskykytestien tulokset... 78
8 Yhteenveto ja johtopäätökset...81
8.1 Yhteenveto... 81
8.2 Parannusehdotuksia... 83
9 Viitteet... 85
1 Johdanto
1.1 Taustaa
Talonrakennuksen hankkeiden aikatauluttamisessa on viime vuosina siirrytty tietokonepohjaisen rakennushankkeille räätälöidyn ohjelmiston käyttöön.
Rakennushankkeet ovat usein niin suuria, että niiden aikatauluja on vaikea hallita käsin paperilla tai edes yleisellä aikataulun suunnitteluohjelmalla. Vico Software Oy:n (entinen DSS Oy) yhdessä muutaman rakennusfirman ja TKK:n rakentamistalouden laboratorion kanssa 2000-luvulla kehittämä Control-ohjelmisto (entinen Dynaproject) on kehitetty nimenomaan talonrakennushankkeiden aikataulujen hallitsemiseen. Ohjelmiston tavoitteena on tehostaa aikataulun suunnittelua, maksimoida töiden jatkuvuus työmaalla, minimoida kustannukset ja vähentää erilaisia häiriöitä ja riskejä työmaalla. Controlissa projektin tehtävät voi jakaa pienempiin osakohteisiin, jotka muodostavat projektin ns.
paikkahierarkian. Tehtävien toteutumisasteen voi syöttää ohjelmalle, jolloin ohjelma näyttää projektin edistymisasteen eri tehtävien suhteen. Lisäksi myöhästyneet tehtävät ja niistä aiheutuvat tuotannon häiriöt näytetään. Control-ohjelmisto on ollut käytössä useassa Suomessa toteutetussa rakennushankkeessa. Näistä esimerkkinä Kampin
suuri kauppakeskus. [ 1,2]
Talonrakennushankkeen optimointi on vaativa tehtävä. Muuttuvia tekijöitä ja erilaisia rajoituksia on useita. Hanke koostuu useista eri paikoissa suoritettavista tehtävistä, jotka puolestaan koostuvat tietyillä resursseilla suoritettavista osatehtävistä. Osatehtävät puolestaan jakautuvat eri paikoissa suoritettaviin osakohdetehtäviin. Resurssit voivat olla ihmistyövoimaa tai sitten erilaisia koneita. Muutettavia tekijöitä ovat esim. resurssien käyttö tehtävien suorituksessa, tehtävien suoritusjärjestykset ja tehtävien suoritusnopeudet. Resursseista muodostetaan työryhmiä, joita asetetaan eri osatehtävien suoritukseen. Eri tehtävien suoritusnopeutta säätämällä esim. resurssien määrää muuttamalla voidaan määrittää missä järjestyksessä tehtävät suoritetaan. Voidaan myös määrittää missä paikkajärjestyksessä tehtävät suoritetaan. Rajoituksia ovat esim.
resurssien yhtäaikaiset käyttörajoitukset, resurssien tehtäväkohtaiset rajoitukset ja
tehtävien mahdolliset suoritusjärjestykset. Resurssien yhtäaikaiset käyttörajoitukset vaikeuttavat niiden käytön säätämistä sopivalle tasolle eri tehtävissä ja eri ajankohtina, koska samoja resursseja voitaisiin tarvita toisissa tehtävissä samaan aikaan. Myös tehtävissä on oma rajoitus resurssien määrälle. Lisäksi monet tehtävät ovat riippuvaisia toisten tehtävien suorituksesta. Tällaisten tehtävien välille voidaan määritellä riippuvuuksia, jotka pakottavat tehtävät suoritettaviksi tietyssä järjestyksessä. Monien tehtävien suoritus on käytännössä mahdotonta ennen kuin jokin edeltävä tehtävä on suoritettu. Myös eri tehtävien suoritusnopeus täytyy säätää viisaasti. Esimerkiksi projektin kokonaisuuden kannalta olennaiset tehtävät on suoritettava nopeasti, ettei koko projekti viivästy niiden takia. Kustannukset ovat yleensä projektin määräävin tekijä, joten optimointikin suunnataan niiden minimoimiseen. Kustannuksia syntyy usealla eri tavalla.
Tehtävien resurssien käytöstä, resurssien odotusajasta tehtävien välillä, resurssien kuljettamisesta työmaalle sekä erilaisista työmaakohtaisista tehtävistä aiheutuu kustannuksia.
Rakennushankkeessa voi olla satoja tehtäviä ja kymmeniä tehtävien suorituspaikkoja.
Niiden aikatau 1 uttam i se 1 le on olemassa hyvin suuri määrä erilaisia toteutusvaihtoehtoja ja siksi optimaalisen ratkaisun löytäminen on vaikeaa. Ratkaisuavaruus on niin suuri, että ratkaisualgoritmin tyyppi on valittava viisaasti. Kaikkia mahdollisia vaihtoehtoja ei voida ajanpuutteen takia käydä läpi. Myöskään ongelmasta ei ole saatavissa minkäänlaista derivoituvaa lauseketta, jonka avulla optimi voitaisiin löytää. Tämän takia ongelmaan on sovellettava lähinnä satunnaisuuteen perustuvaa hakualgoritmia, koska muut algoritmit eivät sovellu ongelman ratkaisemiseksi yhtä hyvin. Satunnaisista algoritmeista optimointiin valitaan geneettiset algoritmit. Nämä soveltuvat hyvin ongelmaan, koska ratkaisuavaruus on hyvin suuri, epätasainen eli se ei koostu esim. vain yhdestä kukkulasta, siitä ei ole paljonkaan tietoa etukäteen ja koska optimaalista ratkaisua ei tarvitse löytää, vaan riittävän hyvä ratkaisu riittää. [3]
1.2 Työn tavoitteet
Tässä työssä etsitään ja toteutetaan rakennusaikataulun optimointiin mahdollisimman tehokas algoritmi, joka kykenee optimoimaan todellisia rakennusprojekteja lähellä olevat
testiongelmat riittävän lähelle optimiratkaisua. Optimointialgoritmin oleellisimmat parametrit estimoidaan sopiviksi testaamalla algoritmia testiongelmilla. Näin algoritmista saadaan mahdollisimman suorituskykyinen, minkä jälkeen testataan miten hyviin optimointituloksiin algoritmi yleisesti ottaen pääsee. Optimointia tehostetaan erilaisilla lisäkeinoilla, jotka nopeuttavat parempien ratkaisujen löytymistä. Näitä ovat mm.
tehtävien osakohteiden oletusjärjestys, työryhmien lukumäärän laskeminen edeltäjistä eli tahdistus, osakohdetehtäväjärjestyksien laskenta edeltäjäriippuvuuksista sekä älykäs alustus. Näillä toimenpiteillä löydetään helpommin mm. optimaalinen resurssien määrä ja tehtävien osakohdejärjestys. Lisäksi älykäs alustus parantaa tehokkaasti ratkaisua jo ennen optimoinnin alkamista. Algoritmi toteutetaan Control-ohjelmistoon lisäosaksi ja sille annetaan syötteenä Control-ohjelmiston projektitiedosto, mikä myös määrittää mitä tietorakenteita optimoinnissa käytetään.
Työ jakautuu kahdeksaan kappaleeseen. Johdannon jälkeen toisessa kappaleessa perehdytään rakennushankkeen teoriaan ja käydään läpi optimoinnin kannalta olennaisia rakennusaikataulun käsitteitä ja siihen liittyviä toimenpiteitä. Kolmannessa kappaleessa esitellään työssä ratkaistava optimointiongelma, johon kuuluu ongelman muuttujat, rajoitukset ja optimointikeinot. Neljännessä kappaleessa esitetään optimointiongelmassa käytettävä algoritmi ja käydään läpi algoritmin teoriaa. Viidennessä kappaleessa on kuvattu miten algoritmi on toteutettu ja miten se toimii käytännössä Control-ohjelmiston osana. Kuudennessa kappaleessa määritellään miten algoritmia testataan ja seitsemännessä kappaleessa raportoidaan ja pohditaan testien tuloksia. Kahdeksannessa kappaleessa on yhteenveto koko työstä ja lisäksi parannusehdotuksia jatkokehitystä varten.
2 Rakennushankkeen teoriaa
Rakennushanke koostuu monista erilaisista tehtävistä, jotka vaativat aikaa ja resursseja.
Usein hankkeessa esiintyy paljon toistuvia tehtäviä, joissa samaa työtä tehdään useassa eri paikassa. Tämän takia tehtävät kannattaa erottaa suuremmiksi kokonaisuuksiksi, joihin määritetään paikat, joissa tehtävä suoritetaan. Tehtävät ovat usein myös riippuvia toisistaan, mikä myös pakottaa tehtävien erottamiseen sopiviksi kokonaisuuksiksi, jotta erilaisia riippuvuuksia voidaan määritellä tehtävien välille. Tällöin myös tehtävien suoritusta pystytään valvomaan paremmin ja työmaan kaikkien osapuolien yhteistoiminta voidaan suunnitella helpommin. [4]
2.1 Paikat
Rakennushanke sisältää mahdolliset paikat, joissa tehtäviä voidaan suorittaa. Paikat muodostavat puumaisen paikkahierarkian, jossa paikat ovat eri hierarkiatasoilla.
Hierarkiatasojen lukumäärää ei ole rajoitettu, mutta kaikkien puun haarojen täytyy olla määritelty alimmalle hierarkiatasolle asti. Ylempänä hierarkiassa oleva paikka sisältää sen alla olevat paikat, jotka ovat pienempiä oman hierarkiatasonsa paikkoja. Kuvan I paikkahierarkiassa hierarkiatasoja on 3. Projekti koostuu paikoista А, В ja C. Näistä kukin puolestaan koostuu paikoista 1 ja 2. Ylemmän hierarkiatason paikat ovat kuvassa alempien tasojen vasemmalla puolella.
Tasot Taso2 TasoS
0
2
1
Project В
2
1
A
2
1
Kuva 1 Paikkahierarkiassa vasemmassa reunassa on paikkahierarkiassa ylimpänä oleva taso ja oikeassa reunassa alimpana oleva taso. Kukin paikka jaetaan sen alempana olevalla hierarkiatasolla oleviin paikkoihin.
2.2 Määrät ja resurssit
Aikataulutehtävät, joita kutsutaan myös lyhyemmin tehtäviksi, rakentuvat määräriveistä, jotka kuvaavat työmaalla tehtäviä tuotoksia. Tällainen tuotos voi olla esim. väliseinä.
Määrärivi sisältää mm. seuraavia tietoja:
• Yksikkö
• Menekki
• Määrät eri paikoille
Määräävillä on yksikkö, joka kuvaa tuotoksen laatua. Yksikkö voi olla esim. työvoiman työaikaa jossain aikayksikössä kuten työtunti, tuotoksen määrä, pinta-ala tai tilavuus.
Määrärivin menekki tarkoittaa sen tarvitsemaa resurssimäärää yhtä yksikköä kohden.
Määrärivi in liittyy määrä jokaisessa tehtävän paikassa. Jos määrä on jonkin paikan kohdalla 0, paikassa ei suoriteta sitä. Määrääville voidaan laskea sen vaatimat resurssityötunnit tietyssä paikassa i:
K =*%»
jossa t' on resurssityötunnit paikassa i, d määrärivin menekki yksikköä kohden ja qt määrä paikassa i.
Resursseja, joita käytetään tuotoksien tuottamiseen ovat esim. työvoima, erilaiset koneet ja raaka-aineet. Resurssit jaetaan erilaisiin resurssityyppeihin, jotka kuvaavat resurssin käyttötarkoitusta ja kykyä selvitä erilaisista tehtävistä. Erilaisista resurssityypeistä voidaan muodostaa työryhmiä, joissa on tietty määrä eri resurssityyppejä.
Työryhmä sisältää seuraavat tiedot:
• Resurssityypit
• Resurssityyppien työsaavutuskertoimet
• Resurssityyppien lukumäärät
Resurssityyppien työsaavutuskertoimet ja lukumäärät työryhmässä on määritelty jokaiselle työryhmän resurssityypille.
Resurssityyppi taas sisältää:
• Toimittajan
• Maksimikäytön
• Käyttökustannuksen (/h)
Resurssityypin toimittaja vastaa resurssityypistä. Toimittajan rajalliset resurssit työskentelevät tyypillisesti useissa eri hankkeissa, jolloin yksittäisen hankkeen näkökulmasta resurssien saatavuus on rajoitettu. Tietyn resurssityypin yhtäaikainen käyttö projektissa voidaan rajoittaa tietyn maksimikäytön tasolle. Myöskään sama resurssi ei voi olla käytössä samaan aikaan monessa paikassa. Työryhmän kokonaistyösaavutus Wwg lasketaan työryhmän n:stä resurssityypistä:
i=\
jossa k.' on resurssityypin i työsaavutuskerroin, nt resurssityypin i lukumäärä työryhmässä.
2.3 Tehtävän osat
Tehtävä koostuu myös pienemmistä tehtäväkokonaisuuksista kuten osatehtävistä ja osakohdetehtävistä. Tehtävä sisältää oletusarvoisesti yhden osatehtävän, mutta osatehtäviä voidaan myös jakaa useiksi osatehtäviksi, jotka voidaan suorittaa eri resursseilla. Osatehtävät sisältävät tietyissä paikoissa suoritettavia osakohdetehtäviä.
Suurin osa Controlin laskelmista tehdään osatehtävä- ja osakohdetehtävätasolla. Kuvassa 2 näkyy Controlin tehtävän osien suhteet toisiinsa.
Tehtävä Osatehtävä Osakohdetehtävä Paikka
Kuva 2 Tehtäväsuunnittelun yksiköiden väliset suhteet
Tehtävä sisältää seuraavia tietoja:
• Vastuuhenkilö
• Resurssien toimittaja
• Tarkkuustaso
• Osatehtävät
• Määrärivit
• Lukitut hierarkiatasot
• Työryhmien lukumäärän maksimiarvo
Tehtävä sisältää tehtäväkokonaisuuteen liittyviä yleisempiä tietoja kuten vastuuhenkilöjä toimittaja. Tehtävällä on myös tarkkuustaso, joka ilmoittaa millä paikkahierarkiatasolle tehtävän osatehtävien paikat on määritelty. Tehtävä sisältää listan sen osatehtävistä ja määräriveistä. Lukitut hierarkiatasot ja työryhmien lukumäärä ovat optimointia rajoittavia tekijöitä.
Osatehtävä taas sisältää seuraavat tiedot:
• Osakohdetehtävät
• Työryhmä
• Työryhmien lukumäärä
• Ajoitus aikaisimmaksi mahdolliseksi
• Ajoitus rytmitetyksi
• Osatehtäväriippuvuudet
Osatehtävä sisältää sen osakohdetehtävät ja työryhmän, jota käytetään osakohdetehtävien suorituksessa. Jos kuitenkin määrärivien määrät jossain paikassa ovat nollia, osatehtävälle ei luoda osakohdetehtäviä siinä paikassa. Osatehtävällä on yksi työryhmä, mutta sille voidaan määrittää kuinka montaa tällaista työryhmää se käyttää. Osatehtävän ajoitus voidaan asettaa aikaisimmaksi mahdolliseksi tai rytmitetyksi eli jatkuvasti ilman taukoja suoritettavaksi. Osatehtäväriippuvuudet määräävät suoritusjärjestyksen muihin tehtäviin tai osatehtäviin verrattuna.
Osakohdetehtävä sisältää taas seuraavat tiedot:
• Paikka
• Aloitusaika
• Kesto
• Edeltäjäosakohdetehtäväriippuvuudet
• Seuraajaosakohdetehtäväriippuvuudet
Osakohdetehtävä suoritetaan tietyssä paikassa ja sillä on aloitusaika ja kesto.
Osakohdetehtävällä on myös riippuvuuksia toisiin osakohdetehtäviin, jotka voivat olla samassa tai eri osatehtävässä. Osatehtävän sisäiset osakohdetehtäväriippuvuudet määräävät osatehtävän osakohdejärjestyksen kun taas eri osatehtävien väliset osakohdetehtäväri ippuvuudet määräävät eri osatehtävien väliset suoritusjärjestykset.
Paikka sisältää seuraavia tietoja:
• Isäpaikka
• Lapsipaikat
Paikat sisältävät lähinnä paikkahierarkiaan liittyviä tietoja. Isäpaikka on hierarkiassa ylempänä ja lapsipaikat ovat alapuolella hierarkiassa.
Tehtävän osien kestojen laskemiseksi täytyy ensin laskea osatehtävään liittyvien osakohdetehtävien kestot. Osakohdetehtävien kesto taas lasketaan kaikkien tehtävän määrärivien suoritusaikojen summana osakohdetehtävän paikassa. Tietyn määrärivin suoritusajaksi (h) paikassa i tulee
jossa t\ on määrärivin resurssityötunnit paikassa i, W resurssien työsaavutus.
Resurssien työsaavutus on osatehtävän resurssien kokonaistyösaavutus Wpl, joka saadaan osatehtävän työryhmästä:
Wp‘ = nWwg,
jossa n on osatehtävän työryhmien lukumäärä ja Wwg on työryhmän työsaavutus.
Lisäksi osakohdetehtävän paikkaa vastaava työsaavutuskerroin k f on otettava huomioon, koska se kuvaa paikan i suorituksen helppoutta. Näin saadaan
4
' nW4c'
Paikan i osakohdetehtävän kesto (h) saadaan laskemalla yhteen sen kaikkien n:n määrärivin kesto
7=1
Lopulta osatehtävän kestoksi tulee sen m:n osakohdetehtävän kestojen summa tP‘
- V tp = У У tV = у у -
d,4u/=1 /=1 7=1
jossa m on paikkojen lukumäärä osatehtävässä ja n osatehtävään liittyvien määrärivien lukumäärä.
Kuvassa 3 näkyy tärkeimpien tehtävään liittyvien kokonaisuuksien suhde toisiinsa ja tehtävän osiin. Osatehtävällä on vain yksi työryhmä, mutta osatehtävä voi käyttää tarvittaessa resursseinaan useita samanlaisia työryhmiä. Työryhmien lukumäärän kasvattaminen nopeuttaa tehtävien suoritusta, mutta varaa enemmän resursseja käyttöön samanaikaisesti. Resursseilla suoritetaan tehtävään ja myös sen osakohdetehtäviin liittyviä määrärivien tuotoksia.
Määrärivi
Tehtävä Paikka
Resurssityyppi Osakohdetehtävä Osatehtävä
Työryhmä
Kuva 3 Resurssien ja tehtäväsuunnittelun yksiköiden väliset suhteet
2.4 Aikataulujen esitysmuotoja
Rakennushankkeen aikataulusuunnittelun tulosten esitysmuotoja ovat jana-aikakaavio, toimintaverkko, tuotantoaikakaavio ja paikka-aikakaavio. Niiden ominaisuudet ovat erilaisia eli niillä on omat hyvät ja huonot puolensa. Nykyään käytetään paljon paikka- aikakaaviota ja sitä käytetään myös Controlissa, joten se on valittu esitysmuodoksi myös tähän työhön. Paikka-aikakaaviossa on pystyakselilla tehtävien suorituspaikat, jotka ovat yleensä rakennuksen fyysisiä osia kuten kerroksia ja vaaka-akselilla aika. Tehtäviä kuvataan vinoviivoilla, jotka piirretään kaavioon kuvaamaan tehtävän suunniteltua suoritusajankohtaa ja paikkaa. Paikka-aikakaaviosta selviää helposti tehtävien tuotantonopeus, jonka näkee viivojen kaltevuudesta ja tehtävien suoritusjärjestys eri paikoissa. [5]
ii iiim n пн n n i и
ТПТТТ III IMI TTTTTT III IMI
Kuva 4 Paikka-aikakaaviossa tehtävät esitetään vinoviivoina, jotka peittävät osan sekä vaaka- että pystyakselilta. Nämä osat kuvaavat tiettyjen paikkojen suoritusta pystyakselilla tiettynä ajankohtana vaaka-akselilla.
Esimerkki paikka-aikakaaviosta on kuvassa 4. Siinä on pystyakselilla paikkahierarkia ja vaaka-akselilla aika. Tehtävät kuvataan vinoviivoina, jotka ilmaisevat missä
järjestyksessä paikat suoritetaan ja milloin.
2.5 Riippuvuudet
2.5.1 Riippuvuustyypit
Rakennushankkeessa tehtävien suoritus riippuu usein toisista tehtävistä. Tehtäville on tiettyjä järjestyksiä, joissa ne on suoritettava. Esimerkiksi tietty tehtävä voidaan aloittaa paikassa vasta, kun jokin toinen tehtävä on jo saatu valmiiksi samassa paikassa.
Riippuvuudet voivat johtua erilaisista syistä:
• Luonnolliset riippuvuudet ovat ehdottomia riippuvuuksia, jotka kuvaavat teknisesti mahdollista suoritusjärjestystä (esim. edellisen kerroksen katto on saatava valmiiksi ennen kuin aloitetaan seuraavan kerroksen rakentamista).
• Olosuhderiippuvuudet aiheutuvat olosuhteista, joita voi olla erilaiset sopimukset, sääolosuhteet ja työmaajärjestelyt (esim. katon täytyy olla vesitiivis ennen väliseinälevyjen asentamista, jotta levyt eivät kastuisi sateella).
• Tekniset riippuvuudet johtuvat tekniikasta, jota on käytetty tehtävän toteutuksessa (esim. laudoitus on oltava lähes valmis ennen raudoitusta).
e Resurssiriippuvuudella tarkoitetaan, että erilaisten resurssien kuten työvoiman tai erilaisten koneiden käyttö riippuu niiden aikaisemmasta käytöstä. Jos resurssi on edelleen edellisen tehtävän käytössä, seuraavaa tehtävää ei voida aloittaa, koska resurssi ei ole vapaana.
Rakennushankkeen riippuvuudet ovat yleensä tyypiltään ns. loppu-alkuriippuvuuksia.
Tällöin edeltävä tehtävä on saatava loppuun paikassa ennen seuraavan tehtävän aloittamista ko. paikassa. Alku-alkuriippuvuudessa edeltävän tehtävän paikka on oltava aloitettu ennen seuraavan tehtävän aloittamista ko. paikassa. Loppu-loppuriippuvuudessa taas edeltävän tehtävän paikka on saatava loppuun ennen kuin seuraavan tehtävän suoritus ko. paikassa voidaan lopettaa. Alku-loppuriippuvuus tarkoittaa taas, että edeltävä
tehtävä on aloitettava paikassa ennen kuin seuraavan tehtävän suoritus ko. paikassa voidaan lopettaa. [4]
2.5.2 Riippuvuuksien käyttö
Riippuvuuksia asetetaan sekä osatehtävien että osakohdetehtävien välille.
Osatehtäväriippuvuudet asetetaan osatehtävien välille ja ne sisältävät mm. seuraavia tietoja:
• Riippuvuuden tyyppi
• Viive
• Puskuriviive
• Tarkkuustaso
• Osakohdetehtäväriippuvuudet
Osakohdetehtäväriippuvuudet sisältävät:
• Edeltävä osakohdetehtävä
• Seuraava osakohdetehtävä
Osatehtäväriippuvuuden tyyppi kertoo miten edeltävän ja seuraavan osatehtävän aloituksen ja lopetuksen täytyy suhtautua toisiinsa. Viive viivyttää seuraavan osatehtävän aloittamista/lopettamista viiveen suuruuden mukaan. Puskuriviive on taas käyttäjän määräämä viive, jonka tarkoitus on pienentää osatehtävän mahdollisen myöhästymisen vaikutuksia muihin tehtäviin. Se kuvaa kuinka paljon edeltävän osatehtävän aloittaminen/lopettaminen voisi viivästyä, ettei se vaikuttaisi seuraajan aloittamiseen/lopettamiseen. Suunnitelmassa puskuriviive toteutuu, mutta käytännössä sen ei tarvitse toteutua. Normaalin viiveen on kuitenkin toteuduttava aina.
Osatehtäväriippuvuudet sisältävät osakohdetehtäväriippuvuudet, jotka ilmaisevat osatehtäväriippuvuuden osatehtävien eri osakohdetehtävien suoritusjärjestyksen toisiinsa nähden. Jos riippuvuuden molemmat osakohdetehtävät kuuluvat samaan osatehtävään, riippuvuus on ns. sisäinen riippuvuus. Jos taas osakohdetehtävät kuuluvat eri osatehtäville, on kyseessä ns. ulkoinen riippuvuus. Sisäisillä riippuvuuksilla määräytyy
osatehtävän sisäisten osakohteiden suoritusjärjestys. Ulkoisilla riippuvuuksilla määräytyvät tehtävien ja osatehtävien väliset suoritusjärjestykset.
Osatehtäväriippuvuuksia voidaan määritellä eri tarkkuustasoille, jotka määräävät miten tehtävien osatehtävät ajoitetaan. Jos esimerkiksi projektissa on 3 tarkkuustasoa (1, 2 ja 3), 4 tehtävää (Tl, T2, T3 ja T4) ja kullakin tehtävällä yksi osatehtävä, voidaan määritellä tason 1 osatehtäväriippuvuus välille Tl, T2, tason 2 osatehtäväriippuvuudet välille T2, T3 ja tason 3 osatehtäväriippuvuudet välille T3, T4. Osatehtäväriippuvuudet ovat tässä tapauksessa loppu-alkuriippuvuuksia. Tehtävien ajoitus eri tason osakohdetehtäväriippuvuuksilla näkyy kuvassa 5.
Su Iluto iTu IWe № I Fr ÍSÍ~
Su IMo ITU iTh 1 Fr ISa Isu Iluto ITu~
Su IMo ITU Th IFr [S3
Kuva 5 Tehtävien ajoitus eri tarkkuustason ulkoisilla loppu-alkuriippuvuuksilla. Tehtävien 1 ja 2 välillä on 1. tason osatehtäväriippuvuus ja kolmen päivän viive. Tehtävien 2 ja 3 välillä on 2. tason osatehtäväriippuvuus ilman viivettä. Tehtävien 3 ja 4 välillä on 3. tason osatehtäväriippuvuus yhden päivän viiveellä. Osakohdetehtäväriippuvuudet on kuvattu punaisilla nuolilla.
Kuvassa 6 näkyy tehtävien ajoitus eri tyyppisillä riippuvuuksilla. Osatehtävien välinen ajoitus määräytyy tehtävien ulkoisten riippuvuuksien suhteen osakohdetehtävien välillä.
Kaikkien tehtävien sisäiset osakohdejärjestykset ovat samoja. Osatehtävien 1 ja 2 välillä on vain yksi osakohdetehtäväriippuvuus T1:C3 -> T2:A1, joka määrää, että tehtävä 2 voidaan suorittaa, kun tehtävä 1 on suoritettu tasolla 1 loppuun. Tehtävien 2 ja 3 välillä on 3 riippuvuutta T2:A3 -> T3:A1, T2:B3 -> T3:B1, T2:C3 -> T3:C1. Ne määräävät, että tehtävä 3:n suoritus tason 2 paikassa voidaan aloittaa aikaisintaan, kun tehtävän 2 suoritus tason 2 ko. paikassa on loppunut. Tehtävien 3 ja 4 välillä on riippuvuudet T3:A1 -> T4:A1, T3:A2 -> T4:A2, T3:A3 -> T4:A3, T3:B1 -> T4:B1, T3:B2 -> T4:B2, T3:B3 -
> T4:B3, T3:C1 -> T4:C1, T3:C2 -> T4:C2, T3:C3 -> T4:C3. Ne määräävät, että tehtävän 4 suorituksen tasolla 3 voi aloittaa aikaisintaan, kun tehtävän 3 suoritus on loppunut ko.
tason 3 paikassa.
Kuva 6 Tehtävien ajoitus eri tyyppisillä osatehtäväriippuvuuksilla. Tehtävien 1 ja 2 välillä on tason 2 loppu-alkuriippuvuus, jolloin tehtävän 1 paikkojen suorituksen on loputtava ennen kuin tehtävän 2 suoritus samoissa paikoissa voi alkaa. Tehtävien 2 ja 3 välillä on tason 2 alku-alku riippuvuus yhden päivän viiveellä, jolloin tehtävän 2 suoritus paikoissa on oltava alkanut ennen kuin tehtävän 3
suoritusta samoissa paikoissa voidaan aloittaa kun myös viive on otettuhuomioon. Tehtävien 3 ja 4 välillä on tason 2 loppu-loppuriippuvuus kahden päivän viiveellä, jolloin tehtävän 2 suoritus paikoissa on oltava lopetettu ennen kuin tehtävän 4 suoritus samoissa paikoissa voidaan lopettaa viive huomioonottaen. Tehtävien 4 ja 5 välillä on tason 2 alku-loppuriippuvuus, jolloin tehtävän 4 suorituksen on oltava alkanut paikoissa ennen kuin tehtävän 5 suoritus paikoissa voidaan lopettaa.
Punaiset ja siniset nuolet kuvaavat riippuvuuksia.
Riippuvuuksien asettamisessa täytyy aina tarkistaa, ettei synny ns. kehäriippuvuuksia.
Niillä tarkoitetaan tilannetta, jossa kahden osakohdetehtävän pitäisi olla yhtäaikaa 2 eri järjestyksessä. Esimerkiksi jos tehtävillä Tl, T2 ja T3 on loppu-alkuriippuvuudet Tl ->
T2 ja T2 -> T3, riippuvuuden T3 -> Tl lisääminen aiheuttaa kehäriippuvuuden eikä sitä voida lisätä. Tehtävää T3 ei voida suorittaa tehtävän T2 ja siten myös tehtävän Tl jälkeen, jos vaaditaan myös T3:n suoritus ennen tehtävää Tl.
2.6 Osatehtävien ajoitus
Osatehtävät pyritään ajoittamaan aina niihin talletetun halutun aloitusajan mukaan.
Tämän voivat kuitenkin estää erilaiset riippuvuudet, resurssirajoitukset, osatehtävien ajoitus aikaisimmaksi mahdolliseksi ja osatehtävien rytmitys. Jos osatehtävien ja osakohdetehtävien välillä on riippuvuuksia, niiden suoritusjärjestys määräytyy riippuvuuksien mukaan. Jos resurssityypeille on asetettu käyttörajoituksia, osatehtävien yhtäaikainen suoritus voi tulla mahdottomaksi, jolloin tiettyjä osatehtäviä voidaan joutua siirtämään suoritettavaksi myöhempänä ajankohtana, kun resursseja on vapaana riittävästi. Osatehtävän aikaisin mahdollinen suoritus siirtää osatehtävän suoritettavaksi niin aikaisin kuin muut rajoitukset sallivat. Jos muita rajoitteita ei ole, osatehtävän suoritus voidaan aloittaa projektin aloitushetkenä.
Osatehtävän rytmitys määrää osatehtävän suoritettavaksi jatkuvasti. Silloin osatehtävän suorituksessa ei ole katkoja. Rytmitys tehdään rytmitettävän osatehtävän osakohdetehtävien aloitusaikoja muuttamalla. Osatehtävän osakohdetehtävät käydään läpi osatehtävän riippuvuusjärjestyksessä. Jokaista osakohdetehtävää siirretään yksi kerrallaan eteenpäin halutusta aloitusajasta niin paljon kuin sen edeltäjät vaativat. Jos kyseessä on osatehtävän ensimmäinen osakohdetehtävä, sille etsitään paikka, jossa on
tilaa koko osatehtävän osakohdetehtävien yhteenlasketun keston verran, jotta osatehtävän jatkuva suoritus olisi mahdollinen. Sopivaa paikkaa etsittäessä täytyy ottaa huomioon myös resurssityyppien käyttörajoitukset riippuvuuksien lisäksi. Kun osatehtävän ensimmäiselle osakohdetehtävälle on löydetty paikka, käydään läpi osatehtävän seuraavat osakohdetehtävät ja etsitään niille aikaisin mahdollinen ajoitus edellisen osakohdetehtävän loppuhetkestä lähtien. Kun ajoitus on löydetty, tarkistetaan, että osatehtävän aikaisempien osakohdetehtävien ajoitus on jatkuva. Jos ajoitukset eivät ole jatkuvia, siirretään aikaisempia osakohdetehtäviä eteenpäin niin paljon, että osakohdetehtävien suoritus tapahtuu jatkuvasti. Jos osatehtävän osakohdetehtävien jatkuva suoritus pakottaisi osatehtävän niin paljon myöhemmäksi, ettei koko osatehtävän jatkuva suoritus ole enää mahdollista, joudutaan etsimään koko osatehtävälle uusi väli
myöhemmästä ajankohdasta ja ajoittamaan osatehtävän osakohdetehtävät uudestaan.
Esimerkkinä ajoituksen laskennasta kuvassa 7 on 4 tehtävää, joista 3 ensimmäistä käyttää resurssityyppinään rakennusmiestä ja 1 työmiestä. Resurssityypeillä on sama toimittaja ja niiden maksimikäyttö on 1. Lisäksi tehtävät ovat riippuvia toisistaan, jolloin niille määräytyy kuvan mukainen suoritusjärjestys. Tehtävä 5 on asetettu rytmitetyksi ja aikaisimmaksi mahdolliseksi, ja se täytyy suorittaa tehtävän 2 jälkeen. Lisäksi tehtävä 5 käyttää resurssinaan rakennusmiestä, jonka maksimikäyttö on 1.
Kuva 7 Ajoitusesimerkissä on 4 toisistaan riippuvaa tehtävää, joilla on käytössä resurssit rakennusmies ja työmies samalta toimittajalta. Rakennusmiehen käyttörajoitus on 1. Yläpuolella oleva näkymä on paikka-aikakaavio, alapuolella oleva on resurssikuvaaja, jossa näkyy resurssien käyttö ajan funktiona.
Tehtävälle 5 etsitään ajoitusta etsimällä ensin koko osatehtävän osakohdetehtävien yhteenlasketun keston pituista aikaväliä lähtien tehtävän 2 lopetushetkestä eli riippuvuuksien määräämästä aikaisimmasta ajankohdasta. Tehtävien 2 ja 3 välissä olisi tilaa vain 10 päivää, mikä riittäisi ainoastaan osalle tehtävän 5 osakohdetehtävistä.
Tehtävän 5 täytyy olla jatkuva, joten sille täytyy etsiä seuraava ajankohta, jossa olisi tilaa koko osatehtävälle. Tehtävän 3 suorituksen loputtua löytyy seuraava sopiva ajankohta, koska silloin rakennusmiehen käyttö loppuu ja rakennusmiestä ei olla käyttämässä sen jälkeen. Tehtävän 4 suorituksella ei ole merkitystä, koska se käyttää eri resurssia kuin tehtävä 5. Tehtävä 5 voidaan siis sijoittaa alkavaksi jatkuvasti heti tehtävän 3 jälkeen.
Lopputilanne näkyy kuvassa 8.
Kuva 8 Ajoitusesimerkin lopputilanne, jossa tehtävälle 5 on löydetty rytmitetty ajoitus heti tehtävän 3 suorituksen loputtua. Ylläoleva näkymä on paikka-aikakaavio ja allaoleva resurssikuvaaja.
2 .7 Kustannukset
Kustannuksia syntyy erilaisten resurssien käytöstä. Kustannus on yleensä verrannollinen resurssin käyttöaikaan, mutta myös resurssien seisottaminen työmaalla työvaiheiden välissä tai erilaisten häiriöiden takia voi tuoda kustannuksia. Tällaisia resursseja ovat esim. työvoima ja myös jotkin koneet laitevuokran takia. Häiriöitä voivat aiheuttaa esim.
muiden tehtävien myöhästyminen, jolloin voidaan joutua odottamaan muiden tehtävien suoritusta riippuvuuksien takia.
Resurssit on usein sidottu tiettyihin aikataulutehtävien osatehtäviin, jolloin ne ovat käytössä osatehtävän suorituksen aikana. Resurssit voivat vaatia mobilisointia eli niitä voidaan joutua kuljettamaan työmaalle ja takaisin, mikä aiheuttaa myös kustannuksia.
Resurssit voivat myös olla sidottuja ns. työmaateknisiin tehtäviin, joiden suoritus voi kestää esim. koko projektin ajan. Työmaateknisiä tehtäviä voivat olla esim. työmaahan liittyvät yleiset tehtävät kuten työmaan palvelut.
Projektin kokonaiskustannukset koostuvat erilaisten kustannustyyppien kustannusten summana. Controlissa erilaisia kustannustyyppejä ovat
• Työkustannukset
• Odotuskustannukset
• Mobilisointikustannukset e Työmaatekniset kustannukset
Työkustannukset lasketaan resurssien käyttöajan perusteella. Osatehtävän i työkustannus c,w saadaan sen kestosta ja sen työryhmien resurssityyppien käyttökustannuksista:
H
jossa n"g on työryhmien lukumäärä osatehtävässä i, t¡” osatehtävän i kesto, c"
resurssityypin j käyttökustannus ja n" resurssityypin j lukumäärä työryhmässä.
Odotuskustannusten laskemiseksi osatehtävässä on ensin laskettava jokaisen osatehtävän työryhmän resurssityypin odotusaika. Odotusaika on tehtävän suorituksen väliset tauot yhteenlaskettuna. Jos resurssityyppi on kuitenkin määrätty lähtemään työmaalta taukojen ajaksi, odotusaika on nolla. Osatehtävän i odotuskustannuksiksi c(wo" saadaan
cr"
=«;gX(«ca"),
jossa n”g on työryhmien lukumäärä osatehtävässä i, cr] resurssityypin j käyttökustannus, nr¡ resurssityypin j lukumäärä työryhmässä, /"wo" resurssityypin j odotusaika ja n osatehtävän resurssityyppien lukumäärä.
Mobilisointikustannukset aiheutuvat resurssien liikuttelusta eri paikkoihin. Esim.
kaivinkoneen siirtämiskustannukset työmaalle ja takaisin on otettava huomioon.
Mobilisointikustannukset ovat mobilisointi- ja demobilisointikustannusten summa.
Mobilisointi tarkoittaa resurssien siirtämistä tehtävän suorituspaikkaan ja demobilisointi
sieltä takaisin. Jokaisella tehtävällä on oma mobilisointi- ja demobilisointiaikansa.
Osatehtävän i mobilisointikustannuksiksi c"'oh tulee näiden aikojen aiheuttamien resurssien käyttökustannuksien summa:
- nwg ^ mob ^ demob
jossa /f0'1 on osatehtävän i tehtävän mobilisointiaika, tfmoh osatehtävän i tehtävän demobilisointiaika, c" työryhmän resurssityypin j käyttökustannus, n‘ työryhmän resurssityypin j lukumäärä työryhmässä ja n työryhmän resurssityyppien lukumäärä.
Työmaatekniset kustannukset aiheutuvat työmaateknisistä tehtävistä. Työmaatekniset tehtävät ovat työmaahan tai sen paikkoihin liittyviä tehtäviä, jotka suoritetaan tiettyjen niihin liitettyjen tehtävien ajan. Työmaateknisen tehtävän määrärivit sisältävät varsinaiset tehtävän suoritteet. Työmaatekninen tehtävä sisältää seuraavat tiedot:
• Määrärivit
• Aikataulutehtävät
Työmaateknisen tehtävän kustannus clasketaan summana kaikista sen määräriveistä eli c°' = d°‘,
i=i
jossa c“c on työmaateknisen tehtävän määrärivin j yksikkökustannus ja d"‘
työmaateknisen tehtävän kesto, joka on sen aikataulutehtävien yhteenlaskettu kesto päivän tarkkuudella.
Kuvassa 9 on esimerkki kustannustyyppien laskennasta. Projektissa on 2 tehtävää, joiden välillä on loppu-alkuriippuvuus tarkkuustasolla 2 ja viiveellä 5. Tehtävän 1 kesto on 7 päivää ja tehtävän 2 kesto 5 päivää. Tehtävä 2 suoritetaan nopeammin kuin tehtävä 1 kussakin tason 2 paikassa А, В ja C. Tämän takia tehtävän 2 suoritukseen tulee tauko, kun joudutaan odottamaan kunnes tehtävän 1 valmistumisesta kussakin paikassa on kulunut riippuvuuden vaatimat viisi päivää.
Projektin kokonaiskustannuksiksi tulee 2780 euroa. Työkustannuksia tulee 900 euroa.
Tehtävissä käytetyn resurssityypin kustannus on 10 euroa tunti, resurssityypin lukumäärä 1 kummassakin työryhmässä ja työryhmien lukumäärä 1 kummassakin tehtävässä.
Tehtävien kestot muutetaan työtunneiksi, joita on päivässä 7,5. Näistä saadaan työkustannuksiksi 1 * 7 * 7,5 * 10 * 1 + 1 * 5 * 7,5 * 10 * 1 = 900.
Odotuskustannukset saadaan laskemalla resurssityypin odotusaika tehtävän 2 suorituksen aikana. Tauoiksi tulee yhteensä 2 työpäivää, joka muutetaan tunneiksi käyttämällä koko työpäivän yhteenlaskettua työssäoloaikaa eli 8 tuntia. Työryhmien lukumäärä osatehtävässä on yksi ja myös resurssityypin lukumäärä on työryhmässä yksi. Näin saadaan odotuskustannuksiksi 1 * 10*2*8* 1 = 160.
Mobi 1 isaatiokustannukset lasketaan resurssityyppien kuljetusajoista työpaikalle ja takaisin. Tehtävissä käytetään samaa resurssityyppiä, jonka saaminen työpaikalle kestää 2 tuntia ja poistuminen 2 tuntia. Näin mobilisaatiokustannuksiksi saadaan 1 * (2 + 2) * 10 *
1 = 40 euroa.
Työmaatekniset kustannukset tulevat yhdestä työmaateknisestä tehtävästä, jonka tehtävien yhteenlasketuksi kestoksi tulee (5 + 7 + 2) * 24 h = 336 h. Viimeiset kaksi päivää aiheutuvat resurssityypin saapumisesta ja poistumisesta työmaalta.
Työmaateknisen tehtävän määrärivin yksikkökustannus on 5 euroa, joten työmaateknisiksi kustannuksiksi saadaan 336 h * 5 euroa / h = 1680 euroa.
Kuva 9 Kahden tehtävän aikataulu, jonka eri kustannustyypit näkyvät kuvan pienessä ikkunassa.
Tehtävän 2 nopeampi suoritus ja tehtävien välinen tason 2 loppu-alkuriippuvuus 5 päivän viiveellä aiheuttaa katkoja tehtävän 2 suorituksessa. Tehtävän 2 resurssit joutuvat odottamaan
katkokohdissa tehtävän 1 suorituksen lopettamista tasolla 2, mistä aiheutuu odotuskustannuksia.
3 Rakennushankkeen aikataulun optimointiongelma
Rakennushankkeen aikataulu sisältää paljon erilaisia muuttujia ja sen optimointi on vaativa tehtävä. Optimointi voidaan tehdä joko kokeilemalla useita eri aikatauluehdokkaita tai lisäämällä optimointiin älykkyyttä, jolloin päästään yleensä nopeammin kohtuulliseen hyvään ratkaisuun.
3.1 Ongelman kuvaus
Tavoitteena on löytää sopiva ratkaisutapa, joka pystyy optimoimaan aikataulua riittävän tehokkaasti annetuilla lähtötiedoilla ratkaisuavaruudessa. Optimaalisessa aikataulussa kustannukset on minimoitu, niin että kuitenkin aikataulutehtävät tulee tehtyä ennen projektin loppuhetkeä ja resurssityyppien käyttörajoitteita ja riippuvuuksia ei rikota.
Ratkaisutavan pitäisi löytää riittävän hyvä aikataulu kaikilla lähtötiedoilla. Aikataulujen keskinäinen hyvyys tulee esille niiden kokonaiskustannusten kautta. Algoritmi pitää myös säätää mahdollisimman sopivaksi erilaisia algoritmin toimintaan liittyviä parametreja käyttäen. Algoritmi saa käyttää optimointiin tiettyjä toimenpiteitä, joita ovat mm. tehtävien paikkajärjestyksen muuttaminen, tehtävien pilkkominen ja osatehtävien työryhmien lukumäärän muuttaminen. Optimoinnin lähtötietona on projektitiedosto, joka sisältää optimointiongelmaan käyvän ratkaisun, joka ei riko rajoitteita eikä riippuvuuksia.
Ratkaisu ei kuitenkaan ole välttämättä lähellekään optimaalinen. Projektitiedosto sisältää mm. projektin paikkahierarkian, tehtävät, resurssit ja riippuvuudet.
3.2 Optimointikeinot
Optimointikeinot voidaan jakaa kahteen ryhmään. Ensin ovat välittömästi muuttavat keinot ja toiseksi välillisesti muuttavat keinot. Välittömästi muuttavat keinot muuttavat suoraan aikataulun tietoja. Näitä ovat:
1. Osatehtävien osakohdetehtävien alkamisajan muuttaminen aikataulutehtäväriippuvuuksien viivepuskuria muuttamalla
2. Osatehtävien osakohdejärjestyksen muuttaminen 3. Osatehtävän työryhmien lukumäärän muuttaminen 4. Osakohdetehtävien työsaavutuskertoimen muuttaminen
5. Osatehtävien asettaminen aikaisimmaksi mahdolliseksi 6. Osatehtävien asettaminen rytmitetyksi
7. Osatehtävien jakaminen osiin 8. Osatehtävien yhdistäminen
Ensimmäiset 6 näistä vastaavat suoraan osatehtävien sisältäviä tietoja. Osatehtävien jakaminen osiin ja yhdistäminen tarkoittavat kuitenkin suurempia operaatioita.
Osatehtävän jakamisessa osiin kumpikin uusi osatehtävä saa osansa osatehtävän osakohdetehtävistä. Yhdistämisessä kahden osatehtävän osakohdetehtävät siirretään uudelle osatehtävälle. Lisäksi molemmissa operaatioissa muuttuvat mm. osatehtävien aloitusaika, kestoja resurssien käyttö.
Välilliset keinot taas on tarkoitettu vaikuttamaan arvoihin välillisesti eli niiden vaikutus riippuu kulloisestakin vallitsevasta tilanteesta optimoinnin aikana. Niitä ovat:
• Oletuspaikkajärjestyksen käyttö
• Osatehtävien osakohdejärjestyksen laskeminen edeltäjäriippuvuuksista
• Osatehtävän työryhmien laskenta edeltäjäriippuvuuksista eli tahdistus
• Yksilön alustaminen älykkäästi
Oletuspaikkajärjestys tarkoittaa aikataulukohtaista yleisempää järjestystä, jota useammat osatehtävät voivat käyttää. Oletusjärjestys määrätään jokaiselle projektin osakohdetehtävälle ja sitä voidaan soveltaa myös osatehtäviin, jotka eivät sisällä kaikkia projektin osakohteita. Oletusjärjestyksellä saadaan sitä noudattavat samat osakohteet sisältävät tehtävät samaan järjestykseen. Se on usein järkevää, koska tehtävien suoritus usein riippuu toisistaan ja useiden tehtävien suoritus eri järjestyksissä todennäköisesti vain pidentää aikataulua. Esimerkkinä kuvassa 10 nähdään kolmen eri osakohdejärjestyksissä olevan tehtävän suoritusaikataulu. Tehtävien 1 ja 2 välillä on tason 2 loppu-alkuriippuvuus ja tehtävien 2 ja 3 välillä tason 3 loppu-alkuriippuvuus.
Tehtävät tulee suoritettua 21 päivässä. Kuvassa 11 on samat tehtävät, mutta suoritusjärjestys on sama. Suoritukseen kuluu huomattavasti vähemmän aikaa eli 16 päivää.
Kuva 10 3 tehtävää eri osakohdejärjestyksissä, jolloin suoritukseen kuluu aikaa 21 päivää.
Kuva 11 3 tehtävää samassa osakohdejärjestyksessä, jolloin aikaa kuluu vain 16 päivää.
Jos tehtävällä on edeltäjäriippuvuuksia, joissa tehtävä on seuraajana, voidaan paikkajärjestys laskea paikkakohtaisesti aikaisimmaksi mahdolliseksi edeltäjätehtävistä laskettuna. Tällöin käydään läpi kaikki osatehtävän osakohteiden edeltäjäriippuvuudet ja lasketaan niistä aikaisin mahdollinen aloitushetki jokaiselle osakohdetehtävälle. Jokainen näistä riippuvuuksista määrää aikaisimman mahdollisen aloitushetken osakohdetehtäväl le tietyssä paikassa. Näistä aloitusajoista valitaan kullekin osakohdetehtäväl le myöhäisin, jolloin yhtäkään osakohdetehtävän riippuvuutta ei rikota. Tämän jälkeen osakohdetehtäväl järjestetään saatujen aloitusaikojen mukaan järjestykseen, jolloin saadaan aikaisin mahdollinen osakohdejärjestys. Aikaisimmalla mahdollisella osakohdej ärj esty ksel lä päästään monissa tapauksissa nopeimpaan mahdolliseen osatehtävien suoritukseen.
Kuva 12 Tehtävälle 3 on laskettu osakohdejärjestys edeltäjäriippuvuuksista.
Osakohderiippuvuudet näkyvät sinisinä nuolina.
Kuvassa 12 on laskettu osatehtävän 3 osakohdejärjestys osatehtävistä 1 ja 2. Tehtävien välillä on loppu-alku osakohdetehtäväriippuvuudet Tl:A -> T3:C ja T2:A -> T3:B.
Tehtävän 3 osakohteiden aikaisimmat aloitusajat saadaan tehtävän riippuvuuksista.
Osakohteen A suoritukselle ei ole riippuvuusrajoituksia, joten sen suoritus voi alkaa periaatteessa jo projektin alkuhetkellä. Osakohteen В suoritus voi alkaa aikaisintaan 18.6 ja osakohteen C suoritus voi alkaa aikaisintaan 10.6. Osakohteille saadaan siis suoritusjärjestys А, C, B. Järjestys antaa enemmän pelivaraa edeltävien osakohteiden suoritukselle.
Osatehtävän työryhmien laskenta edeltäjänippuvuuksista tarkoittaa, että osatehtävän työryhmien lukumäärä säädetään niin, että osatehtävän tehtävän kesto on mahdollisimman lähellä, mutta kuitenkin suurempi kuin sen osatehtävän edeltäjäriippuvuuksia vastaavien edeltäjätehtävien keskimääräinen kesto. Sopiva osatehtävän työryhmien lukumäärä löydetään kasvattamalla sitä lähtien arvosta 1, jolloin osatehtävän ja sen tehtävän kesto lyhenee. Tavoitteena on saada tehtävien kesto yhtä suureksi. Näin rakennusajan käyttö saadaan tehokkaammaksi ja tehtäviä ohjattavammiksi. Tehtävien keston tasaamista työryhmien lukumäärää muuttamalla kutsutaan tahdistukseksi. [6]
Aikataulun alustaminen älykkäästi vaikuttaa aikatauluun sekä suoraan että välillisesti.
Älykkäässä alustuksessa aikataulun kokonaiskesto minimoidaan säätämällä resursseja eli kasvattamalla työryhmien lukumäärää, jolloin osatehtävän kesto lyhenee. Osatehtävät järjestetään kestonsa mukaan järjestykseen ja kasvatetaan yksitellen kunkin osatehtävän työryhmien lukumäärää yhdellä lähtien pisimmästä osatehtävästä ja siirtyen aina seuraavaksi pisimpään. Osatehtäviä käydään läpi niin kauan kuin yhdenkin osatehtävän työryhmien lukumäärän nosto lyhentää aikataulun kokonaiskestoa tai kunnes osatehtävän suurin mahdollinen työryhmien lukumäärä saavutetaan. Näin päästään mahdollisimman nopeaan aikatauluun, jossa erityisesti aikataulun kokonaiskestoon vaikuttavat osatehtävät on saatu optimoitua nopeammiksi. Älykkäässä alustuksessa asetetaan myös suoraan arvoja aikataululle. Tehtävien riippuvuuspuskuriviive asetetaan nollaksi, ja osatehtävät asetetaan rytmitetyiksi ja ajoitetuiksi niin aikaisin kuin mahdollista. Myös työsaavutuskertoimet asetetaan ykkösiksi ja osatehtäviä ei aseteta leikattaviksi tai yhdisteltäviksi. Myös näillä toimenpiteillä pyritään lyhentämään aikataulun
kokonaiskestoa ja sitä kautta myös pienentämään kustannuksia. Yksinkertaisemmissa projekteissa älykkään alustuksen pitäisi päästä lähelle optimia tai peräti optimiin.
Suuremmissa projekteissa älykäs alustus ei todennäköisesti pääse lähelle optimia, mutta tarjoaa todennäköisesti paremman lähtökohdan optimoinnille.
3.3 Rajoitukset
Optimointiongelman rajoitteita ovat
• Osatehtävien työryhmien maksimilukumäärät
• Resurssityyppien käyttörajoitus
• Optimoitava hierarkiataso
• Lukitut hierarkiatasot
Optimointi ei saa ylittää missään vaiheessa minkään tehtävän työryhmien maksimilukumäärää tehtävän osatehtävissä. Myöskään resurssien käyttörajoituksista laskettavaa suurinta työryhmien lukumäärää osatehtävälle ei saa ylittää optimoinnissa.
Optimoitava hierarkitaso on taso, jonka paikkajärjestystä optimoinnissa pääasiassa vaihdellaan. Muiden hierarkiatasojen paikkajärjestyksiä ei ensisijaisesti lähdetä optimoimaan. Optimoitava hierarkiataso valitaan aikataululle ennen optimoinnin alkua.
Lukitut hierarkiatasot kuitenkin rajoittavat tai estävät optimoitavan hierarkiatason käytön.
Hierarkiatasojen lukitus on tehtäväkohtainen ja tarkoittaa, että lukitun hierarkiatason paikkojen osakohdetehtävät lukitaan projektin osakohdejärjestykseen, jolloin optimointi ei voi muuttaa niitä. Muiden hierarkiatasojen paikkojen järjestyksien muuttaminen on kuitenkin sallittua. Kuvassa 13 nähdään miten eri hierarkiatasojen lukitus vaikuttaa tehtävän mahdolliseen osakohdejärjestykseen. Tehtävän 1 hierarkiatasoja ei ole lukittu, joten sen järjestys voi olla mikä tahansa. Tehtävän 2 hierarkiataso 2 on lukittu, mikä pakottaa sen osakohdetehtävät järjestettäviksi projektin alkuperäiseen osakohdejärjestykseen tason 2 suhteen. Tällöin tehtävästä suoritetaan ensin paikan A osakohdetehtävät, sitten B:n ja C:n. Tason 2 paikkojen sisäiset osakohdetehtävät järjestetään niiden alkuperäiseen keskinäiseen järjestykseen tehtävässä. Tehtävän 3 hierarkiataso 3 on lukittu, jolloin tason 3 paikkojen osakohdetehtävät pakotetaan
projektin alkuperäiseen osakohdejärjestykseen 1, 2, 3. Osakohdejärjestykset voivat kuitenkin vaihdella tason 2 suhteen.
in |Ke Ilo IP« iLa |Su \Ш Щ |Ке |To |Pe Цл Su |Mi |T1 |Ke |To |Pe iLa Su iMi IT. IKe Ito |Pe ILa JSu \НЬ Щ |Ke Цо |P«
Kuva 13 3 tehtävää, joissa on esitetty yksi mahdollinen paikkajärjestys, kun eri hierarkiatasot ovat tehtävissä lukittuna. Tehtävässä 1 paikkajärjestystä ei ole lukittu, joten järjestys voi olla mikä vaan.
Tehtävässä 2 taso 2 on lukittu, jolloin tason 2 paikkojen А, В ja C osakohdetehtävät järjestetään paikkahierarkian mukaiseen järjestykseen А, В, C. Tehtävässä 3 taso 3 on lukittu, jolloin tason 3 paikkojen 1,2 ja 3 osakohdetehtävät on järjestetty paikkahierarkian mukaiseen järjestykseen 1, 2,3.
Resurssityyppien käyttörajoitus taas asettaa resurssityypin yhtäaikaiselle käytölle ylärajan. Tällöin tehtävät täytyy ajoittaa niin, ettei niiden käyttämien resurssityyppien käyttö kasva millään ajanhetkellä suuremmaksi kuin resurssityypin sallittu maksimikäyttö.
4 Ongelman ratkaisualgoritmi
4.1 Sopivan ratkaisutavan valinta
Luvussa 3 määritellyssä optimointiongelmassa on todella suuri määrä erilaisia ratkaisuvaihtoehtoja. Niiden kaikkien kokeileminen ei tule kyseeseen, koska siihen menisi aivan liikaa aikaa. Normaalissa rakennushankkeessa on tehtäviä, paikkoja ja resurssityyppejä suuri määrä ja sen takia myös ratkaisuavaruuden koko on todella suuri.
Esimerkiksi Kampin keskuksen rakennusprojekti koostui 250:stä tehtävästä. [2] Tämän takia joudutaan käyttämään etsintäalgoritmia ratkaisun löytämiseksi.
Erilaiset etsintäalgoritmit jaetaan laskenta-algoritmeihin, numeerisiin algoritmeihin ja satunnaisuuteen perustuviin algoritmeihin. Laskenta-algoritmit voivat olla suoria tai epäsuoria menetelmiä. Epäsuorissa menetelmissä etsitään funktion ääriarvoja asettamalla funktion gradientti nollaksi. Suorissa menetelmissä etsitään ääriarvoja kulkemalla mahdollisesti moniulotteisen funktion pinnalla aina gradientin suuntaan. Numeerisilla algoritmeilla tarkoitetaan ihmisen toimintaan perustuvia algoritmeja, joissa etsitään ääriarvoja kokeilemalla kaikkia mahdollisia arvoja yksi kerrallaan. Satunnaisuuteen perustuvat algoritmit etsivät ratkaisuja avaruudesta satunnaisuuden avulla. [3]
Tässä tapauksessa laskenta-algoritmit eivät käy, koska ongelmasta ei ole saatavilla minkäänlaista derivoitavaa lauseketta, jota hyvyysfunktio noudattaisi eri lähtöarvoilla.
Gradienttia ei siis voida laskea. Numeeriset algoritmit vievät taas aivan liikaa aikaa.
Kaikkien vaihtoehtojen kokeileminen on mahdotonta, kun ratkaisumahdollisuuksia on vähänkin enemmän. Tässä tapauksessa jo tehtävien paikkojen mahdollisten kombinaatioiden lukumääräksi tulee sadalla kymmenpaikkaisella tehtävällä (lOi)'00, joka on aivan liian suuri määrä tapauksia käytäväksi yksitellen läpi. Sen sijaan satunnaisuuteen perustuvaa algoritmia voidaan käyttää. Kaikkia vaihtoehtoja ei voida eikä tarvitse käydä läpi, vaan jo kokeilemalla osaa ratkaisuista, voidaan löytää riittävän hyvä ratkaisu vertailemalla ja yhdistelemällä ratkaisuja toisiinsa. Optimaalista ratkaisua on hankala löytää, koska ratkaisuavaruuden epämääräisyyden ja suuruuden takia ei voida
yleensä tietää täysin varmasti onko ratkaisu optimaalinen ellei ole käyty kaikkia ratkaisuja läpi. Optimaalista ratkaisua ei kuitenkaan välttämättä tarvitse löytää, vaan riittävän hyvä ratkaisu riittää.
Satunnaisia algoritmeja ovat esim. geneettiset algoritmit, Monte Carlo-menetelmä jne.
Tässä työssä ratkaisualgoritmiksi valitaan geneettiset algoritmit, koska ne ovat toimineet tehokkaasti monissa vastaavissa ongelmissa myös esim. aikataulujen optimointitehtävissä. [7] Geneettiset algoritmit sopivat hyvin ongelmiin, joissa
• etsintäalue on suuri
• se on epätasainen eikä koostu esim. vain yhdestä kukkulasta
• siitä ei ole paljon tietoa
• fitness-funktio on häiriöinen tai
• jos optimaalista ratkaisua ei ole välttämätöntä löytää, vaan riittävän hyvä ratkaisu riittää
Tässä ongelmassa etsintäalue eli erilaisten aikatauIuvaihtoehtojen lukumäärä on hyvin suuri. Erilaisten aikatau 1 uvaihtoehtojen kustannuksista ei ole etukäteen tietoa, joten ei voida sanoa kovin paljoa etsintäalueen tasaisuudesta. Etsintäalueen muoto riippuu aika paljon aikataulun monimutkaisuudesta. Yksinkertaisen aikataulun etsintäalue voi olla aika yksinkertaisenkin muotoinen, esim. vain yksi kukkula tms. Todelliset rakennusaikataulut ovat kuitenkin yleensä niin suuria ja monimutkaisia, että etsintäalue on usein hyvin epätasainen, jolloin hyviä lähellä optimia olevia erilaisia ratkaisuja voi löytyä hyvinkin monia. Optimaalista ratkaisua ei ole välttämätöntä löytää kunhan löydetään ratkaisu, joka on hyvyydeltään riittävän lähellä optimia. Näiden syiden takia ongelmaan voidaan hyvin käyttää geneettisiä algoritmeja. [7]
4.2 Geneettiset algoritmit
Geneettiset algoritmit ovat satunnaisuuteen perustuvia algoritmeja, jotka perustuvat idealtaan luonnossa havaittuun muunteluun eläinlajien sisällä. Geneettisissä algoritmeissa ratkaisut ovat yksilöitä, jotka tuottavat jälkeläisiä ja joita verrataan toisiinsa tietyn hyvyysfunktion avulla. Yksilöt koodataan eli muunnetaan alkuperäisestä ongelmasta
geneettiselle algoritmille sopivaan muotoon. Parhaimmat yksilöt valitaan jokaisesta sukupolvesta jollain tietyllä valintamenetelmällä ja nämä yksilöt tuottavat uuden sukupolven yksilöitä, joista taas valitaan osa seuraavaa sukupolvea varten. Yksilöiden perimä kuvaa yksilön edustaman ratkaisun määrittäviä tietoja. Perimä vastaa luonnon kromosomeja, jotka sisältävät yksilön geenit eli rakennusohjeet. Uusien yksilöiden perimä otetaan vanhempien perimästä tiettyä risteytysmenetelmää käyttäen. Näin voidaan yhdistellä osaratkaisuja ja saada parempia kokonaisratkaisuja. Yksilöihin kohdistetaan myös satunnaisia mutaatioita, jotka tuovat perimään jonkin satunnaisen muutoksen.
Tavoitteena on yhä paremman yksilön löytäminen, kun algoritmia toistetaan useiden sukupolvien ajan. Geneettisten algoritmien teorian kehitti John Holland vuonna 1975. [3]
Algoritmi toimii seuraavanlaisena silmukkana:
1. Alkupopulaation luonti
2. Yksilöiden hyvyyden laskeminen
3. Yksilöiden valinta uutta sukupolvea varten
4. Valittujen yksilöiden perimien risteytys uusia yksilöitä varten 5. Mutaatiot uusille yksilöille
6. Uusien yksilöiden sijoitus alkuperäiseen populaatioon
7. Paluu kohtaan 2. kunnes on toistettu riittävän monta sukupolvea
Ensin luodaan alkupopulaatio eli yksilöt, joista algoritmi lähtee muokkaamaan parempia ratkaisuja. Seuraavaksi määritetään yksilöiden välinen hyvyys mahdollisen ns. fitness- funktion avulla, jolloin yksilöt saadaan paremmuusjärjestykseen. Fitness-funktio kertoo tietyn yksilön hyvyyden, jolloin yksilöitä voidaan verrata toisiinsa. Yksilöiden joukosta valitaan sitten potentiaalisimpia yksilöitä jollain tietyllä valintamenetelmällä. Valitut yksilöt risteytetään keskenään pareittain ja uudet yksilöt saavat risteytyksen tuloksena perimän, joka on yhdistelmä kummankin vanhemman perimästä. Näille uusille yksilöille tehdään vielä mahdolliset mutaatiot johonkin satunnaiseen kohtaan perimää. Tämän jälkeen uudet yksilöt sijoitetaan takaisin alkuperäiseen populaatioon jollakin sijoitusmenetelmällä. Tällöin uudet yksilöt voivat esim. korvata vanhempansa tai ne voidaan sijoittaa täysin satunnaisesti joidenkin toisten yksilöiden tilalle tai ne voidaan
ainoastaan lisätä populaatioon, jonka koko silloin kasvaa. Silmukkaa toistetaan niin kauan, että lopetusehto toteutuu. Lopetusehto voi olla esim. jokin tietty sukupolvimäärä tai jonkin tietyn hyvyystason saavuttaminen.
4.3 Koodaus
Koodauksella tarkoitetaan yksilöiden perimän eli ratkaisun muuntamista algoritmin ymmärtämään muotoon. Yksilön perimän geenit on valittava sopiviksi tietyn ominaisuuskokonaisuuden sisältäviksi palasiksi, jotka sisältävät kaikki optimoinnissa tarvittavat tiedot yksilöstä. Perimään kohdistuva risteytys kohdistuu yleensä juuri geenien rajoille eli kokonaiset geenit säilyvät samassa muodossa. Geenin erilaisia mahdollisia arvoja tietyssä geenipaikassa eli ns. lokuksessa kutsutaan alleeleiksi. Yksilön geenit eli alleeliyhdistelmät määrittävät sen genotyypin, kun taas genomin vaikuttamia yksilön havaittavia ominaisuuksia kutsutaan fenotyypiksi. Usein käytetään binäärilukujonoa perimän esittämisessä. Mutta myös kirjain- ja reaalilukujonoja voidaan käyttää. Koska geneettiset algoritmit tarvitsevat paljon laskentatehoa, on koodauksella hyvin suuri merkitys algoritmin toimintaan ja toimintanopeuteen. Tehokkaalla koodauksella genomi saadaan helposti ja nopeasti käsiteltäväksi, jolloin turhia operaatioita ei tarvitse suorittaa.
Usein toistuvien operaatioiden suorituksen täytyy toimia mahdollisimman nopeasti.
Tällaisia ovat esim. valinta, risteytys, mutaatio ja dekoodaus. Dekoodaus on koodauksen käänteinen operaatio, jossa genomin sisältämä ratkaisu muutetaan takaisin todellisen ratkaisun muotoon, niin että ratkaisun fitness-arvo voidaan laskea.
4.4 Geneettisen algoritmin osat
4.4.1 Alkupopulaation luonti
Alkupopulaatio luodaan algoritmin alussa. Algoritmi lähtee muokkaamaan siitä parempia ratkaisuja. Mitä parempia ratkaisuja alkupopulaatio sisältää jo valmiiksi, sitä parempi, koska silloin on todennäköisesti pienempi matka haettuun riittävän hyvään ratkaisuun.
Toisaalta yksilöiden olisi hyvä olla mahdollisimman erilaisia eri ominaisuuksiltaan, jotta algoritmi pääsisi etsimään ratkaisuavaruuden toisistaan riittävästi eroavista osista parasta ratkaisua heti alussa. Jos yksilöt ovat lähes toistensa kaltaisia, voidaan paljon helpommin juuttua paikalliseen ääriarvoon, vaikka ratkaisuavaruuden jossain toisessa paikassa olisi
