Intervallplanlegging

Intervallplanlegging er et område innen tidsplanlegging og optimalisering som handler om å tildele eller velge tidsintervaller for aktiviteter slik at et givent mål oppnås. En vanlig innfallsvinkel er å maksimere antall gjennomførte aktiviteter uten overlapping, men man kan også søke å maksimere total verdi eller minimere forsinkelser og kostnader.

Grunnleggende variant: Gitt en mengde aktiviteter, hver med et starttidspunkt s_i og et sluttidspunkt f_i, velges en undermengde av aktiviteter som ikke overlapper og som maksimerer antall valgte. Dette kalles ofte interval scheduling eller aktivitetsekseleproblemet.

Løsningsmetoder: For uvektet variant (like stor verdi for alle aktiviteter) finnes en enkel og optimal løsning basert på en greedy-strategi: sorter aktivitetene etter sluttid, og gjenta å velge den aktiviteten som avsluttes først og som ikke overlapper med allerede valgte. Denne tilnærmingen gir en optimal løsning i O(n log n) tid. For den vekte versjonen, der hver aktivitet har en verdi, brukes dynamisk programmering med binær søk og oppnås O(n log n) tid.

Anvendelser: Intervallplanlegging er sentralt i produksjon, maskinplanlegging, tidsplanlegging i prosjekter og i datanettverk- eller serverressursstyring hvor man ønsker effektiv utnyttelse av tilgjengelig kapasitet.

Historie og relaterte begreper: Problemet er en standard modell i programmerings- og optimeringslitteraturen og betegnes også som aktivitetsekseleproblemet. Den enkle greedyløsningen er klassisk; mer generelle varianter behandles innen scheduling theory.

---