---

Hej gruppe.


Jeg sidder og tænker lidt på at lave et script til generereing af
skemaer. Jeg har en database i MySQL med elever, lærere, lokaler, timer
(antal af timer osv.).

Er der nogen der har lidt inspiration, til hvordan man bedst muligt
laver et script, der sætter det hele sammen optimalt? (altså ingen
hultimer osv.)


--
Med venlig hilsen
Kasper Johansen

---

Hej Kasper

Det er vist en større opgave Tror at du allerførst skal skrive
ned (til dig selv eller gerne her) hvordan du ønsker skemaet skal
fungere. F.eks. hvad skal der være ud af hver "akse"? Hvad skal man
kunne vælge som input for skemaet? (dvs. vælger man at se skemaet for
en elev eller lærer, skal man kunne vælge en
periode/semester/skoleår). Disse ting er med til at sammensætte det
(eller de) MySQL-query som du skal have sammensat for at udvælge netop
de data, der skal med i skemaet. Det er også med til at bestemme
hvordan dataene sorteres bedst muligt, så arbejdet i PHP bliver meget
lettere og overskueligt.

Hvor meget kender du til HTML, PHP og MySQL? Så er det lidt nemmere at
guide dig og undgå misforståelser Forresten søger du nok en
ALgoritme, ikke en logaritme

--
Mvh Jesper, http://fdf.dk/landsdel1/

---

Jesper H skrev:
> Hvor meget kender du til HTML, PHP og MySQL? Så er det lidt nemmere at
> guide dig og undgå misforståelser Forresten søger du nok en
> ALgoritme, ikke en logaritme

Jeg ville mene at have ok forstand det ;)

Jeg har allerede stillet en database op, med klasser, elever, courses og
lokaler.

Ideen var så, at man hæftede courses sammen med lokalerne (man vil nok
ikke have idræt i et fysiklokale). Dernæst skulle man angive hvilke dage
og tidspunkter, at et bestemt lokale er ledigt.


At generere skemaet er sådan set simpelt nok. Men at finde det
"optimale" skema, er jo noget ganske andet. Den umiddelbare eneste
løsning, som jeg kan komme på, var at generere flere skemaer, og
sammenligne hultimer og lignende mod hinanden - Men dette virker meget
tungt og langt fra optimalt.

En anden løsning kunne være, at man gennemgik sit skema flere gange, og
prøvede at løse evt. hultimer ved at rykke rundt. Dertil kunne man rykke
ned i systemet måske 4 grader, og der


Jeg har før arbejdet med tunge datamængder med PHP og MySQL. Jeg syntes
at PHP er det mest overskuelige sprog af dem jeg kender (C++, Java, VB,
PHP), og derfor falder mit valg på PHP.

Jeg har programmeret afstemning af regnskab og flere communities (nogle
i mine yngre dage). Set evt. www.partyworm.dk hvis du vil danne dig en
holdning af min programmering (det skal dog siges, at det er et
fritidsprojekt, og jeg har derfor ikke gået så meget op i standarder,
men i stedet serversiden af systemet) ;)


HTML ser jeg dog ikke som relevant, da det virkelig svære jo foregår i
selve programmeringen (PHP og MySQL).


Mit spørgsmål gik egentlig på, hvordan man generere et "optimalt" skema
til brugeren, ud fra de data man har i databasen, som f.eks. i mit
tilfælde: Et skema.


Jeg fandt også noget meget interessant læsning på www.pcskema.dk. De
skriver også en masse om problemet :)


--
Med venlig hilsen
Kasper Johansen

---

Kasper Johansen wrote:

> At generere skemaet er sådan set simpelt nok. Men at finde det
> "optimale" skema, er jo noget ganske andet. Den umiddelbare eneste
> løsning, som jeg kan komme på, var at generere flere skemaer, og
> sammenligne hultimer og lignende mod hinanden - Men dette virker meget
> tungt og langt fra optimalt.
>
> En anden løsning kunne være, at man gennemgik sit skema flere gange, og
> prøvede at løse evt. hultimer ved at rykke rundt. Dertil kunne man rykke
> ned i systemet måske 4 grader, og der

Jeg ville nok vælge noget andet end PHP til opgaven. Har du kigget på
den gamle kending prolog? (og der findes sikkert andre sprog) Det tror
jeg vil være MEGET nemmere end at lave en algoritme i PHP. Det er jo
netop lavet til den slags.

mvh Troels Hansen

---

Kasper Johansen skrev:

> Jeg sidder og tænker lidt på at lave et script til generereing af
> skemaer. Jeg har en database i MySQL med elever, lærere, lokaler, timer
> (antal af timer osv.).

Er det rigtigt forstået at du vil lave et script der kan lægge
hele skemaet for alle lærere og elever?

