4

I have a question about scheduling. I need to make a timetable generator for appointments. this is the current situation.

P1 has an appointment A with P2.
P3 has an appointment B with P4.
and so on...

Appointment A takes about 15 minutes
Appointment B takes about 40 minutes
(The time of duration depends on the number of topics, 1 topic = 5 minutes)

I need to put this into a timetable with a few other constraints, with a limited amount to schedule all the meetings.

My question is: Which algorithms can be used for this?

Thanks in advance.

amit
  • 175,853
  • 27
  • 231
  • 333
Nico Liu
  • 845
  • 2
  • 9
  • 14
  • What is the metrics/constraints? I can put exactly one appointment for each day at noon - but I doubt that it is what you are actually looking for. – amit Mar 28 '12 at 14:41
  • This is for 2 days at morning(09.00-13.00) and noon(13.00-16.00). I just need to know what to study to get this problem solved – Nico Liu Mar 28 '12 at 14:43
  • Can you give a little more context about where did the problem come from? I am afraid that even if the "meetings" will need only one person per meeting - you got yourself a [bin-packing problem](http://en.wikipedia.org/wiki/Bin_packing_problem), which is [NP-Hard](http://en.wikipedia.org/wiki/NP-hard), and adding the 2 people per meeting constraint only makes things harder. – amit Mar 28 '12 at 14:52
  • It's similar to making a schedule for fast-dating events. Only the participants have already made an appointment beforehand – Nico Liu Mar 28 '12 at 15:02
  • If there are not many constraints, these sort of problems can often be solved very quickly with an integer programming solver – BlueRaja - Danny Pflughoeft Mar 28 '12 at 15:24

1 Answers1

4

What you should look into, as long as the dataset is small, is a classic backtracking algorithm, which will solve the problem by bruteforcing. However, the algorithm will get inefficient, if your dataset is growing. In that case, you should have a look at artificial intelligence like genetic algorithms to solve the problem.

Lars
  • 5,757
  • 4
  • 25
  • 55
  • Thanks I think I will base my research on using genetic algorithms to solve this problem. There are in total 6 constraints so I don't know a classic algorithm will solve it. Although the forward state space search is used for airplanes schedules which is similar to my problem. – Nico Liu Mar 28 '12 at 14:54
  • Genetic Algorithms would be the most promising and with 6 constraints, you'll hit the limit for backtracking pretty fast (especially if your solution space is very narrow) - same is true for forward space search. The good thing is, that you can implement Backtracking as a decision tree and buffer the state to account for variations. I guess genetic algorithms are the way to go here, too. – Lars Mar 28 '12 at 18:18