On solving manufacturing cell formation via Bicluster Editing

Rian G.S. Pinheiro, Ivan C. Martins, Fábio Protti, Luiz S. Ochi, Luidi G. Simonetti and Anand Subramanian

European Journal of Operational Research, 2016, vol. 254, issue 3, 769-779

Abstract: This work investigates the Bicluster Graph Editing Problem (BGEP) and how it can be applied to solve the Manufacturing Cell Formation Problem (MCFP). We develop an exact method for the BGEP with a new separation algorithm. We also describe a new preprocessing procedure for the BGEP derived from theoretical results on vertex distances in the input graph. Computational experiments performed on randomly generated instances with various levels of difficulty show that our separation algorithm accelerates the convergence speed, and our preprocessing procedure is effective for low density instances. Another contribution of this work is to take advantage of the fact that the BGEP and the MCFP share the same solution space. This leads to the proposal of two new exact approaches for the MCFP that are based on mathematical formulations for the BGEP. Both approaches use the grouping efficacy measure as the objective function. Up to the authors’ knowledge, these are the first exact methods that employ such a measure to optimally solve instances of the MCFP. The first approach is based on a new ILP formulation for the MCFP, and the second consists of iteratively running several calls to a parameterized version of the BGEP. Computational experiments performed on instances of the MCFP found in the literature show that our exact methods for the MCFP are able to prove several previously unknown optima.

Keywords: Combinatorial optimization; Biclusterization; Graph partitioning; Manufacturing cell formation (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716303307
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:254:y:2016:i:3:p:769-779

DOI: 10.1016/j.ejor.2016.05.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().