Valid inequalities for a class of assembly system problems

This paper establishes a foundation for a cutting plane approach to solve a class of problems that are important to assembly systems, including assembly line balancing (ALB), workload smoothing (WS) and assembly system design (ASD). We describe relationships among the integer programming formulations of these problems and recast their relaxations as node packing problems (NPPs). Exploiting the well-known structure of the NPP and other relationships among the assembly problems, we derive several families of valid inequalities and show conditions under which they also define facets for the associated ALB, WS and ASD polytopes.