Bruk av tabusøk og critical event memory på set partition-problemet

Bruk av tabusøk og critical event memory på set partitioning-problemet Christian Magnus Berg Institutt for Informatikk, Universitetet i Bergen christia@ii.uib.no Arne Løkketangen Institutt for Informatikk, Høgskolen i Molde arne.lokketangen@himolde.no Oversikt Ideer fra en heuristikk skrevet av Glover og Kochenberger for bruk på 0-1 ryggsekk-problemet forsøkes tilpasset og brukt på set partitioning-problemet. Denne heuristikken var basert på tidligere arbeid med tabusøk og surrogate constraints. Den introduserte critical event memory, og benyttet en interessant oscillering mellom lovlige og ulovlige løsninger. Denne er ikke nødvendigvis helt overførbar til set partitioning-problemet, men tankegangen kan lett tilpasses de beslektede problemene set packing og set covering. Set partitioning-problemet forsøkes løst med en spesialtilpasset utgave av denne heuristikken. 1. Introduksjon Et av flyselskapenes største problemer er planlegging av mannskapsdisposisjoner. Reglene for benyttelse av flymannskap er strenge. Flyselskapene er pålagt grenser for hvor mange timer om dagen et mannskap kan være i luften, hvor mange timer et mannskap kan være borte fra sin base før de må ha hotellovernatting, etc. Mannskap utgjør også den nest største utgiften til et flyselskap, etter drivstoff (Hoffman og Padberg, 1993). Set partitioning-problemet kan brukes til å finne det billigste oppsettet for bruk av mannskap på et sett med flygninger, og det å ...