1
$\begingroup$

I've been sent here from StackOverflow with my mathematical / algorithm question.

I am currently working with an organisation developing a web system, one area attempting to resolve in-house training clashes.

An example (as best as I can describe is):

What the company is attempting to do is prevent major clashes (>10 people affected) when planning training course times.

  • 100 people are attending training course A.
  • 75 people are attending training course B.
  • 25 people are attending training course C.
  • 5 people are attending training course D.

If 75 people attending B are all attending course A, and B were to run at the same time, there would be a total of 75 clashes.

If all 25 people from course C are attending course A and B, running any of these courses at the same time would result in at minimum of 25 clashes.

If 3 people were attending A and D, and they were to run at the same time only 3 would have an issue and therefore not be a major problem.

The system they are attempting to develop does not necessarily need to resolve the clash itself, just highlight if a certain number of clashes are likely to occur when arranging a new time.

I hope that explains the situation - I am a programmer by profession so this sort of thing is new to me, any points in the right direction would be fantastic!

  • 0
    @SureshVenkat - You don't know who's signed up in advanced for which class, they are chosen off a list then potential time forecasts are made to attempt not to clash as many as possible. In terms of slots, some have room for 20, others have 50, others more. As Gerry says, it is a complex area and I appreciate for the complex areas of the solution would require professional consulting - but as the web guy attempting to resolve it to the best of my abilities any help is appreciated :)2011-12-04

1 Answers 1

1

If you intend to estimate the expected number of clashes (not necessarily the unique or best measure, but perhaps the more easy to compute) you need a probabilistic model: in particular, you need to know the size of the total population ($N$) and if there is some dependency among courses attendance (i.e. if given that a particular person attends course A then it's more or less probable that he attends course B). Assumming the most simple scenario -no dependencies-, a simple computation (see this related question) shows that if $N_A$ people from a total population of $N$ attends course A, and $N_B$ attends course B, then the expected number of classhes is:

$E(N_{AB}) = \frac{N_A N_B} {N}$