The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problem

The part families with precedence constraints problem (PFP) arises in industry, when flexible manufacturing systems are designed within a group technology approach. The aim of this problem is to arrange parts into families by imposing capacity constraints, concerning both the number of parts and processing times, besides precedence constraints in the building of families. Mixed binary linear programming formulations for the PFP are presented. In endeavoring to strengthen the linear relaxations for the formulations, and hence generate better lower bounds for the optimal value of PFP, some valid inequalities, based on the properties of the problem, were deduced. The lower bounds obtained significantly improved through the very weak, frequently null, bounds resulting from the original linear relaxation. Moreover, it may be concluded that these models can be a useful methodology to enforce the performance of any branch-and-bound for this very important problem in flexible manufacturing systems.