Faculteit Ingenieurswetenschappen Vakgroep Elektronica en Informatiesystemen Voorzitter: prof. dr. ir. J. Van Campenhout
Webapplicatie voor taakplanning in gastronomische keukens door Brecht Demeulenaere en Evelien Van de Velde
Promotor: prof. dr. ir. P. De Neve Thesisbegeleider: ir. S. Notebaert
Afstudeerwerk ingediend tot het behalen van de graad van Master in de toegepaste informatica
Academiejaar 2005–2006
Dankwoord Als eerste willen we onze promotor Peter De Neve bedanken. Door het maken van deze thesis is onze kennis van PHP en MySQL erg verruimd. Alsook onze begeleider Stijn Notebaert, die altijd ter beschikking stond bij problemen. Voor onze praktische vragen konden we altijd terecht bij restaurant Bistro Alfa te Pittem. Hen willen we natuurlijk ook danken voor het beantwoorden van onze lastige vragen. Bij het schrijven van deze thesis werd ons veel leed bespaard door de goede beschrijving van LATEX en de template die kon teruggevonden worden op de website van Peter Lambert. Wij zijn hem ook onze dank verschuldigd. Tot slot wensen we nog iedereen te bedanken die op ´e´en of andere manier zijn steentje heeft bijgedragen.
Toelating tot bruikleen De auteur geeft de toelating deze scriptie voor consultatie beschikbaar te stellen en delen van het werk te kopi¨eren voor persoonlijk gebruik. Elk ander gebruik valt onder de bepaling van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit het werk. Gent, juni 2006
i
Webapplicatie voor taakplanning in gastronomische keukens door Brecht Demeulenaere en Evelien Van de Velde Afstudeerwerk ingediend tot het behalen van de graad van Master in de toegepaste informatica Academiejaar 2005–2006 Universiteit Gent Faculteit Ingenieurswetenschappen Vakgroep Elektronica en Informatiesystemen Voorzitter: prof. dr. ir. J. Van Campenhout Promotor: prof. dr. ir. P. De Neve Thesisbegeleider: ir. S. Notebaert
Samenvatting Deze thesis bestaat uit de ontwikkeling van een webapplicatie die toelaat om a.d.h.v. de recepten en de bestellingen een optimale allocatie van het keukenpersoneel op te stellen. Het uiteindelijke resultaat bestaat uit een tijdsschema voor iedere medewerker die meehelpt aan de bereiding van de gerechten. Bij het opstellen van het tijdsschema moet met verschillende voorwaarden en factoren rekening gehouden worden. Zo moeten de gerechten in de juiste volgorde klaargemaakt worden en moet er een bepaalde wachttijd zijn tussen de verschillende gangen. Ook kunnen bepaalde stappen van de bereiding van een gerecht pas gestart worden nadat sommige andere afgewerkt zijn. De gegevens over de gerechten, de ingredi¨enten, de personeelsleden en het keukenmateriaal worden bijgehouden in een databank. Deze databank wordt opgeslagen op een MySQL-server. Het algoritme die de verschillende taken verdeelt onder de personeelsleden en het keukenmateriaal is een voor deze toepassing aangepaste versie van het gekende critical path scheduling algoritme en wordt ge¨ımplementeerd in de webapplicatie met behulp van de scripttaal PHP. De webapplicatie bevat een gebruiksvriendelijke gebruikersinterface waarmee alle gegevens kunnen toegevoegd en aangepast worden. De gebruikersinterface bevat ook een pagina waarop het werkschema aan de hand van een Gantt-grafiek wordt weergegeven. Trefwoorden: PHP, MySQL, restaurant, webapplicatie, allocatieprobleem, critical path scheduling
ii
Inhoudsopgave 1 Inleiding
1
1.1
Doelstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Indeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2 Software en hulpmiddelen
3
2.1
EasyPHP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2
Gantt-grafieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3
JpGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.4
Installatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
3 Samenstelling van de databank 3.1
6
Ontwerp van het entiteit-relatie diagram . . . . . . . . . . . . . . . . . . .
6
3.1.1
Entiteitstypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.1.2
Relatietypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.1.3
Attributen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1.4
Zwakke entiteitstypes . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2
Databankontwerp uitgaande van het entiteit-relatie diagram . . . . . . . . 16
3.3
De resulterende databank . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4 Het critical path scheduling algoritme 4.1
24
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1.1
Definities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.2
Veronderstellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.3
Precedentiediagram . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.4
Doelstellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 iii
4.2
4.3
4.4
Lijstverwerkingsalgoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2.1
Werking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.2
Optimaliseren van het tijdschema . . . . . . . . . . . . . . . . . . . 28
4.2.3
Critical path scheduling algoritme . . . . . . . . . . . . . . . . . . . 29
4.2.4
Besluit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.1
Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3.2
Functies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3.3
Algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Besluit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5 De website
43
5.1
Structuur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2
Onderliggende code van de menu-bestanden . . . . . . . . . . . . . . . . . 45 5.2.1
HTML-hoofding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2.2
HTML-corpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.3
Onderliggende code van het werkschema . . . . . . . . . . . . . . . . . . . 50
5.4
Onderliggende code van de figuur . . . . . . . . . . . . . . . . . . . . . . . 51
6 Handleiding 6.1
6.2
52
Installatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.1.1
Automatisch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.1.2
Handmatig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Gebruiksaanwijzingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.2.1
Invoegen van de gegevens . . . . . . . . . . . . . . . . . . . . . . . 54
6.2.2
Configuratie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.2.3
Aan de slag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7 Besluit
63
Bibliografie
65
iv
Lijst van figuren 2.1
Voorbeeld van een Gantt-grafiek . . . . . . . . . . . . . . . . . . . . . . . .
4
3.1
Entiteitstypes en relatietypes . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.2
Instellen van vreemde sleutels van de tabel bereidingen . . . . . . . . . . 20
4.1
Precedentiediagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2
Kritieke pad in het precedentiediagram . . . . . . . . . . . . . . . . . . . . 27
4.3
Tijdschema voor prioriteitenlijst T8 − T7 − ... − T1 . . . . . . . . . . . . . . 28
4.4
Tijdschema voor prioriteitenlijst T1 − T2 − ... − T8 . . . . . . . . . . . . . . 29
4.5
Tijdschema voor een optimale prioriteitenlijst . . . . . . . . . . . . . . . . 32
4.6
Algemeen concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.7
Opbouw werkschema.php . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.8
Typisch precedentiediagram . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.9
Stappen van het algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.1
Screenshot van de website . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2
Waarschuwingsvenster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.3
Bevestiging voor het verwijderen van een item . . . . . . . . . . . . . . . . 48
5.4
Hints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.1
Screenshot van EasyPHP 1.8 . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.2
Aanmaken databank restaurant . . . . . . . . . . . . . . . . . . . . . . . . 54
6.3
La Dolce Vita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.4
Werkschema voor spreidingsfactor 0 . . . . . . . . . . . . . . . . . . . . . . 60
6.5
Werkschema voor spreidingsfactor 5 . . . . . . . . . . . . . . . . . . . . . . 60
v
Lijst van tabellen 3.1
Structuur van de tabel bereidingen . . . . . . . . . . . . . . . . . . . . . . 21
3.2
Structuur van de tabel bestellingen . . . . . . . . . . . . . . . . . . . . . . 21
3.3
Structuur van de tabel ingredient . . . . . . . . . . . . . . . . . . . . . . . 21
3.4
Structuur van de tabel ingredienten . . . . . . . . . . . . . . . . . . . . . . 22
3.5
Structuur van de tabel precedenten . . . . . . . . . . . . . . . . . . . . . . 22
3.6
Structuur van de tabel recepten . . . . . . . . . . . . . . . . . . . . . . . . 22
3.7
Structuur van de tabel taken . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.7
Structuur van de tabel taken (vervolgd) . . . . . . . . . . . . . . . . . . . . 23
3.8
Structuur van de tabel verwerker . . . . . . . . . . . . . . . . . . . . . . . 23
3.9
Structuur van de tabel verwerkerstype . . . . . . . . . . . . . . . . . . . . 23
3.10 Structuur van de tabel opvoorhand . . . . . . . . . . . . . . . . . . . . . . 23 4.1
Precedentiediagram opgeslagen in een array . . . . . . . . . . . . . . . . . 36
vi
Hoofdstuk 1 Inleiding Jaren geleden was een bezoek aan het restaurant een waar gebeuren, voorbehouden voor in de weekends of op speciale gelegenheden. Tegenwoordig hebben we met z’n allen steeds minder tijd om zelf te koken en is een gewone weekdag al een gelegenheid om op restaurant te gaan. Vele gastronomische restaurants kennen daarom ook een groot succes. Om als restaurant echter succesvol te blijven moet zoveel mogelijk voldaan worden aan de alsmaar toenemende eisen van de klant. Een gerecht van de menukaart moet niet alleen lekker zijn, maar het moet ook op tijd opgediend worden en budgetvriendelijk zijn. Om daarnaast nog de concurrentie te kunnen bijblijven is het noodzakelijk om de activiteiten in de keuken zo effici¨ent mogelijk te organiseren. Tot op heden is de keukenchef hiervoor verantwoordelijk. Het automatisch planningssysteem dat we in deze thesis wensen te ontwerpen zou de werklast voor de keukenchef aanzienlijk kunnen verlagen en zo zijn steentje bijdragen in een succesvol restaurant.
1.1
Doelstelling
Het hoofddoel van deze thesis is het schrijven van een goed werkende applicatie die zo realistisch mogelijk is. Op het eerste zicht zal moeten rekening gehouden worden met een aantal voorwaarden zoals een optimale wachttijd tussen twee gerechten, gelijktijdige bediening van tafelgenoten, volgorde van gerechten respecteren, enzovoort. E´enmaal men echter wil beginnen met alles op een strategische manier uit te werken, wordt duidelijk dat er veel meer voorwaarden zijn waarmee rekening moet gehouden worden. Zo mag bij het bereiden van een gerecht, de verschillende stappen niet in gelijk welke volgorde worden 1
uitgevoerd. Ook moet men opletten met gerechten die niet per persoon klaargemaakt kunnen worden. Een ander voorbeeld is dat een personeelslid soms een tijd moet wachten op een gerecht dat in de oven zit. Hoe kan je ervoor zorgen dat dat personeelslid zich ondertussen met iets anders kan bezighouden? Zijn er personeelsleden die een bepaalde specialiteit hebben of kan ieder personeelslid alle taken uitvoeren? Al deze dingen en nog ontelbaar vele andere, zorgen ervoor dat het probleem niet zomaar kan opgelost worden. Allereerst moet nagedacht worden over een databank waarmee al deze problemen kunnen aangepakt worden. Eens het concept vastgelegd is, kan begonnen worden om beetje bij beetje het algoritme te ontwikkelen. Vervolgens is het ook noodzakelijk om een gebruiksvriendelijke grafische gebruikersinterface te ontwerpen. Deze moet de gebruiker toelaten om op een snelle en effici¨ente manier de gegevens in de databank op te slaan. Tijdens de ontwikkeling van deze interface moet de volledige webapplicatie voortdurend getest worden op fouten en onvolmaaktheden.
1.2
Indeling
We beginnen in hoofdstuk 2 met een korte bespreking van de gebruikte software. In het derde hoofdstuk wordt het probleem geanalyseerd en wordt reeds vooruit gekeken naar al het nodige zodat we een omschrijving van de databank kunnen geven. Deze dingen worden dan verder besproken bij de ontwikkeling van het algoritme in het vierde hoofdstuk. Er is ook voorzien in een gebruikersinterface die de gebruiker toelaat om alle acties uit te voeren. Dit staat beschreven in hoofdstuk 5. Ook is het nodig dat voor het gebruik van het programma een duidelijke handleiding bestaat, deze is terug te vinden in het voorlaatste hoofdstuk. Tot slot wordt in het laatste hoofdstuk een besluit geformuleerd van ons geleverd werk.
2
Hoofdstuk 2 Software en hulpmiddelen Onze opdracht bestaat uit het maken van een webapplicatie voor taakplanning in gastronomische keukens. We hebben dus een webserver nodig die onze webapplicatie kan uitvoeren. Het is ook noodzakelijk om gegevens over de recepten, de bestellingen, enzovoort te kunnen opslaan. Om dit op een effici¨ente manier te kunnen doen, maken we gebruik van een databank. Voor het ontwerpen van de webapplicatie maken we gebruik van de scripttaal Hypertext Preprocessor (PHP). Een handig hulpmiddel die al deze technologie¨en bevat is EasyPHP 1 . Daarnaast moeten we de opgestelde taakplanning overzichtelijk kunnen weergeven. Een veelgebruikte manier om dit te doen is het gebruik van Gantt-grafieken (zie figuur 2.1). Een krachtig hulpmiddel om dynamische Gantt-grafieken (en ook andere grafieken) weer te geven met PHP is JpGraph 2 . In de volgende paragrafen wordt meer uitleg gegeven over deze technologie¨en.
2.1
EasyPHP
EasyPHP is een compleet en gratis softwarepakket dat het mogelijk maakt om de kracht en flexibiliteit van de dynamische taal PHP en het effici¨ent gebruik van een database te combineren onder Windows. Het pakket bevat een Apache webserver, een MySQL databank, een volledig PHP-uitvoerbaar pakket en eenvoudige ontwikkelingstools voor websites of applicaties. 1 2
http://www.easyphp.org/ http://www.aditus.nu/jpgraph/
3
2.2
Gantt-grafieken 14 mei 2006
Id
Taaknaam
Begindatum
Einddatum
21 mei 2006
Duur 15
1
Taak 1
16/05/2006
18/05/2006
3d
2
Taak 2
17/05/2006
19/05/2006
2d 4h
3
Taak 3
17/05/2006
22/05/2006
4d
4
Taak 4
17/05/2006
18/05/2006
1d 4h
5
Taak 5
16/05/2006
19/05/2006
4d
16
17
18
19
20
21
22
23
24
25
26
27
28
Figuur 2.1: Voorbeeld van een Gantt-grafiek
Gantt-grafieken worden veel gebruikt als visueel hulpmiddel in projectplanning om de planning en de voortgang van een project te laten zien. Op dit moment is het een wereldwijde standaard. Een Gantt-grafiek bestaat uit een aantal rijen die ieder een module of taak binnen het project vertegenwoordigen. Meestal staan de eerste modules bovenaan. Op de horizontale as staat de tijd die nodig is voor het totale project. Per project wordt met een tijdbalk aangegeven welke tijd per module nodig is. Figuur 2.1 is een typisch voorbeeld van een Gantt-grafiek.
2.3
JpGraph
JpGraph is een objectgeori¨enteerde bibliotheek voor PHP om dynamisch grafieken te maken. De bibliotheek is volledig in PHP geschreven en kan door gelijk welk PHP-script gebruikt worden. De bibliotheek is in staat om veel verschillende types van grafieken te maken. Wij hebben echter enkel de module voor de Gantt-grafieken nodig. Gantt-grafieken worden meestal gebruikt om projecten over een tijdsspanne van dagen, weken of zelfs maanden weer te geven. Voor ons taakplanningssysteem in gastronomische keukens gaat het echter om een veel kortere tijdspanne. Met de module voor Ganttgrafieken in JpGraph is het weergeven van zulke korte tijdspannes op zich niet mogelijk. Daarom werden een aantal bestanden in de bibliotheek van JpGraph aangepast. Ook de verticale lijnen die we gebruiken om het huidige tijdstip en het opdienen van de gerechten weer te geven konden niet op een gemakkelijke manier geplaatst worden, zodat we dit hebben aangepast. Tenslotte hebben we nog een kleine aanpassing gedaan zodat we het 4
nummer van de taak konden weergeven in elke taakbalk om de grafiek overzichtelijk te houden.
2.4
Installatie
Voor het installeren van de software en hulpmiddelen hebben we een automatisch installatieprogramma voorzien. Daarnaast kan de software ook handmatig ge¨ınstalleerd worden. Voor meer informatie verwijzen we naar paragraaf 6.1 in de handleiding.
5
Hoofdstuk 3 Samenstelling van de databank In dit hoofdstuk gaan we uit van het entiteit-relatie model om onze databank op te stellen. Dit databankmodel legt de structuur van de data vast aan de hand van entiteitstypes, attributen en relatietypes en wordt gebruikt als tussenstap voor het ontwerpen van een databank. Het ontwerp van het entiteit-relatie model voor onze probleemstelling wordt ontwikkeld in de eerste paragraaf van dit hoofdstuk. Het verkregen model wordt dan in de tweede paragraaf via een algoritme omgezet naar een relationele databank die we verder zullen gebruiken.
3.1
Ontwerp van het entiteit-relatie diagram
Bij het ontwerp van een geschikt diagram moet goed nagedacht worden over de verschillende entiteitstypes, hun attributen, de relatietypes en de structurele restricties. Voor meer informatie hierover verwijzen we naar hoofdstuk 3 van [5] en het vierde hoofdstuk van [3].
3.1.1
Entiteitstypes
In een restaurant draait alles rond de gerechten. Elk gerecht wordt door het personeel klaargemaakt aan de hand van een bepaalde bereiding die bestaat uit een aantal stappen. Hierbij wordt gebruikgemaakt van een aantal ingredi¨enten en bepaald keukenmateriaal. Bij de voorbereiding van de gerechten en in afwachting van de eerste bestellingen, zijn er
6
reeds heel wat activiteiten in de keuken. Zo kunnen reeds op voorhand gerechten (gedeeltelijk) klaargemaakt worden, zodat er reeds een voorraad aanwezig is. Uiteindelijk kan de klant in het restaurant een bestelling plaatsen en genieten van de culinaire gerechten. Uit deze korte bespreking van wat zich afspeelt in een restaurant, kunnen we reeds de volgende entiteitstypes afleiden: recept, stap van de bereiding, ingredi¨ ent, bestelling en op voorhand. Merk op dat we als entiteitstype voor recept gekozen hebben en niet voor gerecht. Voor de klanten van een restaurant worden de items op de menukaart gezien als gerechten. In de keuken wordt een gerecht echter gezien als een recept dat aan de hand van bepaalde stappen moet worden bereid. Daarom zal in het vervolg deze twee termen door elkaar worden gebruikt naargelang de context. We spraken ook al van personeelsleden en materiaal dat in de keuken gebruikt wordt. In principe zouden we dit als twee aparte entiteiten kunnen beschouwen. Om echter geen conflicten te verkrijgen bij het cre¨eren van de relationele databank, is het nodig dat we dit als ´e´en entiteit beschouwen. We spreken in het algemeen van een verwerker waarbij elke verwerker tot een verwerkerstype behoort. Elk personeelslid behoort tot het verwerkerstype personeelslid, terwijl bijvoorbeeld de ovens tot het type oven zullen behoren. Naast deze dingen, die evident zijn in een restaurant, hebben we ook nog een bijkomend entiteitstype taak nodig om al het werk dat in een keuken moet gebeuren in goede banen te leiden en te kunnen verwerken.
3.1.2
Relatietypes
In figuur 3.1 is het schema weergegeven met alle entiteitstypes en relatietypes. Voor de duidelijkheid werden geen attributen getekend. In dit gedeelte word een bespreking gemaakt van de verschillende relatietypes. ¨ NT RECEPT - INGREDIE In elk recept zijn een aantal ingredi¨enten nodig. We moeten dus een relatietype voorzien tussen de entiteitstypes recept en ingredi¨ ent. Aangezien elk gerecht meerdere ingredi¨enten kan bevatten en elk ingredi¨ent kan gebruikt worden in meerdere recepten, hebben we te maken met een veel-op-veel (M:N) relatie. 7
1
VERWERKERSTYPE
N VERWERKER
1
N
1
N
N
1
STAP VAN DE BEREIDING
1 TAAK 1
1 M
N
N
N
1 OP VOORHAND
1
1
N
1 RECEPT
BESTELLING
N
M
INGREDIËNT
Figuur 3.1: Entiteitstypes en relatietypes
8
Een gerecht kan niet klaargemaakt worden zonder ingredi¨enten, we zeggen dat de participatie van recept in de relatie totaal is. Een ingredi¨ent hoeft echter niet in een recept gebruikt te worden zodat de participatie van ingredi¨ ent in de relatie partieel is. Natuurlijk moet ook geweten zijn hoeveel eenheden van elk ingredi¨ent moet gebruikt worden in het gerecht. Dit wordt meegegeven in het attribuut hoeveelheid van het relatietype. RECEPT - BESTELLING In dit databankmodel hebben we er voor gekozen om een bestelling te laten bestaan uit ´e´en recept. Als een ober bijvoorbeeld een bestelling opneemt aan een tafel bestaande uit twee verschillende gerechten, dan worden deze gerechten als aparte bestellingen ingegeven in de databank. Dit maakt het databankmodel aanzienlijk eenvoudiger. Doordat een gerecht kan opgenomen zijn in meerdere bestellingen, verkrijgen we een ´e´enop-veel (1:N) relatie. Een bestelling zal altijd bestaan uit een recept, wat betekent dat de participatie van bestelling in de relatie totaal is. Een recept heeft echter geen bestelling nodig om te kunnen bestaan, de participatie van recept in de relatie is dus partieel. RECEPT - STAP VAN DE BEREIDING Voor elk recept bestaat de bereiding uit een aantal stappen. Een specifieke stap behoort tot ´e´en bepaald recept. Dit geeft ons dus een ´e´en-op-veel (1:N) relatie. Een stap uit de bereiding kan niet bestaan zonder dat er een bijhorend recept bestaat, de participatie van stap van de bereiding in de relatie is dus totaal. Bij het ingeven van een recept en zijn bereiding, wordt eerst de omschrijving van het recept in de databank gestoken en dan pas de bereiding ervan. Een recept kan dus bestaan zonder er eerst een bereiding voor te specificeren. Dit impliceert dat de participatie van recept in deze relatie partieel is. STAP VAN DE BEREIDING - VERWERKERSTYPE Deze relatie koppelt een stap van de bereiding aan een bepaald verwerkerstype door te zeggen dat een bepaald item van het keukenmateriaal nodig is om de stap te kunnen uitvoeren. Bij het ingeven van de stappen worden de stappen zodanig opgedeeld dat in 9
elke stap hoogstens ´e´en item uit het aanwezige keukenmateriaal gebruikt wordt. Elk item uit dat materiaal (en dus uit het entiteitstype verwerkerstype) kan uiteraard voor verschillende stappen gebruikt worden. We krijgen dus een veel-op-´e´en (N:1) relatie. Een stap kan uitgevoerd worden zonder materiaal te gebruiken, waardoor de participatie van stap van de bereiding in de relatie partieel is. De participatie van verwerkerstype in de relatie is ook partieel aangezien het materiaal steeds aanwezig is in de keuken. STAP VAN DE BEREIDING - OP VOORHAND Als er een (gedeelte van een) gerecht op voorhand klaargemaakt wordt, wordt voor elke stap een nieuwe entiteit van op voorhand aangemaakt. Een stap van de bereiding kan meerdere malen op voorhand klaargemaakt worden, zodat we te maken hebben met een ´e´en-op-veel (1:N) relatie. Doordat voor elke stap een nieuwe entiteit wordt toegevoegd in op voorhand, is de participatie van op voorhand in de relatie totaal. De participatie van stap van de bereiding is partieel want elke stap kan bestaan zonder dat een entiteit van op voorhand moet bestaan. STAP VAN DE BEREIDING - TAAK Elke stap zal leiden tot ´e´en taak en een taak is afkomstig van slechts ´e´en stap. Hierdoor zien we dat we met een ´e´en-op-´e´en (1:1) relatie te maken hebben. Om een stap te specifi¨eren van de bereiding van een gerecht is het niet nodig dat er taken bestaan. De participatie van stap van de bereiding in de relatie is dus partieel. De omgekeerde participatie is echter totaal, aangezien er reeds stappen moeten gedefinieerd zijn vooraleer je ze kan uitvoeren. STAP VAN DE BEREIDING - STAP VAN DE BEREIDING Deze relatie kan ook omschreven worden als ‘is een precedent van’ of ‘is een voorganger van’. Een stap zal een precedent zijn van een andere stap als de eerste stap eerst moet afgewerkt zijn voordat de andere stap kan aangevangen worden. Om een stap te kunnen beginnen, kan het zijn dat meerdere andere stappen reeds afgewerkt moeten zijn. Een
10
stap kan ook precedent zijn van meerdere stappen. Hierdoor verkrijgen we een veel-opveel (N:M) relatie. Elke stap behalve de laatste stap moet precedent zijn van een bepaalde stap en aangezien niet elke stap een precedent moet hebben, zijn beide kanten van de relatie partieel. TAAK - BESTELLING Een bestelling heeft tot gevolg dat meerdere taken moeten uitgevoerd worden, dit komt doordat elke stap van de bereiding van een gerecht een aparte taak is. Langs de andere kant kan een taak slechts afkomstig zijn van ´e´en bestelling, zodat we een veel-op-´e´en (N:1) relatie verkrijgen. Een taak kan bestaan zonder afhankelijk te zijn van een bestelling, ze kan namelijk ook afhankelijk zijn van een bestelling op voorhand. De participatie van taak in de relatie is dus partieel. Ook de participatie van bestelling is partieel, een bestelling kan ingevoerd worden in de databank zonder dat er reeds taken voor gedefinieerd zijn. TAAK - VERWERKER Deze relatie kan ook omschreven worden als ‘wordt toegewezen aan’. Zo zal een taak meestal worden toegewezen aan een personeelslid, maar het kan ook zijn dat het toegewezen wordt aan een item uit het beschikbare keukenmateriaal. Deze relatie is bijvoorbeeld nodig om er voor te kunnen zorgen dat een personeelslid andere stappen zou kunnen uitvoeren terwijl iets een tijd in de oven zit. Hierdoor kan een taak slechts worden toegewezen aan ´e´en verwerker. Een verwerker kan in de loop van de tijd wel meerdere taken toegewezen krijgen. We verkrijgen dus een veel-op-´e´en (N:1) relatie. Een taak moet altijd toegewezen worden aan een verwerker en kan er dus niet zonder bestaan, de participatie van taak in de relatie is dus totaal. Langs de andere kant kunnen er verwerkers zijn die geen taken toegewezen gekregen hebben, deze participatie is dus partieel. TAAK - OP VOORHAND Een taak kan slechts met ´e´en entiteit uit op voorhand corresponderen. Doordat bij het entiteitstype op voorhand elke stap gezien wordt als een aparte entiteit, verkrijgen we 11
een ´e´en-op-´e´en (1:1) relatie. De participatie van beide entiteitstypes in de relatie is partieel. Een taak kan ook afkomstig zijn van een entiteit uit bestelling. Bij het ingeven van een entiteit in op voorhand kan geen overeenkomstige entiteit uit taak bestaan, aangezien deze eruit afgeleid worden. VERWERKER - VERWERKERSTYPE Een verwerker zal altijd behoren tot juist ´e´en verwerkerstype en er kunnen verschillende verwerkers bestaan van een bepaald verwerkerstype zodat we een veel-op-´e´en (N:1) relatie verkrijgen. Een verwerker zal altijd tot een bepaald verwerkerstype behoren, zodat de participatie van verwerker totaal is in de relatie. De participatie van verwerkerstype is partieel aangezien het kan bestaan zonder dat er een verwerker voor bestaat.
3.1.3
Attributen
RECEPT rnr Uniek nummer behorende bij het recept dat we kiezen als primaire sleutel. omschrijving Korte omschrijving van het recept. gang Het is de bedoeling dat de gebruiker kan kiezen tussen 1, 2 of 3, wat respectievelijk staat voor voorgerecht, hoofdgerecht en nagerecht. prijs De prijs van het recept per persoon. personen Dit attribuut geeft aan voor hoeveel personen de bereiding zal ingegeven worden. De bereiding van een recept wordt meestal beschreven voor meer dan ´e´en persoon. Als er dan een bestelling wordt geplaatst, worden de hoeveelheden van de ingredi¨enten en de bereidingstijden herrekend naar het aantal personen in de bestelling. minimum Om ook rekening te kunnen houden met het feit dat niet alle gerechten per persoon kunnen klaargemaakt worden, is dit attribuut nodig. Een taart zal bijvoorbeeld altijd voor meerdere personen klaargemaakt worden. Voor een taart van 4 12
personen, zal het minimum ook 4 zijn. Voor een recept waarbij deze moeilijkheid zich niet voordoet, is het minimum gelijk aan 1. STAP VAN DE BEREIDING stap Uniek nummer behorend bij elke stap van het recept. omschrijving Omschrijving van de stap uit de bereiding. duur De duur van de stap uitgedrukt in minuten. voorraad Sommige stappen (of zelfs volledige gerechten) kunnen reeds op voorhand klaargemaakt worden. Voorraad duidt aan hoeveel van deze stappen reeds werden gemaakt en klaarstaan om verder te gebruiken. vooraf Indien deze stap op voorhand kan klaargemaakt worden, staat vooraf op 1, anders op 0. vfactor Met vfactor wordt een vermenigvuldigingsfactor bedoeld. Hier hoort een waarde in het interval [0, 1] thuis. Een waarde 0 voor de vfactor wil zeggen dat het evenlang duurt om de stap uit te voeren voor 2 personen als voor 1 persoon. Als het dubbel zo lang duurt om de stap uit te voeren, krijgt vfactor de waarde 1. wachttijd Indien er een stap moet toegekend worden aan het materiaal dat bij deze stap wordt gebruikt (een oven bijvoorbeeld), moet dit attribuut op 1 staan. In alle andere gevallen staat het op 0. BESTELLING bnr Een uniek nummer behorende bij de bestelling dat we gebruiken als primaire sleutel. tafel Tafelnummer. tijdstip Het tijdstip waarop deze bestelling werd ingegeven. aantal Het aantal gerechten die besteld werden. afgewerkt Dit attribuut krijgt de waarde 1 als het gerecht klaar is om op te dienen. Als voor deze bestelling de rekening werd opgevraagd, krijgt dit attribuut waarde 2. In alle andere gevallen krijgt het de waarde 0. 13
deadline Met dit attribuut wordt de deadline ingesteld waarop het recept moet klaar zijn om op te dienen. ¨ NT INGREDIE inr Een uniek nummer behorende bij het ingredi¨ent (primaire sleutel). omschrijving Korte omschrijving of naam van het ingredi¨ent. voorraad Aantal eenheden dat in de voorraad zit. eenheid De eenheid, zoals gram of liter. Indien dit attribuut een lege string is, wordt gerekend per stuk. OP VOORHAND vnr Een uniek nummer behorende bij deze entiteit (primaire sleutel). aantal Het aantal van de gespecificeerde stap dat moet klaargemaakt worden. tijdstip Het tijdstip waarop de entiteit werd toegevoegd. afgewerkt Dit attribuut is gelijk aan 1 indien de stap afgewerkt is, en op 0 in het andere geval. TAAK begintijdstip Tijdstip waarop een taak begint. eindtijdstip Tijdstip waarop de taak eindigt. voorraad Dit is het aantal stuks van de uit te voeren stap die uit de voorraad kunnen gehaald worden. aantal Dit is het aantal stuks van de uit te voeren stap die nog effectief moeten klaargemaakt worden.
14
op voorhand Dit attribuut is het aantal stuks van een stap die op voorhand klaargemaakt worden. De waarde van dit attribuut wordt toegevoegd aan het attribuut voorraad van de corresponderende entiteit in stap van de bereiding. Het attribuut kan in twee gevallen worden aangesproken. Dit gebeurt als er een gerecht op voorhand wordt klaargemaakt, of als er bijvoorbeeld een bestelling binnenkomt voor 1 stukje taart die minimum voor 4 personen gemaakt kan worden. VERWERKERSTYPE vtnr Een uniek nummer behorende bij een verwerkerstype (primaire sleutel). omschrijving De omschrijving van een bepaald verwerkerstype. VERWERKER vwnr Uniek nummer behorend bij elke item van een bepaald verwerkerstype. omschrijving De omschrijving van de verwerker. status Staat op 1 indien gebruik kan gemaakt worden van de verwerker en op 0 in het andere geval.
3.1.4
Zwakke entiteitstypes
Als slot zijn er ook nog een aantal entiteitstypes uit paragraaf 3.1.1 die geen eigen sleutelattributen hebben, dit zijn zwakke entiteitstypes. In ons schema zijn dit de entiteitstypes taak, stap van de bereiding en verwerker. De taken die gepland zijn voor een bepaald personeelslid, zijn uniek gedefinieerd door hun begintijdstip doordat een personeelslid niet met twee taken tegelijk kan bezig zijn of beginnen. We nemen dus begintijdstip als parti¨ele sleutel van taak en als identificerend entiteitstype personeelslid. Voor elk recept wordt elke stap van de bereiding uniek gekenmerkt door het attribuut stap zodat dit als parti¨ele sleutel fungeert. Het identificerend entiteitstype van stap van de bereiding is recept. Analoog worden alle verwerkers van een bepaald verwerkerstype aangeduid met een uniek nummer vwnr. We nemen vwnr als parti¨ele sleutels en het identificerend entiteitstype is verwerkerstype. 15
3.2
Databankontwerp uitgaande van het entiteit-relatie diagram
In hoofdstuk 4 van [3] staat het algoritme beschreven om uit het entiteit-relatie diagram de relationele databank te verkrijgen. Het algoritme bestaat uit 7 stappen: Stap 1 • Cre¨eer voor elk regulier entiteitstype E een relatie R. • Voeg aan R alle enkelvoudige attributen van E toe. • Voor de samengestelde attributen van E worden enkel de enkelvoudige componenten als attribuut aan R toegevoegd. • Kies ´e´en van de sleutels van E als primaire sleutel voor R; als de gekozen sleutel samengesteld is, dan vormen de enkelvoudige componenten samen de primaire sleutel. In de eerste stap wordt voor elk niet-zwak entiteitstype een relatie gecre¨eerd waaraan alle enkelvoudige attributen worden toegevoegd. Dit geeft ons de volgende relaties. recepten {rnr, omschrijving, gang, prijs, personen, minimum} bestellingen {bnr, tafel, tijdstip, aantal, afgewerkt, deadline} ingredi¨ enten {inr, omschrijving, voorraad, eenheid} opvoorhand {vnr, tijdstip, aantal, afgewerkt} verwerkerstype {vtnr, omschrijving} Stap 2 • Cre¨eer voor elk zwak entiteitstype W een relatie R. • Voeg alle attributen van W toe aan R (zoals in stap 1). • Als E een identificerend entiteitstype is van W, voeg dan de primaire sleutelattributen van de met E corresponderende relatie als vreemde sleutel toe aan R. • De primaire sleutel van R wordt gevormd door deze vreemde sleutel(s) en de parti¨ele sleutel van W (indien deze bestaat). 16
In de tweede stap doen we hetzelfde met de zwakke entiteitstypen. Om de primaire sleutel te bekomen, wordt bij de relatie bereidingen de primaire sleutel rnr van recepten toegevoegd als vreemde sleutel. Deze vormt dan samen met stap de primaire sleutel. Analoog voor verwerker en taken. bereidingen {recepten.rnr, stap, omschrijving, duur, voorraad, vooraf, vfactor, wachttijd} verwerker {verwerkerstype.vtnr, vwnr, omschrijving, status} taken {verwerker.vtnr, verwerker.vwnr, begintijdstip, eindtijdstip, voorraad, aantal, opvoorhand}
Stap 3 (optie 1) • Voor elk binair 1:1 relatietype R worden de relaties S en T beschouwd, die corresponderen met de betrokken entiteitstypes. • Kies ´e´en van deze relaties, stel S (kies bij voorkeur de relatie die correspondeert met een entiteitstype met een totale participatie). • Voeg de primaire sleutel van T als vreemde sleutel toe aan S. • Voeg eveneens alle attributen van het 1:1 relatietype R toe aan S (als enkelvoudige attributen). Stap 3 (optie 2) • Voor elk binair 1:1 relatietype R worden de relaties S en T beschouwd, die corresponderen met de betrokken entiteitstypes. • Kies ´e´en van deze relaties, stel S (kies bij voorkeur de relatie die correspondeert met een entiteitstype met een totale participatie). • Voeg alle attributen van T toe aan S. • Voeg eveneens alle attributen van het 1:1 relatietype R toe aan S (als enkelvoudige attributen). • Verwijder de relatie T.
17
Opmerking: deze optie is i.h.b. geschikt wanneer beide participaties totaal zijn. Bij de derde stap maken we gebruik van optie 1. Er zijn twee 1:1 relatietypes aanwezig, namelijk stap van de bereiding - taak en taak - op voorhand. We voegen de primaire sleutel rnr, stap toe aan taken als vreemde sleutel. Voor het tweede 1:1 relatietype voegen we vnr ook als vreemde sleutel toe aan taken. taken {verwerker.vtnr, verwerker.vwnr, begintijdstip, eindtijdstip, voorraad, aantal, opvoorhand, bereidingen.rnr, bereidingen.stap, opvoorhand.vnr } Stap 4 • Voor elk regulier (niet-zwak) binair 1:N relatietype R wordt de relatie S gekozen, die overeenkomt met het betrokken entiteitstype aan de N-zijde van R. • Voeg de primaire sleutel van T (de relatie die overeen-komt met het betrokken entiteitstype aan de 1-zijde van R) als vreemde sleutel toe aan S. • Voeg alle attributen van het 1:N relatietype R toe aan S (als enkelvoudige attributen). Dit levert ons: taken {verwerker.vtnr, verwerker.vwnr, begintijdstip, eindtijdstip, voorraad, aantal, opvoorhand, bereidingen.rnr, bereidingen.stap, opvoorhand.vnr, bestellingen.bnr } opvoorhand {vnr, tijdstip, aantal, afgewerkt, bereidingen.stap, bereidingen.rnr } bestellingen {bnr, tafel, tijdstip, aantal, afgewerkt, deadline, recepten.rnr } bereidingen {recepten.rnr, stap, omschrijving, duur, voorraad, vooraf, vfactor, wachttijd, verwerkerstype.vtnr } Stap 5 • Cre¨eer voor elk binair M:N relatietype R een nieuwe relatie S (om R te representeren). • Voeg de primaire sleutels van beide betrokken entiteitstypes als vreemde sleutels toe aan S. • De combinatie van beide vreemde sleutels vormt de primaire sleutel van R.
18
• Voeg alle attributen van het M:N relatietype R toe aan S (als enkelvoudige attributen). Als eerste M:N relatietype hebben we recept - ingredi¨ ent. Hiervoor maken we een nieuwe relatie ingredi¨ ent, waaraan we rnr en inr als vreemde sleutels toevoegen, samen vormen ze de primaire sleutel. Als bijkomend attribuut hebben we ook nog het attribuut hoeveelheid van het relatietype. Ten tweede cre¨eren we voor het relatietype stap van de bereiding - stap van de bereiding de nieuwe relatie precedenten. We voegen een eerste keer rnr, stap toe als vreemde sleutel. rnr hoeft niet nogmaals toegevoegd worden aangezien we binnen hetzelfde recept blijven. Tenslotte noemen we precedent de stap die moet afgewerkt worden voor de stap gedefinieerd in bereidingen.stap. Deze drie vormen samen de primaire sleutel van de relatie precedenten. ingredi¨ ent {ingredienten.inr, recepten.rnr , hoeveelheid} precedenten {bereidingen.rnr, bereidingen.stap, precedent} Stap 6 • Cre¨eer voor elk meerwaardig attribuut A van het entiteitstype E een nieuwe relatie R. • Voeg de primaire sleutel van de relatie S die overeenkomt met E als vreemde sleutel toe aan R. • Voeg een attribuut toe dat een waarde voor A kan bevatten. Als A is samengesteld, dan moet er een attribuut worden toegevoegd voor elke enkelvoudige component. • Alle attributen samen vormen de primaire sleutel van R. Stap 7 • Cre¨eer voor elk n-air relatietype R (n > 2) een nieuwe relatie S (om R te representeren). • Voeg de primaire sleutels van (de relaties die overeenkomen met) alle betrokken entiteitstypes als vreemde sleutels toe aan S.
19
• De primaire sleutel van S is meestal de combinatie van al deze vreemde sleutels; indien de kardinaliteit van een betrokken entiteitstype 1 is, moet de vreemde sleutel van dit entiteitstype worden weggelaten uit de primaire sleutel van S. • Voeg alle attributen van R toe aan S (als enkelvoudige attributen). De twee laatste stappen zijn niet van toepassing. Er zijn namelijk geen meerwaardige attributen en geen n-aire relatietypes met n > 2.
3.3
De resulterende databank
Nu we het volledige ontwerp van de databank hebben, kunnen we ze ingeven met behulp van phpMyAdmin. Hiervoor moet gelet worden op een aantal dingen. Om met vreemde sleutels te kunnen werken is het noodzakelijk dat het tabeltype ingesteld staat op inno db1 .
Figuur 3.2: Instellen van vreemde sleutels van de tabel bereidingen
Belangrijk is ook dat bij alle vreemde sleutels de opties on delete cascade en on update cascade staan ingesteld. Als de gebruiker een entiteit probeert te wissen of wijzigen, en er ´e´en of meerdere entiteiten zijn in een andere tabel die naar de eerste entiteit verwijzen, zal de eerste entiteit gewist of gewijzigd worden en automatisch ook alle corresponderende entiteiten uit de andere tabel.2 Dit heeft bijvoorbeeld tot gevolg dat als een recept wordt verwijderd, dat dan ook alle corresponderende stappen worden 1 2
http://dev.mysql.com/doc/refman/5.0/en/innodb.html http://dev.mysql.com/doc/refman/5.0/en/innodb-foreign-key-constraints.html
20
verwijderd uit de tabel bereidingen. Geven we alle relaties met hun attributen in in de databank, dan verkrijgen we volgende tabellen. Tabel 3.1: Structuur van de tabel bereidingen
Veld
Type
Null Standaardwaarde
rnr
int(11)
Nee
1
stap
int(11)
Nee
1
text
Nee
duur
int(10)
Nee
1
vtnr
int(11)
Ja
NULL
voorraad
int(11)
Nee
0
vooraf
(1)
Nee
0
vfactor
double
Nee
0.5
(1)
Nee
0
omschrijving
wachttijd
Tabel 3.2: Structuur van de tabel bestellingen
Veld
Type
Null Standaardwaarde
bnr
int(11)
Nee
tafel
int(11)
Nee
1
rnr
int(11)
Nee
1
tijdstip
datetime
Nee
0000-00-00 00:00:00
aantal
int(11)
Nee
1
afgewerkt
int(2)
Nee
0
deadline
timestamp
Ja
0000-00-00 00:00:00
Tabel 3.3: Structuur van de tabel ingredient
Veld
Type
Null Standaardwaarde
rnr
int(11)
Nee
1
inr
int(11)
Nee
1
hoeveelheid
double
Nee
0
21
Tabel 3.4: Structuur van de tabel ingredienten
Veld inr
Type
Null Standaardwaarde
int(11)
Nee
omschrijving varchar(255)
Nee
voorraad
int(11)
Nee
eenheid
varchar(10)
Nee
0
Tabel 3.5: Structuur van de tabel precedenten
Veld
Type
Null Standaardwaarde
rnr
int(11)
Nee
1
stap
int(11)
Nee
2
precedent
int(11)
Nee
1
Tabel 3.6: Structuur van de tabel recepten
Veld rnr
Type
Null Standaardwaarde
int(11)
Nee
omschrijving varchar(255)
Nee
gang
int(2)
Nee
1
prijs
double
Nee
1
personen
int(11)
Nee
1
minimum
int(11)
Nee
1
Tabel 3.7: Structuur van de tabel taken
Veld
Type
Null Standaardwaarde
vtnr
int(11)
Nee
1
vwnr
int(11)
Nee
1
begintijdstip
timestamp
Ja
0000-00-00 00:00:00
eindtijdstip
timestamp
Ja
0000-00-00 00:00:00
rnr
int(11)
Nee
1
stap
int(11)
Nee
1
bnr
int(11)
Ja
NULL
22
Tabel 3.7: Structuur van de tabel taken (vervolgd)
Veld
Type
Null Standaardwaarde
voorraad
int(11)
Nee
0
aantal
int(11)
Nee
1
opvoorhand
int(11)
Nee
0
vnr
int(11)
Ja
NULL
Tabel 3.8: Structuur van de tabel verwerker
Veld
Type
Null Standaardwaarde
vtnr
int(11)
Nee
1
vwnr
int(11)
Nee
1
omschrijving varchar(255)
Nee
status
Nee
(1)
0
Tabel 3.9: Structuur van de tabel verwerkerstype
Veld vtnr
Type
Null Standaardwaarde
int(11)
Nee
omschrijving varchar(255)
Nee
Tabel 3.10: Structuur van de tabel opvoorhand
Veld
Type
Null Standaardwaarde
vnr
int(11)
Nee
rnr
int(11)
Nee
1
stap
int(11)
Nee
1
tijdstip
timestamp
Ja
0000-00-00 00:00:00
aantal
int(11)
Nee
1
(1)
Nee
0
afgewerkt
23
Hoofdstuk 4 Het critical path scheduling algoritme 4.1
Inleiding
In onze huidige maatschappij wordt het effici¨ent plannen en verdelen van taken steeds belangrijker. Denken we maar aan het gebruik van operatiekamers en gespecialiseerde apparatuur in ziekenhuizen, het plannen en verdelen van werk onder verschillende machines in een bedrijf of het verdelen van taken in een computersysteem met meerdere processors. Het oplossen van dergelijke problemen wordt tot op heden meestal met de hand gedaan, maar het gebruik van wiskundige algoritmen neemt snel toe. De kern van ons planningssysteem bestaat uit een algoritme die de taakverdeling voor het keukenpersoneel opstelt. Dit algoritme moet aan de hand van de binnenkomende bestellingen de taken in de keuken zo effici¨ent mogelijk verdelen waarbij rekening gehouden wordt met verschillende voorwaarden en omstandigheden. Zo moet er bijvoorbeeld rekening gehouden worden met welke personeelsleden aanwezig zijn, de beperkingen in de opeenvolging van de taken en de optimale wachttijd tussen twee gangen. Het algoritme dat we hier gebruiken is gekend als het critical path scheduling algoritme [6]. In paragraaf 4.2 van dit hoofdstuk bespreken we de algemene werking van dit algoritme. In paragraaf 4.3 gaan we dan dieper in op de implementatie ervan in ons taakplanningssysteem.
24
4.1.1
Definities
In een typisch taakplanningssysteem moeten een aantal activiteiten op een zo effici¨ent mogelijke manier ingepland worden. Een activiteit bestaat uit ´e´en of meerdere taken die allemaal moeten afgewerkt zijn om de activiteit als afgewerkt te kunnen beschouwen. Elke taak wordt uitgevoerd door ´e´en verwerker (dit kan bijvoorbeeld een machine, een mens of een robot zijn) en heeft een vooraf bepaalde uitvoeringstijd. Meestal zijn er meerdere verwerkers beschikbaar. Voor de eenvoud veronderstellen we dat elke taak door gelijk welke verwerker uitgevoerd kan worden.
4.1.2
Veronderstellingen
Als bijkomende problemen hebben we nog het feit dat sommige taken een hogere prioriteit hebben dan andere en de beperking dat sommige taken moeten afgewerkt zijn voordat andere taken kunnen beginnen. Om deze problemen te verwerken worden de volgende veronderstellingen gemaakt: • Als een verwerker begint aan een taak zal deze ononderbroken verder werken tot de taak afgewerkt is. • Geen enkele verwerker blijft vrijwillig zonder werk. Als er een verwerker is zonder werk en er komt een taak beschikbaar dan zal de verwerker hiermee onmiddellijk starten. • De beperkingen voor de volgorde van de taken van een activiteit worden voorgesteld in een gerichte graaf (zie figuur 4.1). Deze beperkingen moeten realistisch zijn (zie paragraaf 4.1.3). • De taken zijn geordend in een prioriteitenlijst die onafhankelijk is van het precedentiediagram. In deze lijst worden de taken geordend volgens een bepaald criterium.
4.1.3
Precedentiediagram
Het precedentiediagram van een activiteit is een enkelvoudige gerichte graaf waarmee de volgorde van de taken waaruit de activiteit bestaat, voorgesteld wordt. De knopen stellen hierin de verschillende taken voor. Binnenin de knopen staat de geschatte tijdsduur van 25
5
7 T7
8
5 T8
3 T5
T6
6 T1
T2
9
4 T3
T4
Figuur 4.1: Precedentiediagram
de taak, erbuiten het nummer van de taak. De pijlen in het precedentiediagram stellen de relatie ‘moet uitgevoerd worden v´o´or’ voor. Uit de graaf in figuur 4.1 kunnen we bijvoorbeeld afleiden dat T1 moet uitgevoerd worden v´o´or taak T2 , dat T3 en T5 maar kunnen beginnen nadat taak T2 afgewerkt is en dat T7 en T8 onafhankelijke taken zijn. Verder kunnen we nog het kritieke pad (zie figuur 4.2) in het precedentiediagram defini¨eren. Dit is het pad in de graaf waarvan de som van de duur van alle knopen in dit pad het grootst is. In het voorbeeld uit figuur 4.1 is het kritieke pad T1 − T2 − T3 − T4 . De totale duur van dit pad bedraagt 27 tijdseenheden. Het kritieke pad is belangrijk omdat de duur om een activiteit af te werken nooit korter kan zijn dan de totale duur van de taken in dit pad.
4.1.4
Doelstellingen
Het is ook belangrijk om de doelstellingen van het planningssysteem voorop te stellen. Enkele mogelijke doelstellingen zijn: • De totale tijdsduur van de activiteiten minimaliseren. • De tijdsduur waarin verwerkers geen werk hebben minimaliseren. 26
5
7 T7
5 T8
8
3 T5
T6
6 T1
T2 9
4 T3
T4
Figuur 4.2: Kritieke pad in het precedentiediagram
• Het minimum aantal verwerkers bepalen om de activiteit binnen een bepaalde tijds5 te werken. 7 5 3 duur af T7 T6 8 Voor het taakplanningssysteem in Tgastronomische keukensT5gaan we uit van de eerste doelstelling, we zullen ons dus hiertoe beperken. 6
4.2
T2 Lijstverwerkingsalgoritme
In deze paragraaf zullen we de werking van de lijstverwerkingssalgoritmen bespreken. 9 4 Het critical path scheduling algoritme dat we gebruiken is een lijstverwerkingsalgoritme. Een T4 3 taak wordt als klaar om te starten beschouwd op een bepaaldTtijdstip als alle voorafgaande taken in het precedentiediagram op dit tijdstip afgewerkt zijn. In figuur 4.1 zijn de taken T1 , T7 en T8 klaar om te starten op tijdstip 0. Met deze taken kan dus onmiddellijk gestart worden. Taak T2 daarentegen kan maar starten als taak T1 afgewerkt is, dit is dus 8 tijdseenheden na de start van taak T1 . 5 7 5 3
4.2.1
T7 Werking
T8
T5
T6
Wanneer op een bepaald ogenblik een verwerker zonder werk valt, wordt de eerstvolgende taak aan de verwerker toegekend. De eerstvolgende taak is de eerste taak in de prioritei27 9
4 T3
T4
tenlijst die op dat moment klaar is om te starten en nog niet aan een verwerker toegekend is. Als we dit algoritme toepassen op het voorbeeld uit figuur 4.1, met de prioriteitenlijst T8 − T7 − ... − T1 en twee verwerkers krijgen we het volgende tijdschema. Verwerker 1
8
Verwerker 2
2
7
0
5
1
5
7
6
4
3
13
19
24
27 28
32
Figuur 4.3: Tijdschema voor prioriteitenlijst T8 − T7 − ... − T1
Hoe wordt het tijdschema in figuur 4.3 nu door het algoritme opgesteld? Taak T8 is de eerste taak in de prioriteitenlijst die op tijdstip 0 klaar is om te starten en wordt dus aan verwerker 1 toegekend. Taak T7 , de volgende taak in de prioriteitenlijst, is ook klaar om te starten op tijdstip 0 en wordt dus aan verwerker 2 toegekend. Op tijdstip 5 valt verwerker 2 zonder werk. De eerste (en enige) taak in de prioriteitenlijst die klaar is op tijdstip 5 is taak T1 . Op tijdstip 7 valt verwerker 1 zonder werk. Uit het precedentiediagram in figuur 4.1 kunnen we echter afleiden dat er geen enkele taak klaar is om te starten. Pas na het afwerken van taak T1 kan er opnieuw een taak toegevoegd worden. Verwerker 1 staat dus stil van tijdstip 7 tot tijdstip 13. Het vervolg van het tijdschema wordt op een analoge manier opgesteld.
4.2.2
Optimaliseren van het tijdschema
In figuur 4.3 zijn er relatief lange periodes waarin verwerkers stil staan, waarschijnlijk is het tijdschema niet optimaal. Welke parameters kunnen we nu aanpassen zodat de taken optimaal verdeeld worden? In het lijstverwerkingsalgoritme zijn er vier factoren die het tijdschema be¨ınvloeden: • de tijdsduur van de taken • het aantal verwerkers • het precedentiediagram • de ordening van de taken in de prioriteitenlijst 28
In het taakplanningssysteem voor gastronomische keukens zijn de eerste drie factoren niet als variabel te beschouwen. De tijdsduur van de taken en het precedentiediagram wordt bepaald door het recept. Het aantal verwerkers (personeelsleden en keukenmateriaal) beschouwen we ook als constant. De vierde factor is dus de enige die we kunnen wijzigen om het tijdschema te optimaliseren. Als we nu hetzelfde precedentiediagram behouden maar de prioriteitenlijst veranderen naar T1 − T2 − ... − T8 bekomen we het tijdschema zoals in figuur 4.4. Verwerker 1
1
Verwerker 2
2
7
0
3
5
8
5
8
12
14
4
6
19
22 23
27
Figuur 4.4: Tijdschema voor prioriteitenlijst T1 − T2 − ... − T8
Het tijdschema is nu optimaal omdat de opeenvolging T1 − T2 − T3 − T4 overeenkomt met het kritieke pad in het precedentiediagram (zie figuur 4.2). Uit het voorbeeld blijkt dat voor verschillende prioriteitenlijsten een verschillend tijdschema kan gegenereerd worden met eventueel een verschillende volgorde van de taken en een andere afwerkingstijd. Voor welke prioriteitenlijst is het tijdschema nu optimaal? Voor een activiteit bestaande uit n taken kunnen n! prioriteitenlijsten opgesteld worden. Voor een activiteit bestaande uit 8 taken zijn er dus al 40.320 mogelijkheden. Het komt er dus op neer om een methode te vinden waarmee een prioriteitenlijst kan opgesteld worden die het optimale tijdschema genereert. Tot op heden is er echter geen enkele methode gekend die in alle omstandigheden hiertoe in staat is.
4.2.3
Critical path scheduling algoritme
Het critical path scheduling algoritme is een veelgebruikt lijstverwerkingsalgoritme die de prioriteitenlijst ordent volgens het kritieke pad. Taken aan het begin van het precedentiediagram worden vooraan in de prioriteitenlijst geplaatst zodat deze het afwerken van de activiteit zeker niet vertragen. Het algoritme werkt als volgt: • Het kritieke pad in het precedentiediagram wordt bepaald. 29
• De eerste taak in dit pad wordt aan de prioriteitenlijst toegevoegd. • Deze taak en alle aanliggende pijlen worden uit het precedentiediagram verwijderd. • De eerste drie stappen worden opnieuw uitgevoerd tot alle taken aan de prioriteitenlijst toegevoegd zijn. Voor het precedentiediagram uit figuur 4.1 geeft dit de volgende oplossing: 5
7
5
T7
T8
T7
8
8
33
T5 T5
T8
T6
6
6 T1
T1
5 5
7
T2
T2
9
9
4
4 T3
T4
T3
T4
Het kritieke pad is T1 − T2 − T3 − T4 . De prioriteitenlijst begint dus met T1 . 5
5
7
7
T7
T7
5
3
5
T8
T8
T5
3
T5
T6
T6
6
6
T2
T2
9
4 T3
9
4 T4
T3
T4
5 7 uit het diagram 5 verwijderd. Het kritieke 3 Taak T1 en de aanliggende pijl worden pad wordt T7 T5 T6 dan T2 − T3 − T4 , de prioriteitenlijst TT18 − T2 .
5
7 T7
5 T8
3 T5
T6
9
4 T3
30
9
T4
4 T3
T4
T2 9
4 T3
5
7 T7
5 T8
T4
3 T5
9
T6
4 T3
T4
Taak T2 en de aanliggende pijlen worden uit het diagram verwijderd. Het kritieke pad is nu T3 − T4 en de prioriteitenlijst T1 − T2 − T3 . 5 5
7 7 T7 T7
5 5 T8 T8
3 3 T5 T5
T6 T6
4 4 T4 T4
Op dezelfde manier bekomt men nu de prioriteitenlijst T1 − T2 − T3 − T5 . 5 5
3 3
7 7 T7 T7
T6 T6
T8 T8
4 4 T4 T4
De overblijvende onafhankelijke taken worden volgens dalende tijdsduur toegevoegd aan de prioriteitenlijst. 31
De uiteindelijke prioriteitenlijst is dan T1 − T2 − T3 − T5 − T8 − T7 − T4 − T6 . Als we nu het lijstverwerkingsalgoritme toepassen op deze prioriteitenlijst, het precedentiediagram uit figuur 4.1 en twee verwerkers bekomen we het volgende tijdschema. Verwerker 1
1
Verwerker 2
2
8
0
3
5
7
7 8
12
14
4
6
19
22 23
27
Figuur 4.5: Tijdschema voor een optimale prioriteitenlijst
4.2.4
Besluit
Het critical path scheduling algoritme zoals hierboven beschreven genereert in de meeste gevallen een aanvaardbare oplossing. Onder sommige omstandigheden presteert het algoritme echter minder goed. Dit is veelal het gevolg van een te hoge complexiteit van het precedentiediagram. In ons taakplanningssysteem voor gastronomische keukens verwachten we echter geen noemenswaardige problemen omdat de complexiteit van de precedentiediagrammen beperkt is.
4.3
Implementatie
In deze paragraaf zullen we de implementatie van het critical path scheduling algoritme in PHP bespreken.
4.3.1
Concept
In ons taakplanningssysteem moet het algoritme aan de hand van de binnenkomende bestellingen een werkschema opstellen voor het klaarmaken van de verschillende gerechten. Om het algemene concept van het algoritme te verduidelijken hebben we het schema uit figuur 4.6 opgesteld. De gegevens die het algoritme nodig heeft zijn opgeslagen in de databank (zie hoofdstuk 3). De volgende tabellen worden door het algoritme gebruikt: 32
Tabellen VERWERKER
VERWERKERSTYPE
RECEPTEN
Databank restaurant OPVOORHAND
BESTELLINGEN
BEREIDINGEN
TAKEN
werkschema.php
figuur.php
Figuur 4.6: Algemeen concept
33
• In de tabel bestellingen staat welke recepten klaargemaakt moeten worden en voor hoeveel personen. • Uit de tabellen verwerker en verwerkerstype haalt het algoritme de aanwezige personeelsleden en het beschikbaar keukenmateriaal. De taken in het werkschema worden onder deze personeelsleden verdeeld. • De tabellen recepten en bereidingen bevatten de verschillende stappen voor het klaarmaken van de gerechten. • In de tabel opvoorhand staan de recepten of stappen die op voorhand klaargemaakt worden wanneer er weinig bestellingen zijn. Aan de hand van deze gegevens kent het algoritme (opgeslagen in werkschema.php) taken toe aan de personeelsleden en het keukenmateriaal. De duur van de taken wordt bepaald met de volgende formule: totduur = duur(1 + vermenigvuldigingsf actor(
aantal − 1)) personen
(4.1)
Hierin stelt duur de tijdstuur voor van de stap van de bereiding voor het aantal personen (personen) waarvoor het gerecht opgeslagen is. Totduur is dan de tijdsduur om deze stap klaar te maken voor aantal personen. De vermenigvuldigingsfactor speelt hierin ook een rol (zie paragraaf 3.1.3). We bewijzen hier nog dat de formule in alle omstandigheden klopt. De totale duur mag natuurlijk nooit kleiner of gelijk zijn aan 0. Aangezien de duur altijd strikt groter is dan nul, moet dus 1 + vermenigvuldigingsf actor( of vermenigvuldigingsf actor(
aantal − 1) > 0 personen
aantal − 1) > −1 personen
De vermenigvuldigingsfactor is altijd gelegen in het interval [0, 1]. Als de vermenigvuldigingsfactor gelijk is aan nul, volgt uit formule (4.1) dat de totale duur gelijk is aan de duur, wat uiteraard voor zich spreekt. Voor het geval dat de vermenigvuldigingsfactor
34
gelegen in het interval ]0, 1] volgt aantal − 1 > −1 personen of
aantal >0 personen
Aantal en personen zijn beide getallen groter dan nul, zodat de formule klopt. De berekende taken worden opgeslagen in de tabel taken. Het bestand figuur.php genereert daarna een GANTT-grafiek (zie paragraaf 2.2) waarin de verschillende records uit de tabel taken grafisch weergegeven worden. Zoals reeds vermeld is het algoritme opgeslagen in het bestand werkschema.php. Bij het inladen van dit bestand in de webbrowser wordt het algoritme uitgevoerd door de PHPparser en wordt het werkschema weergegeven. Het bestand moet nu op regelmatige basis opnieuw ingeladen worden om nieuwe bestellingen te verwerken en het werkschema upto-date te houden. Om dit te realiseren laten we het bestand automatisch vernieuwen. Het interval hiervoor is instelbaar via config.php (zie hoofdstuk 6).
HTMLhoofding
Functies
Algoritme
Weergave werkschema
Weergave uit te voeren stappen
Figuur 4.7: Opbouw werkschema.php
In het begin van werkschema.php staan enkele functies (zie figuur 4.7) die in het algoritme gebruikt worden. Daarna komt het eigenlijke algoritme. De daaropvolgende codefragmenten in werkschema.php hebben te maken met de weergave van het werkschema en zijn dus niet relevant voor het algoritme. Ze worden hier dan ook niet besproken. Wel is er een korte bespreking in hoofdstuk 5.
35
3 min
Stap 5 3 min
Stap 3 1 min
4.3.2
Stap 4
Functies
3 min
function precedentiediagram($db,$bnr) Deze functie stelt het precedentiediagram op voor alle gerechten die besteld werden door ´e´en tafel en dit voor ´e´en gang. Over welke tafel en gang het gaat wordt bepaald aan de hand van het bestellingsnummer ($bnr ). Voorgerecht 2: Beursje met scampi en een coulis van rode paprika Vervolgens wordt een lijst van alle verschillende recepten opgesteld die voor deze tafel en gang klaargemaakt moeten worden. De precedentiediagrammen voor alle recepten uit deze gang worden opgesteld en samengevoegd tot ´e´en groot diagram. Het samengevoegde
Stap 1
Stap 3
Stap 2
Stap 4
Stap 6
Stap 7
Stap 5
Stap 8
Figuur 4.8: Typisch precedentiediagram
2:0.325:50:0:8 2:1.85:50:1:5 2:9.3:50:1:4 2:0.325:50:0:8 2:10:50:0:7 2:0.8:50:1:6 2:3.5:50:1:2 2:0.325:50:0:8 2:10:50:0:7 2:0.8:50:1:6 2:1:50:1:3 2:6.25:50:1:1 Tabel 4.1: Precedentiediagram opgeslagen in een array
diagram wordt opgeslagen in een array (zie tabel 4.1) die teruggegeven wordt als resultaat van de functie. De rijen in de array stellen de paden van het precedentiediagram uit figuur 4.8 voor. De elementen van de array bevatten de volgende parameters: receptnummer:duur:bestellingsnummer:vooraf:stap
36
De parameters duur en vooraf dienen om het kritieke pad te kunnen bepalen. De parameters receptnummer, bestellingsnummer en stap dienen om elke taak uniek te kunnen identifici¨eren. function kritiekpad($diagram) Deze functie bepaalt het kritieke pad uit het precedentiediagram dat meegegeven wordt via de parameter $diagram. Deze parameter is het resultaat van de functie precedentiediagram. Als eerste stap wordt de totale tijdsduur van elk pad berekend. Deze gegevens worden opgeslagen in een lijst. In een tweede stap wordt het kritieke pad bepaald waarvan de laatste stap vooraf uitgevoerd mag worden (vooraf = 1). Als er geen enkele stap gevonden is wordt het kritieke pad bepaald waarvan de laatste stap niet vooraf uitgevoerd mag worden (vooraf = 0). Als resultaat geeft de functie de positie van het kritieke pad in de array terug. function zoekbegintijdstip($vtnr,$vwnr,$duur,$minimum,$db) Hiermee wordt voor een verwerker (gekenmerkt door $vtnr en $vwnr ) het minimale tijdstip (groter dan $minimum) bepaald waar een taak (met een tijdsduur $duur ) aan het werkschema kan toegevoegd worden. In een eerste stap worden alle lege tijdssloten in het werkschema van deze verwerker opgehaald. Daarna wordt er gezocht naar het eerste tijdsslot waarbinnen een taak met tijdsduur $duur past. Als tweede voorwaarde mag het begintijdstip van dit tijdslot niet v´o´or $minimum liggen. Als er geen enkel tijdsslot gevonden is, wordt de taak toegevoegd aan het einde van het werkschema van deze verwerker. Als resultaat geeft de functie het tijdstip terug waar het begin van de taak geplaatst moet worden. function minstewerk($vtnr,$db) Bepaalt de verwerker van het type $vtnr met het minste werk. Als eerste stap wordt het laatste eindtijdstip uit de tabel taken opgehaald. Daarna wordt voor iedere verwerker de som van de werkduur tot aan dit tijdstip berekend. Het resultaat van de functie is het nummer van de verwerker met de kleinste werkduur. function zoekpersoon($bnr,$db) Deze functie bepaalt het personeelslid aan wie een volgende taak van bestelling $bnr kan toegevoegd worden. Als eerste stap wordt het personeelslid met het minste werk opgehaald (p1 ). Vervolgens wordt het eindtijdstip t1 van de laatste taak in het werkschema van dit personeelslid opgehaald. Daarna wordt per personeelslid waarvan de laatste taak deel uitmaakt van de bestelling $bnr het eindtijdstip van de laatste taak opgehaald. Het kleinste tijdstip t2 (corresponderend met personeelslid 37
p2 ) uit deze lijst wordt vergeleken met het eerst opgehaalde tijdstip t1 . Als t1 + 5 kleiner is dan t2 + spreidingsf actor geeft de functie p1 als resultaat terug. In het andere geval is het resultaat p2 . De spreidingsfactor is een factor tussen nul en vijf en wordt opgehaald uit het configuratie-bestand config.php (zie hoofdstuk 6).
4.3.3
Algoritme
In het tweede gedeelte van werkschema.php staat dan het eigenlijke algoritme. Het verloop van de stappen wordt grafisch voorgesteld in figuur 4.9. Als eerste stap wordt de verbinding met de databank gemaakt. $db = mysql_connect (’localhost’,’root’,’root’); mysql_select_db(’restaurant’, $db); Daarna worden de afgewerkte taken voor stappen die op voorhand klaargemaakt worden verwerkt. De taken waarvan het eindtijdstip v´o´or het huidige tijdstip ligt worden geselecteerd en de voorraad in de tabel bereidingen wordt aangepast. In de tabel opvoorhand wordt de taak als afgewerkt gemarkeerd en tenslotte wordt de taak verwijderd.
In een volgende stap worden de afgewerkte bestellingen verwerkt. Een bestelling wordt als afgewerkt beschouwd als alle stappen van de bereiding van het gerecht afgewerkt zijn. We selecteren de bestellingen waarvan de laatste stap afgewerkt is. Voor elke bestelling wordt de voorraad van de gerechten en de ingredi¨enten aangepast. Daarna worden de desbetreffende stappen uit de tabel taken verwijderd en wordt de bestelling als afgewerkt gemarkeerd. Als laatste stap v´o´or het opstellen van het nieuwe werkschema worden de taken waaraan nog geen enkele verwerker begonnen is verwijderd uit de tabel taken. Dit is noodzakelijk om wijzigingen van externe factoren, zoals het aantal aanwezige personeelsleden, zo snel mogelijk op te vangen. Als bijvoorbeeld een personeelslid op afwezig gezet wordt, zullen bij de eerstvolgende berekening van het werkschema de reeds toegekende taken verdeeld worden onder de andere personeelsleden. Enkel de taak waaraan hij/zij bezig was dient nog afgewerkt te worden. Eerst worden de taken waarvan het begintijdstip na het huidige tijdstip ligt uit de tabel taken verwijderd. Daarna worden de deadlines opnieuw ingesteld. Voor voorgerechten wordt de deadline ingesteld op de grootste van de volgende twee mogelijkheden. 38
Parameters ophalen
Ja
Nee
Stap toegevoegd?
Openen databank Nee
Afgewerkte gerechten op voorhand
Precedenten?
Bestelling selecteren
Ja
Alle precedenten toegevoegd?
Afgewerkte bestellingen
Nee
Precedentiediagram opstellen
Ja
Verwerker bepalen Nog niet begonnen taken
Nee
Zelfde verwerker?
Prioriteitenlijst opstellen Ja
Begintijdstip bepalen Nieuw werkschema
Stappen toevoegen Eindtijdstip bepalen
Gerechten op voorhand Deadlines aanpassen
Stap toevoegen
Figuur 4.9: Stappen van het algoritme
39
• tijdstip van de bestelling + wachttijd • grootste eindtijdstip van de taken die al begonnen zijn wachttijd stelt de optimale tijdsduur tussen twee gangen voor. Deze parameter is instelbaar via de configuratiepagina van de website. Voor hoofd- en nagerechten wordt de deadline ingesteld op deadline van de vorige gang + wachttijd. Indien er geen vorige gang is (bijvoorbeeld geen voorgerecht besteld) wordt de deadline ingesteld op tijdstip van de bestelling + wachttijd. Na het voorbereidende werk kan nu gestart worden met het opstellen van het nieuwe werkschema (tweede kolom in figuur 4.9). Als eerste stap worden de bestellingen die nog niet afgewerkt zijn geselecteerd en geordend volgens stijgende deadline. Op deze manier worden de eerste bestellingen ook eerst verwerkt. Voor de eerste bestelling in de lijst wordt het precedentiediagram opgesteld. Daarna wordt de prioriteitenlijst uit het precedentiediagram opgesteld. Alle stappen uit de prioriteitenlijst worden nu ´e´en voor ´e´en toegevoegd aan de tabel taken (derde kolom in figuur 4.9). Het receptnummer, de bereidingsduur, het bestellingsnummer en de stap worden uit het eerste element van de prioriteitenlijst gehaald. Vervolgens wordt het aantal personen die het gerecht besteld hebben en het minimum aantal personen voor wie het gerecht klaargemaakt moet worden opgehaald. Met de parameters receptnummer,stap en bestellingsnummer wordt dan gecontroleerd of de stap nog niet toegevoegd is aan het werkschema. Als dit nog niet het geval is, kan de verwerking van de stap gebeuren. Eerst worden de precedenten gecontroleerd. Hiervoor zijn drie mogelijkheden: 1. De huidige stap heeft geen precedenten. 2. De huidige stap heeft wel precedenten en deze zijn reeds aan het werkschema toegevoegd. 3. De huidige stap heeft precedenten maar deze zijn nog niet allemaal aan het werkschema toegevoegd. In de eerste twee gevallen kan de stap toegevoegd worden en in het derde geval wordt de stap overgeslagen. Als er geen precedenten zijn (mogelijkheid 1) wordt bepaald aan welk personeelslid of welk 40
apparaat uit de keuken de taak moet toegekend worden. Daarna wordt met de functie zoekbegintijdstip het tijdstip bepaald waar de taak in het werkschema moet toegevoegd worden. De parameter $overgeslagen wordt eventueel op false gezet. Dit om een stap in de prioriteitenlijst die overgeslagen werd straks opnieuw te kunnen verwerken. Als er wel precedenten zijn moet gecontroleerd worden of deze al dan niet toegevoegd zijn. De precedenten van de huidige stap, waarvoor geen stap in de tabel taken te vinden is, worden bepaald. Als er geen enkel precedent nog niet toegevoegd is (mogelijkheid 2), kan de stap toegevoegd worden aan de tabel taken. Er wordt bepaald of de taak aan een personeelslid of aan een apparaat uit de keuken moet toegekend worden. In het eerste geval worden het eindtijdstip van het laatste precedent en het personeelslid die deze taak uitvoert opgehaald. Indien mogelijk wordt de huidige taak aan dit personeelslid toegekend. Dit om de stappen van de bereiding van een gerecht zoveel mogelijk door ´e´enzelfde personeelslid te laten uitvoeren. Als dit niet mogelijk is wordt met de functies zoekpersoon en zoekbegintijdstip een ander personeelslid en begintijdstip gezocht. Als de taak echter aan een apparaat uit de keuken moet toegekend worden, wordt bepaald aan welk apparaat en op welk tijdstip. Eventueel wordt terug de parameter $overgeslagen op false gezet. Als nog niet alle precedenten toegevoegd zijn (mogelijkheid 3) wordt de parameter $overgeslagen op true gezet. Als de stap toegevoegd kan worden ($overgeslagen staat op false) moet nog het eindtijdstip van de taak bepaald worden. Dit hangt af van het aantal personen die het gerecht besteld hebben, de voorraad van (delen van) het gerecht en het minimum aantal personen waarvoor het gerecht moet klaargemaakt worden. Als er geen voorraad meer is dan is het eindtijdstip van de taak begintijdstip + bereidingsduur. Eventueel wordt het gerecht voor meer personen klaargemaakt dan het aantal personen die het gerecht besteld hebben (als $minimum groter is dan $aantal ). Alle attributen zijn berekend en de stap kan nu toegevoegd worden aan de tabel taken. Als de voorraad groter of gelijk is aan het aantal personen die het gerecht besteld hebben, moet de stap niet meer uitgevoerd worden. De stap wordt als een taak van 1 seconde toegevoegd aan het werkschema. Dit om bij het toevoegen van een volgende stap geen problemen te krijgen bij het controleren van de precedenten. Als de voorraad kleiner is dan het aantal personen die het gerecht besteld hebben wordt berekend voor hoeveel personen de stap nog moet klaargemaakt worden. De bereidingsduur wordt herberekend met formule (4.1) en de stap wordt uiteindelijk aan de tabel taken toegevoegd. 41
Als het eindtijdstip van de toegevoegde taak voorbij de deadline ligt, wordt de deadline voor alle bestellingen van dezelfde tafel en gang verschoven. De deadline voor de volgende gangen wordt daarna ook aangepast. De volgende stap in de prioriteitenlijst wordt nu geselecteerd en op analoge manier verwerkt. Als tenslotte alle stappen toegevoegd zijn, wordt opnieuw de lijst met nog niet afgewerkte bestellingen opgesteld en geordend volgens deadline. De eerstvolgende bestelling wordt nu verwerkt. Als laatste stap in werkschema.php worden nog de bereiding van de gerechten die in voorraad klaargemaakt worden toegevoegd. Door deze als laatste stap aan het werkschema toe te voegen krijgen ze automatisch een lagere prioriteit dan de gewone bestellingen. Alle nog niet afgewerkte stappen worden uit de tabel opvoorhand gehaald en ´e´en voor ´e´en toegevoegd aan het werkschema. Als er al een stap van het huidige gerecht toegevoegd is, wordt de huidige stap aan hetzelfde personeelslid toegekend (als de status van het personeelslid op aanwezig staat). Als dit niet het geval is, wordt de stap toegekend aan het personeelslid met het minste werk. Daarna wordt de duur, het begintijdstip en het eindtijdstip van de stap berekend. Tenslotte wordt de stap toegevoegd aan de tabel taken.
4.4
Besluit
Het algoritme genereert volgens ons een aanvaardbare oplossing. De gerechten voor de opeenvolgende gangen worden in de juiste volgorde en na een instelbare wachttijd klaargemaakt. De eerste bestellingen worden ook eerst verwerkt, delen van de gerechten die niet op voorhand klaargemaakt kunnen worden staan achteraan in het werkschema, de spreidingsfactor zorgt ervoor dat de verschillende stappen van een bereiding zoveel mogelijk aan hetzelfde personeelslid toegekend worden zonder het werschema significant te be¨ınvloeden. We veronderstellen wel dat het restaurant uitgerust is met een soort warmhoudtoestel zodat ook warme gerechten voor een gedeelte op voorhand kunnen klaargemaakt worden.
42
Hoofdstuk 5 De website 5.1
Structuur
De belangrijkste component in onze scriptie, was het schrijven van een goed werkend algoritme. We vonden het echter ook belangrijk dat naast het algoritme een handige website ter beschikking was waarin het beheer van de keuken volledig kon worden bijgehouden. In het ideale geval zijn de obers uitgerust met een draagbaar zakcomputertje waar zij hun bestellingen kunnen ingeven. De bestellingen kunnen dan rechtstreeks toegevoegd worden aan de databank, waardoor het algoritme deze bestellingen direct in rekening brengt. Het schrijven van zo’n applicatie valt echter buiten het bestek van deze thesis. De bestellingen worden dus eigenhandig in de computer ingegeven. Naast een computer waar bestellingen kunnen ingegeven worden, moet zich ook een computer in de keuken bevinden. Deze dient om het resultaat van het algoritme weer te geven zodat het personeel onmiddellijk kan aflezen welke gerechten ze moeten klaarmaken. De website speelt zich volledig af op de indexpagina aangezien we met een iframe werken. Op de indexpagina kan de gebruiker zijn keuze maken in het menu, waarna de gekozen pagina in het iframe zal getoond worden. Hierdoor wordt navigatie tussen de verschillende pagina’s gemakkelijker en is het niet nodig om op elke aparte pagina een menu te voorzien. Net als in de databank, werd in de website een onderverdeling gemaakt tussen de belangrijkste categorie¨en: personeel, gerechten, bestellingen, ingredi¨enten en materiaal. Die categorie¨en leiden tot volgende pagina’s: personeel.php, recepten.php, bestellingen.php, ingredienten.php en materiaal.php. Deze categorie¨en vormen samen de menubalk. In elke 43
categorie kunnen gegevens toegevoegd, gewijzigd of gewist worden. Via het menu gerechten is het mogelijk om verder te gaan naar de verschillende stappen van de bereiding van een specifiek gerecht (bereidingen.php) en naar de ingredi¨enten die nodig zijn voor het gerecht (ingredient.php). In de categorie bestellingen is het naast het plaatsen van een gewone bestelling ook mogelijk om stappen in te geven die klaargemaakt moeten worden om in de voorraad te steken (voorraad.php). Naast de menubalk kan de gebruiker nog andere pagina’s bekijken. In de rechterbovenhoek kan vooreerst naar het werkschema gegaan worden (werkschema.php) en kan ook de rekening verkregen worden van een tafel (rekeningen.php). Helemaal onderaan kan ook nog een keuze gemaakt worden. Met het huisje ga je terug naar de thuispagina (home.php). De instellingen kunnen aangepast worden op de pagina config.php. De i staat voor informatie (info.php) en in de brievenbus kan je een e-mail achterlaten.
Figuur 5.1: Screenshot van de website
44
5.2 5.2.1
Onderliggende code van de menu-bestanden HTML-hoofding
Alle PHP-bestanden die bereikbaar zijn via de menubalk van de website, hebben grotendeels dezelfde indeling. In de HTML-hoofding komt reeds een stukje javascript-code voor doordat deze pagina’s voorzien zijn van foutcontrole. Bij het ingeven van data in de formulieren, wordt v´o´or het versturen van het formulier nagegaan of alle velden goed werden ingevuld. Dit houdt vooral in dat de omschrijving of de naam niet leeg is en dat geldige getallen worden ingegeven. Bij de form-tag die in de body van het bestand staat, wordt daarvoor een attribuut onsubmit ingevuld: onsubmit=\"return controle(...)\" met op de 3 puntjes, de naam van het formulier. Hierbij wordt een functie controle opgeroepen in de HTML-hoofding, die er bijvoorbeeld als volgt kan uitzien: function controle(form) { if (form.omschr.value==’’) { alert(’De omschrijving is leeg’) return false } else { var myRegxp = /^[1-9][0-9]*$|^0$/ if (!myRegxp.test(form.voorraad.value)) { alert(’De voorraad is niet juist ingevuld’) return false } else return true } } Indien zich een fout voordoet, wordt de gebruiker op de hoogte gebracht doordat een waarschuwingsvenster verschijnt (zie figuur 5.2). De inhoud van de invulvelden zijn strings, dus om te controleren of een getal correct werd ingevuld, zouden we deze string in eerste
45
Figuur 5.2: Waarschuwingsvenster
instantie moeten omzetten naar een geheel getal of een vlottend kommagetal. Bij omzetting gaat echter een gedeelte van de informatie verloren. Zo wordt de string ‘12euro’ omgezet naar de integer 12 zonder een foutmelding te geven. Ook bij het ingeven van zulke foute waarden in de databank wordt deze omzetting toegepast zonder de gebruiker op de hoogte te brengen. Om deze problemen te vermijden, wordt gebruik gemaakt van reguliere uitdrukkingen 1 . In het voorbeeld van daarjuist moet de voorraad van de volgende vorm zijn: /^[1-9][0-9]*$|^0$/ Met de forward-slash wordt het begin en einde van de reguliere uitdrukking aangeduid. [1-9] komt overeen met ´e´en enkel getal tussen 0 en 9. De circonflexe geeft weer dat de reguliere uitdrukking moet beginnen met een cijfer van 1 tot 9. De asterisk geeft aan dat 1
Uitleg over reguliere uitdrukkingen is te vinden op de webpagina http://www.regular-expressions.info
46
daarna nul of meerdere keren een cijfer van 0 tot 9 mag voorkomen. Het dollarteken wijst er op dat hierna niets meer mag komen. De verticale streep fungeert als een of-functie. Dit betekent dus dat de voorraad een positief (0 inbegrepen) geheel getal moet zijn. Om nog te vermijden dat de gebruiker als omschrijving of naam een lege string ingeeft, maken we ook gebruik van een functie trimString2 . Bij het ingeven van kommagetallen moeten punten gebruikt worden. Dit omzeilen we door bij de controle van de gegevens, in mogelijke kommagetallen, de komma’s te vervangen door punten zoals in de volgende lijn javascript-code: form.prijs.value=form.prijs.value.replace(/,/, ".")
5.2.2
HTML-corpus
Algemeen De body van de bestanden bestaat bijna volledig uit PHP-code. Het eerste dat de gebruiker te zien krijgt, is een opsomming van alle rijen die in de specifieke tabel zit. Ten tweede wordt een formulier getoond waarmee nieuwe rijen kunnen toegevoegd worden. Het is dit formulier dat de javascript-functie controle oproept. Er kan ook gekozen worden om een bestaande rij aan te passen. Dan zal het formulier voor nieuwe rijen vervangen worden door een formulier om een rij te wijzigen. Ook dit formulier zal dezelfde functie controle oproepen. Met behulp van IsSet($_POST["invoegen"]) of IsSet($_POST["wijzig"]) (waarbij invoegen en wijzig de namen zijn van de respectievelijke submit-buttons) wordt bij het inladen van de pagina gecontroleerd of een formulier werd ingevuld. Bij het ingeven van een string in de databank moet gelet worden op het feit dat er accenten in kunnen voorkomen. Opdat ze goed zouden kunnen ingegeven worden in de databank zonder fouten te veroorzaken, moeten ze ‘escaped’ worden. De functie mysql escape string controleert een string voor gebruik in een MySQL querywoord dat wil zeggen dat bijvoorbeeld ’ vervangen wordt door \’. Om een rij te wissen kan naast elke rij op een kruisje geklikt worden. Omdat een link vlug aangeklikt is en grote gevolgen kan hebben indien het ongewenst was, wordt ook een bevestiging gevraagd voordat de gegevens gewist worden. Dit wordt met het onclick attribuut van de linktag gedaan: 2
Deze functie werd gevonden op http://www.faqts.com/knowledge base/view.phtml/aid/1678/fid/1
47
onClick=\"return confirm(’Bent u zeker dat u dit item wilt verwijderen?’)\"
Figuur 5.3: Bevestiging voor het verwijderen van een item
Wordt op OK geduwd, dan wordt de waarde wis en het nummer van het te wissen item meegegeven in de URL waarna bij het herladen van de pagina met behulp van IsSet($_GET["wis"]) en $_GET["id"] gecontroleerd wordt welke rij gewist moet worden. We hebben ook geprobeerd om hier en daar een kleine hint te geven. Dit gebeurt door de invulvelden te voorzien van een title attribuut (zie figuur 5.4). Bestellingen.php Bij het invoegen van een nieuwe bestelling in het bestand bestellingen.php werd nog wat extra code geschreven. Zo wordt gecontroleerd of er nog voldoende ingredi¨enten aanwezig 48
Figuur 5.4: Hints
zijn, of er niet reeds een bestelling aanwezig is voor deze tafel met hetzelfde recept en wordt er een onderscheid gemaakt naargelang de gang waartoe het recept behoort. Bij het wijzigen wordt opnieuw controle gedaan naar de voorraad van de ingredi¨enten en of de bestelling niet reeds bezig was. Bereidingen.php Op de webpagina waar men de stappen van de bereiding voor een bepaald recept kan ingeven, is het nodig om aan te duiden van welke voorgaande stappen de huidige stap afhangt. Hiervoor kan een gewone selectbox gebruikt worden waarbij het multiple attribuut aanwezig is. Bij een gewone selectbox moet men dan echter de Ctrl-toets ingedrukt houden om meerdere items aan te kunnen duiden. Om het de gebruiker gemakkelijker te maken, werd daarvoor een script gebruikt dat de gewone selectbox omzet naar een selectbox met checkboxes 3 . Hiermee is het ook mogelijk om direct alles, niets of de oorspronkelijke waarden te selecteren. Rekeningen.php Het bestand rekeningen.php ziet er qua opbouw iets anders uit. Het heeft de functionaliteit om van een gevraagde tafel de rekening te geven. Nadat een rekening is opgevraagd, zal het attribuut afgewerkt van bestellingen op 2 ingesteld worden. 3
Het script is terug te vinden op de website http://verens.com/archives/2005/04/27/son-ofmultiselect/
49
Config.php Met het bestand config.php kunnen enkele instellingen gewijzigd worden. Bij het inladen van deze pagina ziet de gebruiker een formulier waar de waarden voor de instellingen ingegeven kunnen worden. De huidige waarden worden als standaard weergegeven. Als de gebruiker op de knop Opslaan klikt worden de ingestelde waarden op geldigheid gecontroleerd en opgeslagen in het bestand config.ini. In de handleiding (hoofdstuk 6) kan een lijst van configuratie-instellingen teruggevonden worden, samen met hun betekenis.
5.3
Onderliggende code van het werkschema
Om de grafiek van het werkschema zo duidelijk mogelijk weer te geven, is het handig dat de pagina werkschema.php zo groot mogelijk wordt weergegeven. In eerste instantie zouden we de webpagina in fullscreen-mode kunnen weergeven. Hier komt echter een moeilijkheid naar boven. Tijdens het ontwikkelen van de website werd voortdurend met Firefox gewerkt. In Firefox is het echter niet mogelijk om in fullscreen-mode te werken, in tegenstelling tot Internet Explorer. Om toch een zo groot mogelijk scherm te verkrijgen bij het openen van de pagina vanuit de index-pagina, werd volgende JavaScript-code ingevoegd: window.open(src, "_blank", "location=no, menubar=no, status=no, toolbar=no, scrollbars=yes, resizable=yes") Merk op dat bij Firefox de statusbar niet verdwijnt, in tegenstelling tot bij Internet Explorer. Om helemaal fullscreen te gaan, raden we aan om F11 te gebruiken. Om het werkschema up-to-date te houden, moet het regelmatig opnieuw worden ingeladen. Daarvoor moet volgende PHP-code in de HTML-hoofding staan. In de eerste lijn wordt het configuratiebestand verwerkt, de tweede lijn geeft aan dat het bestand moet vernieuwd worden na $ini["vernieuwen"] seconden. $ini = parse_ini_file("config.ini"); echo ’<meta http-equiv="refresh" content="’.$ini["vernieuwen"].’">’ Het grootste deel van de PHP-code uit werkschema is de uitwerking van het algoritme dat beschreven staat in hoofdstuk 4. 50
Het gedeelte dat de gebruiker ook daadwerkelijk kan zien op zijn scherm volgt daarna. Bovenaan de pagina kan de gebruiker de keuze maken tussen de weergave van de taken per personeelslid of voor alle personeelsleden. Dit gebeurt via de variabele personeel die is opgeslagen in het bestand config.ini. De figuur figuur.php die uit de tabel werk wordt afgeleid volgt daarna. Ook wordt er een tabel gecre¨eerd die het werk toont voor een bepaalde tijd v´o´or en na het huidige tijdstip.
5.4
Onderliggende code van de figuur
Het bestand figuur.php bevat enkel PHP-code. Na een aantal instellingen wordt eerst het tijdsinterval ingezet zodat het huidige en het volgende uur zichtbaar zijn. Het is altijd handig om te weten waar we ons momenteel bevinden in het werkschema, zodat we een verticale lijn plaatsen op het huidige moment. Met behulp van de variabele personeel uit het bestand config.ini wordt bepaald welke personeelsleden in de figuur moeten komen. De namen van de personeelsleden worden dan aan de linkerkant van de figuur geplaatst, terwijl aan de rechterkant de stappen uitgetekend worden in de vorm van een balk. In elke balk wordt ook het stapnummer vermeld. In de originele versie van Gantt is dit niet mogelijk, zodat we hiervoor een kleine aanpassing gemaakt hebben in jpgraph plotmark.inc. Daarna worden ook de deadlines toegevoegd als verticale lijnen. Als slot krijgen ook de gebruikte materialen een plaats aan de linkerkant van de figuur, met aan de rechterkant een aanduiding van wanneer ze gebruikt worden. Merk tenslotte nog op dat alle pagina’s geldige HTML-code gebruiken. Meer informatie over hoe u de website kan gebruiken, is te vinden in de handleiding in het volgende hoofdstuk.
51
Hoofdstuk 6 Handleiding 6.1 6.1.1
Installatie Automatisch
Er is een automatisch installatieprogramma voorzien die alle software in ´e´en keer installeert. Dit bestand is te vinden op de CD-ROM van ons afstudeerwerk. Eerst wordt een hulpmiddel ge¨ınstalleerd waarmee het installatieprogramma SQL-scripts kan uitvoeren. Daarna start een wizard die ons toelaat de installatie-map waarin de software ge¨ıntalleerd wordt, te kiezen. Vervolgens gaat de wizard verder met de installatie van EasyPHP en daarna worden de bestanden van de website ge¨ınstalleerd. Als laatste stap wordt de databank ge¨ımporteerd. Na het opnieuw opstarten van de computer zou het taakplanningssyteem moeten werken.
6.1.2
Handmatig
Indien een automatische installatie niet gewenst is, kan de software ook handmatig ge¨ınstalleerd worden. EasyPHP Als eerste installeren we EasyPHP 1.8. Het installatiebestand (easyphp1-8 setup.exe) hiervoor is terug te vinden op de CD-ROM van ons afstudeerwerk of op de website van 52
EasyPHP 1 . Bij het uitvoeren van dit bestand kan gewoon de wizard gevolgd worden. Na de installatie moeten er nog wat instellingen gemaakt worden. De instellingen zijn bereikbaar via de knop met het EasyPHP-logo (zie figuur 6.1). • Bij Configuratie → EasyPHP moet de optie Start bij het opstarten van Windows aangevinkt worden. • Bij Configuratie → PHP Extensie moet de uitbreiding php gd2 aangevinkt worden. Deze uitbreiding is nodig om het werkschema te kunnen weergeven.
Figuur 6.1: Screenshot van EasyPHP 1.8
De werking van de webserver kan nu getest worden door naar de webpagina http://localhost/ te surfen. Op deze pagina zou het logo van EasyPHP moeten staan. JpGraph De bestanden van JpGraph zijn terug te vinden op de CD-ROM van ons afstudeerwerk. De volledige map src moet gekopieerd worden naar de www-map van EasyPHP. Aangezien we deze bestanden aangepast hebben kunnen ze niet van de website van JpGraph gedownload worden. Databank Daarna moet de databank in de MySQL-server opgeslagen worden. Alle instellingen in verband met de databank doen we met phpMyAdmin 2 . Dit hulpmiddel is bereikbaar 1 2
http://www.easyphp.org/ http://www.phpmyadmin.net/
53
door de webpagina http://localhost/mysql/ te openen. Eerst moeten we een nieuwe databank aanmaken. Tik restaurant in het voorziene venster en klik op Aanmaken (zie figuur 6.2). Daarna moet de databank ge¨ımporteerd worden. Bij het tabblad SQL kunnen
Figuur 6.2: Aanmaken databank restaurant
we query’s intypen om door de server te laten uitvoeren. Kopieer de inhoud van het bestand databank.txt naar dit venster en klik op Start. De databank is nu ge¨ımporteerd en klaar voor gebruik. Website De website bestaat uit PHP-bestanden, een configuratiebestand en een map met foto’s. De bestanden zijn terug te vinden op de CD-ROM en moeten gekopi¨eerd worden naar de www-map van EasyPHP. Alle onderdelen zijn nu ge¨ınstalleerd en de website is bereikbaar door de pagina http://localhost/ te openen in een webbrowser.
6.2
Gebruiksaanwijzingen
Start eventueel EasyPHP op en surf naar http://localhost/. Dit is de homepagina van La Dolce Vita (zie figuur 6.3).
6.2.1
Invoegen van de gegevens
Voordat kan begonnen worden met het echte werk, moeten eerst alle gegevens worden ingevoegd.
54
Figuur 6.3: La Dolce Vita
Personeel In het menu personeel kan het personeel beheerd worden. Er wordt een overzicht gegeven van alle personeelsleden. Daaronder kan een nieuw personeelslid toegevoegd worden door zijn naam in te geven, dit vak mag niet leeg zijn. Bij het toevoegen van een nieuw personeelslid wordt de status automatisch op afwezig gezet. Daarna kan de status gewijzigd worden door in de kolom status te klikken. Zoals in alle andere overzichten kunnen ook de gegevens gewijzigd worden door op het potloodje te klikken of wissen door op het kruisje te klikken. Ingredi¨ enten Alle ingredi¨enten die gebruikt worden in ´e´en of ander recept, moeten ook ingegeven worden. De omschrijving van een nieuw ingredi¨ent mag niet leeg zijn en de voorraad moet 55
een geheel getal zijn. De eenheid mag leeg zijn, er wordt dan gerekend per stuk. Als een nieuw gerecht wordt klaargemaakt, wordt gecontroleerd of er nog voldoende ingredi¨enten aanwezig zijn en wordt de voorraad verminderd indien dit het geval is. Materiaal Ook het keukenmateriaal wordt opgeslagen. Dit gebeurt in het menu materiaal. Voor nieuw materiaal kan toegevoegd worden, moeten eerst een aantal materiaaltypes worden ingegeven. Een materiaaltype is bijvoorbeeld een oven, mixer, bakplaat en dergelijke. Bij een nieuw item mag de omschrijving niet leeg zijn. Het materiaal zelf kan dan ingegeven worden en moet behoren tot een bepaald materiaaltype. Zo zal bijvoorbeeld de ‘oven in de hoek’ van het materiaaltype ‘oven’ zijn. Er kunnen meerdere items van eenzelfde materiaaltype tegelijkertijd worden toegevoegd, bijvoorbeeld een groep van vier bakplaten. Gerechten In het menu gerechten is een overzicht te zien van alle gerechten die in La Dolce Vita kunnen klaargemaakt worden. Bij het ingeven van een nieuw gerecht moet rekening gehouden worden met een aantal voorwaarden. Zo mag de omschrijving niet leeg zijn en is de prijs uitgedrukt in euro per persoon. Om de laatste twee vakjes te kunnen invullen is het nodig dat reeds geweten is voor hoeveel personen de bereiding van het gerecht zal beschreven worden. Dat aantal komt in het vakje ‘aantal personen’. Het is echter wel mogelijk dat een recept altijd voor dat aantal personen (of een veelvoud ervan) moet klaargemaakt worden. Denken we bijvoorbeeld aan een taart voor 4 personen, dan kan dit in principe niet klaargemaakt worden voor ´e´en persoon. Daarom moet in het laatste vakje ingevuld worden wat het minimum aantal personen is waarvoor het gerecht kan klaargemaakt worden. Bij een taart voor 4 personen zal dit 4 zijn, bij een gewoon gerecht zal dit 1 zijn. Bereiding Het bepalen van de verschillende stappen moet op een specifieke manier gebeuren opdat het algoritme zo optimaal mogelijk zou kunnen werken. We zullen aan de hand van volgend recept de grootste moeilijkheden bespreken. 56
Beursje met scampi en een coulis van rode paprika Benodigdheden voor 4 personen 20 scampi 6 gr gember 60 gr sojascheuten komijnzaad 1/2 rammenas proven¸caalse kruiden 1 grote wortel 1 ui 1/2 bundel lente uitjes 1/2 l rode paprika in blik 60 gr mange tous 40 gr suiker
1/4 l witte wijn 100 gr boter 6 bl feuille de brick eigeel 1/2 l gevolgtefonds
Bereiding
• De gember schillen en raspen. • De pijpajuin en de mange tous in de juiste vorm snijden en fruiten in olijfolie. • De rammenas en de wortelen in plakjes snijden en eveneens fruiten in de olijfolie. • De sojascheuten fruiten in olijfolie. • Alle groenten laten afkoelen, mengen en bestrooien met een weinig komijnzaad. • De scampi pellen, darmkanaal verwijderen en half gaar sauteren in olijfolie. Bestrooien met proven¸caalse kruiden en laten afkoelen. • Saus: de uien fijnsnijden en sueren in de olijfolie, voeg er de paprika’s uit blik bij en laat kort meestoven; bestrooien met suiker, bevochtigen met de witte wijn en de gevogeltefonds en voor de helft laten inkoken. Mixen, passeren en eventueel monteren met boter. • Beursjes: 1 blad feuille de brick open leggen en 1/4 blad in het midden erop schikken. De groenten en de scampi erop schikken. De boorden van het brickdeeg doreren en het deeg dichtplooien. Afbakken in de oven op 170 ◦ C (gedurende een 10 minuten). Afwerking • Beursje in het midden van het bord. • Saus er rond napperen 57
De stappen moeten op een goede manier gekozen worden. Teveel kleine stapjes zijn niet nodig, daarom mogen de eerste vijf stappen grotendeels als ´e´en grote stap gezien worden. Omdat het mengen van de groenten en bestrooien met komijnzaad kan gedaan worden nadat de groenten afgekoeld zijn, wordt dit als een aparte stap gezien. Veel hangt echter ook af van de eigen interpretatie hierover. Het is ook belangrijk dat voor elke stap maximaal ´e´en item uit de materialenlijst gebruikt wordt. Daarom wordt ‘Mixen, passeren en eventueel monteren met boter’ gezien als een aparte stap. Zo ontstaan er een achttal verschillende stappen: 1. De gember schillen en raspen. De pijpajuin en de mange-tous in de juiste vorm snijden en fruiten in olijfolie. De rammenas en de wortelen in plakjes snijden en eveneens fruiten in de olijfolie. De sojascheuten fruiten in olijfolie. Alle groenten laten afkoelen. 2. De scampi pellen, darmkanaal verwijderen en half gaar sauteren in olijfolie. Bestrooien met Proven¸caalse kruiden en laten afkoelen. 3. Alle groenten mengen en bestrooien met een weinig komijnzaad. 4. Saus: de uien fijnsnijden en sueren in de olijfolie, voeg er de paprikas uit blik bij en laat kort meestoven; bestrooien met suiker, bevochtigen met de witte wijn en de gevogeltefonds en voor de helft laten inkoken. 5. De saus mixen, passeren en eventueel monteren met boter. 6. Beursjes: 1 blad feuille de brick open leggen en 1/4 blad in het midden erop schikken. De groenten en de scampi erop schikken. De boorden van het brickdeeg doreren en het deeg dichtplooien. 7. De beursjes afbakken in de oven op 170 ◦ C (gedurende 10 minuten). 8. Beursje in het midden van het bord. Saus er rond napperen. Bij het ingeven van de gegevens moeten een aantal voorwaarden indachtig gehouden worden. Opnieuw mag de omschrijving niet leeg zijn. De duur is het aantal minuten dat de stap ongeveer duurt om klaar te maken. Bij materiaal kan er hoogstens ´e´en element meegegeven worden. Bij het ingeven van een nieuw recept zal er nog niets in de voorraad 58
zitten. Dit element wordt aangepast door het algoritme zelf en zal dus enkel handmatig moeten aangepast worden als besloten wordt om een voorraad weg te doen omdat het bijvoorbeeld niet meer vers is. Indien deze stap op voorhand kan klaargemaakt worden, vinkt u ‘ja’ aan. De vfactor is dan een vermenigvuldigingsfactor die aanduidt hoe veel langer het duurt om een gerecht klaar te maken voor meerdere personen. In het voorbeeld van daarnet zal de zevende stap evenlang duren voor ´e´en als voor twee personen. Hiervoor wordt wel aangenomen dat er zich genoeg ovens in de keuken bevinden of dat de ovens groot genoeg zijn. Tenslotte moeten ook nog de precedenten ingevuld worden. Hiervoor is het nodig dat je goed weet welke stappen reeds moeten afgewerkt zijn bij de huidige stap. Zo moet voor het afbakken van de beursjes in de oven (stap 7) de beursjes reeds klaargemaakt zijn. Dat gebeurt in stap 6. Om aan stap 6 te kunnen beginnen moeten ook de tweede en derde stap afgewerkt zijn. Dit is belangrijk zodat het algoritme alles in de goede afwerkvolgorde kan plaatsen. Ingredi¨ enten behorende bij een specifiek recept Bij de tabel waar de recepten opgesomd staan, kunnen ook de ingredi¨enten bekeken worden die nodig zijn voor het recept. Om dit te kunnen invullen moeten reeds alle ingredi¨enten ingegeven zijn in het menu ingredi¨enten. Daarna kunnen de nodige ingredi¨enten aangeduid worden samen met hun hoeveelheid in de eenheid die opgegeven staat (tot op 3 cijfers na de komma).
6.2.2
Configuratie
Naast het ingeven van alle gegevens, kunnen ook nog een aantal parameters aangepast worden. Het aanpassen van deze parameters kan gebeuren door op het configuratieicoontje te klikken dat zich onderaan de webpagina bevindt. vernieuwen Deze parameter bepaalt om de hoeveel tijd het werkschema automatisch vernieuwd wordt. Bij het vernieuwen van het werkschema worden nieuwe bestellingen opgenomen in het schema en worden de taken zo optimaal mogelijk verdeeld onder het personeel. De waarde is uitgedrukt in seconden en staat standaard ingesteld op 60 seconden. 59
spreidingsfactor
Figuur 6.4: Werkschema voor spreidingsfactor 0
Figuur 6.5: Werkschema voor spreidingsfactor 5
Hiermee kan ingsteld worden in welke mate de taken van eenzelfde gerecht verdeeld worden onder het personeel. Bij spreidingsfactor 0 (zie figuur 6.4) staan de taken zoveel mogelijk bij hetzelfde personeelslid. De verdeling van de taken is dan meestal echter minder optimaal. Bij spreidingsfactor 5 (zie figuur 6.5) worden de taken optimaal verdeeld. Er wordt geen poging gedaan om de taken van eenzelfde gerecht zoveel mogelijk aan hetzelfde personeelslid toe te kennen. Deze parameter staat standaard ingesteld op 0. wachttijden Met deze parameter wordt de optimale wachttijd tussen twee gangen ingesteld. Als een klant een gerecht bestelt, duurt het minstens een bepaalde tijdsduur (de wachttijd) vooraleer het gerecht opgediend wordt, ook al staat het klaar om op te dienen. Na het opdienen van een gang wordt er ook een bepaalde tijdsduur gewacht vooraleer de volgende gang opgediend wordt. Deze parameter is uitgedrukt in minuten en staat standaard voor het voorgerecht op 20 minuten, voor het hoofdgerecht op 30 minuten en voor het nagerecht op 40 minuten ingesteld.
60
weergave De parameter bepaalt van hoeveel taken de omschrijving bij het werkschema weergegeven wordt. De waarde van de parameter is uitgedrukt in minuten en staat standaard op 5 minuten. Dit wil zeggen dat de taken waarvan het eindtijdstip minder dan 5 minuten v´o´or het huidige tijdstip en het begintijdstip minder dan 5 minuten na het huidige tijdstip ligt worden weergegeven. Dit om ervoor te zorgen dat er een zekere speling mogelijk is tussen het berekende werkschema en de realiteit. waarschuwingsniveau Bij het ingeven van een bestelling wordt nagegaan of er nog voldoende ingredi¨enten in de voorraad zitten. Vanaf het ogenblik dat de voorraad minder is dan waarschuwingsniveau maal de hoeveelheid nodig om het recept klaar te maken voor het aantal personen ingegeven bij het menu gerechten, wordt een waarschuwing gegeven.
6.2.3
Aan de slag
Bestellingen Nadat al het vorige ingevuld is, is alles klaar om de bestellingen in te geven. Dit gebeurt in het menu bestellingen, waar een overzicht wordt gegeven van alle geplaatste bestellingen en waar nieuwe bestellingen kunnen ingegeven worden. Een bestelling kan er bijvoorbeeld als volgt uitzien: 1 1 2 1 1
maal maal maal maal maal
Noorse zalm met komkommer en zure room beursje met scampi en een coulis van rode paprika parelhoenfilets met jonge groenten en roze pepersaus gebakken peperkoek met peer en chocoladesabayon bretoense appeltaart
Elk recept geeft u apart in, zodat er vijf bestellingen in de lijst bijkomen. Helemaal onderaan is er ook de mogelijkheid om op voorhand iets klaar te maken. Klik het recept aan dat op voorhand moet klaargemaakt worden. Er wordt dan een nieuwe pagina ingeladen waarop de stappen kunnen aangeduid worden die reeds bereid moeten 61
worden. Stappen waarvoor werd ingegeven dat ze niet op voorhand konden klaargemaakt worden, kunnen uiteraard niet aangevinkt worden. Het wissen van een bestelling is pas mogelijk als de bestelling afgewerkt en betaald is.
Werkschema Door op het icoontje in de rechterbovenhoek te klikken, kan dan het uiteindelijke werkschema bekeken en gevolgd worden. Rekening Na het nuttigen van de maaltijd moet natuurlijk ook nog een rekening betaald worden. Door op het -icoontje te klikken kan het tafelnummer ingegeven worden. Alle nog niet betaalde bestellingen aan die tafel worden daar in rekening gebracht. Het is mogelijk om deze pagina af te printen.
62
Hoofdstuk 7 Besluit Voor het ontwerpen van onze webapplicatie zijn we begonnen met een grondige analyse van het probleem. We hebben onderzocht wat de eisen zijn, welke factoren belangrijk zijn, welke informatie over de gerechten bijgehouden moet worden, enzoverder. Hierbij willen we opmerken dat er h´e´el veel voorwaarden en factoren zijn en dat het voor ons vrijwel onmogelijk was om deze allemaal te behandelen. We hebben echter geprobeerd om de belangrijkste voorwaarden en factoren te bepalen en deze zoveel mogelijk in rekening te brengen, om zo een zo realistisch mogelijk planningssysteem te ontwerpen. Daarna hebben we onderzocht welke informatie het taakplanningssysteem nodig heeft en op welke manier deze informatie kan opgeslagen worden in de databank. We hebben een entiteit-relatie diagram opgesteld en de tabellen in de databank aangemaakt. Hierbij hebben we ervoor gezorgd dat er zich geen dubbele informatie in de databank bevindt en dat de attributen een logische naam en standaardwaarde kregen. Verder hebben we zoveel mogelijk de relaties tussen de verschillende tabellen vastgelegd zodat de databank consistent blijft. Tijdens het ontwerp van het taakplanningssyteem werd de structuur van de databank verschillende keren gewijzigd. Voor de databank kunnen we besluiten dat vrijwel alle denkbare informatie over de recepten zonder problemen kan opgeslagen worden. Na het ontwerp van de databank konden we beginnen met het zoeken naar een algoritme. Tijdens het ontwerpen van verschillende algoritmes, die met steeds meer factoren rekening hielden kwamen we tot een algoritme die gebruik maakt van een precedentiediagram en het kritieke pad ervan. Tot onze grote verwondering bleek ons algoritme in grote mate overeen te komen met het veelgebruikte critical path scheduling algoritme. We hebben 63
dan uiteindelijk ons algoritme uitgebreid zodat het hiermee volledig overeenkwam. Het algoritme genereert volgens ons een aanvaardbare oplossing. De gerechten voor de opeenvolgende gangen worden in de juiste volgorde en na een instelbare wachttijd klaargemaakt. De eerste bestellingen worden ook eerst verwerkt, delen van de gerechten die niet op voorhand klaargemaakt kunnen worden staan achteraan in het werkschema, de spreidingsfactor zorgt ervoor dat de verschillende stappen van een bereiding zoveel mogelijk aan hetzelfde personeelslid toegekend worden zonder het werschema significant te be¨ınvloeden. We veronderstellen wel dat het restaurant uitgerust is met een soort warmhoudtoestel zodat ook warme gerechten voor een gedeelte op voorhand kunnen klaargemaakt worden. Het zal ook nooit voorkomen dat er aan een stap van een bereiding moet begonnen worden als andere, afhankelijke, stappen niet afgewerkt zijn. Als een gerecht bijvoorbeeld in de oven zit, wordt aan het personeelslid ondertussen een andere taak toegekend. Ook zal het nooit voorkomen dat er meer ovens tegelijkertijd moeten gebruikt worden dan er beschikbaar zijn. Verder kunnen we besluiten dat het algoritme soms stappen die vlak voor het opdienen moeten uitgevoerd worden niet helemaal tegen het opdientijdstip plaatst. Ook is het nog niet mogelijk om aan bepaalde personeelsleden specialiteiten toe te kennen. We veronderstellen dat ieder personeelslid alle taken kan uitvoeren. Het zou wenselijk zijn om het taakplanningssysteem uit te breiden zodat dit wel mogelijk is. Onze webapplicatie is ook voorzien van een gebruiksvriendelijke en smaakvolle gebruikersinterface. Hiermee kan alle informatie in de databank geraadpleegd of toegevoegd worden. We hebben er overal voor gezorgd dat de gebruiker geen ongeldige gegevens kan opslaan. Verder kan de gebruiker van de meeste invoervelden opvragen op welke manier de gegevens moeten ingevoerd worden, en worden er foutmeldingen weergegeven als er toch iets misloopt. Uiteindelijk wordt het gegenereerde werkschema op een elegante manier weergegeven zodat de personeelsleden duidelijk kunnen zien welke taken uitgevoerd moeten worden. Tot slot kunnen we nog vermelden dat we bij het ontwerpen van ons taakplanningssysteem hebben gemerkt dat de problemen die we tegenkwamen ook voorkomen in andere vakgebieden. We zijn zelfs van de mening dat er weinig of geen aanpassingen nodig zijn om ons taakplanningssysteem in andere vakgebieden, zoals het plannen van activiteiten in een machinepark, te kunnen gebruiken.
64
Bibliografie [1] Ferry Boender. MySQL PHP Tutorial. [2] Michael Garvey, Heather Dismore and Andrew Dismore. Running a Restaurant for dummies. Wiley Publishing, Inc., 2004. [3] Prof. dr. Guy De Tr´e. Databanktechnologie, didactisch materiaal bij het opleidingsonderdeel. Academiejaar 2005-2006. [4] Prof. dr. Leo Storme. Fundamenten van de informatica. Academiejaar 2005-2006. [5] Ramez Elmasri and Shamkant Navathe. Fundamentals of database systems. 3rd Edition, Addison-Wesley, 2000. [6] COMAP Inc. For All Practical Purposes. 7th Edition, W.H. Freeman, 2006. [7] Johan Persson. JpGraph Manual.
65
