From Wiki
Jump to: navigation, search


[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 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.
  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.
  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.
  Science 	 [[QA3]] .M4 v.57 1969     	  NOT CHCKD OUT

Personal tools