Algoritme/roostervoorbeeld

[Ri80]

Wie kan me helpen bij het volgende vraagstuk:

Voor een rondvaartbedrijf zoek ik naar de beste zoekmethode voor automatisch roosteren. Ik moet dit onderbouwen met een simpel/vereenvoudigd voorbeeld. Bijvoorbeeld dagelijks 2 boten en 3 schippers. En bijvoorbeeld de criteria:

Schipper 1 kan niet op boot A varen,

Schipper 2 & 3 hebben na 2 dagen werken minimaal 2 dagen rust.

D = totaal aantal mogelijke diensten d

M = totaal aantal medewerkers m (schippers)

i = een criterium

xmd = 1 als schipper m, dienst d werkt

yid = strijdigheid, als criterium i op dienst d wordt overschreden

Optimaliseringsfunctie: Minimaliseer: yid xmd

Onder:

Elke schipper heeft precies één dienst

Alle diensten zijn vervuld.

Hoe kan ik een dergelijk voorbeeldje utwerken en laten zien dat het met linieair programmeren moeilijk is om bijvoorbeeld een eerlijke verdeling van de weekenden linieair te maken.

Uit de theorie haal ik dat ik meer kan met een local search algoritme (tabu search) waarbij ik de criteria opneem in de fitnessfunctie? Hoe kan ik dit laten zien in een voorbeeld?