Messages

Hi Emiliano,

Can we coordinate?

I will have 35 available hours starting tomorrow to help with the Spanish translation as a result of SUSE's hackweek

Did you already started your working on this?

As promised, here is an anonymized input file for a Russian medical college (in this context could be similar to a pre-universitary vocational training if my english is correct!):

• 14 groups
• More than 45 subgroups
• More than 40 teachers
• More than 120 subjects
• A huge number of restrictions

Feel free to ask other details that can help you with the file categorization for the examples folder.

FET was able to manage a fairly complex two-week timetable for a Russian educational institution (14 groups, more than 45 subgroups, more than 40 teachers, more than 120 subjects and a lot of required restrictions).

Not just FET is a great program, but the authors were really helpful (as you can see at this thread), allowing us to achieve our goal.

Keep up the good work, Liviu and Volker!

I made a small change, see the attached code. I think you can compile (just overwrite the old file). Use the "new" folder file, and in the "old" you can compare with the official FET-5.30.8.

It is a good change, but a bit not elegant, that's why I won't add it right away.

Instead of copying files, I created a patch file (attached) against FET-5.30.8, so applying is just a matter of decompressing the gz file, and being at FET folder, running:

Code Select Expand

patch -p0 < path-to-minhoursprofcheck.patch

I compiled and it is working perfectly for both constraints (constraint for one teacher and constraint for all teachers).

It shows the message:

For teacher Prof1, the constraint min 2 hours daily is useless on day Вторник. Please make this teacher not available on this whole day, for performance and better correctness checking.

I will make another test tomorrow with the full timetable we have, by recreating the issue we had and will let you know.

After you press Generate new (start generation), FET goes to generate_pre, then to generate.

For the moment, I could implement this test just for you, as a minor custom version, for you to test. But I am a bit afraid to add into the official, as things are very safe for now. The code should not be very complicated, so let me know if you would like this customization (no problems for the extra work ).

Well, I don't really need a customization since I was able to locate the problem and fix it, and this started more as a bug/suggestion.

However I am happy to test and help it if you think it could be useful and it could go to mainstream code at some point   

Otherwise, let's add it to the TODO and let's review that CI (Continuous Integration) stuff I told at another thread, so we can perform automated tests to make it safe to add new changes (even concurrently)

I am not sure I understand this entire last quote, even if I tried reading more times. Once you start the generation, you cannot modify the constraints anymore. The best is to choose the min hours daily constraints for each teacher, if you have some exception teachers. I am so sorry, but I did not care enough from the beginning and now the exceptions are so hard to manage

This is my entire fault :-D

For me "starting the generation" meant clicking the "Generate button".

But according to your code and Volker's comment, you have a "generation_pre" phase where you perform checks, and were you could perform this new check and show the correct suggestions for the user depending on the constraint being violated.

about your pseudo code: a small "bug".
your code/check can/should be added in generation_pre, not in generation because of speed.
so there is no "abort generation" because it shouldn't start at all.

Yes, that was the idea 

But as I didn't have look at the code, I was not aware of "generation_pre" (I just opened the CPP file and see what you mean).

other bug: it is only correct if the teacher is not allowed to have free days. if the teacher can have free days, then your code is wrong.

Correct! I forget about the free days.

a) fet should show a "speed warning" only. so user can modify himself
or
b) fet should automaticly disallow that timeslots for related activities. but this is a bit critical. (i wrrote similar stuff for rooms and same starting time consttraints but we didn't added it yet, since there where small problems with other example files. i think they only happen since the free time slot check where done after the "set disallwd" even it must be done before. but that mean we must split that in the source, since currently Liviu done both very close at the same time.)

I would go with option A, with a warning for each problem found. In my opinion it's better to allow the user to fix it and least you are sending a warning to the user about the speed (I'd mention that in this case you can even have impossible timetables as it was in my case).

I guess I could try to have a look at the source code and see if I can make a patch... but I feel it would take ages for me to understand current code and would do more harm than good (as you can see with the "free days" problem and also because I never coded anything in C++ and much less for QT, only C ages ago and just simple code for terminal apps).

I am not sure I understand correctly, but:

