P. Preijer
Een programma voor crew scheduling
Computeropdracht,
Rapport 97.3.LT.4829, Transporttechnologie, Logistieke Techniek.
Er is een programma geschreven voor de behandeling van een crew scheduling
probleem in de scheepvaart. Dit probleem is een deelprobleem van het scheduling
probleem uit de doctoraalopdracht van Warrens (rapport 95.3.LT.4461).
Dit probleem is een scheduling probleem uit de scheepvaart met de volgende
gegevens:
- Er is een vloot van drie schepen
- Op elk schip dienen twee officieren van verschillende rang
- Er zijn twee extra officieren die op alle drie de schepen invallen als de
officier van hun rang wegens vacantie niet aanwezig is.
- Het rooster beslaat een periode van 3 jaar
- Elk jaar wordt onderverdeeld in 24 periodes, waardoor het rooster 72
perioden telt
De doelfunctie is het minimaliseren van de kosten van het rooster. De kosten
bestaan hier uit de reiskosten van de officieren als zij voor vacantie naar huis
gaan, en als zij na een vacantie weer terugkomen naar de haven waar hun schip op
dat moment ligt. In het programma worden de kosten berekend over alle reizen
binnen het rooster. De kosten worden geminimaliseerd onder de volgende
voorwaarden:
- De twee officieren die op hetzelfde schip varen mogen niet tegelijkertijd op
vacantie;
- Elke officier moet in een periode van 3 jaar (72 perioden) 50 to 57 perioden
werken;
- In de laatste 3 perioden van het jaar (de 'Kertsttijd') werkt men of heeft
men vacantie(kerstvoorwaarde 1);
- Men mag hoogstens 1 keer in de 3 jaar tijdens de kerstperiode vacantie
hebben (kerstvoorwaarde 2).
De gebruikte oplossingsmeyhode is een constructiemethode met random invloeden.
Deze methode wordt een groot aantal keren uitgevoerd en elke keer als er een
beter rooster gevonden wordt, wordt het rooster opgeslagen. Door de sctructuur
van het probeleem zijn er veel verschillende roosters mogelijk die allemaal
dezelfde reiskosten hebben en toch allemaal aan de voorwaarden voldoen. Met het
grote aantal herhalingen wordt er dus in feite gehoopt op een toevalstreffer.
Het programma is geschreven in Borland Pascal 7.0 en maakt gebruik van Turbo
Vision om de layout vast te leggen; ook wordt er gebruik gemaakt van objecten.
Naar aanleiding van de gevonden resultaten zijn de volgende Conclusies
getrokken:
- 1. Het is mogelijk via constructie met random invloeden een geschikt rooster te
maken voor het beschouwde probleem:
- 2. De methode gebruikt erg veel computertijd (3 minuten voor 250 herhalingen, op
een 33 MHz-machine);
- 3. Het optimale rooster zal alleen benaderd kunnen worden door het programma
zeer lang door te laten lopen (bijvoorbeeld 5000 herhalingen, oftewel
één uur op een 33MHz-machine).
De volgende Aanbevelingen worden gedaan:
- 1. Voor een realistischer beeld van de reiskosten kan de reiskostenberekening
beter ook rekening houden met de reizen tussen de laatste periode van het
vorige rooster en de eerste periode van het nieuwe rooster;
- 2. Om de kerstvoorwaarden niet aan te tasten moeten er veranderingen worden
aangebracht in de verbeteringsprocedure;
- 3. Het gericht experimenteren met bepaalde kansen (bijvoorbeeld afhankelijk van
de boetes) en boetesystemen die gebruikt worden in de constructiemethode kan
verbeteringen opleveren, daar de nu gebruikte kansen en boetesystemen min of
meer intuitief zijn bepaald.
- 4. De roosters worden alleen op het scherm afgebeeld; het kunnen afdrukken van
de roosters is daarom een nuttige uitbreiding.
Rapporten studenten Logistieke Techniek
Gewijzigd: 1997.10.28;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.