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

Lídia Lampreia Lourenço, Margarida Vaz Pato

Research output: Contribution to journalArticlepeer-review

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 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.

Original languageEnglish
Pages (from-to)181-196
Number of pages16
JournalEuropean Journal of Operational Research
Volume183
Issue number1
DOIs
Publication statusPublished - 16 Nov 2007

Keywords

  • Flexible manufacturing systems
  • Mixed binary linear formulations
  • Part families problem
  • Precedence constraints
  • Valid inequalities

Fingerprint

Dive into the research topics of 'The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problem'. Together they form a unique fingerprint.

Cite this