Help choosing FET version and something else.

[josemgs]

Hello! I am new to FET and in some manner I am also also new to timetabling. I am trying to figure out how FET can help me in solving my problem. It is a two stage problem. I'll try to explain it.

Consider a given year in FET. In my institution, in Spain, there are four sections: 1.- Ordinary spanish section, 2.-British program section, 3.-Bilingual English  section and 4.- Bilingual French section. Each have three subjects not share with the other sections, but there are a good quantity of optional subjects that are common and elligible for all the students, no matter which section they pertain to. There are also optional subjects exclusive of each section. We have to form a maximum of 6 groups with a maximum of 30 students. Minimum number of students to teach a course is 10. If the number of students is under 10 they are encouraged to change their options. Usually, all groups are full  or almost full. As a consequence we need to find a distribution of students among the groups in such a way some subjects run simultaneously and this requires that the subjects involved have no students in commmon. Up to my  poor knownledge of FET details, I could do that with the FET-BP custom version. An additional "constraint" is that groups have to be as uniform as possible in the sense that students in each group should follow the common lectures (subjects) at the same time with the same teacher and separate only for optional subjects.

Up to now this hard work is done manually, spending weeks to find the appropiate distribution of students in the six different groups.

Do you think is it possible to solve this whitin FET?

Once the groups are established FET Official version could be use in the normal way to find a timetable, with teachers and room constraints and all this kind of things. Of course, this is a formidable problem, but the required previous problem that I have tried to describe is not a trivial one when the number optional subjects increase.

Thanks a lot.

[Volker Dirr]

Sounds like a problem that can be solved with FET-bp but also with StElTo.
Not 100% sure, since some information is missing.
I thinh you should just try, or sent us (old) data so we can have a closer look.

[josemgs]

Of course, there are missing data.  I will have a look at StEITo (I was not aware of their existence until now) and then I'll tell you all the details.

Thanks.

[Liviu Lalescu]

Maybe the first phase is possible with FET-BP, as Darren McDonald does. The students will not be placed in the same moment for two activities.

a) You have constraints for min/max students per block and teacher (constraint activities min/max simultaneous in selected time slots). The teachers are FET days and the blocks (time slots) are FET hours. You can use a progressive approach, strengthening the constraints as you find timetables.

I am not sure about:

1) If number of students is less than 10, they are encouraged to change their option - this should be done before inputting data to FET-BP?

2) Additional "constraint" - it is of course possible to say: same starting FET time (which means same teacher and same block) for some activities. But do you know which?

As Volker said, some pdf timetables of the previous years might help.

[josemgs]

Hi,
thank you for your answers.

Next, I try to answer your questions:

1) If number of students is less than 10 they should change the option before inputting date in FET-BP, yes.
2) One of the problems is this: I don´t know which activities (one student, one subject) should go in a given block with a given teacher before solving the problem of partitioning the students set.

As a matter of fact  I have tried FET-BP (I like it very much, specially speed) with some artificial, simple data. It solve very well the non-overlapping problem, but I can´t find a way to force the following: If a set of students meet in Spanish they should also meet in maths if possible. Remember a don't know weather students will meet in Spanish  "a priori" . This is part of the problem to be solved.

Thanks a lot.

I attach a file with one unreal simple example. 20 students, 2 sections. In the Excel file I set the problem and one example of a feasible but not optimal solution. TXT file is a summary of the problem with some comments.

[Liviu Lalescu]

This is just to inform you that I am working on it. I like the way you explained things - it is very clear now. I'll let you know if I can think of something.

[Liviu Lalescu]

It is a very interesting and difficult situation.

I have some ideas:

Suppose: 4 groups GA, GB, GC, GD (like in your situation).

Then schedule the activities in a table with days = these 4 groups and hours = Spanish1, 2, 3, 4, Math1, 2, 3, ....

All activities of a student must be on the same day (existing constraint).

Say (unlike your example) we have 2 French and 3 Literature subgroups.

And activities: A1(Student1, French), A2(Student3, French), A3(Student1, Literature), A4(Student3, Literature).

If we place A1 on day GA hour French1, then if we place A2 on day GA it will be preferred 95% (or something like that) to be placed on hour French1, otherwise it goes to French2. If we place A2 on days GB, GC, or GD, it can go to any French (1 or 2).

Hmm, but what about the 30 hours per week constraint?

It is not going to be easy.

[josemgs]

A quote from you:

"If we place A1 on day GA hour French1, then if we place A2 on day GA it will be preferred 95% (or something like that) to be placed on hour French1, otherwise it goes to French2. If we place A2 on days GB, GC, or GD, it can go to any French (1 or 2).

Hmm, but what about the 30 hours per week constraint? "

Yes, that's the question. Some Activities in GA will certainly go at the same time in the real timetable. In order to place A2(Student 3, French) in  GA we have to be sure that all their other activities can run without overlappings. 

My approach is as follows:

The table now have 4 columns (groups GA,GB,GC,GD) and 8 rows (Time slots for subjects, each with its own duration corresponding with different hours per week ). Subjects placed in a given column and row must to be planned together in the final timetable.

