Branch and Bound Methods for Multi-Item Scheduling

This paper presents two solution approaches for the multi-item activity scheduling problem; a problem of practical importance because it models many resource allocation and combinatorial problems. Both approaches are easily incorporated into commercially available linear programming (LP) based branch-and-bound codes such as IBM's MPSX370-MIP. Many practitioners rely on such codes and will find these approaches useful. The first approach is a specialization of a method for decomposing integer programs with block angular structure. In the second approach, the reduced costs in the solution to the usual LP relaxation are used to develop improved priorities for branching. Computational results on real applications are reported using MPSX 370-MIP.