Messages

I have just tried to compile FET source on my computer, with QT 5.7.0
But I got this message: [sub-src-src-pro-make_first] Error -1073741515.
The generate message tab shows that: "The system cannot find the path specified." Please look at my attachment.

It is probably a problem with qmake, the build tool used by Qt Creator. At least in the past, it was important to have your compiler and all other tools in directories which do not contain spaces. From the looks of your screenshot, you are building on Windows? MS Visual Studio likes to install itself in such a path if you do not specify otherwise.

It is also possible to use cmake instead of qmake, but I never tried it.

Can you compile a simple "Hello World" project in Qt Creator in your environment? I have never had a problem compiling FET with Qt Creator on Linux Ubuntu, BTW.

Thanks, Liviu ... I need some time to set it up. This week is pretty much impossible because our IT department upgraded the server, and I am stuck with changing character sets and collations in my MySQL databases from utf8 to utf8mb4 and testing about 50 different views ...  ... besides teaching, of course...

Hi Volker,

Thanks for the input!

i think you can't do that with official FET.

I was slowly coming to the same conclusion...

i think you can try the FET custom mapr version for that ...

Where can I download it?

... or a tool like BLOCK_PLANER_SAT4J ( https://sites.google.com/site/digitalewerkegymnasiumeickel/home/werke/ )

Looks interesting ... still, it would be difficult to define the problem in the expected CNF format.

Hello, Bob,

I am just back. I will try to read your forum post later and maybe answer. Meanwhile, maybe you could attach an example of final schedule resulted.

The final schedule is merely one or more lists sorted in different ways. For example, there are three columns: col 1 = participant, col 2 = activity 1, col 3 = activity 2 (either can also be empty). Or a list of all presentations, two columns: col 1 = presentation, col 2 contains ∈ {'1','2','both'}.

What would be the best way to set this up in FET?

Once every year, we have presentations at our school for students given on a certain day during two time blocks by about 65 different professionals about their various occupations. There are two parameters which determine if and how a presentation takes place: (1) at least 3 participants registered for a presentation are required, otherwise it isn't scheduled; and (2) if more than 13 participants register, the presentation is presented twice, i.e. in both slots. All students are given leave from other subjects for those two periods, so the only conflicts are potential scheduling conflicts within the presentations themselves.

Students can choose one or two subjects as well as a third alternate subject. In essence, once the participants and their subject choices have been registered, some scheduling in the following cases can be done automatically without invoking FET because it is trivial:

(1) All participants who have registered for only one presentation can attend in either block;
(2) All participants who have registered for at least one split presentation (activity) can be assigned in any case depending on when the other activity takes place. There is often a problem of load balancing after automatic placement, however;
(3) If one of the requested presentations cannot take place due to too few participants, the third choice should be considered. This can also mean that some courses which had too few requests as 1st and 2nd choice now can suddenly take place because of additional 3rd choices;
(4) Only the activities which take place once need to be scheduled, and only if there are participants whose other choice also takes place once. Some conflicts are therefore usually inevitable ... student 1 has activities A and B, student 2 has activities B and C, and student 3 has activities A and C: one of the students can only attend one of the chosen courses (this is the simplest form of that conflict which can actually manifest itself as a long chain of connected activities).

I have actually implemented a brute force solution which performs rather quickly due to the fact that there are only two possible time blocks, and since there are always only about 20-25 activities which can take place once, it is possible to store the entire set of presentations as a bitmap in an unsigned 64-bit integer. The index of each bit corresponds to an index of an array containing the presentation data, and each student's choices will be a similar unsigned 64-bit integer with just those two bits set. Then a simple loop over all possible values is performed, and each loop increments a counter. The counter value is treated as a possible schedule: if a certain bit is set, then that presentation takes place in block 2; else it takes place in block 1. The student data is treated as a binary mask: if both choices take place in the same block, a score is kept and incremented (=failure). If different blocks, then success and the score remains the same. After all students choices have been examined, if the resulting score is lower than the previous, it is pushed up to the front of an array containing the ten best scores. Runtime is adequate because there are only 2^20 iterations for 20 presentations. Last time there were 23, and the typical run took about 1.5 minutes on my laptop. Of course, each additional presentation doubles the time necessary to finish. I implemented this as a CGI script in C++.

However, it can't be done that way should the organization decide to use three or more blocks instead of just two. So I think it would be safer to move the scheduling job to FET if possible. But how to define the constraints?

Very nice ... "Activities have a set of preferred starting times", I had missed that one.

One more question: I noticed that you did not define any "Student set not available" times. In the "Activity has a set of preferred starting times", you set four slots preferred. However, shouldn't it be necessary to also define "not available" for the other times?

Thanks!

Activity(ies) preferred starting times (time slots) consider for each slot the maximum value of denial of all constraints of this type.

For instance, in the attached file, 100% denied for all slots but the first four. 90% denied for Wed and Thu first hour, and 80% denied for Tue first hour.

I hope I am not mistaking at some point.

Thank you! I shall look into the file tomorrow.

If you want an activity not preferred time slots - just add preferred slots the other slots   The strongest constraint in each time slot for each activity will win.

There is only one activity for each student in the finished timetable (one piano lesson per week; I am the only teacher, at least in the FET environment, because it is my personal working schedule). Assuming that only four free hours are available for a certain student, I would like to prioritize these according to student choice (1st, 2nd, and perhaps the other two as last choice, only if one of the other hours is not available).

That would appear to mean entering multiple constraints for the same activity with different weights. Is that right? Is it possible?

I have a very simple timetable -- I teach individual piano lessons at a school and need to use the free hours available when students are not attending other courses. So I set each student as a "year" with one "student". For each student, I set the available hours by setting up a constraint "student not available hours". I then assign each student an activity: teacher (me), subject (piano).

If I want to specify preferred lesson times, I use the constraint "activity has a preferred starting time" with appropriate weight (100% if i want to guarantee a certain time, otherwise maybe less). But how do I do a "negative weight", i.e. an activity might occur at a specified time, but preferably not? Right now I am limited to setting an undesirable time as "student not available", but those constraints are always 100%. Can I just set the weight of "activity has preferred starting time" to a very low value?

Thank you, Liviu ... this is good to know.

It would be really nice to have as a new feature (and probably easy to implement).

Unfortunately, it is not easy to implement, and not elegant if I implement it. But you can generate the timetable very fast from the _data_and_timetable.fet.

Would the resulting timetable be exactly the same as the first time?

[timetable]

I'll add your request in the TODO. Meanwhile, did you notice that there is a file name_data_and_timetable.fet in the results? You can open this file and generate on it - it will go very fast, and after that you can export the CSV results.

I did notice the "_data_and_timetable.fet" ... That's what I opened, but i skipped the next step (generating) because I thought it would already have all of the timetable data in it from the last time I generated it. After all, the name says "_data_and_timetable"... 

It would be really nice to have as a new feature (and probably easy to implement). Thanks for listening to the users!

yes, but there are many other possible algorithms we didn't checked yet.

also we didn't proof that the current one is correct. maybe there is still a bug and it can find only 99.9999% of all possible solutions.
in normal case not critical, but in wost case we might skip possible solution and we will never find a solution with this algorithm even there is one.

i think Liviu also talked a bit more general. so not only timetabling algorithms.

I have read somewhere that timetabling belongs to the class of problems which are "NP complete" (or "NP hard"?) In other words, there is no algorithm which is guaranteed to find a solution, or which can guarantee that there is no solution with the given data, except for brute force. There are only heuristic algorithms, some of which work better than others.

However, I am not a computer scientist or engineer, so I think that the present algorithm which introduces an element of randomness to the search path works quite well. If one generation takes too long, you can cancel it and try again. The random ordering should make it possible to find a solution quickly (if there is one).

When I generate a timetable, I can successfully save it in CSV format. However, if I do not generate a timetable but open a .FET file from a previous session, it will export all of the data but without without any planned activities because "no timetable has been generated". So if I want to have CSV timetables, I have to remember to export them immediately after they have been generated.

This would be a nice feature to have since there is the schedule contained in the "{Name}_activities.xml" file, and the export routine would only have to read it.

Or is there a better way?

We got information from the forum user Bob Hairgrove that he intends to complete the German translation, so he will be in charge with this.

Thanks, Liviu!