Technische Universiteit Delft
Faculteit Werktuigbouwkunde, Maritieme Techniek en Technische Materiaalwetenschappen
Transporttechnologie / Logistieke Techniek



F.C. van Lookeren Campagne Methoden voor paarsgewijze taaktoewijzing.
Literatuuropdracht/scriptie, Rapport 93.3.LT.4176, Transporttechnologie, Logistieke Techniek.


Dit onderzoek beschouwt methoden om paarsgewijs taken aan servers toe te wijzen.

Paarsgewijze taaktoewijzing is een verbijzondering van het klassieke toewijzingsprobleem, die specifiek kan worden toegepast in situaties waarin
  1. kortstondige taken zich in groten getale aandienen;
  2. een fase-onderscheid kan worden onderkend, of
    de taken in te delen zijn in twee groepen;
  3. zich een volgorde-afhankelijk karakter voordoet tussen de verschillende taken en groepen.
Paarsgewijze taaktoewijzing wordt in eerste instantie gemodelleerd als een 0,1-programmeringsprobleem, waarbij de totale kosten van de toewijzing worden geminimaliseeerd, onderworpen aan de volgende restricties:
  1. Elke server wordt precies één keer in de eerste toewijzing gebruikt.
  2. Elke taak wordt precies één keer uitgevoerd.
  3. Als een taak in de eerste ronde wordt uitgevoerd dan moet hij precies één opvolger hebben.
    Als een taak in de eerste ronde niet wordt uitgevoerd dan mag hij geen opvolger hebben.
Om gebruik te kunnen maken van efficiënte lineaire programmeringstechnieken wordt het 0,1-probleem getransformeerd tot een minimum cost flow probleem, waarvan bekend is dat bij gebruik van geheeltallige data een geheeltallige oplossing volgt. Hiertoe wordt voorgaande restrictie 2 vervangen door de volgende twee restricties:
  1. Elke taak wordt maximaal één keer in de eerste toewijzing uitgevoerd.
  2. Elke taak wordt maximaal één keer in de tweede toewijzing uitgevoerd.
Voor het oplossen van dit minimum cost flow probleem wordt gebruik gemaakt van het e-Relaxation Algorithm van Bertsekas.

Het vervangen van restrictie 2 door restricties 2a en 2b leidt er toe dat een bepaalde taak twee keer kan worden toegewezen. De volgende drie technieken kunnen worden gebruikt om dit probleem op te lossen:
  1. Branch-and bound techniek: De dubbel toegewezen taak wordt verplicht toegewezen in de eerste ronde dan wel in de tweede ronde, waarna een grens wordt bepaald door het e-Relaxation Algorithm toe te passen.
  2. Toepassen prijsverhogingen: De dubbel toegewezen taak wordt minder "geliefd" gemaakt door z'n prijzen te verhogen, waarna het e-Relaxation Algorithm opniew wordt toegepast.
  3. Het minimum cost flow probleem wordt verlaten door het toevoegen van een nieuwe restrictie die expliciet dubbele toewijzing verbiedt.

Rapporten studenten Logistieke Techniek
Gewijzigd: 2000.12.07; logistics@3mE.tudelft.nl , TU Delft / 3mE / TT / LT.