کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
480505 1445973 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On solving manufacturing cell formation via Bicluster Editing
ترجمه فارسی عنوان
درباره حل تشکیل سلول های تولید از طریق ویرایش دوخوشه ای
کلمات کلیدی
بهینه سازی ترکیبی؛ دوخوشه ای کردن؛ افراز گراف. تشکیل سلول های تولید
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• We study the Bicluster Graph Editing Problem and how it can be applied to solve the Manufacturing Cell Formation Problem.
• We develop a Branch & Cut method for the Bicluster Graph Editing Problem that uses a dynamic programming separation module.
• Our exact methods for the Manufacturing Cell Formation Problem are able to prove several previously unknown optima.

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 254, Issue 3, 1 November 2016, Pages 769–779
نویسندگان
, , , , , ,