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

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