The allocation of machines to part families in cellular manufacturing systems is formulated as 0-1 integer programming models, and a solution procedure based on Lagrangian relaxation is presented. Alternate relaxations are compared in terms of the quality of bounds and computational time. The application of the formulations is illustrated using large, randomly generated problems.