> Er der nogen der har lidt inspiration, til hvordan man bedst muligt
> laver et script, der sætter det hele sammen optimalt? (altså ingen
> hultimer osv.)

God fornøjelse. Den slags programmer koster det hvide ud af
øjnene, kræver tilhørende kursus og skal betjenes af erfarne
skemalæggere for at komme til at fungere.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

Åh, sådan læste jeg det slet ikke - at det var til at automatisk
planlægge skemaer. Måske PHP ikke er det rigtige værktøj til det,
det egner sig vist mere til at vise færdige skemaer lagt ind i
mySQL-databasen.

Må give Bertel Lund Hansen ret, det er vist ikke lige sådan at lave
et sådant program, hmm... Men skulle du nu alligevel have mod på at
kaste dig ud i det, så virker de fleste planlægningsprogrammer
(uanset om det er til planlægning af skemaer, print-baner på
printplader, ruteplanlægning, eller hvad-nu) vel ud fra noget i denne
retning:
1. En algoritme kommer med nogle mere eller mindre kvalificerede
forslag til hvilke muligheder, der kan lade sig gøre - Det kan være
baseret på en systematisk gennemgang af alle muligheder, eller måske
vha. noget tilfældigt sammensat. Algoritmen sørger evt. for at selve
muligheden KAN lade sig gøre og at den ikke bryder med reglerne - dvs.
således at en lærer ikke sættes til at have to klasser på én gang,
og sådan.
2. En cost-funktion "mapper" de enkelte muligheder over til en slags
point. Den evaluerer så at sige muligheden. I dit eksempel vil der
f.eks. gives færre point jo flere hul-timer der er, fordi hul-timer er
noget skidt. Det giver måske også færre point at have samme fag to
gange på en dag, hvis det ikke er sammenhængende timer. Og det giver
måske også væsentligt færre point at have det samme fag mere end to
timer ad gangen. Endeligt giver det måske en lille smule færre point
at have to eller flere forskellige sprog-fag efter hinanden, osv. osv..
3. De muligheder med flest point vil derefter umiddelbart være de mest
optimale (ellers bør man nok revurdere sin cost-funktion). Evt. kan
man herefter igen gå til punkt 1 og lade denne algoritme lave
"mutationer" af muligheden/skemaet, for derefter at gå til punkt 2 og
lade denne vurdere om de nye muligheder er bedre, osv. osv., og på den
måde iterere sig frem til et rimeligt skema.

Den største udfordring er nok at lave algoritmen til punkt 1, og der
skal du måske spørge i en anden gruppe end her, fordi det begynder at
bevæge sig lidt for langt fra denne gruppe som (ifølge navnet i alt
fald) nok koncentrerer sig mest om serverside-relaterede emner til
design af websider.

--
Mvh Jesper, http://fdf.dk/landsdel1/

---

Kasper Johansen wrote:
> Hej gruppe.
>
>
> Jeg sidder og tænker lidt på at lave et script til generereing af
> skemaer. Jeg har en database i MySQL med elever, lærere, lokaler, timer
> (antal af timer osv.).
>
> Er der nogen der har lidt inspiration, til hvordan man bedst muligt
> laver et script, der sætter det hele sammen optimalt? (altså ingen
> hultimer osv.)
>
>

Der findes tykke bøger om lignende algoritmer. Som de andre er inde på,
giver det hurtigt en masse kombinationsmuligheder, så hvis dit eneste
værktøj er et sæt regler, ville jeg sætter maskinen til at lave en
hulens masse skemaer og give hvert skema point for derefter at udtrække
en kandidat som du evaluerer. Er det ikke tilfredstillende, sætter du
den til at give dig en ny kandidat som er tilfredstillende i modsætning
til optimal eller bedst.

Frederik

---

Frederik Sunne wrote:
> Kasper Johansen wrote:
>
>> Jeg sidder og tænker lidt på at lave et script til generereing af
>> skemaer. Jeg har en database i MySQL med elever, lærere, lokaler,
>> timer (antal af timer osv.).
>>
>> Er der nogen der har lidt inspiration, til hvordan man bedst muligt
>> laver et script, der sætter det hele sammen optimalt? (altså ingen
>> hultimer osv.)
>>
> Der findes tykke bøger om lignende algoritmer. Som de andre er inde på,
> giver det hurtigt en masse kombinationsmuligheder, så hvis dit eneste
> værktøj er et sæt regler, ville jeg sætter maskinen til at lave en
> hulens masse skemaer og give hvert skema point for derefter at udtrække
> en kandidat som du evaluerer. Er det ikke tilfredstillende, sætter du
> den til at give dig en ny kandidat som er tilfredstillende i modsætning
> til optimal eller bedst.