Consider now the activities for Student 1: A1(Student 1, French) A2( Student 1, Literature).......A8 (Student 1, Philoshophy) with no (Student 1, Chemistry)
Similar for Students 2 and 3 , A9(Student 2, French), A10 (Student 2, Chemistry).....A16(Student 2, Philosophy) with no (Student 1, Literature) and the rest as Student 1
                                                   A17(Student 3, French), A18(Student 3, Chemistry), A19(Student 3, Literature),.....A24(Student 3, Philosophy) and the rest equal to Student 1, for instance.

Now we place all the activities for Student 1 in column GA. For Student 2 we can place all but activity A10 in the same positions than for Student 1. For A10 we can choose among all slots with the same duration, for instance slot occupied by A2 (Student 1, Literature) because they share the same duration and could be planned together. These activities have no students in common.
When Student 3 arrives we cannot place it in the same column because she has activities A18 and A19 which were placed in the same slot before. She can´t attend Chemistry and Literature at the same time. So we can place Student 3 in another column (GB,GC,GD) or try to change our previous decisions in order to allocate all the activities of Student 3 in column GA. This is a kind of recursive algorithm, as yours in FET.
Another question is the order to visit activities. If we want forming groups as homogeneous as possible we can visit activities based in a kind of student's affinity. A measure of this affinity could be the number of subjects they have in common.

But I don´t know if this approach fits FET features or probably there is a much better and simple way to do it. I suspect it should.

[Liviu Lalescu]

Your approach enlightened me.

I think we can use the official FET, with the modification below:

From your example before: First, let's say we put A2, A10, and A18 on day GA hour 4. Then we need to put A19. Displace all activities of Student3 from the other days. Then, in the same day, search for subject Literature of A19 on this day. If it exists, we need to put it there and displaces A18. Otherwise if we put Literature A19 on other hour on day GA (say H1), all Literature activities from the same day GA and other hours than H1 are displaced.

I hope it will work.

Then we will see about other constraints, but this is the first step.

Please let me know what you think. I might begin some work on this, but I would also like your feed-back.

In the above method, how can we ensure your important condition that students from the same group should go together preferably? I think that we could use a progressive approach: on each hour (from 1 to 8) we can have a single subject? So add a constraint activities occupy max time slots from selection, activities with that subject, selected slots = say hour 5 (4 slots: GA 5, GB 5, GC 5, GD 5), max occupied = a progressive approach to minimize this value for all subjects.

[Volker Dirr]

Or try with StElTo, since it will fit all your needs.
If you want to keep the groups of the 3 subjects of SCIENCES, then don't add that 3 subjects separated. just add "SCIENCES" as subject name. Similar to HUMANITIES.
Enter all other subjects pretty normal.
By that you will get perfect results very fast.
It will generate a FET file and so you can set the correct 3 subjects to group SCIENCES (and HUMANITIES).

[josemgs]

It sounds pretty good your method. I don't know the internals of FET, so I don't  know what modifications are needed in order to solve this situation.

What do you think when you say  "Displace all activities of Student3 from the other days" ? Do you mean trying to place all the activities of Student 3 in time slots corresponding to GA? I think this is correct. By definition a Student is in group GA if all its activities are in the column corresponding to GA. This doesn't mean that all the activities have to be held together with the group, but at least simultaneously with other activities of its classmates. I think your method should work.

I 'm not sure wether I understand the constraint "activities occupy max time slots from selection". You select a set of actvities, for instance all the activities involving Maths, and try to allocate them only in the selected slots. It will work as long as you can mantain all the selected activities in the same group they pertaint to.(column).

Thanks a lot for the interest you hace taken in this problem.

[josemgs]

I am reading the manual from StEITo. I'll tell you.

Thanks

[Liviu Lalescu]

What do you think when you say  "Displace all activities of Student3 from the other days" ? Do you mean trying to place all the activities of Student 3 in time slots corresponding to GA? I think this is correct. By definition a Student is in group GA if all its activities are in the column corresponding to GA.

Yes, this is what I mean.

I 'm not sure wether I understand the constraint "activities occupy max time slots from selection". You select a set of actvities, for instance all the activities involving Maths, and try to allocate them only in the selected slots. It will work as long as you can mantain all the selected activities in the same group they pertaint to.(column).

You can read that constraint's help. Select slots (GA,2), (GB,2), (GC,2), and (GD,2), and all activities of Math, and say max occupied slots = 3.

Please tell me: each subject can be on a single FET hour in our notation (a table row)?

Also please tell me: duration 5 activities are on different FET hours (from 1 to 8) than duration 3 activities?

[josemgs]

"Please tell me: each subject can be on a single FET hour in our notation (a table row)? "

Yes, it can.


Also please tell me: duration 5 activities are on different FET hours (from 1 to than duration 3 activities?

Yes.They must be in different FET hours.

[Liviu Lalescu]

"Please tell me: each subject can be on a single FET hour in our notation (a table row)? "

Yes, it can.

No, I meant: "it must?"  I mean it is mandatory for an optional subject to be on say line 7? Or it can be on lines 6, 7, or 8? Or only 7 or 8?