On solving manufacturing cell formation via Bicluster Editing
| Autor: | Rian G. S. Pinheiro, Anand Subramanian, Fábio Protti, Ivan C. Martins, Luiz Satoru Ochi, Luidi Simonetti |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
021103 operations research Information Systems and Management General Computer Science Computer science 0211 other engineering and technologies Graph partition Parameterized complexity 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering Graph Vertex (geometry) Modeling and Simulation 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) Combinatorial optimization 020201 artificial intelligence & image processing Manufacturing cell Algorithm |
| Zdroj: | European Journal of Operational Research. 254:769-779 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2016.05.010 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect