28

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.

I could use brute force, but that's rarely the best solution. I'd prefer any links where I could read up on this, or even just a name I could Google.

user4157124
  • 2,809
  • 13
  • 27
  • 42
stillinbeta
  • 1,977
  • 3
  • 17
  • 23
  • 3
    Scheduling problems are in general NP-complete, meaning you cannot do better *(we think)* than brute-force. I'm not sure about this more-specific problem, though. – BlueRaja - Danny Pflughoeft Apr 30 '10 at 17:07
  • 7
    It's true that these problems are usually NP-complete and so have no efficient algorithms for optimal solutions, but there are efficient algorithms that get reasonably good answers in most cases. As far as keywords go, I'd maybe look for the "bin-packing problem" although it's not quite right. You might also try searching for "class scheduling algorithm" and see what you find. – Dale Hagglund Apr 30 '10 at 17:12
  • 1
    "Each schedule"? So you want to find all possible ways to attend all events? – Beta Apr 30 '10 at 17:15
  • To clarify the question: You have (say) 5 schedules and 10 meetings, each with 5+ non-overlapping meeting times, and you want all 5 schedules to contain all 10 meetings, with no overlapping times in any one schedule. Is this correct? – BlueRaja - Danny Pflughoeft Apr 30 '10 at 17:17
  • @Beta That'd be optimal, yes, but if it's significantly faster to do it that only finds one that's fine. @BlueRaja Yes, that's right – stillinbeta May 01 '10 at 03:11
  • @stillinbeta I don't completely understand the problem description. Are you trying to fit as many events into the schedule as possible, given a list of events with their corresponding times? – Anderson Green May 20 '13 at 03:25
  • https://www.geeksforgeeks.org/given-n-appointments-find-conflicting-appointments/ better approach – anubhs Jun 08 '20 at 08:05

4 Answers4

11

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

Betamoo
  • 14,964
  • 25
  • 75
  • 109
6

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.

nielsle
  • 381
  • 1
  • 10
  • BTW: I wouldn't use genetic programming for a task like this: 1) Genetic algorithms are somewhat slow 2) They are somewhat difficult to debug because it doesn't always converge to the global optimum. – nielsle Jun 09 '10 at 10:18
3

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.

ire_and_curses
  • 68,372
  • 23
  • 116
  • 141
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.

Feanor
  • 2,715
  • 4
  • 29
  • 43