Minimizing the SUM algorithm
Did you check what's the class of your problem? I'd try a reduction to a scheduling problem. 

If you want to have something so you solve it today, use Branch and Bound. Bounds should be easy to find.