Algoritmit avuksi aikataulutusongelmiin

21.10.2020

Jos tehtävänäsi on aikatauluttaa esimerkiksi satojen henkilöiden työvuorot seuraavalle kvartaalille, lentojen nousut ja laskeutumiset tai työkoneiden käyttö- ja huoltosuunnitelma, optimointialgoritmien hyödyntäminen kannattaa. Ne etsivät tehokkaan ratkaisun ongelmaasi kädenkäänteessä. Mistä sitten tietää, soveltuvatko optimointialgoritmit sinun ongelmaasi? Lähes kaikki aikataulutusongelmat ovat optimoitavissa. Jos tunnistat minimoitavan tai maksimoitavan tavoitteen tai suunnittelua ohjaavia rajoitteita, niin olet jo pitkällä.

Optimointimallit muodostuvat tavoitteesta, päätösmuuttujista ja rajoitteista. Tavoite on jokin minimoitava tai maksimoitava mittari. Esimerkiksi jos suunnittelet kuljettajien työvuoroja, saatat pyrkiä minimoimaan osa-aikaisten kuljettajien käyttöä tai työvuorojen pituuksien vaihtelua. Toisaalta ehkä haluatkin maksimoida lomatoiveiden täyttymistä tai toiminnan kannattavuutta. Päätösmuuttujat ovat ne päätökset, joihin algoritmilta pyydetään vastauksia. Kuljettaja-työvuoro-yhdistelmät ovat siten päätösmuuttujia. Päätöksille asetetut vaatimukset ilmaistaan rajoitteina, joiden avulla voidaan huomioida vaikkapa työaikalaki ja kuljettajien pätevyys eri tehtäviin.

Tässä muutamia esimerkkejä aikataulutusongelmista:

  • Työvuorojen suunnittelu
  • Lomasuunnittelu
  • Leikkaussaleissa tehtävien leikkauksien aikataulutus
  • Koneiden huoltoaikataulun suunnittelu
  • Sataman, lentokentän tai vastaavan käytön aikataulutus
  • Eri tuotteiden valmistamisen aikataulutus tuotantolinjalla

Yleisiä tavoitteita:

  • Kustannusten minimointi / voiton maksimointi
  • Henkilöiden tasapuolisen kohtelun maksimointi
  • Toimitusnopeuden maksimointi
  • Tarvittavien resurssien minimointi
  • Joku muu tai edeltävien yhdistelmä

Yleisiä rajoitteita:

  • Tiettyyn tehtävään vaaditaan tietyn ominaisuuden omaava henkilö tai kone
  • Tehtävillä on tietty järjestys
  • Kukin resurssi voi tehdä vain rajattua määrää tehtäviä kerralla
  • Työtä ei saa tehdä liian pitkään kerralla
  • Jotkin tehtävät ovat vaihtoehtoisia keskenään

Teimme myös demovideon aikataulujen optimoinnista. Videolla optimoidaan rakennustöitä ja rakennuskoneiden huoltoja. Jokainen työtehtävä vaatii tietyn tyyppisen koneen, mutta jokainen työtunti tuo valitun koneen seuraavan huollon määräaikaa askelen lähemmäksi. Videolla esitellään, miten algoritmi luo aikataulusuunnitelman ja kustannusennusteen. Lisäksi näytetään, kuinka tuloksista voi päätellä, onko resursseissa puutteita ja skenaarioiden avulla tutkitaan, mikä olisi uusien investointien tuoma hyöty.

Visa Linkiö
Lead Data Scientist