rafentheorie planning maken

© h.hofstede (h.hofstede@hogeland.nl)

Een planning maken.

Stel je hebt een aantal taken T₁, T₂, ...T_n die allemaal door een bepaalde machine verricht moeten worden. Tussen twee taken in moet de machine steeds opnieuw afgesteld worden en dat kost een bepaalde tijd. De tijd die het kost om van taak T_i over te gaan op taak T_j noemen we t_ij
Dan is het voor de bedrijfsleider van de fabriek waarin dit alles gebeurt natuurlijk erg interessant om de volgorde van die taken zó te plannen dat de totale afsteltijd minimaal is.

Als we de taken voorstellen door n knooppunten van een digraaf D en de afsteltijden als de weging van de verbindingslijnen, dan is dit een soort handelsreizigerprobleem geworden, maar nu in een gerichte graaf.
Het zal je niet verbazen dat ook hiervoor nog geen geen kant-en-klare oplossing is gevonden.

We zullen een redelijke methode om zo'n planning te maken bekijken.

Maak eerst de digraaf D, en kies die zó, dat je tussen twee knooppunten (taken) de verbindingslijn kiest die bij de kortste tijd hoort. Je neemt van t_ij en t_ji dus steeds het kleinste getal (als ze gelijk zijn kies je er willekeurig eentje).

Die D is dan een toernooi.

Nou weten we uit stelling 2 van de vorige les dat elk toernooi een Hamilton-route heeft.
Als redelijke planning nemen we gewoon die Hamiltonroute!!

Blijft nog een beetje de vraag over: hoe vinden we die?
Nou, daar is een hele eenvoudige methode voor die nogal lijkt op het bewijs van stelling 4 van de vorige les.

Stel dat je een zo lang mogelijke route P hebt gevonden die nog geen Hamiltonroute is omdat een knooppunt K er nog niet bijhoort. Dan weet je dat K een uitbuur van het eerste punt van P is, en een inbuur van het laatste punt (als dat niet zo was kon je K eenvoudig direct aan P toevoegen).
Loop nu alle knooppunten van P langs, dan moeten ergens twee opeenvolgende knooppunten te vinden zijn zodat K daar wisselt van uitbuur naar inbuur (zie de middelste figuur hierboven).
Maar door P daar te onderbreken en K toe te voegen kun je een langere P vinden! Zie de figuur rechts.
En zo ga je door met alsmaar langere P's maken totdat het een Hamiltonroute is.

Voorbeeld.

Neem de taken en tijden hieronder met de bijbehorende digraaf rechts.

Nu nog even een Hamiltonroute vinden:

Links ben ik zomaar bij 1 begonnen en kwam ik tot het rode pad P.
Daar zit knooppunt 6 nog niet in, dus in de middelste figuur heb ik alleen de zwarte verbindingen van 6 overgelaten. Je ziet dat 6 een uitbuur van 2 is, en direct al een inbuur van de volgende knoop 1. Dus kun je de rode 1-2 route vervangen door de blauwe 2-6-1.
De Hamiltonroute is dan 2-6-1-3-4-8-7-5 en heeft afsteltijd 4 + 2 + 4 + 5 + 2 + 2 + 3 = 22.