Det er begyndelsen til en genetisk algoritme, som godt kan bruges til at
løse problemet generelt.

Se http://en.wikipedia.org/wiki/Genetic_algorithm

Mvh. Michael.
--
Which is more dangerous? TV guided missiles or TV guided families?
Visit my home page at http://michael.zedeler.dk/
Get my vcard at http://michael.zedeler.dk/vcard.vcf

---

Frederik Sunne skrev:

> en kandidat som du evaluerer. Er det ikke tilfredstillende, sætter du
> den til at give dig en ny kandidat som er tilfredstillende i modsætning
> til optimal eller bedst.

Det er også den algoritme Jesper H. beskriver. Der skal være
mulighed for at skemalæggeren kan vægte de forskellige parametre.
Det kan godt være at få mellemtimer skal have høj prioritet, men
hvis det viser sig at give skemaer med timer til klokken 18.00,
vil man sikkert gerne justere prioriteringen.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

Bertel Lund Hansen wrote:
> Frederik Sunne skrev:
>
>> en kandidat som du evaluerer. Er det ikke tilfredstillende, sætter du
>> den til at give dig en ny kandidat som er tilfredstillende i modsætning
>> til optimal eller bedst.
>
> Det er også den algoritme Jesper H. beskriver. Der skal være
> mulighed for at skemalæggeren kan vægte de forskellige parametre.
> Det kan godt være at få mellemtimer skal have høj prioritet, men
> hvis det viser sig at give skemaer med timer til klokken 18.00,
> vil man sikkert gerne justere prioriteringen.

Det er rigtigt, men det er altså nemmere sagt end gjort. Det er vel
nærmest fuzzy logic du er ude i der...?
http://en.wikipedia.org/wiki/Fuzzy_logic

Mvh,

Frederik

---

Frederik Sunne skrev:

>> Det kan godt være at få mellemtimer skal have høj prioritet, men
>> hvis det viser sig at give skemaer med timer til klokken 18.00,
>> vil man sikkert gerne justere prioriteringen.

> Det er rigtigt, men det er altså nemmere sagt end gjort. Det er vel
> nærmest fuzzy logic du er ude i der...?

Ja, hvis det skal være automatisk. Skemalæggerne på min skole
justerede mange ting når de lavede skema, og computerne (flere)
stod og snurrede i mange dage når der blev lagt skema. Der er ca.
700 elever og 60 lærere inkl. børnehaveklassepersonale.
Programmet kostede dengang (10 år siden?) ca. 5'000 kr. og kurset
noget lignende.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

Bertel Lund Hansen skrev:
> Ja, hvis det skal være automatisk. Skemalæggerne på min skole
> justerede mange ting når de lavede skema, og computerne (flere)
> stod og snurrede i mange dage når der blev lagt skema. Der er ca.
> 700 elever og 60 lærere inkl. børnehaveklassepersonale.
> Programmet kostede dengang (10 år siden?) ca. 5'000 kr. og kurset
> noget lignende.

Jeg har nu siddet og arbejdet et par timer på det, og den kan allerede
generere et helt skema (testet på 4 elever, 2 lærere, 3 lokaler og 5
courses).

Den tager hensyn til, at flere courses ikke ligger oven i hinanden, og
jeg har også næsten fået det til at virke med lokale-"krævninger" (hvis
skolen har lejet en gymn-sal til gymn og lignende, som de kun har adgang
til på bestemte dage, i bestemte lektioner).

Loadtiden tager 0,05 sek. uden indeksering af databasen, når den skal
generere skemaet (testet med de få data, som jeg har lagt ind).

Der er stadig masser af ting der skal rettes, og koden er langt fra optimal.


Jeg lavede det på den måde, at jeg fik den til at gennemgå alle
lektioner alle dage, hvor den ved hver lektion under, om der var et
lokale, som der kun var adgang til der. Hvis ja, undersøgte den
yderligere om der kunne smides en krævet klasse på, ellers en random
lektion.

Yderligere holdte den øje med (via et array), om der var 2 eller flere
af samme lektioner på en dag (således at der ikke kom 6 dansktimer efter
hinanden).

Planen er så, som en anden også har skrevet, at lave et
"optimerings-script", der gennemgår skemaet endnu engang, for at se om
der kan laves optimeringer (mht. hultimer og lignende).


Det var nogle rigtig gode links i alle sammen kom med (og i må sku også
gerne komme med flere ;) ). Betragtet ud fra hvor lidt tid, som jeg har
brugt på det, synes jeg det er gået rigtig godt :)


Når jeg har skrevet lidt mere kode, poster jeg det lige i tråden, hvis i
har lyst til at se den :)


--
Med venlig hilsen
Kasper Johansen