Usage of integer programming in scheduling problems

Tässä diplomityössä tutkitaan lineaarisen kokonaislukuoptimoinnin käyttöä aikataulutusongelmien ratkaisemisessa. Tavoitteena on vertailla erilaisia ratkaisumetodeja keskenään. Ongelmat ratkaistaan käyttämällä numeerisia kokonaislukuratkaisijoita, kuten Matlabin intlinprog. Lineaarisen optimoinnin perusteiden lisäksi teoriaosiossa tehdään kirjallisuuskatsaus numeeristen ratkaisijoiden matemaattisen pohjaan. Lineaarista kokonaislukuoptimointia käytetään sellaisten optimointiongelmien ratkaisemiseen, joissa muuttujien arvot ovat diskreettejä tai kokonaislukuja. Muuttujia, joiden arvot on rajoitettu kokonaislukuihin antavat vastauksen esimerkiksi kysymyksiin siitä, kuinka monta kappaletta tilataan tuotetta x, kuinka monta työntekijää kohdennetaan projektin osa-alueeseen x, ja niin edelleen. Erityistapauksena lineaarisesta kokonaislukuoptimoinnista on lineaarinen binäärilukuoptimointi (BIP). Optimointiongelmassa, joka on tyypistään BIP, muuttujat saavat vain arvoja 0 tai 1. Nämä arvot kuvaavat kyllä-ei luonteisia päätöksiä, kuten ostetaanko, palkataanko tai sijoitetaanko. Binäärilukuoptimointi on tämän diplomityön kannalta oleellinen, sillä työssä esiintyvät ongelmat formuloidaan ja ratkaistaan BIP-ongelmina. Aikataulutusongelmien ratkaiseminen käyttäen lineaarista kokonaislukuoptimointia edellyttää, että voimme formuloida nämä ongelmat kokonaislukuoptimointi ongelmiksi ja ratkaista ne kohtuullisessa ajassa. Keskitymme kahteen eri aikataulutusongelmaan. Ensimmäinen ongelma on luoda optimaalisia työvuorolistoja yhtiön työntekijöille ja toinen ongelma on luoda optimaalisia lukujärjestyksiä yliopiston opiskelijoille. Nämä ongelmat voidaan formuloida IP-ongelmiksi ja simulaatiosta saatujen tulosten perusteella huomataan, että instanssit saadaan ratkaistua nopeasti tai kohtuullisessa ajassa. Eri ratkaisijoiden välillä löydetään myös eroja niiden kyvyssä ja tehokkuudessa ratkaista testattuja instansseja