Scheduling puzzle

[Bob Hairgrove]

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?

[Liviu Lalescu]

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.

[Bob Hairgrove]

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

[Volker Dirr]

i think you can't do that with official FET. i think you can try the FET custom mapr version for that or a tool like BLOCK_PLANER_SAT4J ( https://sites.google.com/site/digitalewerkegymnasiumeickel/home/werke/ )

[Bob Hairgrove]

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.

[Volker Dirr]

see custom version 3:
http://lalescu.ro/liviu/fet/custom.html

[Liviu Lalescu]

Or a list of all presentations, two columns: col 1 = presentation, col 2 contains ∈ {'1','2','both'}.

Do you mean col 1 = participant ?

[Liviu Lalescu]

It might be possible with the FET-mapr-asa8-zt3 version.

Add students as FET students and conferences as FET rooms.

Add two activities for each student.

Then maybe first and second preferences of the activity of each student as preferred rooms with 95% and third preference as preferred room with 80%.

Add only one day and two time slots.

Neglect the equivalence properties of the mapr version, and neglect many things in the help for mapr version.

Volker, what do you think?

Let's debate over this. I might be able to come up with an input file, but I would prefer to talk with you, Bob, instead, maybe you can come up with your own data file.

FET mapr-asa8-zt3 allocates activities to FET rooms, allowing more activities for a room (mapr means more activities per room).

[Bob Hairgrove]

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