I am creating a scheduling program that I need to either optimize or prove that what I have is already optimal.
I have n groups, all of which need to do some activity a in time slot t. A person can belong to several groups. A person cannot perform two activities in the same time slot. There is also a limit to the number of persons that can do an activity in the same time slot.
Here is pseudocode for my current (greedy) algorithm
sort groups by size (descending) t = 1 for each group place group in slot t if there is a conflict in this slot ( p1->a1 && p1->a2) place group in slot t+1 if slot t is full t++
What I am looking for is the minimum number of slots possible. I have an algorithm ready that does hill climbing with simulated annealing, which is used for another scheduling problem. The question is do I need it, or is there something else I can use? Or is this current algorithm already resulting in an optimal solution? And how do I find the theoretical minimum of slots?