Best Fit Scheduling Algorithm

Question

I'm writing a scheduling program with a difficult programming problem. There are several events, each with multiple meeting times. I need to find an arrangement of meeting times such that each schedule contains any given event exactly once, using one of each event's multiple meeting times.

Obviously I could use brute force, but that's rarely the best solution. I'm guessing this is a relatively basic computer science problem, which I'll learn about once I am able to start taking computer science classes. In the meantime, I'd prefer any links where I could read up on this, or even just a name I could Google.

Answer 1

I think you should use genetic algorithm because:

• It is best suited for large problem instances.
• It yields reduced time complexity on the price of inaccurate answer(Not the ultimate best)
• You can specify constraints & preferences easily by adjusting fitness punishments for not met ones.
• You can specify time limit for program execution.

• The quality of solution depends on how much time you intend to spend solving the program..

  Genetic Algorithms Definition

  Genetic Algorithms Tutorial

  Class scheduling project with GA

Answer 2

There are several ways to do this

One approach is to do constraint programming. It is a special case of the dynamic programming suggested by feanor. It is helful to use a specialized library that can do the bounding and branching for you. (Google for "gecode" or "comet-online" to find libraries)

If you are mathematically inclined then you can also use integer programming to solve the problem. The basic idea here is to translate your problem in to a set of linear inequalities. (Google for "integer programming scheduling" to find many real life examples and google for "Abacus COIN-OR" for a useful library)

My guess is that constraint programming is the easiest approach, but integer programming is useful if you want to include real variables in you problem at some point.