Optimise Europython competition

[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 europython at python.org 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.

--