Tweaking FET settings suit Morrocan schools needs

[Chafik Graiguer]

why a standart FET version cant suit morrocan schools standards ?
Well, there are tree special requirement for morrocan schools:
Requirement 1: each day is devided into two periods: morning (08:00, 09:00, 10:00, 11:00), afternoon (14:00, 15:00, 16:00, 17:00) seprarted by lunch break for all (12:00, 13:00)
Requirement 2: Teachers work one period either mornig or afternoon, in very rare cases, they can work on both
Requirement 3: Students can have gaps around lunch break
for example , a students group can have lessons at  08:00, 09:00 then at 16:00, 17;00 same day !!!
like this:


I will discuss here how I tried to tweak FET setting to suit those requirements, along with same trailing problems
NB: FET was able to generate a perfect timetable for teachers, ther are only some minor problems for in students timetables)

It is very easy to suit requirement number 1:
-Define 6 working days
-10 periods per day
-make all rooms R1, R2, R3 ... only available at morning periods (08:00, 09:00, 10:00, 11:00)
-make a mirror list of rooms
R1 ---> mirror R01
R2 ---> mirror: R02
....
-make R01, R02, R03 ... only available on afternoon periods  (14:00, 15:00, 16:00, 17:00)
-Now, there is no room available for lunch timeslots 12:00, 13:00  
-Every teacher or group or subject who has prefrd or home room R1 has also R01... and so on....
----
Now, How to suit requirement 2 ?
Very easy:
-Teachers max gaps per day ---> 0
-Since there is already two lunch gaps due to rooms unavaillability, teachers will only work on morning or afternoon
We can achieve the same result by making R1, R2... into one building B1,
R01, R02... into one building B2
and define:
Max building changes per day for teachers -- > 0

The requirement 3 is most difficult  
We can force FET to schedule a students group whenever neccessay at 08:00, 09:00 then at 16:00, 17;00
by setting:
minimum gaps between building changes ---> 2
the number 2 refers to lunch break
So, in some extreme cases, students can have 6 contiguous/consecutive gaps a day ( including lunch gaps- see big red rectangle in screenshoot above)
There is Two problems thought:

Problem 1: ( see screenshoot below- the 3 red rectangles)
There is no way to ensure 0 gpas between morning or afternoon activities
Problem 2: ( see screenshoot below- activity marked 2 in red color)
FET sometimes puts ONE hour activity at morning or afternoon.   This is not legal, At least, we must have either:
-no activity; or
-two consecutives activities (1+1); or
- a single activity (duration 2)



Possible FIX:
1- FET shouldnot count gaps while changing building into TOTAL gaps
So we can set Max gaps per week for all students --> 0
2- We need a new constraint: Minimum consecutive activities ( like Maxmimum consecutive activities   )
and we will set it to : 2
This will solve problem 1 and problem 2
since, whenever FET put two activities separated by a gaps, It will violate "minimum consecutive activities" constraint
In other words, If we have a "minimum consecutive activities" constraint, we dont need gap constraints any more !!
what do you think Liviu ?
Is there any way to go further ?

[Chafik Graiguer]

Another quesion:
How deos the algorithm handle the following combined constaints:
- Min gaps between building changes for students ---> 2
- maximum gaps per week for students -----> 0
Wich constraint get priority ?

[Liviu Lalescu]

Possible FIX:
1- FET should not count gaps while changing building into TOTAL gaps
So we can set Max gaps per week for all students --> 0
2- We need a new constraint: Minimum consecutive activities ( like Maximum consecutive activities   )
and we will set it to : 2
This will solve problem 1 and problem 2
since, whenever FET put two activities separated by a gaps, It will violate "minimum consecutive activities" constraint
In other words, If we have a "minimum consecutive activities" constraint, we dont need gap constraints any more !!
what do you think Liviu ?
Is there any way to go further ?

1. It is too difficult to add to the algorithm (impossible?)
2. Again too difficult to add to the algorithm (impossible?)

[Liviu Lalescu]

Another quesion:
How deos the algorithm handle the following combined constaints:
- Min gaps between building changes for students ---> 2
- maximum gaps per week for students -----> 0
Wich constraint get priority ?

Both must be respected, if they have 100% weight. But if you say that students are not available from 12 to 14 (or add a constraint break), the break will not be counted as gaps. But you'll need:

lesson
lesson
---------
---------
lesson

(legal)

because:

lesson
---------
---------
---------
lesson

is illegal, because you have 1 gap.

[Chafik Graiguer]

Yes. I know, Breacks and timeslot marked unavailable are not counted as gaps
but

Both must be respected, if they have 100% weight. .