- About removing the constraint for all the teachers and adding one for each teacher - this is unfortunately the only solution to this problem. I should have thought from the beginning of a better solution. This suggestion is in the TODO (item #82), and I'll add you as a proposer also.

That is what I did in my case, because in the end I was allowed to have teachers with different minimums.

But if we are sure that nobody can teach less hours than the global constraint (for all teachers), another option is to mark as unavailable the days for the teacher(s) with problems.

For example if we have "min hours per day = 2" for all teachers, and TeacherA has Wednesday with only one free hour (time slot), it is clear we can mark the whole Wednesday as not available (as it won't be used anyway).

- You cannot stop the generation and modify the constraints and continue the generation, at least not with the current algorithm.

Maybe you can explain in other way your suggestion, or I'll try to read a bit later.

In the end, the problem can happen because of two reasons (that can happen at the same time):

• For one or more days the teacher does not have enough activities to respect the constraints(s), despite it has enough time slots for all days. This depends on how activities are distributes during the generation
• For one or more days the teacher simply does not have enough free time slots so it can never respect the constraint(s). This depends on how the user configured the "min hours" constraint and teachers' availability (this was my problem, and the problem at the FET files I sent)

While the first case can be tricky to detect, the second one should be easy even before starting actual generation (as happens for other problems, where the generation does not start because of errors)

With pseudocode, something such as:

Code Select Expand


for each teacher:
    for each day of the teacher:
        if free slots for the day < min hours per day for the teacher
            show an error with teacher and day with problems, and suggestions
            raise flag for errors
        else if free slots for the day < min hours per day for all teachers:
            show an error with teacher and day with problems, and suggestions
            raise flag for errors
if flag for errors raised:
      abort generation


For the error the suggestions could be:

 
• If we are breaking min hours per day for the teacher:
  
       
  • Make the problematic day unavailable for the affect teacher
  • Or remove the constraint
  • Or just increase the value of the contraint
   
• If we are breaking min hours per day all teachers:
  
       
  • If all teachers must have the same minimum:
    
             
    • Make the problematic day unavailable for the affected teacher
    • Or remove the "all teachers" exception
    • Or just increase the value
  • If some teachers can have a different minimum:
    
             
    • Remove the constraint for all teachers and add one for each of the teachers with the correct values.
   

Hope this makes more sense.

Please let me know if you want some changes in this TODO item.

Sounds fine to me, but a (maybe stupid) suggestion:

What if FET checks slots for all teachers and days, and tries to enforce the "min hours daily" constraints, and if one or more days are to break the constraint shows a warning and offers the user the option to stop and fix?

This way the user can choose one of the following options (can be offered depending on which contraint is broken):

For all cases:

• mark the days with less hours available than "min hours daily = X" as not available.
  

When the problem is a constraint for a teacher:

• modify/remove the constraint for the teacher.

When the problem is the constraint for all teachers:

• modify the constraint for all teachers.
• remove the constraint for all teachers and add one for every teacher (this was my option in the end).

I am not sure if this is a bug or a suggestion (if it's the second, feel free to move the thread)

The endless loop happen when a teacher with the constraint "Min hours daily for a teacher" or a teacher for "Min daily hours for all teachers" can't meet the requirement because one of it's days only have one free slot, but the assigned activities are correct.

For example:

• We have a teacher with two activities assigned, each of them with 1 hour which need to happen different days.
• He is available only two days: the first one two hours (slots), and second one one hour.
• He can teach the activities, but can't meet the "min hours daily" constraint (either for him or for all teachers)

In this case, FET doesn't warn about it. It will start creating the time table, and when the activities for the affected teacher are to be placed, will enter an endless loop.

It's easy to notice at the attached FET files, but in my case it took me a little bit more to notice, as my teacher was part of a large timetable, and when I had a look at the highest generated timetable I could only see that all the activities for the teacher except one were placed (yes: I didn't have in mind that "Min hours daily for all teachers" was 2 -with free days- )

Not sure how hard it is, but It would be great if FET could check that both constraints can be fulfilled by the teachers before starting the timetable creation

Thank you for your kind words!

You might want to read the FAQ: "Q: How to define the students into sections?" and "Q: How can one work with overlapping structures of students?". And I think in Volker's manual there are some words about this.

Now that I had a second look at that part of the FAQ, I was able to understand how to apply it to this P/B problem and how the subgroups created by the division process, while not useful to be assigned to activities, can help to identify relationships between groups.

So I didn't really need to even use any kind of tags: looking the activities by year showed all the info for the groups, and the problem is now 100% solved 

Now were are struggling with all the restrictions we need, which are almost more than activities, and I hope the timetable will be ready during this week.

I talked to Ilya (the old Russian translator) and he said he cannot continue with the translation.

Future correspondence about the Russian translation would be best to be taken on the dedicated thread, http://lalescu.ro/liviu/fet/forum/index.php?topic=699.0

Got it! She already wrote a message there and, as soon as we all have timetable ready, I will show her how to make the translations (she's not IT so I will need to help her with QT Linguist installation and some first steps), and I will have a look at the other things mentioned (I'll send you an email with a few questions about how you manage your code so I can see how I can integrate this with package generation).

Thanks a lot for your for all your help and patience!

Yes, a large number. Not too much for the timetable generation. I worked with more constraints of this type and it was OK. The constraint is highly optimized. The only problem is your patience to input them - or do you have a script to generate the .fet file?

I am not using a script right now. I could do it, of course, but most probably the correct solution is using correct group division.

I could add the constraints or even script the input. But the person who is going to use the program is not so technical, and will need to understand how to do it, so the group division solution is far way better.

I think your idea works. But I was thinking of something a bit different. LD101 a year, divide it automatically by 2 categories: (P1, P2) and (B1, B2, B3). Then, you will have 2*3=6 subgroups in LD101: LD101_P1_B1, LD101_P1_B2, LD101_P1_B3, LD101_P2_B1, LD101_P2_B2, LD101_P2_B3. You can remove the empty subgroups, like LD101_P1_B3, if I understood correctly. Then for activities you can use the year, the group or the subgroup, as you wish. You can add more students sets per activity. For the group P1 you will use the subgroups LD101_P1_B1, LD101_P1_B2, or the group LD101_P1 (but be careful with LD101_P1_B3, it is I think necessary to remove it in this case, so you don't have problems with it).

It is a bit difficult for me to visualize this whole situation. But I hope I am right and it works. Please do a small test. Please let me know.

Absolutely right! It is hard to visualize it but you understood the problem correctly.

However when I divide automatically (I create two categories, assign P1 and P2 for the first one and B1, B2, B3 for the second one as you can see at the screenshots) I get 5 groups (P1, P2, B1, B3, B2) and 12 subgroups with all the possible combinations between Ps and Bs. I think this is the expected behaviour.

So to get the screenshots you saw at the previous post, I divided automatically and then removed groups LD101-B1, LD101-B2 and LD101-B3 and also subgroups LD101_P1_B3 nor LD101_P2_B1 (as you correctly guessed, I do not need them).

Just in case, I am adding a couple of screenshots on how I divided, and the resultant .fet file.

I will make a small test with one of the groups tomorrow and will let you know, but I have the feeling that it will work perfectly 

I do not understand the drawback - manually calculate the correct B? You just add a dummy activity tag for each activity to group this activity to an activity tag section in the activity tags timetable.

Once again, you are right, I was thinking of a dummy tag just for the group (year), but I can create one tag for each group, P and B as needed.

Thank you for your patience and support!

PS: I will let you know about the other things I mentioned soon, as soon as the time table is ready.

My girlfriend will took out over the translation as she is a Russian language teacher and she's willing to help as a way to thank you, and I will help you with the technical stuff (RPM/DEB, maybe the windows installer if I show you the benefits and you thing it can help -we can use NSIS which is Free Software and it works even under Linux to package for windows-, and maybe a Continous Integration if you want to automatically build and package all the changes you make and check that it works -instead of doing it manually-).

And needless to say, we'll send you a donation, as both you and the program are preventing someone becoming crazy making the timetable ;-)

Hi again.

Yes, I think I understand both ideas (I hope!).

The problem about the first one is that it will generate a lot of constraints (unless I'm wrong):

- 4 for each day (each P/B combination)
- 12*4 for each group (LD101, LD102...) having both P and B
- And since we have 7 groups with this configuration, that's 336 restrictions.

Most probably too much, even if I just ignore the warning about this kind of constraints.

So for me you are obviously right, and the way to go is using a proper group/subgroup division.

If I understand the idea correctly, that means:

- The groups (LD101, LD201...) being years and not groups as now
- Two groups (from FET perspective) being LD101-P1 and LD101-P2.
- LD101-P1 will contain LD101-P1-B1 and LD101-P1-B2 as subgroups.
- LD101-P2 will contain LD101-P2-B2 and LD101-P2-B3 as subgroups.

Then fake tags with the same names as the groups -years for FET- such as LD101, LD201... to be assigned to the activities:

- Theory activities will be assigned to years (FET)
- Practice activities will use the correct groups or subgroups:
  * P1 will use group LD101-P1
  * P2 will use subgroups LD101P2
  * B1 will use subgroup LD101-P1-B1.
  * B2 will use subgroups LD101-P1-B2 and LD101-P2-B2.
  * B3 will use subgroups LD-101-P2-B3.
- All activities (both theory and practice) will have the tag for the parent group (i.e. LD101).

So in this case:

- LD101-P1 and LD102-P2 activities happen at the same time as long as they use different teachers, or can't if they use the same (which is correct).
- B activities won't require "A set of activities are not overlapping" anymore since the subgroups will prevent it.
- The constraint "Max hours daily for all students" will work even for B* since for example LD101-P1-B1 is a children of LD101-P1 which itself is a children of LD101.

To make it more graphical, the attached screenshots is what I need for every group having both P and B, plus a dummy tag LD101 (and the same for the rest of groups, of course).

And finally, since I am using activity tags, I can use "Activity Tags" at the HTML pages to visualize each real group with the only drawback that when there are subgroups I will need to manually calculate the correct B according to the rules above.

Is that the idea?

Thanks for your help!

Thank you for your kind words! Did you obtain good timetables for other files?

Yes, FET is doing a nice job when there are only subgroups P* or B* for a given group 

Did you see the constraint activities occupy max time slots from selection? You can add a set of activities, select a single day, and say that max occupied is 4. If you add n_days_per_week constraints, you can obtain a custom max hours daily.

But I think you are complicating things. I think you just need to divide the year by 2 categories (divisions P1, P2, and divisions B1, B2, B3). Then maybe delete useless subgroups, like B3_P1, and use subgroups like B2_P1.

The problem with the constraints is that (if I understand the idea) I would need to create four "activities occupy max time slots " constraints for each group using P and B (we have four of them).

- Full group, P1 activities, B1 activities
- Full group, P1, B2
- Full group, P2, B2
- Full group, P2, B3

And most probably I would need to repeat this for each one of the days (we have 12 as we configured two weeks of six days) so this will go against the advice of not adding too many constraints of this tipe.

However I am not sure what do you mean with "n_days_per_week" constraints.

About the categories and divisions I think I can get the idea, but in this case there will be separate tables for P1 and P2 (as both will be groups, not subgroups), while what is needed is a table for the group which contains all the info for the common lessons (theory) and all practice lessons for P1, P2, B1, B2 and B3.

As I think my explanation wasn't too clear, I'll post a couple of screenshots (one with student groups and one with chunk of a timetable). The original stuff produced by FET is on the left, but I provide the translation (without subject names) on the right.

In this case, and only for this day, students' availability is restricted (first hour is not available), but other than that it is fine as an example.

As you can see FET is working charmly, as it can fill the five slots.

However a student such as for example student #2 would have 5 hours, because he belongs to SD31-P1, SD-31 (theory lessons), and SD31-B1

So in the end what I guess I need is something like "restrict max number of hours that several sets of students can study per day" so all sets are considered for the calculation and I can combine .

My friend just told me that I can share the .fet file, so it is now attached to this post.

Instead of having a look at LD101 (ЛД101) which is the first we added and more or less is working because students can't study during the last two hours in any case, I suggest you have a look at SD31 (СД31). П1 is P1, П2 is P2, Б1 is B1, Б2 is B2 and Б3 is B3.

Hi everyone.

First of all, thanks to Liviu Lalescu and Volker Dirr for this excellent software.

I am trying to help a friend here with a particular group structure, and trying to get rid of the problems so we can have the time table ASAP and we can help you with the Russian translation (I noticed there are several things without translation), maybe creating windows installers with NSIS and DEB/RPM packages, so it's easier to distribute FET (maybe I could even help you with a Continuous Integration if you are interested)

Now, going back to the problem:

In this particular case, the timetable has several groups for each year (in our case, a year is not a year but a Degree), for example:

LD11, LD32, LD33

The groups study all the theory together, but for the practical activities they are distributed differently depending on the activity:

- Either two subgroups (let's call them P1 and P2) with equal size.
- Either three subgroups (let's call them B1, B2, B3) with equal size.

With the current distribution of students:

- B1 contains half of P1.
- B2 contains the other half from P1 and half of P2
- B3 contains the last half for P2.

So P1 is "parent" for B1 and B2, and P2 is "parent" for B2 and B3

Obviously this allows activities for B1, B2, and B3 to happen at the same time, but also for P1 and B3, and P2 and B1.

This is what I already achieved, after adding all the activities, by adding constraints "A set of activities are not overlapping":

- Activities from P1 never happen at the same activites from B1.
- Activities from P1 never happen at the same activites from B2.
- Activities from P2 never happen at the same activites from B2.
- Activities from P1 never happen at the same activites from B3.

This works without any issue.

But the problem is that no student can have more than 4 hours of lessons each day without gaps (each day have 6 hours), and since Bs are not related to Ps (since all of them are subgroups, with one of the groups as parent), the restriction "Max hours daily for all students" does not work.

In other words, the sequence  "A, P1, P1, B2, B2" does not trigger the constraint since for FET P1 and P2 are different subgroups. It also doesn't prevent gaps for sequences such as "P1, P1, B2, B1" despite some students will be present at P1 and B1, but not at P2.

I tried several things like:

- Applying "Max hours daily for a students set" for all of the groups.
- Creating tags B1, B2 and B3 and adding them to all theory and practice activities showing which Bs are part of each P, and showing that all Bs are part of each group, then I tried to enable the constraint "Max hours continuously with an activity tag for all students" and "Max hours continuously with an activity tag for a students set" and it is not working.
- Playing with the availability for the students sets reducing each day to four hours, but it doesn't help as if I restrict the groups to have only four hours available, the teachers are not able to teach all the activities.

Does anyone has any suggestion about how to proceed?

At this moment I can't publish the .fet file or tables, but I'll request permission to do so if you fell that it can help.