Graph Theory and Scheduling
The classic use for graph coloring is in the problem of scheduling: the textbook
example is 'how do you schedule exams so that no student has more than two exams
on a given day." However, this problem exists in any field where scheduling is an
issue: airline crews, sport schedules, hotel stays.
Due to the NP nature of this problem, a given graph can be colored using a brute
force approach, but the problems and difficulties occur when you start dealing with
a large number of parameters. On the web, there are a number of mathematical treatises
available, but very few concrete examples and code solutions.
The approach that I have taken is to implement a sorted vector of nodes(reservations)
that will be coloured (or scheduled) according to their respective value. This means that
priority will be given to reservations with the greatest value and that are competing for
the fewest vacancies.
By iterating through the highest value reservations first, you are guaranteed that revenue
will be optimized and that if 'bumping' must occur it will happen to the short stay guests
first.
Links for more information