How does algorithm respect both f them
they are mutually exclusives
whenever FET will try to respect one constraint, it will break the other !!
(sorry if I am making wrong stupid conclusions/inferences.     I am not a programmer! and my mathematics's skill are moderate )

[Liviu Lalescu]

Yes. I know, Breacks and timeslot marked unavailable are not counted as gaps
but

Both must be respected, if they have 100% weight. .

How does algorithm respect both f them
they are mutually exclusives
whenever FET will try to respect one constraint, it will break the other !!
(sorry if I am making wrong stupid conclusions/inferences.     I am not a programmer! and my mathematics's skill are moderate )

Please try a sample. I think FET will oscillate forever.

FET puts an activity. Then another. Then another. If it cannot find a good place, FET takes out an activity to put this new one, and the one taken out is placed again in another place. So, say it puts A1, A2 and A3, then A4 cannot be put. It takes out A2. So, placed A1, A3 and A4, tries to put A2. Takes out A3, and so on, it cycles infinitely.

[Chafik Graiguer]

Please try a sample. I think FET will oscillate forever.

Yes . I already test it with real .fet file when I rtied to tweak standart FET version seetings above
It hang forever at 160 out of 323 placed activities
So user should never use this two constraint similtanuouslly

[Liviu Lalescu]

If you want to see more, you can use GNU/Linux. On this system, FET outputs some more information on console. Or compile FET on Windows with console (add a line in interface.pro at the and, "CONFIG+=console" and compile). Then FET writes you a sequence of replacements and you can see if it cycles (the "times" variable increases much, above say 50 - you can see it in the console).

[Chafik Graiguer]

If you want to see more, you can use GNU/Linux. On this system, FET outputs some more information on console. Or compile FET on Windows with console

Very intersting feature !!
I will try both on Linux and Windows
but I will start by Linux, since I have already dual boot system
Later, I will try to compile on Wondows. I remember, a couple of years ago, I recompiled Linux kernel to include My sound card driver !! so I think I can do it    

This is a very usefull feature, since I can see in real time, what FET is doing

1. It is too difficult to add to the algorithm (impossible?)
2. Again too difficult to add to the algorithm (impossible?)

sad to hear that, since I was thinking, adding Minimum consecutive activities, into algorithm, need only a sign inversion ( + ---> - ) like in elementary mathemetics

[Liviu Lalescu]

In GNU/Linux, you can also write: ./fet >output_file.txt

And you can examine this file, because usually the things are too fast.

[Liviu Lalescu]

1. It is too difficult to add to the algorithm (impossible?)
2. Again too difficult to add to the algorithm (impossible?)

sad to hear that, since I was thinking, adding Minimum consecutive activities, into algorithm, need only a sign inversion ( + ---> - ) like in elementary mathemetics

:-)  I wished it was that simple. But generation algorithm (generate.cpp) is very difficult.

I am adding activities one at a time. I can always detect if there are more than x consecutive and repair situation, but a progressive approach I think cannot work on minimum consecutive.

Hmm, you might be right in a way, like min hours daily: I keep track of the remaining activities at each time, to see if the timetable can be filled to respect the minimum hours daily. But min hours continuously is more difficult:

suppose I have:

Math
---
Phys

Then FET should consider that putting an activity between Math and Phys solves the problem. But this situation is difficult to detect, because I need to think of each place to put an activity -> many possibilities.

[Volker Dirr]

Hallo,

I solved your problem with the official Fet version.
But i need a small trick for that. I sent you the datafile.
Please check and tell em if that trick is allowed at your school.
I think it is, because we use this trick every year (but because of an other reason).

[Chafik Graiguer]

 

I solved your problem with the official Fet version.
But i need a small trick for that. I sent you the datafile.
Please check and tell em if that trick is allowed at your school.

many thanks Volker for taking time to help me
As I said before , the main problem is those single activites scheduled at morning or afternoon
we need to supress them or to add another activity so the two activiites will be consecutive/contiguous

But min hours continuously is more difficult:

suppose I have:

Math
---
Phys

Then FET should consider that putting an activity between Math and Phys solves the problem. But this situation is difficult to detect, because I need to think of each place to put an activity -> many possibilities.

But how FET keep track of maximum consecutive activitites cconstraint ?
I think ( maybe I am wrong) FET put first activity , then whenever FET add anonthe ractivity, it  checks two things:
are  those activities consecutives ?
Do we reach maximum consecutive activities value ?
in other words: FET knows all the time about consecutive activities value
I dont know the way FET populated the timetable  
I imagine FET puts first activity, then checks if putting another activity adjcent to it is possible
After that, when swapping activities, FET should check if ...
Oh ! sorry  I am totally lost  

[Liviu Lalescu]

@alfaromeo previous post:

You are right in a way, everything should be possible in timetabling. But it is not easy.

I put activities each at its time. At each step I need to check that the timetable is still a valid partial solution.

To check that it is valid partial solution, I need to compute if by adding the rest of activities, the solution can be obtained.

So, I have some lonely activities and some unplaced yet activities. May I put the unplaced activities in good places so that the rest of the activities are not lonely?

This is easy - for each activity, consider that it needs a pair, so I need to have left n activities for n placed lonely activities? Hmm, not quite so, because, like I said earlier, say we have Math, empty, Phys. Then I may put one activity on empty slot, so I need only one unplaced, not 2.

It seems quite difficult.

I admit I did not think very much, because I am tired of working on a nice new feature.

It might be a solution as you say, but it seems too complicated to me now. I'll think about it. Maybe you can talk more about your ideas here, if you read something about the algorithm.