Экспериментальное исследование эффективности применения некоторых современных методов решения задач комбинаторной оптимизации при планировании сопутствующего производства

 pdf (313K)

В работе формализуется задача оптимизации сопутствующего производства на гибких или реконфигурируемых производствах. В рассматриваемой постановке на входе задан набор обязательных изделий, требуется решить две взаимосвязанные подзадачи: 1) для каждого изделия из набора обязательных сформировать группу дополнительных изделий, которые могут быть произведены без изменения состояния производства, и 2) определить порядок переналадок производства между группами дополнительных изделий, а также «точки входа и выхода» в каждую из групп. В настоящей работе указанные подзадачи рассматриваются последовательно: первая подзадача сведена к задаче поиска клики максимального веса в ориентированном графе, вторая - к кластерной задаче коммивояжера. В ходе масштабных вычислительных экспериментов изучен выигрыш от применения эффективных современных методов решения обеих подзадач в сравнении с жадным решением, моделирующим рациональные действия человека-оператора в условиях большой размерности исходной комплексной задачи и ограниченного времени, имеющегося для ее решения.

Ключевые слова: оптимизация сопутствующего производства, гибкие и перенастраиваемые производства, клика максимального веса, кластерная задача коммивояжера
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2019, т. 29, вып. 4, с. 599-611
DOI: 10.20537/vm190410

Experimental research of the application of modern combinatorial optimization solvers to the accompanying manufacturing optimization problem

The paper is devoted to the problem of optimization of accompanying manufacturing in flexible or reconfigurable manufacturing systems. Using a set of obligatory products as an input, the initial problem is reduced to two interrelated subproblems: 1) for each product from the set of obligatory products, form a group of additional (accompanying) products that can be manufactured without changing the state of production, and 2) determine the order of manufacturing changeovers between the groups of additional products, as well as the “points of entry and exit” for each group. The subproblems are considered sequentially: the first subproblem is reduced to the maximum weight clique problem, the second - to the cluster traveling salesman problem. Large-scale computational experiments were conducted to reveal the benefits of applying effective modern methods for solving both subproblems in comparison with the greedy solution (which models the rational actions of a human operator solving large accompanying manufacturing problems in short time).

Keywords: optimization of accompanying manufacturing, flexible and reconfigurable manufacturing, maximum weight clique, cluster travelling salesman problem
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2019, vol. 29, issue 4, pp. 599-611

Журнал индексируется в Web of Science (Emerging Sources Citation Index)

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref