J
Jacob Hallen
A classic dilemma for conferences is that if you have many tracks,
you may find that all of a sudden, a room is swamped, and there is
a queue of people wanting to get in. Another problem is that you
risk scheduling talks against each other that have a very large
set of interested people in common.
At Europython we are this year going to try a new way of scheduling,
in order to reduce these problems. Before the schedule is made, we
will give all attendees the opportunity to register what talks they
are most interested in. We then want to make a schedule that is
optimised based on these data.
Since I am no expert in optimising algorithms of this type, and since
the time I have available for these things is limited, I'm turning to
the readers of c.l.p and python-logic for help.
I'm offering the following bounty for a working solution (in Python):
- Free attendance at this years Europython, as a guest of honour
- A Europython T-shirt in a limited special edition
- Fame and gratitude from conference attendees who get better scheduling
The winner of the bounty is the person who scores most points, according
to the criteria below. If we get more than one solution that does good
optimisation, we will award more than one bounty.
Here are the parameters:
1. There are 10 tracks with between 1 and 30 talks in each track.
You may not schedule two talks in the same track against each other,
unless there is more talks than available calendar time.
2. A track should be continuous. Each track that is continuous gives you
10 points.
3. We expect about 300 attendees. About half of them are expected to
register their interests. Interests may range from a single talk
to more than half of all the talks. You get one point for each
talk an attendee can attend out of the ones the attendee has registered
interest in.
4. Talks are of varying lengths. Lengths can be 30, 45, 60 and 90 minutes.
The large majority of talks are 30 minutes. Only a very few are 45
minutes.
5. Rooms come in different sizes
Room A has 180 seats
Room B has 140 seats
Room C has 140 seats
Room D has 70 seats
Room E has 70 seats
Room A-D should be scheduled throughout the conference while room E
is extra expansion space, only to be used when absolutely necessary.
For every person scheduled above (Room capacity * (Number of responding
attendees / Total number of attendees)) you get one point taken off
your score.
6. There are a total of 10 90-minute time blocks.
Day 1: 09:00
Day 1: 11:00
Day 1: 14:00
Day 1: 16:00
Day 2: 09:00
Day 2: 11:00
Day 2: 14:00
Day 2: 16:00
Day 3: 09:00
Day 3: 11:00
A track should not change room in the middle of a time block. Doing
so reduces your score by 50 points.
7. Input data
You get your input data in the form of a list of tuples; one tuple
per talk.
Each tuple looks like this:
(<talk id>, <talk length>, <track id>, [list of interested attendees])
Talk length is an integer, all other items are strings.
8. Output data
You should supply your output data in the form of a list of tuples; one
tuple per talk.
Each tuple should look like this:
(<talk id>, <room>, <day>, <starting time>)
Talk id should be the same as in the input. Room should be a one letter
string with a value in the range A-E. Day should be a one letter string
in the range 1-3. Starting time should be a string on the form HH:MM,
in the 24 hour clock.
Solutions should be sent by email to (e-mail address removed) no later than
1 June 2005. Currently we haven't started gathering real data, but there should be some available for real world testing before 1 June.
--
you may find that all of a sudden, a room is swamped, and there is
a queue of people wanting to get in. Another problem is that you
risk scheduling talks against each other that have a very large
set of interested people in common.
At Europython we are this year going to try a new way of scheduling,
in order to reduce these problems. Before the schedule is made, we
will give all attendees the opportunity to register what talks they
are most interested in. We then want to make a schedule that is
optimised based on these data.
Since I am no expert in optimising algorithms of this type, and since
the time I have available for these things is limited, I'm turning to
the readers of c.l.p and python-logic for help.
I'm offering the following bounty for a working solution (in Python):
- Free attendance at this years Europython, as a guest of honour
- A Europython T-shirt in a limited special edition
- Fame and gratitude from conference attendees who get better scheduling
The winner of the bounty is the person who scores most points, according
to the criteria below. If we get more than one solution that does good
optimisation, we will award more than one bounty.
Here are the parameters:
1. There are 10 tracks with between 1 and 30 talks in each track.
You may not schedule two talks in the same track against each other,
unless there is more talks than available calendar time.
2. A track should be continuous. Each track that is continuous gives you
10 points.
3. We expect about 300 attendees. About half of them are expected to
register their interests. Interests may range from a single talk
to more than half of all the talks. You get one point for each
talk an attendee can attend out of the ones the attendee has registered
interest in.
4. Talks are of varying lengths. Lengths can be 30, 45, 60 and 90 minutes.
The large majority of talks are 30 minutes. Only a very few are 45
minutes.
5. Rooms come in different sizes
Room A has 180 seats
Room B has 140 seats
Room C has 140 seats
Room D has 70 seats
Room E has 70 seats
Room A-D should be scheduled throughout the conference while room E
is extra expansion space, only to be used when absolutely necessary.
For every person scheduled above (Room capacity * (Number of responding
attendees / Total number of attendees)) you get one point taken off
your score.
6. There are a total of 10 90-minute time blocks.
Day 1: 09:00
Day 1: 11:00
Day 1: 14:00
Day 1: 16:00
Day 2: 09:00
Day 2: 11:00
Day 2: 14:00
Day 2: 16:00
Day 3: 09:00
Day 3: 11:00
A track should not change room in the middle of a time block. Doing
so reduces your score by 50 points.
7. Input data
You get your input data in the form of a list of tuples; one tuple
per talk.
Each tuple looks like this:
(<talk id>, <talk length>, <track id>, [list of interested attendees])
Talk length is an integer, all other items are strings.
8. Output data
You should supply your output data in the form of a list of tuples; one
tuple per talk.
Each tuple should look like this:
(<talk id>, <room>, <day>, <starting time>)
Talk id should be the same as in the input. Room should be a one letter
string with a value in the range A-E. Day should be a one letter string
in the range 1-3. Starting time should be a string on the form HH:MM,
in the 24 hour clock.
Solutions should be sent by email to (e-mail address removed) no later than
1 June 2005. Currently we haven't started gathering real data, but there should be some available for real world testing before 1 June.
--