We study a scheduling problem with costs and capacity constraints. The problem is NP-complete and combinatorial algorithms have not been very successful. We identify a general class of facets which subsumes as a special case all facets described earlier. We also develop a cutting plane based procedure for the dynamic version of the problem, and solve problem instances with up to 1200 integer variables to optimality without resorting to branch and bound procedures.