DebConf5COMASTalkScheduling
Contents |
[edit] DebConf5 COMAS Talk Scheduling
Finding potential for parallelizing talks/bofs by identify disjoint set of people wanting to attend different talks and put those talks into different rooms at the same time if possible, minimizing the overlap. Needs to be done, right? A. between reconfirmation and conference start
[edit] Assumptions of the Scheduling Algorithm
- People prioritize talks that they want to attend (certain number of points that they can assign to each talk, people can change their minds, but this is for scheduling.) See http://comas.donarmstrong.com/debconf5/attendees/account/voting for the implementation of this.
- Rooms have a maximum number of people (should target 90% of the actual maximum)
- Speakers cannot overlap
- Rooms can be unoccupied for a talk slot
[edit] Thoughts on Algorithm
The algorithm should allow the most people possible to attend the talks with highest priority.
Each valid (ie, below maximum number of people in all rooms, un-overlapping speakers) schedule arrangement gets a score.
The schedule with the highest score (most people satisfied with the schedule) is the schedule used. Heuristic algorithms to find the highest score
The scoring function should:
- add points for every person who is able to attend the talk because it does not conflict with a talk with higher priority,
- subtract points because it conflicts with a talk with higher priority.
We assume that people will attend the talk that they rank higher.
[edit] Andreas' comments:
I would just define a error function which i would try to minimize. (This could be what you are doing above, not sure :-) On that i would use an existing full blown search algorithm like Simulated Annealing to find the minimum. (see cpan, there is a simulated annealing module there i just saw.) Since this is probably a cpu intensive task, it might be run only occasionaly.
[edit] Random notes
Title Practice and theory of automated timetabling : first international conference, Edinburgh, U.K., August 29-September 1, 1995 : selected papers / Edmund Burke, Peter Ross, eds. Publisher Berlin ; New York : Springer, 1996. LOC CALL # STATUS Science Q341 .P7 1996 NOT CHCKD OUT
Author Knjazew, Dimitri, 1974- Title [[OmeGA]] : a competent genetic algorithm for solving permutation and scheduling problems / by Dimitri Knjazew. Publisher Boston : Kluwer Academic Publishers, c2002. LOC CALL # STATUS Science [[QA402]].5 .K595 2002 NOT CHCKD OUT
Author Iri, Masao. Title Network flow, transportation, and scheduling; theory and algorithms. Publisher New York, Academic Press, 1969. LOC CALL # STATUS Science [[QA3]] .M4 v.57 1969 NOT CHCKD OUT
