Модели и алгоритмы для задачи о формировании производственных ячеекModels and algorithms for the cell formation problem

Диссертационная работа посвящена теме оптимизации производства с помощью решения задачи бикластеризации множеств производственных мощностей и производимых деталей. Данная задача в литературе называется задачей о формировании производственных ячеек (cell formation problem). В последние годы ее решению было посвящено большое количество работ, включающих множество различных эвристических алгоритмов (в частности метаэвристик) и несколько точных подходов. В качестве основных результатов исследования в диссертации доказан сложностной статус задачи для нескольких используемых в литературе целевых функций, разработаны два точных подхода для формулировки задачи с произвольным числом кластеров и дробной целевой функцией эффективности группировки (grouping efficacy), а также предложен эвристический алгоритм поиска во многих окрестностях с рестартами (variable neighborhood search). Еще одним вкладом работы стала корректировка имеющегося набора данных 35 GT и формирование нового набора данных из более редких задач в литературе. Вычислительные эксперименты с точными подходами позволили найти глобально оптимальные решения для 63 из 67 задач, представленных матрицами с размерами от 5х7 до 50х150. Предложенный эвристический алгоритм позволил найти лучшие результаты для целевой функции производительность группировки (grouping efficiency) в 23 из 24 тестовых примерах.