Min hours daily for a teacher/for all teachers can lead to endless loops

[Julio González Gil]

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

[Liviu Lalescu]

It is more a suggestion rather than a bug, so I moved it on the suggestions board.

Thank you for reporting this! Unfortunately, there are too many possible situations like this. It is not too difficult to report the impossibility of this situation, but probably other reports would come. I therefore rely on the user to check the highest stage timetable and the difficult activity.

I added this in the TODO:

Code Select Expand


301---------------------------------------------------------
From Julio González Gil (on forum):

Rephrased by Liviu Lalescu:

We need more preliminary tests for the constraint teacher(s) min hours daily, to avoid
unnecessary work to discover the bugs. For instance, if we have teacher(s) min 2 hours daily
with allow empty days, and:

- The teacher is only available one hour on a day, or
- The teacher has one activity divided into two components, 100% min 1 days between them,
each component having duration 1.


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

[Julio González Gil]

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).

[Liviu Lalescu]

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.

- 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.

[Julio González Gil]

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.

[Volker Dirr]

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.

[Volker Dirr]

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.

[Volker Dirr]

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 wrote similar stuff for rooms and same starting time constraints but we didn't added it yet, since there where small problems with other example file. i think they only happen since the free time slot check where done after the "set disallowd" 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.)

[Julio González Gil]

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).

[Liviu Lalescu]

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).

Yes, this is good, might tell you impossible before starting to generate, or improve generation speed. In practice it won't bring much speed improvement during generation, though. I'll add this in the TODO, but I am not sure if I'll do it soon.

There are however very many possible "impossible to generate" situations to treat.

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


As Volker said, the days may be empty.

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.

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

[Liviu Lalescu]

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'll add this in the TODO, as option A, but I am not sure when I'll be able to do it. In fact, for the moment I prefer to keep the changes to a minimum, until I get in a new stage with FET, as now it is very stable.

[Julio González Gil]

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.

[Liviu Lalescu]

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.

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 ).

[Julio González Gil]

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)

[Liviu Lalescu]

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.