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 eu********@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.

--