3
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Your problem generalizes bin packing and is hence NP-hard. Consider formulating your problem as an integer program and use a standard solver. $\endgroup$ – Kristoffer Arnsfelt Hansen Feb 27 '14 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.