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

Your problem description isn't entirely clear, but if all you're trying to do is find a schedule which has no overlapping events, then this is a straightforward bipartite matching problem.

You have two sets of nodes: events and times. Draw an edge from each event to each possible meeting time. You can then efficiently construct the matching (the largest possible set of edges between the nodes) using augmented paths. This works because you can always convert a bipartite graph into an equivalent flow graph.

An example of code that does this is BIM. Standard graphing libraries such as GOBLIN and NetworkX also have bipartite matching implementations.

Answer 2

This sounds like this could be a good candidate for a dynamic programming solution, specifically something similar to the interval scheduling problem.

There are some visuals here for the interval scheduling problem specifically, which may make the concept clearer. Here is a good tutorial on dynamic programming overall.

Answer 3

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 4

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.