Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: What algorithms should I research to code a conference scheduling app

news.ycombinator.com

Post reply on HN
Print view View original

1–10 of 24 posts

Ask HN: What algorithms should I research to code a conference scheduling app

#1

Post by viertaxa »

I'm interested in writing a utility to assist with scheduling un-conferences. Lets take the following situation for an example:

* 4 conference rooms across 4 time slots, for a total of 16 talks.

* 30 proposed talks

* 60 total participants

Each user would be given 4(?)votes, un-ranked. (collection of the votes is a separate topic) Voting is not secret, and we don't need mathematically precise results. The goal is just to minimize conflicts.

The algorithm would have the following data to work with:

* List of talks with the following properties:

     * presenter participant ID

     * the participant ID for each user that voted for the talk
I'd like to come up with an algorithm that does the following:

* fills all time slots with the highest voted topics

* attempts to avoid overlapping votes for any particular given user in a given time slot

* attempt to not schedule a presenter's talk during a talk they are interested in.

* Sugar on top: implement ranked preferences

My question: where do I start to research the algorithms that will be helpful? I know this is a huge project, but I have a year to work on it. I'm also not overly concerned with performance, but would like to keep it from being exponential.

Thank you for any references you can provide!

Re: Ask HN: What algorithms should I research to code a conference scheduling app

#4

Post by westurner »

Resource scheduling, CSP (Constraint Satisfaction programming)

CSP: https://en.wikipedia.org/wiki/Constraint_satisfaction_proble...

Scheduling (production processes):

https://en.wikipedia.org/wiki/Scheduling_(production_process...

Scheduling (computing):

https://en.wikipedia.org/wiki/Scheduling_(computing)

... To an OS, a process thread has a priority and sometimes a CPU affinity.

Re: Ask HN: What algorithms should I research to code a conference scheduling app

#5

Post by westurner »

westurner wrote: post #4

Resource scheduling, CSP (Constraint Satisfaction programming) CSP: https://en.wikipedia.org/wiki/Constraint_satisfaction_proble... Scheduling (production processes): https://en.wikipedia.org/wiki/Scheduling_(production_process... Scheduling (computing): https://en.wikipedia.org/wiki/Scheduling_(computing) ... To an OS, a process thread has a priority and sometimes a CPU affinity.

From http://markmail.org/search/?q=list%3Aorg.python.omaha+pysche... :

Pyschedule:

- Src: https://github.com/timnon/pyschedule

- Docs: https://github.com/timnon/pyschedule/blob/master/docs/pysche...

Re: Ask HN: What algorithms should I research to code a conference scheduling app

#6

Post by larose »

Your problem is a scheduling problem. It has been well studied in operations research [1] / mathematical optimization [2].

Basically, you formulate your problem as a integer programming model [3] and use a solver [4] to solve it. You should check PuLP [5].

You can also ask your question at OR Exchange [6].

[1] https://en.wikipedia.org/wiki/Operations_research

[2] https://en.wikipedia.org/wiki/Mathematical_optimization

[3] https://en.wikipedia.org/wiki/Integer_programming

[4] https://en.wikipedia.org/wiki/List_of_optimization_software

[5] https://pythonhosted.org/PuLP/

[6] https://www.or-exchange.org/

Re: Ask HN: What algorithms should I research to code a conference scheduling app

#7

Post by viertaxa »

larose wrote: post #6

Your problem is a scheduling problem. It has been well studied in operations research [1] / mathematical optimization [2]. Basically, you formulate your problem as a integer programming model [3] and use a solver [4] to solve it. You should check PuLP [5]. You can also ask your question at OR Exchange [6]. [1] https://en.wikipedia.org/wiki/Operations_research [2] https://en.wikipedia.org/wiki/Mathematical_optimizatio…

Thank you for the detailed response!

Re: Ask HN: What algorithms should I research to code a conference scheduling app

#9

Post by viertaxa »

westurner wrote: post #4

Resource scheduling, CSP (Constraint Satisfaction programming) CSP: https://en.wikipedia.org/wiki/Constraint_satisfaction_proble... Scheduling (production processes): https://en.wikipedia.org/wiki/Scheduling_(production_process... Scheduling (computing): https://en.wikipedia.org/wiki/Scheduling_(computing) ... To an OS, a process thread has a priority and sometimes a CPU affinity.

Thanks for the information! CSP definitely sounds like something to look into.

Re: Ask HN: What algorithms should I research to code a conference scheduling app

#10

Post by TheCoreh »

What everyone else said, but if you want a "quick and dirty" way of doing it, you can just use a simple genetic algorithm:

- Start with a couple (say 100) completely random schedules

- Measure how good they are via a fitness function (say, start at 0 and everytime a constraint is violated add 1 point. You can be fancy and add different amounts depending on the type of constraint violated)

- Sort the schedules from lowest to highest

- Pick the top 20 or so

- Generate other 80 schedules by mutating the 20 you selected before, randomly shuffling the talks, and possibly mixing up different schedules together (crossover).

- Repeat for a couple thousands of generations, the population should quickly evolve towards better schedules

- You might get stuck on local minima, but for the most part you can just run it again several times from the start and it eventually won't get stuck

- Not guaranteed to give optimum results but should give decent enough results

Post reply on HN