| Abstract | 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 group N parts into K 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 generating better lower bounds for the optimal value of PFP, some valid inequalities based on the properties of the problem. The lower bounds obtained by the strengthened linear relaxations significantly improved through the very weak, frequently null, bounds resulting from the original linear relaxation. Moreover, one may conclude that these models can be a useful methodology to enforce the performance of branch-and-bound for this very important problem in flexible manufacturing systems. |
