# Optimization of class schedule

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?

• Your problem generalizes bin packing and is hence NP-hard. Consider formulating your problem as an integer program and use a standard solver. Feb 27 '14 at 22:48