Развитие методов решения задач плотной упаковки объектов произвольной формы и различной размерности тема диссертации и автореферата по ВАК РФ 05.01.01, доктор наук Чеканин Владислав Александрович

• Чеканин Владислав Александрович
• доктор наук
• 2021

Оглавление диссертации доктор наук Чеканин Владислав Александрович

ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР НАУЧНЫХ ИССЛЕДОВАНИЙ В ОБЛАСТИ РЕШЕНИЯ ЗАДАЧ РАСКРОЯ-УПАКОВКИ

1.1. Место исследований в области решения задач раскроя-упаковки в отечественной и мировой науке

1.2. Классификации задач раскроя-упаковки

1.2.1. Первоначальная классификация задач раскроя-упаковки

1.2.2. Современная классификация задач раскроя-упаковки

1.3. Методы решения задач раскроя-упаковки

1.3.1. Методы математического программирования

1.3.2. Методы комбинаторной оптимизации

1.3.3. Эвристические методы

1.3.4. Метаэвристические методы

1.4. Постановка задачи плотной упаковки

1.4.1. Основные понятия и общая постановка задачи

1.4.2. Геометрические условия корректного размещения объектов

1.5. Анализ геометрических аспектов существующих подходов к решению задач раскроя-упаковки

1.6. Цель диссертационного исследования

Выводы по главе

ГЛАВА 2. МОДЕЛИ ГЕОМЕТРИЧЕСКОГО ОПИСАНИЯ ОРТОГОНАЛЬНОЙ

УПАКОВКИ

2.1. Обзор моделей геометрического описания ортогональной упаковки

2.1.1. Рецепторная модель

2.1.2. Узловая модель

2.1.3. Блочная модель

2.1.4. Модель виртуальных объектов

2.1.5. Сравнение моделей геометрического описания упаковки

2.2. Модель потенциальных контейнеров для задач ортогональной упаковки

2.2.1. Описание модели потенциальных контейнеров

2.2.2. Алгоритм поиска и удаления вложенных потенциальных контейнеров

2.2.3. Алгоритм размещения объектов для модели потенциальных контейнеров

2.3. Структура данных для быстрого доступа к потенциальным контейнерам

2.3.1. Описание многоуровневой связной структуры данных

2.3.2. Анализ эффективности многоуровневой связной структуры данных

2.4. Анализ эффективности модели потенциальных контейнеров

2.4.1. Вычислительные эксперименты на тестовых задачах двухмерной прямоугольной упаковки (S.P. Fekete, J. Schepers)

2.4.2. Вычислительные эксперименты на тестовых задачах трёхмерной ортогональной упаковки (S. Martello, D. Pisinger, D. Vigo)

2.4.3. Вычислительный эксперимент на тестовых задачах прямоугольной упаковки на полубесконечную полосу (E. Hopper, B.C.H. Turton)

2.5. Универсальный метод решения задач раскроя-упаковки на основе структурной декомпозиции свободного пространства контейнеров

Выводы по главе

ГЛАВА 3. ИССЛЕДОВАНИЕ ЭВРИСТИЧЕСКИХ И МЕТАЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ОПТИМИЗАЦИИ

3.1. Разработка эвристик размещения объектов

3.1.1. Понятие эвристики размещения объектов

3.1.2. Мультиметодный генетический алгоритм

3.1.3. Эвристики размещения в задачах двухмерной упаковки

3.1.4. Эвристики размещения в задачах трёхмерной упаковки

3.2. Анализ эффективности применения мультиметодного генетического алгоритма

3.2.1. Вычислительный эксперимент на тестовых задачах двухмерной прямоугольной упаковки (S.P. Fekete, J. Schepers)

3.2.2. Вычислительный эксперимент на тестовых задачах прямоугольной упаковки на полубесконечную полосу (O. Berkey и P. Wang, S. Martello и

D. Vigo)

3.2.3. Вычислительный эксперимент на тестовых задачах прямоугольной упаковки на полубесконечную полосу (B.E. Bengtsson)

3.2.4. Вычислительный эксперимент на тестовых задачах прямоугольной упаковки на полубесконечную полосу (E. Pinto, J.F. Oliveira)

3.2.5. Вычислительный эксперимент на тестовых задачах трёхмерной ортогональной упаковки (S. Martello, D. Pisinger, D. Vigo)

Выводы по главе

ГЛАВА 4. МЕТОДЫ ПОВЫШЕНИЯ КАЧЕСТВА РАЗМЕЩЕНИЯ ОБЪЕКТОВ В ПЛОТНОЙ УПАКОВКЕ

4.1. Алгоритм удаления ортогональных объектов

4.2. Уплотнение упаковки

4.2.1. Алгоритм поиска объектов, расположенных вокруг выбранного потенциального контейнера

4.2.2. Выбор структуры данных для хранения объектов

4.2.3. Методы и правила выбора объектов для перераспределения в контейнере

4.2.4. Алгоритм уплотнения упаковки

4.2.5. Вычислительные эксперименты

4.2.6. Получение плотной упаковки

4.3. Размещение порций объектов

4.3.1. Понятие порции объектов

4.3.2. Определение наилучшего размера порции объектов

4.4. Стратегии выбора контейнеров при размещении объектов

4.4.1. Стратегия выбора первого подходящего контейнера

4.4.2. Стратегия оптимизации заполнения текущего контейнера

4.4.3. Вычислительные эксперименты

4.5. Оптимизация распределения веса упаковки в контейнере

4.6. Решение практических задач компоновки груза

4.6.1. Решение задачи центровки воздушного судна

4.6.2. Решение задачи компоновки груза внутри авиационного контейнера

Выводы по главе

ГЛАВА 5. РАЗРАБОТКА АЛГОРИТМОВ ФОРМИРОВАНИЯ И

РАЗМЕЩЕНИЯ ОРТОГОНАЛЬНЫХ МНОГОГРАННИКОВ

5.1. Формирование ортогональных многогранников

5.1.1. Теоретико-множественные операции, используемые при формировании ортогональных многогранников

5.1.2. Поворот ортогонального многогранника

5.1.3. Отображение ортогонального многогранника

5.2. Алгоритм декомпозиции ортогонального многогранника

5.2.1. Описание алгоритма декомпозиции ортогонального многогранника

5.2.2. Примеры декомпозиции ортогональных многогранников

5.2.3. Повышение скорости декомпозиции ортогонального многогранника

5.3. Алгоритм размещения ортогональных многогранников

5.3.1. Размещение набора ортогональных многогранников

5.3.2. Алгоритм размещения ортогонального многогранника в контейнере

5.3.3. Определение оптимальной позиции для каждого размещаемого ортогонального многогранника

5.3.4. Усовершенствованный алгоритм размещения ортогонального многогранника в контейнере

5.4. Алгоритм удаления ортогональных многогранников

5.5. Размещение ортогональных многогранников внутри контейнеров произвольной формы

5.5.1. Формирование ортогонального многогранника геометрических ограничений контейнера

5.5.2. Примеры размещения ортогональных многогранников внутри контейнеров сложной формы

5.6. Решение практических задач компоновки деталей сложной формы

Выводы по главе

ГЛАВА 6. ПРАКТИЧЕСКИЕ АСПЕКТЫ ПРОГРАММНОЙ РЕАЛИЗАЦИИ

АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ РАСКРОЯ-УПАКОВКИ

6.1. Проектирование системы оптимизации решений задач раскроя-упаковки

6.1.1. Архитектура построения универсального программного комплекса для решения задач раскроя-упаковки различной размерности

6.1.2. Описание разработанной системы оптимизации решения задач прямоугольного раскроя и ортогональной упаковки

6.2. Алгоритмы корректной визуализации двухмерных и трёхмерных ортогональных многогранников

6.2.1. Общие положения

6.2.2. Алгоритм удаления совпадающих отрезков рёбер

6.2.3. Алгоритм формирования набора рёбер двухмерного ортогонального многогранника

6.2.4. Алгоритм формирования набора рёбер трёхмерного ортогонального многогранника

6.3. Создание ортогональных многогранников с использованием воксельной модели

6.4. Поддержка трёхмерных полигональных моделей объектов

6.4. Построение диаграммы распределения веса в контейнере

Выводы по главе

ОБЩИЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

Приложение А. Тестовые задачи раскроя-упаковки

А. 1. Стандартные тестовые задачи двухмерной прямоугольной упаковки

(S.P. Fekete, J. Schepers)

А.2. Стандартные тестовые задачи трёхмерной контейнерной упаковки

ортогональных объектов (S. Martello, D. Pisinger, D. Vigo)

А.3. Стандартные тестовые задачи прямоугольной упаковки на

полубесконечную полосу (E. Hopper, B.C.H. Turton)

А.4. Стандартные тестовые задачи упаковки на полубесконечную полосу

(O. Berkey и P. Wang, S. Martello и D. Vigo)

А.5. Стандартные тестовые задачи прямоугольной упаковки на

полубесконечную полосу (B.E. Bengtsson)

А.6. Стандартные тестовые задачи прямоугольной упаковки на

полубесконечную полосу (E. Pinto и J.F. Oliveira)

А.7. Частная тестовая задача прямоугольного раскроя «C03_23»

Приложение Б. Результаты вычислительных экспериментов

Б.1. Результаты тестирования мультиметодного генетического алгоритма на

тестовых задачах трёхмерной ортогональной упаковки

Б.2. Результаты тестирования алгоритма уплотнения упаковки

Приложение В. Особенности программной реализации разработанных

алгоритмов

В.1. Структура файла исходных параметров задачи

Приложение Г. Объекты интеллектуальной собственности

Приложение Д. Акты о внедрении

Приложение Е. Информация о научных работах, выполненных соискателем

учёной степени лично и в соавторстве

Введение диссертации (часть автореферата) на тему «Развитие методов решения задач плотной упаковки объектов произвольной формы и различной размерности»

ВВЕДЕНИЕ

Актуальность темы. Решение многих практически важных оптимизационных задач сводится к поиску наиболее компактного способа распределения ресурсов, представленных в виде элементов одного типа (называемых объектами) среди элементов другого типа (называемых контейнерами). В зависимости от характера использования объектов и контейнеров, решаемые задачи можно разделить на задачи раскроя и задачи упаковки. Решение задач раскроя заключается в поиске наиболее рационального способа использования свободного пространства контейнеров, в то время как задачи упаковки характеризуются поиском наиболее компактной компоновки заданного набора объектов. Для решения этих задач используется единая математическая модель, что делает алгоритмы и методы, разработанные для решения задач упаковки, применимыми также и для решения задач раскроя. Наиболее часто задачи раскроя и упаковки описываются моделью задачи плотной упаковки, для которой ни один из размещённых в каждом контейнере объектов не может быть сдвинут относительно других объектов для получения более компактного размещения.

К решению задачи плотной упаковки сводится решение множества оптимизационных задач распределения ресурсов, являющихся стратегически важными в различных отраслях экономики, в частности: оптимизации хранения запасов в складских системах, планирования грузоперевозок воздушным, морским, железнодорожным и автомобильным транспортом; раскроя листового промышленного материала (из картона, фанеры, оргстекла, поролона, поликарбоната и др.), раскроя рулонного промышленного материала (металла, бумаги, ткани и пр.), раскроя трёхмерных блоков большой длины (из дерева, пенопласта, мрамора, гранита и др.), проектирования компоновок пространства, помещений, оборудования, сверхбольших интегральных схем, распределения памяти и вычислительных ресурсов в мультипроцессорных системах, теории расписаний и объёмно-календарного планирования, расчёта оптимальных капиталовложений (формирования инвестиционного портфеля), моделирования зернистых сред и проектирования геометрических конфигураций молекул, проектирования фазированных антенных решёток.

Повышенный интерес исследователей к разработке и развитию методов оптимизации размещения объектов объясняется как широким распространением практических приложений задач плотной упаковки, так и сложностью их решения, обусловленной принадлежностью этих задач к классу NP-трудных задач дискретной оптимизации.

Поскольку применение методов получения оптимального решения, основанных на полном переборе всех вариантов решения, является на практике неэффективным из-за существенных затрат временных и вычислительных ресурсов, то целесообразно применение методов, направленных на сокращение числа возможных вариантов решения задачи, а также методов, обеспечивающих получение приближённых решений. Применяемые методы комбинаторной оптимизации и математического программирования являются очень чувствительными к размерности задачи, поэтому, как правило, их применение оправдано лишь при размещении нескольких десятков объектов. Наилучший компромисс между скоростью и качеством решения задачи плотной упаковки большого числа объектов в условиях единичного и мелкосерийного производства достигается при использовании эвристических и метаэвристических методов, применение которых позволяет относительно быстро получить приближённые решения, близкие к оптимальным.

Степень разработанности темы исследования. Наибольший вклад в развитие методов решения задач раскроя и упаковки внесли уфимская школа раскроя-упаковки под руководством профессора Э.А. Мухачевой, а также харьковская научная школа под руководством профессора Ю.Г. Стояна. Оптимизации решения задач плотной упаковки посвящены работы Л.В. Канторовича, В.А. Залгаллера, И.В. Романовского,

A.И. Липовецкого, Л.Б. Беляковой, В.Н. Гаврилова, В.В. Бухваловой, М.А. Верхотурова,

B.М. Картака, А.Ф. Валеевой, А.С. Филипповой, О.В. Корчевской, М.Ю. Куприкова, а также многих других авторов. Среди зарубежных исследователей, оказавших наибольшее влияние на развитие методов решения задач плотной упаковки, можно выделить H. Dyckhoff, S.P. Fekete, J. Schepers, G. Wäscher, A. Bortfeldt, G. Scheithauer, J. Terno, S. Martello, D. Vigo, M. Iori, M. Monaci, P. Perboli, P. Toth, A. Lodi, P.C. Gilmore, R.E. Gomory, M.R. Garey, P.Y. Wang, M.G.C. Resende, E. Hopper, B.C.H. Turton, T.G. Crainic, D. Pisinger, J.F. Gonçalves, J.F. Oliveira, E.G. Birgin, F.K. Miyazawa, R. Morabito, A. Alvarez-Valdes, W. Huang, D. Chen.

Анализ научной литературы в области задач раскроя и упаковки показал, что большинство исследований направлено на решение задач упаковки ортогональных объектов, представленных в виде отрезков, прямоугольников или параллелепипедов. Для размещения объектов произвольной формы в подавляющем большинстве случаев используются подходы, основанные на описании объектов с использованием полигональной модели и последующем применении предложенного Ю.Г. Стояном годографа функции плотного размещения, который требует применения методов нелинейного программирования, характеризующихся высокой вычислительной сложностью. Для геометрического описания объектов сложной формы в задачах упаковки большого числа объектов может быть применена воксельная модель с использованием результатов исследований, проведённых В. Л. Рвачёвым, А.В. Толоком, Д.М. Зозулевичем, Л.В. Маркиным.

В настоящее время в научной среде сформирована чёткая классификация задач раскроя и упаковки, а их решения имеют большое число практических приложений в различных областях промышленности и производства, что говорит как об актуальности развития исследований в области оптимизации решений этих задач, так и о высокой востребованности получаемых результатов. Подробные результаты анализа степени разработанности темы исследования приведены в п. 1.1 работы.

Несмотря на глубокую проработанность существующих методов решения задач раскроя и упаковки, можно выделить ряд нерешённых проблем.

1. Отсутствует единый алгоритмический подход к решению различных типов задач раскроя и упаковки объектов произвольной формы и различной размерности.

2. Отсутствуют методы решения задач упаковки объектов сложной геометрии внутри контейнеров произвольной формы и различной размерности.

3. Отсутствует модель геометрического описания упаковки, обеспечивающая в процессе размещения ортогональных объектов и ортогональных многогранников заданной размерности выбор наилучших свободных областей контейнера с целью получения наиболее плотной упаковки.

4. Не рассматривается вопрос локального повышения плотности размещения объектов внутри сформированной плотной упаковки.

Объектом диссертационного исследования являются задачи раскроя и упаковки объектов произвольной формы и различной размерности.

Предметом диссертационного исследования являются методы и алгоритмы повышения эффективности формирования и размещения объектов при решении задач раскроя и упаковки.

Цель диссертационного исследования - совершенствование методов оптимизации распределения ресурсов при решении задач плотной упаковки объектов произвольной формы, сводящихся к задачам прямоугольного раскроя и ортогональной упаковки различной размерности.

Для достижения указанной цели были поставлены следующие теоретические и прикладные задачи:

1. Разработка универсального метода решения различных типов задач раскроя и упаковки на основе структурной декомпозиции свободного пространства контейнеров различной размерности.

2. Разработка модели, обеспечивающей полное геометрическое описание свободного пространства контейнеров сложной формы при размещении ортогональных объектов и ортогональных многогранников различной размерности.

3. Развитие эвристических и метаэвристических методов оптимизации решений задач раскроя и упаковки.

4. Разработка алгоритмов, обеспечивающих повышение плотности размещения ортогональных объектов различной размерности.

5. Разработка алгоритмов формирования объектов в форме ортогональных многогранников заданной размерности и их размещения внутри контейнеров произвольной формы.

6. Программная реализация разработанных алгоритмов в виде прикладного программного обеспечения, предназначенного для решения задач раскроя и упаковки объектов различной размерности, а также для анализа эффективности применяемых алгоритмов оптимизации.

Проблематика диссертационного исследования соответствует следующим областям исследования паспорта научной специальности 05.01.01 «Инженерная геометрия и компьютерная графика»:

п. 2 «Теория и практика непрерывного и дискретного геометрического моделирования. Конструирование кривых линий, поверхностей и тел по наперед заданным требованиям»;

п. 4 «Геометрические методы оптимизации в разных отраслях науки и техники»;

п. 6 «Геометрические основы компьютерного исследования процессов: проектирования, конструирования и технологии производства».

Научная новизна работы заключается в получении следующих научных результатов:

1. Разработан универсальный метод, заключающийся в структурной декомпозиции пространства упаковки на потенциальные контейнеры и дальнейшем приведении решаемых задач к задачам прямоугольного раскроя и ортогональной упаковки, предназначенный для решения различных типов NP-трудных задач распределения ресурсов, позволяющий размещать объекты произвольной формы в контейнерах сложной геометрии и различной размерности. Метод отличается от известных использованием специально разработанных алгоритмов геометрического конструирования пространства упаковки, основанных на анализе всех потенциальных контейнеров заданной размерности с целью получения наиболее плотного размещения объектов (п. 6 паспорта научной специальности 05.01.01).

2. Разработана модель потенциальных контейнеров, предназначенная для геометрического конструирования пространства упаковки при решении задач прямоугольного раскроя и ортогональной упаковки объектов, реализующая наиболее быстрое и плотное размещение ортогональных объектов и ортогональных многогранников, которая отличается от известных использованием полного геометрического описания свободного пространства контейнеров сложной геометрии и произвольной размерности (п. 2 паспорта научной специальности 05.01.01).

3. Разработана многоуровневая связная структура данных, заключающаяся в представлении многомерных наборов данных в виде рекурсивно вложенных линейных связных списков, содержащих уникальные значения координат потенциальных контейнеров, предназначенная для упорядоченного хранения наборов свободных областей контейнера произвольной размерности, позволяющая повысить скорость геометрического конструирования пространства ортогональной упаковки, отличающаяся эффективным многоуровневым хранением наборов данных, не требующим применения трудоёмких операций сортировки (п. 2 паспорта научной специальности 05.01.01).

4. Разработаны эвристики размещения двухмерных и трёхмерных ортогональных объектов, основанные на анализе сочетания комбинаций размещаемых объектов и свободных областей контейнеров, предназначенные для формирования плотной компоновки ортогональных объектов, обеспечивающие повышение плотности размещения объектов при использовании мультиметодного генетического алгоритма. Эвристики отличаются анализом свободных областей контейнера, что позволяет выбирать наиболее подходящую область для каждого размещаемого объекта (п. 4 паспорта научной специальности 05.01.01).

5. Разработан итерационный алгоритм уплотнения упаковки объектов произвольной формы, заключающийся в локальном перераспределении размещённых объектов с целью минимизации объёмов свободных областей внутри упаковки, предназначенный для повышения эффективности решения задач раскроя и упаковки. Алгоритм характеризуется применимостью для дополнительного повышения плотности размещения объектов внутри сформированной плотной упаковки объектов произвольной размерности (п. 4 паспорта научной специальности 05.01.01).

6. Разработан алгоритм декомпозиции ортогонального многогранника произвольной размерности, основанный на применении модели потенциальных контейнеров, предназначенный для сокращения числа составляющих объектов ортогонального многогранника без искажения его формы, обеспечивающий существенное повышение скорости размещения объектов сложной формы. Алгоритм отличается от известных обобщением по размерности и применимостью к объектам произвольной геометрии (п. 2 паспорта научной специальности 05.01.01).

7. Разработан алгоритм размещения ортогональных многогранников, заключающийся в применении теоретико-множественных операций с использованием модели потенциальных контейнеров, предназначенный для быстрого определения областей допустимого размещения ортогональных многогранников, обеспечивающий формирование плотной компоновки объектов произвольной формы внутри контейнеров сложной геометрии и различной размерности. Алгоритм отличается от известных определением наиболее подходящей области контейнера для каждого размещаемого объекта нерегулярной формы, применимостью к контейнерам сложной геометрии и обобщением по размерности (п. 6 паспорта научной специальности 05.01.01).

Теоретическая значимость работы заключается в разработке нового метода решения различных типов задач плотной упаковки объектов произвольной формы и различной размерности. В его основе лежит приведение решаемых задач к задачам прямоугольного раскроя и ортогональной упаковки с последующей декомпозицией свободного пространства контейнеров и применением разработанных алгоритмов геометрического конструирования пространства упаковки, обеспечивающих размещение каждого объекта в наиболее подходящей области контейнера.

Практическая значимость работы заключается в разработке алгоритмов оптимизированного решения задач плотной упаковки объектов произвольной формы и различной размерности, а также в их программной реализации в виде прикладного программного обеспечения.

Методология и методы исследований. Теоретические исследования выполнены с использованием методов системного анализа, исследования операций, дискретной оптимизации, геометрического моделирования, статистической обработки данных. Практическая реализация разработанных моделей и алгоритмов выполнена с использованием методов проектирования и разработки программного обеспечения, технологии объектно-ориентированного программирования, методов компьютерной графики. Проведение вычислительных экспериментов и оценка полученных результатов проводились с использованием методов экспериментального исследования с применением программных инструментов обработки информации и современных средств вычислительной техники.

Достоверность и обоснованность научных положений, рекомендаций и выводов обеспечиваются корректным применением математического аппарата. Достоверность результатов работы подтверждается сериями вычислительных экспериментов путём анализа и сравнения полученных результатов с результатами ведущих отечественных и зарубежных исследователей в области оптимизации решения задач раскроя и упаковки. Исследование достоверности и эффективности разработанных алгоритмов осуществлялось на стандартных (эталонных) тестовых задачах раскроя и упаковки, для которых известны значения точных нижних границ решений. Достоверность полученных результатов проверялась также с помощью визуальной диагностики, проводимой с использованием разработанного автором программного обеспечения, содержащего реализацию всех описанных в диссертационном исследовании алгоритмов.

Основные положения, выносимые на защиту

1. Универсальный метод решения различных типов NP-трудных задач раскроя и упаковки объектов произвольной формы на основе структурной декомпозиции свободного пространства контейнеров сложной геометрии с обобщением по размерности.

2. Модель построения потенциальных контейнеров посредством декомпозиции пространства упаковки сложной геометрии, состоящей из ортогональных объектов и ортогональных многогранников заданной размерности.

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

4. Алгоритм уплотнения упаковки и эвристические методы размещения двухмерных и трёхмерных объектов, предназначенные для повышения плотности упаковки при решении задач прямоугольного раскроя и ортогональной упаковки.

5. Алгоритм декомпозиции ортогонального многогранника произвольной размерности на множество наибольших по объёму ортогональных объектов.

6. Алгоритмы формирования и размещения ортогональных многогранников для решения задач раскроя и упаковки объектов сложной геометрии внутри контейнеров произвольной формы.

7. Архитектура построения универсального программного комплекса, предназначенного для решения различных типов задач раскроя и упаковки на основе эвристических и метаэвристических алгоритмов оптимизации.

8. Результаты тестирования разработанных алгоритмов и методов на тестовых задачах раскроя и упаковки.

Реализация результатов работы. Основные результаты диссертационного исследования внедрены и используются в следующих организациях: Федеральное государственное унитарное предприятие «Всероссийский научно-исследовательский институт автоматики им. Н.Л. Духова» (ФГУП «ВНИИА»), г. Москва; ООО «НД Плэй», г. Москва; ООО «КСБ Стелс», г. Москва; ООО «Инженерная фирма АБ Универсал», г. Москва; в учебном процессе федерального государственного бюджетного образовательного учреждения высшего образования «Оренбургский государственный университет» (ОГУ), г. Оренбург; в учебном процессе федерального государственного

бюджетного образовательного учреждения высшего образования «Московский государственный технологический университет «СТАНКИН» (ФГБОУ ВО «МГТУ «СТАНКИН»), г. Москва.

Результаты диссертационного исследования также использованы при выполнении следующих работ: научно-исследовательской работы по теме «Разработка компьютерных технологий для инженерного анализа и проектирования» (№ госрегистрации 01201254488, участие в качестве исполнителя, период участия: 01.01.2012-31.12.2013); государственного задания в сфере научной деятельности «Математическое моделирование молекулярных кластеров, наночастиц и высокодисперсных частиц обладающих особыми термодинамическими, электрическими и магнитными свойствами: структура, микрофизические характеристики, коллективная динамика, нелинейные, квантовые и полевые эффекты» (проект № 1441, задание № 2014/105, № госрегистрации 114051270018, участие в качестве исполнителя, период участия: 01.01.2014-31.12.2016); государственного задания в сфере научной деятельности «Мультимасштабное математическое моделирование неоднородностей в газовых и конденсированных системах с использованием проблемно-ориентированной вычислительной среды» (проект № 1.7706.2017/8.9, № госрегистрации АААА-А17-117042410207-5, участие в качестве исполнителя, период участия: 13.02.201731.12.2017); программы научных исследований и разработок получателя стипендии Президента Российской Федерации для молодых учёных и аспирантов, осуществляющих перспективные научных исследования и разработки по приоритетным направлениям модернизации российской экономики СП-1987.2013.5 (тема «Ресурсно-эффективное решение NP-полных задач многокритериальной оптимизации на основе развития аппарата эвристических алгоритмов», период выполнения программы: 20132015 гг.); программы научных исследований и разработок получателя стипендии Президента Российской Федерации для молодых учёных и аспирантов, осуществляющих перспективные научных исследования и разработки по приоритетным направлениям модернизации российской экономики СП-2135.2016.5 (тема «Разработка алгоритмов и методов решения ресурсоемких задач оптимизации распределения ресурсов», период выполнения программы: 2016-2018 гг.).

Апробация работы

Основные положения и результаты, полученные в ходе выполнения диссертационного исследования, неоднократно докладывались и обсуждались на научных семинарах кафедры инженерной графики и заседаниях научно-технического совета ФГБОУ ВО «МГТУ «СТАНКИН», научных семинарах НГТУ им. Р.Е. Алексеева, проводимых под руководством д.т.н., профессора В.П. Хранилова и д.т.н., профессора М.В. Ульянова, а также на следующих всероссийских и международных научных конференциях:

- Всероссийской конференции молодых ученых и специалистов «Будущее машиностроения России» (Москва, МГТУ им. Н.Э. Баумана, 2011);

- VI, VII, VIII Всероссийской междисциплинарной конференции студентов, аспирантов и молодых учёных «Искусственный интеллект: философия, методология, инновации» (Москва, МГТУ МИРЭА, 2012-2014);

- Международной научно-практической конференции «Инновационные информационные технологии (I2T)» (Чехия, Прага, 2013);

- XI Международной научно-практической конференции «Инновации на основе информационных и коммуникационных технологий (ИНФО-2014)» (Москва, НИУ ВШЭ, 2014);

- X, XII, XIII Международной научно-практической конференции «Объектные системы» (Ростов-на-Дону, 2015-2016);

- XXIV, XXV, XXVI Международной научно-практической конференции «Информационные системы и технологии» (Нижний Новгород, 2018-2020);

- 2, 3, 4, 5, 6, 7, 8, 9-й Международной научно-практической конференции «Современное машиностроение. Наука и образование» (Санкт-Петербург, ФГАОУ ВО СПбПУ, 2012-2020);

- V Международной научной конференции «Моделирование нелинейных процессов и систем (MNPS-2020)» (Москва, 2020);

- 30-й Международной конференции по компьютерной графике и машинному зрению «ГрафиКон-2020» (Санкт-Петербург, 2020);

- 4th International Conference on Mechanical and Aerospace Engineering (ICMAE 2013) (Russia, Moscow, 2013);

rd

- 3 International Conference on Energy and Environmental Protection (ICEEP 2014)

(China, Xi'An, 2014);

- 5th International Conference on Manufacturing Science and Engineering (ICMSE 2014) (China, Shanghai, 2014);

- 4th International Conference on Mechanics, Simulation and Control (ICMSC 2014) (Russia, Moscow, 2014);

- 7th 2015 International Conference on Artificial Intelligence and Industrial Engineering (AIIE 2015) (Thailand, Phuket, 2015);

- 7th International Conference on Mechanical and Electrical Technology (ICMET 2015) (Indonesia, Bali, 2015);

- 3rd International Symposium on Computer, Communication, Control and Automation (3CA 2015) (France, Paris, 2015);

- 2nd International Conference on Advanced Materials, Structures and Mechanical Engineering (ICAMSME 2015) (South Korea, Incheon, 2015);

- International Conference on Structural, Mechanical and Materials Engineering (ICSMME 2017) (South Korea, Seoul, 2017);

- 4th International Conference on Industrial Engineering (ICIE 2018) (Russia, Moscow, 2018);

- International Conference «High-tech and Innovations in Research and Manufacturing (HIRM-2019)» (Russia, Krasnoyarsk, 2019);

- International Russian Automation Conference «RusAutoCon 2019» (Russia, Sochi, 2019).

Публикации. По теме диссертационной работы опубликовано 70 работ, в том числе 21 публикация - в периодических изданиях из перечня ВАК РФ, 24 публикации -в изданиях, индексируемых международными наукометрическими базами Scopus и Web of Science, 21 публикация в трудах всероссийских и международных научных конференций, 1 свидетельство о государственной регистрации программы для ЭВМ. Информация о научных работах, выполненных лично соискателем и в соавторстве, приведена в Приложении Е диссертации.

Структура и объём работы. Диссертационная работа состоит из введения, шести глав, заключения, списка литературы и пяти приложений. Основной текст содержит 435 страниц. Список литературы состоит из 431 наименования. Приложения выполнены на 60 страницах.

Личный вклад автора. Все теоретические и практические результаты работы, изложенные в диссертации, получены лично автором. Конфликт интересов со всеми соавторами научных работ отсутствует.

Содержание работы

Во введении обосновывается актуальность темы диссертационной работы; формулируются цель и задачи исследований; представляются основные положения работы, выносимые на защиту; определяются научная новизна, теоретическая и практическая значимость полученных результатов; приводится краткая характеристика основных разделов диссертации.

В первой главе проводится обзор существующих типов задач раскроя и упаковки, а также основных методов их решения, приводится общая постановка задачи плотной упаковки и рассматриваются особенности и геометрические аспекты подходов, применяемых для решения различных задач этого класса.

Во второй главе исследуются различные модели, используемые для геометрического описания пространства контейнера при формировании ортогональной упаковки. Предлагается модель потенциальных контейнеров, разработанная для описания всех свободных областей, находящихся внутри контейнера произвольной размерности. Эта модель лежит в основе разработанного метода решения различных типов задач раскроя-упаковки на основе структурной декомпозиции пространства контейнеров. Для модели потенциальных контейнеров разработан ряд алгоритмов, обеспечивающих полное управление свободным пространством контейнера при размещении и удалении ортогональных объектов. Для упорядоченного хранения наборов областей, находящихся внутри контейнера произвольной размерности, предлагается многоуровневая связная структура данных. Анализ эффективности применения модели потенциальных контейнеров и многоуровневой связной структуры данных проводится на основе ряда вычислительных экспериментов на наборах стандартных тестовых задач раскроя-упаковки различной размерности, для которых известны значения точных нижних границ решений.

Список литературы диссертационного исследования доктор наук Чеканин Владислав Александрович, 2021 год

СПИСОК ЛИТЕРАТУРЫ

1. Александров, А.В., Алгоритмические и статистические свойства разреженной рюкзачной криптосистемы с общей памятью / А.В. Александров, А. Д. Метлинов // Известия высших учебных заведений. Приборостроение. - 2017. - Т. 60, № 1. -С. 5-9.

2. Александров, А.С. Выделение пустых областей прямоугольной формы в области с препятствиями / А.С. Александров, А.В. Войцев // Восточно-Европейский журнал передовых технологий. - 2012. - Т. 3, № 11. - С. 67-69.

3. Бабаев, Ф.В. Автоматическая оптимизация одномерного и двумерного раскроя / Ф.В. Бабаев // Приборы и системы управления. - 1974. - № 17. - С. 5-8.

4. Бабаев, Ф.В. Использование ЭВМ для оптимизации норм расхода материалов / Ф.В. Бабаев // Машиностроитель. - 1977. - № 8. - С. 36-37.

5. Бабаев, Ф.В. Оптимальный раскрой материалов с помощью ЭВМ / Ф.В. Бабаев. -М.: Машиностроение, 1982. - 168 с.

6. Бабаев, Ф.В. Оптимальный способ раскроя металла с помощью ЭВМ в условиях единичного и мелкосерийного производства / Ф.В. Бабаев // Вестник Машиностроения. - 1966. - № 12. - С. 43-46.

7. Басалин, П. Д. Многомерная задача раскроя бухт на кабельные отрезки / П.Д. Басалин [и др.] // Приволжский научный журнал. - 2015. - № 2. - С. 42-48.

8. Белякова, Л.Б. Алгоритм построения множества возможных сдвигов фигуры по заданному направлению на плоскости с областями запрета для движения / Л.Б. Белякова, Н.О. Рябина // Вычислительная техника в машиностроении. -Минск: ИТК АН БССР, 1974. - Вып. 4. - С. 9-15.

9. Белякова, Л.Б. Алгоритм рационального раскроя полос на фигурные заготовки / Л.Б. Белякова, О.М. Орехова, О.В. Дмитриевская // Труды ОНТИ ПТНИИ Волго-Вятского совнархоза. - 1964. - Т. 1. - С. 53-65.

10. Белякова, Л.Б. Об оптимальном раскрое листового проката / Л.Б. Белякова // Автоматизация технологического проектирования при помощи ЭЦВМ. - М.: Машиностроение. - 1968. - С. 21-32.

11. Белякова, Л.Б. Проектирование на ЭВМ оптимального раскроя заготовок при листовой штамповке сложных форм / Л.Б. Белякова, Н.О. Рябина // Кузнечно-штамповочное производство. - 1977. - № 11. - С. 25-28.

12. Бионические информационные системы и их практические применения / под ред. Л.А. Зинченко, В.М. Курейчика, В.Г. Редько. - М.: ФИЗМАТЛИТ, 2011. - 288 с.

13. Бронфельд, Г.Б. Алгоритм решения задачи оптимального распределения плана производства / Г.Б. Бронфельд // Автоматизация и механизация управления производством: сб. тр. - Горький: НИИУавтопром., 1977. - Вып. 2. - С. 75-83.

14. Бухвалова, В.В. Задача прямоугольного раскроя: метод зон и другие алгоритмы /

B.В. Бухвалова. - СПб.: СПГУ. 2001. - 96 с.

15. Валеева, А.Ф. Применение конструктивной метаэвристики «муравьиная колония» к задаче гильотинного прямоугольного раскроя / А.Ф. Валеева, А.А. Петунин, Р.И. Файзрахманов // Вестник Башкирского университета. - 2007. - Т. 12, № 3. -С 12-14.

16. Валеева, А.Ф. Применение конструктивных эвристик в задачах раскроя-упаковки / А.Ф. Валеева // Информационные технологии. - 2006. - № S11. - С. 1-24.

17. Валиахметова, Ю.И. Гибридный алгоритм на основе последовательного уточнения оценок для задач максимального ортогонального покрытия / Ю.И. Валиахметова,

C.В. Телицкий, Э.И. Хасанова // Вестник Башкирского университета. - 2012. -Т. 17, № 1 (I). - С. 421-424.

18. Валиахметова, Ю.И. Гиперэвристические алгоритмы в задачах прямоугольного раскроя / Ю.И. Валиахметова // Вестник Новосибирского государственного университета. Серия: Информационные технологии. - 2013. - Т. 11, Вып. 2. -С. 36-43.

19. Валиахметова, Ю.И. Мультиметодная технология ортогональной упаковки и ее применение в задачах транспортной логистики / Ю.И. Валиахметова [и др.] // Информационные технологии. - 2009. - № S12. - С. 1-32.

20. Валиахметова, Ю.И. Мультиметодный генетический алгоритм для решения задач ортогональной упаковки / Ю.И. Валиахметова, А.С. Филиппова // Информационные технологии. - 2007. - № 12. - С. 50-56.

21. Валиахметова, Ю.И. Расширение генетического алгоритма комбинирования эвристик для решения задачи прямоугольной упаковки / Ю.И. Валиахметова, Е.В. Карамова // Вестник ВЭГУ. - 2009. - № 2. - С. 89-94.

22. Валиахметова, Ю.И. Теория оптимального использования ресурсов Л.В. Канторовича в задачах раскроя-упаковки: обзор и история развития методов решения / Ю.И. Валиахметова, А.С. Филиппова // Вестник Уфимского государственного авиационного технического университета. - 2014. - Т. 18, № 1 (62). - С. 186-197.

23. Валиахметова, Ю.И. Технологии моделирования алгоритмов ортогонального раскроя-упаковки и геометрического покрытия: сравнение эффективности / Ю.И. Валиахметова [и др.] // Сетевое издание «Нефтегазовое дело». - 2015. -№ 5. - С. 424-445.

24. Васильева, Л.И. Алгоритмы упаковки п-мерных гофров на базе методов линейного программирования : дис. ... канд. техн. наук : 05.13.16 : защищена 22.12.2000 : утв. / Васильева Лидия Ильясовна. - Уфа, 2000. - 124 с.

25. Введение в ИМЬ от создателей языка. 2-е изд. / Г. Буч, Д. Рамбо, И. Якобсон. - М.: ДМК Пресс, 2011. - 496 с.

26. Верхотуров, М.А. Динамическая схема использования условий взаимного непересечения при решении задачи плотной упаковки невыпуклых многогранников / М.А. Верхотуров, Р.Р. Ягудин, Г.Н. Верхотурова // Информационные системы и технологии. - 2013. - Т. 79, № 5. - С. 15-23.

27. Верхотуров, М.А. Упаковка сложных трёхмерных объектов в прямоугольный контейнер на базе дискретно-логического представления информации / М.А. Верхотуров [и др.] // Известия Самарского научного центра Российской академии наук. - 2014. - Т. 16, № 4-2. - С. 378-383.

28. Гаврилов, В.Н. Автоматизированная компоновка приборных отсеков летательных аппаратов / В.Н. Гаврилов. - М.: Машиностроение, 1988. - 136 с.

29. Генетические алгоритмы / Л. А. Гладков, В.В. Курейчик, В.М. Курейчик; под ред. В.М. Курейчика. - 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2006. - 320 с.

30. Герасименко, Е.П. Методы формирования трехмерных рецепторных матриц на ЭВМ / Е.П. Герасименко, Д.М. Зозулевич // Вычислительная техника в машиностроении. - Минск: ИТК АН БССР, 1971. - С. 24-31.

31. Гиля-Зетинов, А. А. Разработка алгоритма укладки паллет на полностью автоматизированном складе / А. А. Гиля-Зетинов, К.К. Панкратов, А.В. Хельвас // Труды МФТИ. - 2019. - Т. 11, № 1. - С. 20-30.

32. Гимади, Э.Х. Задача упаковки в полосу: асимптотически точный подход / Э.Х. Гимади, В.В. Залюбовский, П.И. Шарыгин // Известия высших учебных заведений. Математика. - 1997. - № 12. - С. 34-44.

33. Гладков, Л.А. Гибридный генетический алгоритм решения задачи размещения элементов СБИС с учетом трассируемости соединений / Л.А. Гладков // Вестник Ростовского государственного университета путей сообщения. - 2011. - № 3. -С. 60-68.

34. Головистиков, А.В. Задачи двумерной прямоугольной упаковки и раскроя: обзор / А.В. Головистиков // Информатика. - 2008. - № 4. - С. 18-33.

35. Гончаров, Е.Н. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации / Е.Н. Гончаров, Ю.А. Кочетов // Дискретный анализ и исследование операций. - 2002. - Т. 9, № 2. - С. 13-30.

36. Горанский, Г.К. Алгебрологический метод решения геометрических задач автоматизации проектирования с помощью ЭЦВМ / Г.К. Горанский, Д.М. Зозулевич, Д.Р. Шерлинг // Вычислительная техника в машиностроении. -Минск: ИТК АН БССР, 1967. - С. 121-127.

37. Гребенник, И.В. Упаковка n-мерных параллелепипедов с возможностью изменения их ортогональной ориентации в n-мерном параллелепипеде / И.В. Гребенник [и др.] // Кибернетика и системный анализ. - 2010. - № 5. - С. 122-131.

38. Григорчук, Т.И. Математическая модель многокритериальной задачи покрытия многосвязного ортогонального полигона / Т.И. Григорчук [и др.] // Нефтегазовое дело. - 2017. - Т. 15, № 2. - С. 146-154.

39. Григорьева, Н.С. Задача минимизации максимального временного смещения для параллельных процессоров / Н.С. Григорьева // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. - 2016. - № 4. - С. 51-65.

40. Дивеев, А.И. Решение задачи двумерной упаковки методом вариационного генетического алгоритма / А.И. Дивеев, Е.Ю. Шмалько // Cloud of Science. - 2016. -Т. 3, № 3. - С. 380-395.

41. Евсеева, Л.Г. Задача упаковки интервальных кругов / Л.Г. Евсеева, Г.Н. Яськов // Восточно-Европейский журнал передовых технологий. - 2008. - Т. 1, № 4. - С. 2529.

42. Ермаченко, А.И. Модели и методы решения задач прямоугольного раскроя и упаковки на базе метаэвристики «Поиск с запретами» : дис. ... канд. техн. наук : 05.13.18 : защищена 2004 : утв. / Ермаченко Александр Иванович. - Уфа, 2004. -95 с.

43. Житников, В.П. Задача прямоугольной упаковки в полубесконечную полосу: поиск решения в окрестности локальной нижней границы / В.П. Житников,

A.С. Филиппова // Информационные технологии. - 2007. - № 6. - С. 55-61.

44. Жук, С.Н. Анализ некоторых эвристик в задаче упаковки прямоугольников в несколько полос / С.Н. Жук // Труды Института системного программирования РАН. - 2004. - Т. 6. - С. 13-26.

45. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума / А.С. Мухачева, А.Ф. Валеева, В.М. Картак. - М.: МАИ, 2004. - 193 с.

46. Залгаллер, В.А. Новое в составлении поставов для распиловки бревен /

B.А. Залгаллер. - Л.: ЦНИИЛ «Севзаплес», 1956. - Вып. 67.

47. Как программировать на С++: Третье издание / Х. Дейтел, П. Дейтел - М.: ЗАО «Издательство БИНОМ», 2003. - 1152 с.

48. Канторович, Л.В. Математические методы организации и планирования производства / Л.В. Канторович. - Л.: ЛГУ, 1939. - 67 с.

49. Канторович, Л.В. Рациональные методы раскроя металла / Л.В. Канторович // Производственно-технический бюллетень НК Боеприпасов СССР. - 1942. - № 78. - С. 21-29.

50. Карпенко, А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновлённые природой : учебное пособие / А.П. Карпенко. - 2-е изд. - М.: Издательство МГТУ им. Н.Э.Баумана, 2017. - 446 с.

51. Картак, В.М. Задача размещения ортогональных многоугольников: модели и алгоритм покоординатной упаковки / В.М. Картак [и др.] // Информационные технологии. - 2008. - № 3. - С.46-53.

52. Картак, В.М. Задача упаковки прямоугольников: точный алгоритм на базе матричного представления / В.М. Картак // Вестник Уфимского государственного авиационного технического университета. - 2007. - Т. 9, № 4. - С. 104-110.

53. Картак, В.М. Локальный поиск ортогональных упаковок с использованием нижних границ / В.М. Картак [и др.] // Автоматика и телемеханика. - 2009. - № 6. - С. 153166.

54. Картак, В.М. Матричный алгоритм поиска оптимального решения для решения задачи упаковки прямоугольников в полубесконечную полосу / В.М. Картак // Информационные технологии. - 2008. - № 2. - С. 24-30.

55. Картак, В.М. Методы анализа и оптимизации М-мерной ортогональной упаковки на базе сечений различных размерностей : дис. ... д-ра физ.-мат. наук : 05.13.01 : защищена 16.09.2011 : утв. / Картак Вадим Михайлович. - Уфа, 2011. - 237 с.

56. Картак, В.М. Методы целочисленного линейного программирования в задаче нерегулярного размещения плоских геометрических объектов в форме полимино /

B.М. Картак, А.И. Фабарисова // Вестник Уфимского государственного авиационного технического университета. - 2018. - Т. 22, № 2 (80). - С. 131-137.

57. Картак, В.М. Обновлённая нижняя граница для задачи упаковки прямоугольников в полубесконечную полосу / В.М. Картак // Вестник УГАТУ. - 2008. - Т. 10, № 2 (27). - С. 154-158.

58. Козин, И.В. Генерация случайных карт прямоугольного раскроя / И.В. Козин,

C.Е. Батовский // Питання прикладной математики i математичного моделювання. -2018. - № 18. - С. 118-126.

59. Компоновка самолётов / под ред. М.Ю. Куприкова. - М.: МАИ, 2012. - 296 с.

60. Конин, М.В. Нахождение оптимальных размеров коллектора для инженерных сетей / М.В. Конин // Проблемы информатики. - 2014. - № 4 (25). - С. 1-4.

61. Корн, Г.В. Методы формирования рецепторных геометрических моделей и их применение при решении инженерно-геометрических задач: автореф. дис. ... канд. техн. наук : 05.01.01 / Корн, Галина Васильевна. - Москва, 1990. - 19 с.

62. Корчевская, О.В. Информационные модели и методы решения задач ортогонального раскроя-упаковки на основе конструктивных и нейросетевых подходов : дис. ... канд. техн. наук : 05.13.17 : защищена 07.04.2009 : утв. / Корчевская Оксана Валериевна. - Красноярск, 2009. - 147 с.

63. Корчевская, О. В. Решение задачи двумерной ортогональной упаковки в полубесконечную полосу с помощью метода профиля / О.В. Корчевская // Вестник Красноярского государственного аграрного университета. - 2007. - № 1. - С. 34-37.

64. Корчевская, О.В. Решения задач ортогонального раскроя-упаковки на основе конструктивных и нейросетевых подходов / О.В. Корчевская // Образовательные ресурсы и технологии. - 2014. - № 1(4). - С. 142-149.

65. Кочетов, Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации / Ю.А. Кочетов // Дискретная математика и её приложения. Сборник лекций молодежных и научных школ по дискретной математике и её приложениям. - М.: Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2000. - С. 87-117.

66. Кузнецов, В.Ю. Задачи покрытия ортогональных многоугольников с запретными участками / В.Ю. Кузнецов // Вестник Уфимского государственного авиационного технического университета. - 2008. - Т. 10, № 2. - С. 177-182.

67. Кузюрин, Н.Н. Проблемы двумерной упаковки и задачи оптимизации в распределенных вычислительных системах / Н.Н. Кузюрин, Д.А. Грушин, С.А. Фомин // Труды Института системного программирования РАН. - 2014. -Т. 26, № 1. - С. 483-501.

68. Куприков, М.Ю. Геометрические аспекты автоматизированной компоновки летательных аппаратов / М.Ю. Куприков, Л.В. Маркин // Геометрия и графика. -2018. - Т. 6, № 3. - С. 69-87.

69. Куприяшин, М.А. Исследование алгоритма точного решения задачи о рюкзаке методом динамического программирования / М.А. Куприяшин, Г.И. Борзунов // Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления. - 2016. - № 17. - С. 121-130.

70. Курейчик, В.М. Алгоритмы одномерной упаковки элементов / В.М. Курейчик // Известия Южного федерального университета. Технические науки. - 2013. - № 7. -С. 8-11.

71. Левин, М.Ш. Упаковка в контейнеры (перспективные модели, примеры) / М.Ш. Левин // Информационные процессы. - 2017. - Т. 17, № 1. - С. 43-60.

72. Липовецкий, А.И. К оптимизации свободного размещения прямоугольников / А.И. Липовецкий // Автоматизация проектирования в машиностроении. - 1985. -С. 80-87.

73. Максименко-Шейко, К.В. Я-функции в аналитическом проектировании с применением системы "РАНОК" / К.В. Максименко-Шейко, А.В. Толок, Т.И. Шейко // Вестник МГТУ Станкин. - 2010. - № 4. - С. 139-151.

74. Мальчевский, В.В. Матрично-топологический метод синтеза схемы и компоновки самолета / В.В. Мальчевский. - М.: Изд-во МАИ, 2011. - 356 с.

75. Маркин, Л.В. Подсистема оптимизации размещения коммерческого груза на самолетах / Л.В. Маркин, А.Б. Шатный // Вестник Московского авиационного института. - 2010. - Т. 17. - № 2. - С. 23-30.

76. Марков, В.Н. База знаний для негильотинного раскроя-упаковки / В.Н. Марков // Информационные технологии. - 2007. - № 4. - С. 17-23.

77. Математические модели и оптимизационные методы геометрического проектирования / Ю.Г. Стоян, С.В. Яковлев // Киев: Наук. думка, 1986. - 286 с.

78. Месягутов, М.А. Задача двухмерной ортогональной упаковки: поиск нижней границы на базе решения одномерной продолженной упаковки / М.А. Месягутов // Информационные технологии. - 2010. - № 6. - С. 13-17.

79. Методы и алгоритмы размещения плоских геометрических объектов / Ю.Г. Стоян, Н.И. Гиль. - Киев: Наук. думка, 1976. - 247 с.

80. Модели и методы расчета раскроя-упаковки геометрических объектов / Э.А. Мухачева, М.А. Верхотуров, В.В. Мартынов. - Уфа: УГАТУ, 1998. -216 с.

81. Мурин, М.Н. Математическое обеспечение решения задачи размещения прямоугольников с изменяемыми метрическими характеристиками / М.Н. Мурин, И.А. Чуб, М.В. Новожилова // Системи обробки шформацп. - 2012. - № 7. - С. 196199.

82. Мусин, О.Р. Экстремальные задачи упаковок кругов на сфере и неприводимые контактные графы / О.Р. Мусин, А.С. Тарасов // Труды Математического института имени ВА Стеклова. - 2015. - Т. 288. - С. 133-148.

83. Мухачева, А.С. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения /

А.С. Мухачева [и др.] // Информационные технологии. Приложение. - 2001. -№ 9. - С. 1-28.

84. Мухачева, Э.А. Автоматизация проектирования гильотинного раскроя с обходом дефектных областей на базе эволюционных алгоритмов / Э.А. Мухачева [и др.] // Информационные технологии. - 2009. - № Б2. - С. 1-32.

85. Мухачева, Э.А. Задача двумерной контейнерной упаковки: нижние границы и численный эксперимент с алгоритмами локального поиска оптимума / Э.А. Мухачева [и др.] // Информационные технологии. - 2006. - № 4. - С. 45-52.

86. Мухачева, Э.А. Метод поиска минимума с запретами в задачах двухмерного гильотинного раскроя / Э.А. Мухачева [и др.] // Информационные технологии. -2001. - № 6. - С. 25-31.

87. Мухачева, Э.А. Методы локального поиска в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития / Э.А. Мухачева [и др.] // Информационные технологии. - 2004. - № 5. Приложение. - С. 2-17.

88. Мухачева, Э.А. Методы условной оптимизации в задачах рационального раскроя листового проката / Э.А. Мухачева // Оптимизация: Сб. науч. трудов СО АН СССР. - 1978. - № 22. - С. 83-93.

89. Мухачева, Э.А. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур / Э.А. Мухачева [и др.] // Информационные технологии. - 2004. - № 5. Приложение. - С. 1-31.

90. Мухачева, Э.А. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задач одномерного раскроя / Э.А. Мухачева, В.М. Картак // Информационные технологии. - 2000. - № 9. - С. 15-22.

91. Мухачева, Э.А. Оптимизационные проблемы транспортной логистики: оперативное размещение контейнеров при транспортировке грузов / Э.А. Мухачева [и др.] // Информационные технологии. - 2008. - № 7. - С. 17-22.

92. Мухачева, Э.А. Рациональный раскрой промышленных материалов. Применение АСУ / Э.А. Мухачева. - М.: Машиностроение, 1984. - 176 с.

93. Назаров, Д.А. Задача двухмерной упаковки в полосу: точный алгоритм с разбиением на лестничные частичные упаковки / Д.А. Назаров // Информационные технологии. - 2011. - № 5. - С. 12-16.

94. Норенков, И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации / И.П. Норенков // Информационные технологии. - 1999. - № 1. -С. 2-7.

95. Образцов, А.А. Разработка алгоритмов автоматизированной компоновки оборудования / А.А. Образцов, С.В. Панченко // Известия высших учебных заведений. Проблемы энергетики. - 2008. - № 3-4. - С. 41-50.

96. Орехов, Э.Ю. Равновероятная генерация целочисленных задач прямоугольного раскроя-упаковки / Э.Ю. Орехов // Информационные технологии. - 2014. - № 2. -С. 33-37.

97. Панкратов, А.В. Задача оптимизации упаковки многогранников в сферическом и цилиндрическом контейнерах / А.В. Панкратов [и др.] // Восточно-Европейский журнал передовых технологий. - 2016. - Т. 1, № 4. - С. 39-47.

98. Пантелеев, А.В. Метаэвристические алгоритмы поиска глобального экстремума / А.В. Пантелеев. - М.: Изд-во МАИ-ПРИНТ, 2009. - 160 с.

99. Подлазова, А.В. Генетические алгоритмы на примерах решения задач раскроя /

A.В. Подлазова // Проблемы управления. - 2008. - № 2. - С. 57-63.

100. Потарусов, Р.В. Задача одномерной упаковки. Анализ и обзор эвристических алгоритмов / Р.В. Потарусов, В.М. Курейчик // Перспективные информационные технологии и интеллектуальные системы. - 2006. - № 1. - С. 37-47.

101. Прикладные задачи динамического программирования / Г. Беллман, С. Дрейфус. -М.: Наука, 1965. - 458 с.

102. Расчет рационального раскроя материалов / Л.В. Канторович, В.А. Залгаллер. - Л.: Лениздат, 1951. - 198 с.

103. Рациональный раскрой промышленных материалов / Л.В. Канторович,

B.А. Залгаллер. - Новосибирск: Наука СО, 1971. - 320 с.

104. Рвачёв, В.Л. Об удовлетворении краевым условиям в методе Бубнова-Галеркина с помощью Я-функций / В.Л. Рвачёв // Успехи механики деформируемых сред: Сб. статей. - М.: Наука, 1975. - С. 488-501.

105. Рвачёв, В.Л. Геометрические приложения алгебры логики / В.Л. Рвачёв. - Киев: Изд-во «Техника», 1967. - 207 с.

106. Романовский, И.В. Алгоритмы решения экстремальных задач / И.В. Романовский. -М.: Наука, 1977. - С. 15-23.

107. Романовский, И.В. Решение задачи гильотинного раскроя методом переработки списка состояний / И.В. Романовский // Кибернетика. - 1969. - № 1. - С. 102-104.

108. Руднев, А.С. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу / А.С. Руднев // Дискретный анализ и исследование операций. - 2009. - Т. 16, № 4. - С. 61-86.

109. Рыков, И.А. О сравнении задачи упаковки в полосу с одной задачей календарного планирования / И.А. Рыков // Дискретный анализ и исследование операций. -2008. - Т. 15, № 4. - С. 57-73.

110. Сёмкин, В.В. Квази Ф-функция для сфероконусов с поворотами / В.В. Сёмкин,

A.М. Чугай, А.В. Панкратов // Радиоэлектроника и информатика. - 2014. -№ 1 (64). - С. 35-38.

111. Сиразетдинов, Т.М. Проектирование гильотинного раскроя листового и рулонного материала с использованием послойных алгоритмов : автореф. дис. ... канд. техн. наук : 05.13.12 / Сиразетдинов Тимур Маратович. - Уфа, 2004. - 15 с.

112. Ситу, Л. Рецепторные геометрические модели в задачах автоматизированной компоновки технического отсека легкого самолета / Л. Ситу, Н.Х. Ньи, Л.В. Маркин // Труды МАИ. - 2011. - № 47. - 16 с.

113. Стоян, Ю.Г. Моделирование плотной упаковки 3Б-объектов / Ю.Г. Стоян,

B.В. Сёмкин, А.М. Чугай // Кибернетика и системный анализ. - 2016. - С. 137-146.

114. Телицкий, С.В. Оптимизация многокритериального геометрического покрытия полигона на основе условных оценок с учетом технологических ограничений : дис. ... канд. техн. наук : 05.13.01 : защищена 06.03.2013 : утв. / Телицкий Станислав Владиславович. - Уфа, 2013. - 180 с.

115. Теория и практика эволюционного моделирования / В.В. Емельянов, В.В. Курейчик, В.М. Курейчик. - М.: ФИЗМАТЛИТ, 2003. - 432 с.

116. Теория расписаний. Задачи и алгоритмы / А.А. Лазарев, Е.Р. Гафаров. - М.: МГУ, 2011. - 222 с.

117. Тестовые задачи упаковки на полубесконечную полосу (O. Berkey и P. Wang, S. Martello и D. Vigo) [Электронный ресурс] / Operations Research Group of DEI, University of Bologna. - Режим доступа: http://or.dei.unibo.it/library/two-dimensional-bin-packing-problem (дата обращения: 12.04.2021).

118. Толок, А.В. Графические образы-модели в информационных технологиях /

A.В. Толок // Прикладная информатика. - 2009. - № 4. - С. 31-40.

119. Толок, А.В. Метод функциональной вокселизации полигональных объектов на основе математического аппарата Я-функций / А.В. Толок, М.А. Локтев // Прикладная информатика. - 2016. - Т. 11, № 1. - С. 127-134.

120. Толок, А.В. Решение задач математического программирования функционально-воксельным методом / А.В. Толок, Н.Б. Толок // Проблемы управления. - 2017. -№ 3. - С. 37-42.

121. Труб, И.И. Объектно-ориентированное моделирование на С++ / И.И. Труб. - СПб.: Питер, 2006. - 411 с.

122. Трушников, М.А. Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу / М.А. Трушников // Труды Института системного программирования РАН. - 2012. - Т. 22. - С. 456-461.

123. Тун, Е.В. Дискретные модели обеспечения зон обслуживания и автоматизированной компоновки летательных аппаратов / Е.В. Тун, Л.В. Маркин // Труды МАИ. - 2017. - № 96. - 23 с.

124. Ульянов, М.В. Комбинированный и волновой алгоритмы решения задачи упаковки: принципы построения и особенности / М.В. Ульянов, О.А. Наумова // Бизнес-информатика. - 2009. - № 2. - С. 27-33.

125. Ушаков, В.Н. Алгоритмы построения оптимальных упаковок в эллипсы /

B.Н. Ушаков, П.Д. Лебедев, Н.Г. Лавров // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. - 2017. - Т. 10, № 3. - С. 67-79.

126. Файзрахманов, Р. А. Решение задачи ортогональной упаковки листовых материалов методами линейного раскроя / Р.А. Файзрахманов [и др.] // Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления. - 2014. -№ 10. - С. 29-41.

127. Федорин, А.Н. Многокритериальные задачи ранцевого типа: разработка и сравнительный анализ алгоритмов : автореф. дис. ... канд. техн. наук : 05.13.18 / Федорин Андрей Николаевич. - Нижний Новгород, 2010. - 23 с.

128. Фельдман, Х.Л. Система максимальных поставов на распиловку / Х.Л. Фельдман. -М.: Гослестехиздат, 1932. - 275 с.

129. Филиппова, А.С. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологии блочных структур / А.С. Филиппова // Информационные технологии. - 2006. - № 6. Приложение. - 32 с.

130. Хасанова, Э.И. Матричный способ декомпозиции многосвязного полигона на множество прямоугольных областей минимальной мощности / Э.И. Хасанова, Р.С. Валеев // Вестник УГАТУ. - 2010. - Т. 14. - № 2 (37). - С. 183-187.

131. Хлуд, О.М. Решение задачи оптимальной упаковки гомотетических эллипсоидов в контейнере минимального объема / О.М. Хлуд // Проблемы машиностроения. -2016. - Т. 19, № 2. - С. 44-49.

132. Чебышев, П. Л. О кройке одежды / П. Л. Чебышев // Успехи математических наук. -1946. - Т. 1, № 2. - С.38-42.

133. Чеканин, А.В. Алгоритмы эффективного решения задачи ортогональной упаковки объектов / А.В. Чеканин, В. А. Чеканин // Журнал вычислительной математики и математической физики. - 2013. - Т. 53, № 10. - С. 1639-1648.

134. Чеканин, А.В. Инновационный подход к решению оптимизационных задач распределения ресурсов в промышленности / А.В. Чеканин, В. А. Чеканин // Инновации. - 2015. - № 8. - С. 76-81.

135. Чеканин, А.В. Проектирование инновационной библиотеки бионических алгоритмов для решения практических задач оптимизации / А.В. Чеканин, В.А. Чеканин // Инновации. - № 8. - 2016. - С. 108-112.

136. Чеканин, В.А. Адаптивная настройка параметров генетического алгоритма /

B.А. Чеканин, М.Ю. Куликова // Вестник МГТУ «Станкин». - 2017. - № 3 (42). -

C. 85-89.

137. Чеканин, В.А. Алгоритм декомпозиции ортогонального многогранника произвольной размерности / В.А. Чеканин, А.В. Чеканин // Информационные системы и технологии - 2020: сборник материалов XXVI Международной научно-технической конференции - Н. Новгород: Нижегород. гос. техн. ун-т им. Р.Е. Алексеева, 2020. - С. 889-895.

138. Чеканин, В.А. Алгоритм размещения ортогональных многогранников для задач раскроя-упаковки многогранников / В.А. Чеканин, А.В. Чеканин // Современное

машиностроение: Наука и образование : материалы 8-й международной научно-практической конференции / Под ред. А.Н. Евграфова и А.А. Поповича. - СПб.: ПОЛИТЕХ-ПРЕСС, 2019. - № 8. - С. 539-550.

139. Чеканин, В.А. Алгоритм решения задач ортогональной упаковки объектов на основе мультиметодной технологии / В.А. Чеканин, А.В. Чеканин // Информационные технологии. - 2013. - № 7. - С. 17-21.

140. Чеканин, В.А. Алгоритм удаления объектов в задачах ортогональной упаковки объектов / В.А. Чеканин, А.В. Чеканин // Современное машиностроение: Наука и образование: Материалы 5-й Междунар. науч.-практ. конференции / Под ред. А.Н. Евграфова и А.А. Поповича. - СПб.: Изд-во Политехн. ун-та, 2016. - С. 913922.

141. Чеканин, В.А. Алгоритм уплотнения упаковки для повышения эффективности распределения ортогональных ресурсов / В.А. Чеканин, А.В. Чеканин // Современное машиностроение: Наука и образование : материалы 7-й международной научно-практической конференции / Под ред. А.Н. Евграфова и А.А. Поповича. - СПб.: Изд-во Политехн. ун-та, 2018. - № 7. - С. 430-442.

142. Чеканин, В.А. Алгоритмы корректной визуализации двухмерных и трёхмерных ортогональных многогранников / В.А. Чеканин, А.В. Чеканин // Прикладная информатика. - 2019. - Т. 14, № 4 (82). - С. 19-28.

143. Чеканин, В.А. Алгоритмы построения ортогональных многогранников различной размерности / В.А. Чеканин, А.В. Чеканин // Информационные системы и технологии - 2019: сборник материалов XXV Международной научно-технической конференции. - Н. Новгород: Нижегород. гос. техн. ун-т им. Р.Е. Алексеева, 2019. -С. 709-715.

144. Чеканин, В.А. Алгоритмы размещения и удаления ортогональных многогранников произвольной размерности в задачах раскроя и упаковки / В.А. Чеканин // Вестник МГТУ «Станкин». - 2019. - № 3 (50). - С. 77-81.

145. Чеканин, В.А. Алгоритмы формирования ортогональных многогранников произвольной размерности в задачах раскроя и упаковки / В.А. Чеканин, А.В. Чеканин // Вестник МГТУ «Станкин». - 2018. - № 3 (46). - С. 126-130.

146. Чеканин, В.А. Библиотека алгоритмов искусственного интеллекта для решения задач раскроя-упаковки / В.А. Чеканин, А.В. Чеканин // Искусственный интеллект:

философия, методология, инновации. Сборник трудов VIII Всероссийской конференции студентов, аспирантов и молодых учёных (Москва, МИРЭА, 20-22 ноября 2014 г.). Часть I. Секции 1-5. - М.: Радио и Связь, 2014. - С. 137-142.

147. Чеканин, В.А. Библиотека классов для решения задач упаковки на основе эволюционных алгоритмов / В.А. Чеканин // Современное машиностроение: Наука и образование: Материалы 4-й Междунар. науч.-практ. конференции (Санкт-Петербург, 19-20 июня 2014 г.) / Под ред. М.М. Радкевича и А.Н. Евграфова. -СПб.: Изд-во Политехн. ун-та, 2014. - С. 789-796.

148. Чеканин, В.А. Исследование генетических методов оптимизации распределения прямоугольных ресурсов / В.А. Чеканин, А.В. Чеканин // Материалы 2-й международной научно-практической конференции «Современное машиностроение. Наука и образование» (Санкт-Петербург, 14-15 июня 2012 г.). -СПб.: Изд-во Политехн. ун-та, 2012. - С. 798-804.

149. Чеканин, В.А. Исследование модели виртуальных объектов в задаче ортогональной упаковки произвольной размерности / В.А. Чеканин // Задачи системного анализа, управления и обработки информации: Межвузовский сборник научных трудов. Вып. 3. - М.: МГУП, 2010. - С. 176-181.

150. Чеканин, В.А. К вопросу о повышении плотности ортогональной упаковки / В.А. Чеканин, А.В. Чеканин // Информационные системы и технологии: труды XXIV Международной научно-практической конференции (Нижний Новгород, 20 апреля 2018 г.). - Нижний Новгород: Нижегородский государственный технический университет им. Р.Е. Алексеева, 2018. - С. 1033-1038.

151. Чеканин, В.А. Модели конструирования ортогональной упаковки объектов / В.А. Чеканин, А.В. Чеканин // Информационные технологии и вычислительные системы. - 2014. - № 2. - С. 37-45.

152. Чеканин, В.А. Моделирование и оптимизация технологических операций в промышленном производстве на основе эволюционных алгоритмов / В.А. Чеканин, Е.Е. Ковшов // Технология машиностроения. - 2010. - № 3. - С. 53-57.

153. Чеканин, В.А. Модель потенциальных контейнеров для конструирования ортогональной упаковки / В.А. Чеканин, А.В. Чеканин // Вестник компьютерных и информационных технологий. - 2015. - № 3. - С. 22-27.

154. Чеканин, В.А. Модель представления объектов в задаче многомерной ортогональной упаковки / В.А. Чеканин, А.В. Чеканин // Искусственный интеллект: философия, методология, инновации. Сборник трудов VII Всероссийской конференции студентов, аспирантов и молодых ученых (Москва, МИРЭА, 13-15 ноября 2013 г.). Часть 2. - М.: МГТУ МИРЭА, 2013. - С. 60-64.

155. Чеканин, В.А. Модель размещения объектов в задаче контейнерной ортогональной упаковки / В.А. Чеканин, А.В. Чеканин // Инновационные информационные технологии: Материалы международной научно-практической конференции I2T (Прага, 22-26 апреля 2013 г.). Том 3. - М.: МИЭМ НИУ ВШЭ, 2013. - С. 418-420.

156. Чеканин, В.А. Модель управления свободными пространствами контейнеров в задаче ортогональной упаковки объектов / В.А. Чеканин, А.В. Чеканин // Материалы 3-й Международной научно-практической конференции «Современное машиностроение. Наука и образование» (Санкт-Петербург, 20-21 июня 2013 г.). -СПб.: Изд-во Политехн. ун-та, 2013. - С. 1060-1065.

157. Чеканин, В.А. Модифицированные эволюционные алгоритмы и программные решения задачи ортогональной упаковки объектов : дис. ... канд. техн. наук. : 05.13.17 : защищена 31.03.2011 : утв. 08.07.2011 / Чеканин Владислав Александрович. - Москва, 2011. - 161 с.

158. Чеканин, В.А. Мультиметодный генетический алгоритм для решения задач раскроя и упаковки прямоугольных объектов / В.А. Чеканин // Вестник МГТУ «Станкин». -2019. - № 4 (51). - С. 14-18.

159. Чеканин, В.А. Новые эвристики решения NP-полной задачи ортогональной упаковки объектов / В.А. Чеканин // Математическое моделирование и информатика: тр. XV научной конф. - М.: ФГБОУ ВПО МГТУ «СТАНКИН», 2013. - С. 72-74.

160. Чеканин, В.А. Объектно-ориентированная библиотека классов для решения оптимизационных задач распределения ресурсов / В.А. Чеканин, А.В. Чеканин // Объектные системы - 2015: материалы X Международной научно-практической конференции (Ростов-на-Дону, 10-12 мая 2015 г.) / Под общ. ред. П.П. Олейника. -Ростов-на-Дону: ШИ (ф) ЮРГПУ (НПИ) им. М.И. Платова, 2015. - С. 41-44.

161. Чеканин, В.А. Объектно-ориентированная реализация связной структуры данных для оптимизационных задач упаковки / В.А. Чеканин, А.В. Чеканин // Объектные

системы - 2016: материалы XII Международной научно-практической конференции (Ростов-на-Дону, 10-12 мая 2016 г.) / Под общ. ред. П.П. Олейника. -Ростов-на-Дону: ШИ (ф) ЮРГПУ (НПИ) им. М.И. Платова, 2016. - С. 17-23.

162. Чеканин, В.А. Объектно-ориентированный подход к решению оптимизационных задач упаковки / В.А. Чеканин // Инновации на основе информационных и коммуникационных технологий: Материалы XI Международной научно-практической конференции. - М.: НИУ ВШЭ, 2014. - С. 257-259.

163. Чеканин, В.А. Оптимизация решения задачи ортогональной упаковки объектов /

B.А. Чеканин, А.В. Чеканин // Прикладная информатика. - 2012. - № 4 (40). -

C. 55-62.

164. Чеканин, В.А. Повышение эффективности конструирования ортогональной упаковки объектов / В.А. Чеканин, А.В. Чеканин // Информационные технологии. -

2015. - № 1. - С. 24-29.

165. Чеканин, В.А. Повышение эффективности эволюционных алгоритмов при решении оптимизационных задач упаковки объектов / В.А. Чеканин, Е.Е. Ковшов, Н.Н. Хуэ // Системы управления и информационные технологии. - 2009. - № 3. - С. 63-67.

166. Чеканин, В.А. Прикладное программное обеспечение для решения задач ортогональной упаковки объектов / В.А. Чеканин, А.В. Чеканин // Объектные системы - 2016: материалы XIII Международной научно-практической конференции (Ростов-на-Дону, 10-12 декабря 2016 г.) / Под общ. ред. П.П. Олейника. - Ростов-на-Дону: ШИ (ф) ЮРГПУ (НПИ) им. М.И. Платова,

2016. - С. 10-15.

167. Чеканин, В.А. Программа для ЭВМ «Система оптимизации решения задач прямоугольного раскроя и ортогональной упаковки (Packer)» / В.А. Чеканин // Свидетельство о государственной регистрации программы для ЭВМ № 2019664360 от 06.11.2019 г.

168. Чеканин, В.А. Программная реализация эффективной структуры данных для задач ортогональной упаковки различной размерности / В.А. Чеканин, А.В. Чеканин // Прикладная информатика. - 2017. - Т. 12, № 5 (71). - С. 41-55.

169. Чеканин, В.А. Проектирование библиотеки метаэвристических алгоритмов для решения задач дискретной оптимизации / В.А. Чеканин, А.В. Чеканин // Современное машиностроение: Наука и образование : материалы 6-й

международной научно-практической конференции / Под ред. А.Н. Евграфова и А.А. Поповича. - СПб.: Изд-во Политехн. ун-та, 2017. - С. 527-536.

170. Чеканин, В.А. Разработка алгоритма уплотнения упаковки для повышения эффективности прямоугольного раскроя / В.А. Чеканин, А.В. Чеканин // Прикладная информатика. - 2018. - Т. 13. - № 3 (75). - С. 35-46.

171. Чеканин, В.А. Решение задачи декомпозиции ортогонального многогранника произвольной размерности / В.А. Чеканин, А.В. Чеканин // Современное машиностроение: Наука и образование : материалы 9-й международной научно-практической конференции / Под ред. А.Н. Евграфова и А.А. Поповича. - СПб.: ПОЛИТЕХ-ПРЕСС, 2020. - № 9. - С. 373-384.

172. Чеканин, В.А. Систематизация и анализ структур данных при автоматизации управления складом на основе генетических алгоритмов / В.А. Чеканин, Е.Е. Ковшов // Проблемы полиграфии и издательского дела, 2008. № 5. - С. 42-51.

173. Чеканин, В.А. Структура данных для задачи трехмерной ортогональной упаковки объектов / В.А. Чеканин, А.В. Чеканин // Вестник МГТУ «Станкин». - 2015. -№ 1. - С. 112-116.

174. Чеканин, В.А. Формирование детерминированной начальной популяции для решения задачи упаковки объектов / В.А. Чеканин // Будущее машиностроения России: сборник трудов Всероссийской конференции молодых ученых и специалистов (Москва, 28 сентября - 01 октября 2011 г.). - М.: МГТУ им. Н.Э.Баумана, 2011. - С. 78-79.

175. Чеканин, В.А. Эвристики размещения объектов для задачи трехмерной ортогональной упаковки объектов / В.А. Чеканин, Д.С. Киреев // Вестник МГТУ «Станкин». - 2017. - № 2 (41). - С. 98-102.

176. Чеканин, В.А. Эвристический алгоритм оптимизации решений задачи прямоугольного раскроя / В.А. Чеканин, А.В. Чеканин // Вестник МГТУ «Станкин». - 2014. - № 4. - С. 210-213.

177. Чеканин, В.А. Эффективная модель управления объектами в задачах ортогональной упаковки и прямоугольного раскроя / В.А. Чеканин, А.В. Чеканин // Прикладная информатика. - 2017. - Т. 12, № 3 (69). - С. 129-140.

178. Чеканин, В.А. Эффективная структура данных для оптимизационной задачи ортогональной упаковки объектов / В.А. Чеканин, А.В. Чеканин // Современное

машиностроение: Наука и образование: Материалы 4-й Междунар. науч.-практ. конференции (Санкт-Петербург, 19-20 июня 2014 г.) / Под ред. М.М. Радкевича и А.Н. Евграфова. - СПб.: Изд-во Политехн. ун-та, 2014. - С. 797-805.

179. Чеканин, В.А. Эффективное решение задачи двухмерной контейнерной упаковки прямоугольных объектов / В.А. Чеканин // Вестник компьютерных и информационных технологий. - 2011. - № 6. - С. 35-39.

180. Чеканин, В.А. Эффективные модели представления ортогональных ресурсов при решении задачи упаковки / В.А. Чеканин, А.В. Чеканин // Информационно-управляющие системы. - 2012. - № 5. - С. 29-32.

181. Чеканин, В.А. Эффективные эвристики размещения для задачи ортогональной упаковки объектов / В.А. Чеканин, А.В. Чеканин // Искусственный интеллект: философия, методология, инновации. Сборник трудов VI Всероссийской междисциплинарной конференции студентов, аспирантов и молодых ученых, г. Москва, МГТУ МИРЭА, 29-30 ноября 2012 г. // Под ред. Д.И. Дубровского и Е.А. Никитиной. Часть 1 (секции 1-3). - М.: МГТУ МИРЭА, 2012. - С. 170-175.

182. Чириков, Р.Ю. Проектирование больших антенных решеток как задача оптимальной упаковки / Р.Ю. Чириков // Инфокоммуникационные технологии. -2013. - Т. 11, № 3. - С. 77-82.

183. Чопоров, С.В. Использование функций В.Л. Рвачева для геометрического моделирования областей сложной формы / С.В. Чопоров, А.А. Лисняк, С.И. Гоменюк // Прикладная информатика. - 2010. - № 2. - С. 109-122.

184. Чугай, А.М. Решение задачи упаковки кругов в выпуклый многоугольник с помощью модифицированного метода сужающихся окрестностей / А.М. Чугай // Радиоэлектроника и информатика. - 2005. - № 1. - С. 58-63.

185. Ширгазин, Р.Р. Эволюционные методы и программное обеспечение для решения задач ортогональной упаковки на базе блочных структур : автореф. дис. ... канд. техн. наук : 05.13.18 / Ширгазин Рамиль Ришатович. - Уфа, 2006. - 14 с.

186. Шулепов, А.И. Автоматизированное решение задачи размещения грузов на борту транспортных космических систем / А.И. Шулепов, В.Н. Гаврилов, Г.В. Мятишкин // Вестник Самарского государственного аэрокосмического университета им. академика С.П. Королёва. - 2003. - № 1. - С. 47-49.

187. Щербина, О. А. Метаэвристические алгоритмы для задач комбинаторной оптимизации (обзор) / О.А. Щербина // Таврический вестник информатики и математики. - 2014. - № 1 (24). - С. 56-72.

188. Ягудин, Р.Р. Оптимизация компоновки трехмерных геометрических объектов на основе годографа вектор-функции плотного размещения / Р.Р. Ягудин // Инженерный вестник Дона. - 2012. - Т. 21, № 3. - С. 206-217.

189. Adamowicz, M. A solution of the rectangular cutting-stock problem / M. Adamowicz, A. Albano // IEEE Transactions on Systems, Man, and Cybernetics. - 1976. - № 4. -P. 302-310.

190. Allen, S.D. A hybrid placement strategy for the three-dimensional strip packing problem / S.D. Allen, E.K. Burke, G. Kendall // European Journal of Operational Research. - 2011. - Vol. 209, № 3. - P. 219-227.

191. ANSI/ISO C++ Committee. Programming Languages-C++ ISO/IEC 14882: 1998 (E). -American National Standards Institute, 1998.

192. Babel, L. Algorithms for on-line bin-packing problems with cardinality constraints / L. Babel [et al.] // Discrete Applied Mathematics. - 2004. - Vol. 143, № 1-3. - P. 238251.

193. Bajuelos, A.L. Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces / A.L. Bajuelos, A.P. Tomás, F. Marques // International Conference on Computational Science and Its Applications. - Springer, Berlin, Heidelberg, 2004. - P. 127-136.

194. Baldi, M.M. The three-dimensional knapsack problem with balancing constraints / M.M. Baldi, G. Perboli, R. Tadei // Applied Mathematics and Computation. - 2012. -Vol. 218, № 19. - P. 9802-9818.

195. Bazgan, C. An efficient implementation for the 0-1 multi-objective knapsack problem / C. Bazgan, H. Hugot, D. Vanderpooten // International Workshop on Experimental and Efficient Algorithms. - Springer, Berlin, Heidelberg, 2007. - P. 406-419.

196. Beasley, J.E. An exact two-dimensional non-guillotine cutting tree search procedure / J.E. Beasley // Operations Research. - 1985. - Vol. 33, № 1. - P. 49-64.

197. Beasley, J.E. Библиотека OR-Library тестовых задач теории исследования операций. [Электронный ресурс] / J.E. Beasley. - Режим доступа: http://people.brunel.ac.uk/~mastjjb/jeb/info.html (дата обращения: 12.04.2021).

198. Belov, G. One dimensional relaxations and LP bounds for orthogonal packing / G. Belov [et al.] // International Transactions in Operational Research. - 2009. - Vol. 16. - P. 745766.

199. Bengtsson, B.E. Packing rectangular pieces-a heuristic approach / B.E. Bengtsson // The computer journal. - 1982. - Vol. 25, № 3. - P. 353-357.

200. Bennell, J. Tools of mathematical modeling of arbitrary object packing problems / J. Bennell [et al.] // Annals of Operations Research. - 2010. - Vol. 179, № 1. - P. 343368.

201. Berkey, O. Two-dimensional finite bin-packing algorithms / O. Berkey, P. Wang // Journal of the Operational Research Society. - 1987. - Vol. 38, № 5. - P. 423-429.

202. Berman, P. Approximating Rectilinear Polygon Cover Problems / P. Berman, B. Dasgupta // Algorithmica. - 1997. - Vol. 17, № 4. - P. 331-356.

203. Beyaz, M. Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems / M. Beyaz, T. Dokeroglu, A. Cosar // Applied Soft Computing. -2015. - Vol. 36. - P. 236-245.

204. Biedl, T. Partitioning Orthogonal Histograms into Rectangular Boxes / T. Biedl [et al.] // Latin American Symposium on Theoretical Informatics. - Springer, Cham, 2018. -P. 146-160.

205. Birgin, E.G. An effective recursive partitioning approach for the packing of identical rectangles in a rectangle / E.G. Birgin, R.D. Lobato, R. Morabito // Journal of the Operational Research Society. - 2010. - Vol. 61, № 2. - P. 306-320.

206. Birgin, E.G. Minimizing the object dimensions in circle and sphere packing problems / E.G. Birgin, F.N.C. Sobral // Computers & Operations Research. - 2008. - Vol. 35, № 7. - P. 2357-2375.

207. Birgin, E.G. Optimizing the packing of cylinders into a rectangular container: A nonlinear approach / E.G. Birgin, J.M. Martinez, D.P. Ronconi // European Journal of Operational Research. - 2005. - Vol. 160. - P. 19-33.

208. Birgin, E.G. Orthogonal packing of identical rectangles within isotropic convex regions / E.G. Birgin, R.D. Lobato // Computers & Industrial Engineering. - 2010. - Vol. 59, № 4. - P. 595-602.

209. Birgin, E.G. Packing circles within ellipses / E.G. Birgin [et al.] // International Transactions in Operational Research. - 2013. - Vol. 20, № 3. - P. 365-389.

210. Birgin, E.G. Packing ellipsoids by nonlinear optimization / E.G. Birgin, R.D. Lobato, J.M. Martinez // Journal of Global Optimization. - 2016. - Vol. 65, № 4. - P. 709-743.

211. Bortfeldt, A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces / A. Bortfeldt // European Journal of Operational Research. - 2006. -Vol. 172, № 3. - P. 814-837.

212. Bortfeldt, A. A heuristic for the three-dimensional strip packing problem / A. Bortfeldt,

D. Mack // European Journal of Operational Research. - 2007. -Vol. 183, № 3. -P. 1267-1279.

213. Bortfeldt, A. A reduction approach for solving the rectangle packing area minimization problem / A. Bortfeldt // European Journal of Operational Research. - 2013. - Vol. 224, № 3. - P. 486-496.

214. Bortfeldt, A. Constraints in container loading - A state-of-the-art review / A. Bortfeldt, G. Wascher // European Journal of Operational Research. - 2013. - Vol. 229, № 1. -P. 1-20.

215. Boschetti, M.A. New lower bounds for the finite three-dimensional bin packing problem / M.A. Boschetti // Discrete Applied Mathematics. - 2004. - Vol. 140. - P. 241-258.

216. Brooks, R.L. The dissection of rectangles into squares / R.L. Brooks [et al.] // Duke Mathematical Journal. - 1940. - Vol. 7. - P. 312-340.

217. Buchalter, B.J. Orientational order in random packings of ellipses / B.J. Buchalter, R.M. Bradley // Physical Review A. - 1992. - Vol. 46, № 6. - P. 3046-3056.

218. Burke, E.K A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock-cutting problem / E.K. Burke, G. Kendall, G. Whitwell // INFORMS Journal on Computing. - 2009. - Vol. 21, № 3. - P. 505-516.

219. Burke, E.K. A new placement heuristic for the orthogonal stock-cutting problem /

E.K. Burke, G. Kendall, G. Whitwell // Operations Research. - 2004. - Vol. 52, № 4. -P. 655-671.

220. Byholm, T. Effective packing of 3-dimensional voxel-based arbitrarily shaped particles / T. Byholm, M. Toivakka, J. Westerholm // Powder Technology. - 2009. - Vol. 196, № 2. - P. 139-146.

221. Caldwell, A.E. Optimal Partitioners and End-Case Placers for Standard-Cell Layout / A.E. Caldwell, A.B. Kahng, I.L. Markov // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 2000. - Vol. 19, № 11. - P. 1304-1313.

222. Cetin, T. Genetic algorithm for networks with dynamic mutation rate / T. Cetin, M.A. Yurdusev // Gradevinar. - 2017. - Vol. 69, № 12. - P. 1101-1109.

223. Chan, H.H. Practical slicing and non-slicing block-packing without simulated annealing / H.H. Chan, I.L. Markov // Proceedings of the 14th ACM Great Lakes symposium on VLSI. - 2004. - P. 282-287.

224. Chekanin, A.V. Improved packing representation model for the orthogonal packing problem / A.V. Chekanin, V.A. Chekanin // Applied Mechanics and Materials. - 2013. -Vol. 390. - P. 591-595.

225. Chekanin, V. Solving the Problem of Packing Objects of Complex Geometric Shape into a Container of Arbitrary Dimension / V. Chekanin // CEUR Workshop Proceedings. -2020. - Vol. 2744. - DOI: 10.51130/graphicon-2020-2-3-50.

226. Chekanin, V.A. Algorithm for the placement of orthogonal polyhedrons for the cutting and packing problems / V.A. Chekanin, A.V. Chekanin // Advances in Mechanical Engineering. Lecture Notes in Mechanical Engineering. - Springer, Cham, 2020. - P. 4148.

227. Chekanin, V.A. Algorithms and methods in multidimensional orthogonal packing problems / V.A. Chekanin, A.V. Chekanin // International Journal of Applied Engineering Research. - 2017. - Vol. 12, № 6. - P. 1009-1019.

228. Chekanin, V.A. Algorithms for management objects in orthogonal packing problems / V.A. Chekanin, A.V. Chekanin // ARPN Journal of Engineering and Applied Sciences. -2016. - Vol. 11, № 13. - P. 8436-8446.

229. Chekanin, V.A. An efficient model for the orthogonal packing problem / V.A. Chekanin, A.V. Chekanin // Advances in Mechanical Engineering. - 2015. - Vol. 22. - P. 33-38.

230. Chekanin, V.A. Compaction algorithm for orthogonal packing problems / V.A. Chekanin, A.V. Chekanin // IOP Conference Series: Materials Science and Engineering. - IOP Publishing, 2017. - Vol. 248. - P. 012024.

231. Chekanin, V.A. Deleting Objects Algorithm for the Optimization of Orthogonal Packing Problems / V.A. Chekanin, A.V. Chekanin // Advances in Mechanical Engineering. -Springer International Publishing, 2017. - P. 27-35.

232. Chekanin, V.A. Design of library of artificial intelligence algorithms for solving the optimization problems / V.A. Chekanin, A.V. Chekanin // ARPN Journal of Engineering and Applied Sciences. - 2018. - Vol. 13, № 7. - P. 2690-2696.

233. Chekanin, V.A. Design of Library of Metaheuristic Algorithms for Solving the Problems of Discrete Optimization / V.A. Chekanin, A.V. Chekanin // Advances in Mechanical Engineering. Lecture Notes in Mechanical Engineering. - Springer, Cham, 2018. - P. 2532.

234. Chekanin, V.A. Design of software for orthogonal packing problems / V.A. Chekanin, A.V. Chekanin // Advanced Materials, Structures and Mechanical Engineering: Proceedings of the International Conference on Advanced Materials, Structures and Mechanical Engineering, Incheon, South Korea, May 29-31, 2015. - 2016. - P. 277-280.

235. Chekanin, V.A. Development of algorithms for the correct visualization of two-dimensional and three-dimensional orthogonal polyhedrons / V.A. Chekanin, A.V. Chekanin // In: A. Radionov, A. Karandaev (Eds.) Advances in Automation. RusAutoCon 2019. Lecture Notes in Electrical Engineering. - Springer, Cham, 2020. -Vol. 641. - P. 891-900.

236. Chekanin, V.A. Development of optimization software to solve practical packing and cutting problems / V.A. Chekanin, A.V. Chekanin // Proceedings of the 2015 International Conference on Artificial Intelligence and Industrial Engineering (AIIE 2015). Advances in Intelligent Systems Research. - 2015. - Vol. 123. - P. 379-382.

237. Chekanin, V.A. Development of the multimethod genetic algorithm for the strip packing problem / V.A. Chekanin, A.V. Chekanin // Applied Mechanics and Materials. - 2014. -Vol. 598. - P. 377-381.

238. Chekanin, V.A. Effective data structure for the multidimensional orthogonal bin packing problems / V.A. Chekanin, A.V. Chekanin // Advanced Materials Research. - 2014. -Vol. 962-965. - P. 2868-2871.

239. Chekanin, V.A. Implementation of packing methods for the orthogonal packing problems / V.A. Chekanin, A.V. Chekanin // Journal of Theoretical and Applied Information Technology. - 2016. - Vol. 88, № 3. - P. 421-430.

240. Chekanin, V.A. Improved data structure for the orthogonal packing problem / V.A. Chekanin, A.V. Chekanin // Advanced Materials Research. - 2014. - Vol. 945949. - P. 3143-3146.

241. Chekanin, V.A. Linked Data Structures / V.A. Chekanin, A.V. Chekanin // In: M. Barlow (Ed.), Data Structures and Transmission: Research, Technology and Applications. Series:

Computer Science, Technology and Applications. - New York: Nova Science Publishers Inc., 2017. - P. 35-71.

242. Chekanin, V.A. Multilevel linked data structure for the multidimensional orthogonal packing problem / V.A. Chekanin, A.V. Chekanin // Applied Mechanics and Materials. -2014. - Vol. 598. - P. 387-391.

243. Chekanin, V.A. Multimethod genetic algorithm for the three-dimensional orthogonal packing problem / V.A. Chekanin, A.V. Chekanin // Journal of Physics: Conference Series. - 2019. - Vol. 1353, № 1. - P. 012109.

244. Chekanin, V.A. New Effective Data Structure for Multidimensional Optimization Orthogonal Packing Problems / V.A. Chekanin, A.V. Chekanin // Advances in Mechanical Engineering. - Springer International Publishing, 2016. - P. 87-92.

245. Chekanin, V.A. Object-oriented class library for resource allocation problems / V.A. Chekanin, A.V. Chekanin // Applied Mechanics and Materials. - 2015. - Vol. 799800. - P. 1149-1153.

246. Chekanin, V.A. Packing Compaction Algorithm for Problems of Resource Placement Optimization / V.A. Chekanin, A.V. Chekanin // Advances in Mechanical Engineering. Lecture Notes in Mechanical Engineering. - Springer, Cham, 2019. - P. 1-9.

247. Chekanin, V.A. Packing Compaction Algorithm for Rectangular Cutting and Orthogonal Packing Problems / V.A. Chekanin, A.V. Chekanin // In: Proceedings of the 4th International Conference on Industrial Engineering. ICIE 2018. Lecture Notes in Mechanical Engineering. - Springer, Cham, 2019. - P. 1875-1883.

248. Chekanin, V.A. Software solution of optimization packing problems / V.A. Chekanin, A.V. Chekanin // Proceedings of the 2015 3rd International Symposium on Computer, Communication, Control and Automation (3CA 2015). Computer, Communication, Control and Automation. - 2015. - P. 156-160.

249. Chekanin, V.A. Solving the problem of decomposition of an orthogonal polyhedron of arbitrary dimension / V.A. Chekanin, A.V. Chekanin // Advances in Mechanical Engineering. Lecture Notes in Mechanical Engineering. - Springer, Cham, 2021. - P. 5259.

250. Chen, H. A Hybrid Algorithm for Strip Packing Problem with Rotation Constraint / H. Chen, F. Ye, Y.W. Si // MATEC Web of Conferences. - EDP Sciences, 2016. -Vol. 68. - P. 06001.

251. Cheng, Y. A new method of image compression using irreducible covers of maximal rectangles / Y. Cheng, S.S. Iyengara, R.L. Kashyap // IEEE transactions on software engineering. - 1988. - Vol. 14, № 5. - P. 651-658.

252. Chernov, N. Mathematical model and efficient algorithms for object packing problem / N. Chernov, Y. Stoyan, T. Romanova // Computational Geometry. - 2010. - Vol. 43, № 5. - P. 535-553.

253. Cherri, A.C. The one-dimensional cutting stock problem with usable leftovers - A survey / A.C. Cherri [et al.] // European Journal of Operational Research. - 2014. -Vol. 236, № 2. - P. 395-402.

254. Christofides, N. An algorithm for two-dimensional cutting problems / N. Christofides, C. Whitlock // Operations Research. - 1977. - Vol. 25, № 1. - P. 30-44.

255. Coffman Jr., E.G. Performance bounds for level-oriented two-dimensional packing algorithms / E.G. Coffman Jr. [et al.] // SIAM Journal on Computing. - 1980. - Vol. 9, № 4. - P. 808-826.

256. Coffman Jr., E.G. Variants of Classical One-Dimensional Bin Packing / E.G. Coffman Jr., J.Y.T. Leung, J. Csirik // In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Meta-Heuristics. - Francis and Taylor Books (CRC Press), 2007. - P. 33.

257. Coffman, E.G. Approximation algorithms for bin-packing-an updated survey / E.G. Coffman, M.R. Garey, D.S. Johnson // Algorithm design for computer system design. - Springer, Vienna, 1984. - P. 49-106.

258. Coté, J.F. Combinatorial Benders' cuts for the strip packing problem / J.F. Coté, M. Dell'Amico, M. Iori // Operations Research. - 2014. - Vol. 62, № 3. - P. 643-661.

259. Crainic, T.G. Extreme point-based heuristics for three-dimensional bin packing / T.G. Crainic, G. Perboli, R. Tadei // INFORMS, Journal on Computing. - 2008. -Vol. 20, № 3. - P. 368-384.

260. Crainic, T.G. Recent advances in multi-dimensional packing problems / T.G. Crainic, G. Perboli, R. Tadei // In: C. Volosencu (Ed.), New Technologies-Trends, Innovations and Research. - InTech, 2012. - P. 91-110.

261. Cruz-Matías, I. A new lossless orthogonal simplification method for 3D objects based on bounding structures / I. Cruz-Matías, D. Ayala // Graphical Models. - 2014. - Vol. 76, № 4. - P. 181-201.

262. Cruz-Matías, I. An efficient alternative to compute the genus of binary volume models / I. Cruz-Matías, D. Ayala // Proc. of the Int. Conf. GRAPP 2013. - SciTePress, 2013. -P. 18-26.

263. Cruz-Matías, I. Compact union of disjoint boxes: An efficient decomposition model for binary volumes / I. Cruz-Matías, D. Ayala // Computación y Sistemas. - 2017. - Vol. 21, № 2. - P. 275-292.

264. Csirik, J. Variants of Classical One Dimensional Bin Packing / J. Csirik, C. Imreh // Handbook of Approximation Algorithms and Metaheuristics. - Chapman and Hall/CRC, 2018. - P. 537-556.

265. Cui, Y.P. Sequential heuristic for the two-dimensional bin-packing problem / Y.P. Cui, Y. Cui, T. Tang // European Journal of Operational Research. - 2015. - Vol. 240, № 1. -P. 43-53.

266. Culberson, J.C. Covering Polygons is Hard / J.C. Culberson, R.A. Reckhow // Journal of Algorithms. - 1994. - Vol. 17, № 1. - P. 2-44.

267. Cutting and packing : Special issue / E. Bischoff, G. Wäscher, edit. // European Journal of Operational Research. - 1995. - Vol. 84, № 3. - P. 503-715.

268. Cutting stock: Geometric Resource Allocation (Special issue) / Y. Lirov, edit. // Mathematical and Computer modeling. - 1992. - Vol. 16, № 1.

269. De Korte, A.C.J. Random packing of digitized particles / A.C.J. De Korte, H.J.H. Brouwers // Powder technology. - 2013. - Vol. 233. - P. 319-324.

270. Demaine, E.D. Circle packing for origami design is hard / E.D. Demaine, S.P. Fekete, R.J. Lang // arXiv preprint arXiv:1008.1224. - 2010.

271. Dielissen, V.J. Rectangular partition is polynomial in two dimensions but NP-complete in three / V.J. Dielissen, A. Kaldewaij // Information Processing Letters. - 1991. - Vol. 38, № 1. - P. 1-6.

272. Durocher, S. Computing conforming partitions of orthogonal polygons with minimum stabbing number / S. Durocher, S. Mehrabi // Theoretical Computer Science. -2017. -Vol. 689. - P. 157-168.

273. Dyckhoff, H. A typology of cutting and packing problems / H. Dyckhoff // European Journal of Operation Research. - 1990. - Vol. 44. - P. 145-159.

274. Dyckhoff, H. Cutting and packing in production and distribution: A typology and bibliography / H. Dyckhoff, U. Finke. - Berlin: Springer Verlag, 1992.

275. Dyckhoff, H. Cutting and packing. / H. Dyckhoff, G. Scheithauer, J. Terno // In: Annotated Bibliographies in Combinatorial Optimization, M. Dell'Amico, F. Maffioli, S. Martello (eds.). - John Willey & Sons. - 1997. - P. 393-412.

276. Dyson, R.G. The cutting stock problem in the flat glass industry / R.G. Dyson, A.S. Gregory // Journal of the Operational Research Society. - 1974. - Vol. 25, № 1. -P. 41-53.

277. Egeblad, J. Heuristic approaches for the two-and three-dimensional knapsack packing problem / J. Egeblad, D. Pisinger // Computers & Operations Research. - 2009. -Vol. 36, № 4. - P. 1026-1049.

278. Eiben, A.E. Parameter tuning for configuring and analyzing evolutionary algorithms / A.E. Eiben, S.K. Smit // Swarm and Evolutionary Computation. - 2011. - Vol. 1, № 1. -P. 19-31.

279. El Baz, D. Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0-1 knapsack problem / D. El Baz, M. Elkihel // Journal of Parallel and Distributed Computing. - 2005. - Vol. 65, № 1. - P. 74-84.

280. Eppstein, D. Faster circle packing with application to nonobtuse triangulation / D. Eppstein // International Journal of Computational Geometry & Applications. -1997. - Vol. 7, № 05. - P. 485-491.

281. Erlebach, T. Approximating multiobjective knapsack problems / T. Erlebach, H. Kellerer, U. Pferschy // Management Science. - 2002. -Vol. 48, № 12. - P. 1603-1612.

282. Falkenauer, E. A hybrid grouping genetic algorithm for bin packing / E. Falkenauer // Journal of heuristics. - 1996. - Vol. 2, № 1. - P. 5-30.

283. Faroe, O. Guided local search for the three-dimensional bin packing problem / O. Faroe, D. Pisinger, M. Zachariasen // INFORMS, Journal on Computing. - 2003. -Vol. 15, № 3. - P. 267-283.

284. Feature Cluster: Cutting and Packing / J.F. Oliveira, G. Wäscher, edit. // European Journal of Operational Research. - 2007. - Vol. 183, № 3.

285. Fekete, S.P. A new exact algorithm for general orthogonal d-dimensional knapsack problems / S.P. Fekete, J. Schepers // European Symposium on Algorithms. - Springer, Berlin, Heidelberg, 1997. - P. 144-156.

286. Fekete, S.P. New class of lower bounds for bin packing problems / S.P. Fekete, J. Schepers // Integer Programming and Computational Optimization (IPCO 98). Lecture Notes in Computer Science. - 1998. - Vol. 1412. - P. 257-270.

287. Fernández, A. A parallel multi-objective algorithm for two-dimensional bin packing with rotations and load balancing / A. Fernández [et al.] // Expert Systems with Applications. - 2013. - Vol. 40, № 13. - P. 5169-5180.

288. Floderus, P. 3D rectangulations and geometric matrix multiplication / P. Floderus [et al.] // Algorithmica. - 2018. - Vol. 80, № 1. - P. 136-154.

289. Freeman, H. Determining the minimum-area encasing rectangle for an arbitrary closed curve / H. Freeman, R. Shapira // Communications of the ACM. - 1975. - Vol. 18, № 7. - P. 409-413.

290. Galiev, S.I. Linear models for the approximate solution of the problem of packing equal circles into a given domain / S.I. Galiev, M.S. Lisafina // European Journal of Operational Research. - 2013. - Vol. 230, № 3. - P. 505-514.

291. Gandibleux, X. An ant colony optimisation algorithm for the set packing problem / X. Gandibleux, X. Delorme, V. T'Kindt // International Workshop on Ant Colony Optimization and Swarm Intelligence. - Springer, Berlin, Heidelberg, 2004. - P. 49-60.

292. Gao, Y.Q. A multi-objective ant colony system algorithm for virtual machine placement in cloud computing / Y.Q. Gao [et al.] // Journal of Computer and System Sciences. -2013. - Vol. 79, № 8. - P. 1230-1242.

293. Garey, M. Computers intractability: a guide to the theory of NP-completeness / M. Garey, D. Johnson. - San Francisco: W.H. Freeman, 1979. - 338 p.

294. Gehring, H. A Genetic Algorithm for Solving the Container Loading Problem / H. Gehring, A. Bortfeldt // International transactions in operation research. - 1997. -Vol. 4, № 5-6. - P. 401-418.

295. Gilmore, P.C. A linear programming approach to the cutting stock problem. Part II / P.C. Gilmore, R.E. Gomory // Operations Research. - 1963. - Vol. 11, № 6. - P. 863888.

296. Gilmore, P.C. A linear Programming approach to the Cutting-Stock Problem / P.C. Gilmore, R.E. Gomory // Operations Research. - 1961. - Vol. 9, № 6. - P. 849-859.

297. Gilmore, P.C. Multistage cutting stock problems of two and more dimensions / P.C. Gilmore, R.E. Gomory // Operations Research. - 1965. - Vol. 13, № 1. - P. 94-120.

298. Gilmore, P.C. The theory and computation of knapsack functions / P.C. Gilmore, R.E. Gomory // Operations Research. - 1966. - Vol. 14, № 6. - P. 1045-1074.

299. Glover, F. Tabu search fundamentals and uses / F. Glover. - Boulder: Graduate School of Business, University of Colorado. - 1995. - P. 1-85.

300. Gomes, A.M. Solving irregular strip packing problems by hybridising simulated annealing and linear programming / A.M. Gomes, J.F. Oliveira // European Journal of Operational Research. - 2006. - Vol. 171, № 3. - P. 811-829.

301. Gomory, R.E. All-integer integer programming algorithm / R.E. Gomory // In: Industrial Scheduling (J.I. Muth and G.L. Thompson, eds.). - New York: McGraw-Hill, 1963, pp. 193-206.

302. Gongalves, J.F. A biased random key genetic algorithm for 2D and 3D bin packing problems / J.F. Gongalves, M.G.C. Resende // International Journal of Production Economics. - 2013. - Vol. 145, № 2. - P. 500-510.

303. Gongalves, J.F. A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem / J.F. Gongalves // European Journal of Operational Research. - 2007. -Vol. 183, № 3. - P. 1212-1229.

304. Gonzalez, T.F. Handbook of approximation algorithms and metaheuristics / T.F. Gonzalez. - Chapman and Hall/CRC, 2007. - 1432 p.

305. Grosso, A. Solving the problem of packing equal and unequal circles in a circular container / A. Grosso [et al.] // Journal of Global Optimization. - 2010. - Vol. 47, № 1. -P. 63-81.

306. Gyori, E. Generalized guarding and partitioning for rectilinear polygons / E. Gyori [et al.] // Computational Geometry. - 1996. - Vol. 6, № 1. - P. 21-44.

307. Haims, M.J. A multistage solution of the template-layout problem / M.J. Haims, H. Freeman // IEEE Transactions on Systems Science and Cybernetics. - 1970. - Vol. 6, № 2. - P. 145-151.

308. Harren, R. Approximating the orthogonal knapsack problem for hypercubes / R. Harren // International Colloquium on Automata, Languages, and Programming. - Springer, Berlin, Heidelberg, 2006. - P. 238-249.

309. He, K. An efficient deterministic heuristic for two-dimensional rectangular packing / K. He, W. Huang, Y. Jin // Computers & Operations Research. - 2012. - Vol. 39, № 7. -P.1355-1363.

310. He, K. Heuristics for two-dimensional strip packing problem with 90 rotations / K. He, Y. Jin, W. Huang // Expert Systems with Applications. - 2013. - Vol. 40, № 14. -P. 5542-5550.

311. Hifi, M. A best-first branch-and-bound algorithm for orthogonal rectangular packing problems / M. Hifi, R. Ouafi // International Transactions in Operational Research. -1998. - Vol. 5, № 5. - P. 345-356.

312. Hifi, M. A local search-based method for sphere packing problems / M. Hifi, L. Yousef // European Journal of Operational Research. - 2019. - Vol. 274, № 2. - P. 482-500.

313. Hopper, E. An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem / E. Hopper, B.C.H. Turton // European Journal of Operational Research. - 2001. - Vol. 128, № 1. - P. 34-57.

314. Hopper, E. Application of genetic algorithms to packing problems—a review / E. Hopper, B.C.H. Turton // Soft Computing in Engineering Design and Manufacturing. - Springer, London, 1998. - P. 279-288.

315. Hoto, R. The one dimensional Compartmentalised Knapsack Problem: A case study / R. Hoto, M. Arenales, N. Maculan // European Journal of Operational Research. -2007. - Vol. 183, № 3. - P. 1183-1195.

316. Hu, H. Solving a new 3d bin packing problem with deep reinforcement learning method / H. Hu [et al.] // arXiv preprint arXiv:1708.05930. - 2017.

317. Huang,W. A new heuristic algorithm for rectangle packing / W. Huang, D. Chen, R. Xu // Computers & Operations Research. - 2007. - Vol. 34, № 11. - P. 3270-3280.

318. Introduction to Cutting and Packing Optimization: Problems, Modeling Approaches, Solution Methods / G. Scheithauer, edit. - Berlin: Springer, 2017. - Vol. 263.

319. Johnson, D.S. A Brief History of NP-Completeness, 1954-2012 / D.S. Johnson // Documenta Mathematica. - 2012. - Extra Volume ISMP. - P. 359-376.

320. Johnson, D.S. Worst-case performance bounds for simple one-dimensional packing algorithms / D.S. Johnson [et al.] // SIAM Journal on computing. - 1974. - Vol. 3, № 4. -P. 299-325.

321. Junqueira, L. Three-dimensional container loading models with cargo stability and load bearing constraints / L. Junqueira, R. Morabito, D.S. Yamashita // Computers & Operations Research. - 2012. - Vol. 39, № 1. - P. 74-85.

322. Kahrs, L.A. Visual servoing of a laser ablation based cochleostomy / L.A. Kahrs [et al.] // In: Medical Imaging 2008: Visualization, Image-Guided Procedures, and Modeling. -International Society for Optics and Photonics. - 2008. - Vol. 6918. - P. 69182C.

323. Kaluzny, B.L. Optimal aircraft load balancing / B.L. Kaluzny, R.H.A.D. Shaw // International Transactions in Operational Research. - 2009. - Vol. 16, № 6. - P. 767-787.

324. Kampas, F.J. Optimized ellipse packings in regular polygons / F.J. Kampas, I. Castillo, J.D. Pinter // Optimization Letters. - 2019. - Vol. 13, № 7. - P. 1583-1613.

325. Kasahara, M. Construction of New Classes of Knapsack Type Public Key Cryptosystem Using Uniform Secret Sequence, K (II) LnPKC, Constructed Based on Maximum Length Code / M. Kasahara // IACR Cryptology ePrint Archive. - 2012. - Vol. 2012. -P. 344.

326. Kellerer, H. Multidimensional knapsack problem / H. Kellerer, U. Pferschy, D. Pisinger // Knapsack problems. - Springer, Berlin, Heidelberg, 2004. - P. 235-283.

327. Kenmochi, M. Exact algorithms for the two-dimensional strip packing problem with and without rotations / M. Kenmochi [et al.] // European Journal of Operational Research. -2009. - Vol. 198, № 1. - P. 73-83.

328. Kenyon, C. A near-optimal solution to a two-dimensional cutting stock problem / C. Kenyon, E. Remila // Mathematics of Operations Research. - 2000. - Vol. 25, № 4. -P. 645-656.

329. Kierkosz, I. A hybrid evolutionary algorithm for the two-dimensional packing problem / I. Kierkosz, M. Luczak // Central European Journal of Operations Research. - 2014. -Vol. 22, № 4. - P. 729-753.

330. Knapsack, Packing and Cutting, Part I: One Dimensional Knapsack Problem (Special issue) / S. Martello, edit. // INFOR. - 1994. - Vol. 32, № 3.

331. Knapsack, Packing and Cutting, Part II: Multidimensional Knapsack and Cutting Stock Problems (Special issue) / S. Martello, edit. // INFOR. - 1994. - Vol. 32, № 4.

332. Krause, K.L. Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems / K.L. Krause, V.Y. Shen, H.D. Schwetman // Journal of the ACM (JACM). - 1975. - Vol. 22, № 4. - P. 522-550.

333. Kupriyashin, M.A. Computational load balancing algorithm for parallel knapsack packing tree traversal / M.A. Kupriyashin, G.I. Borzunov // Procedia Computer Science. - 2016. - Vol. 88. - P. 330-335.

334. Lai, K.K. Developing a simulated annealing algorithm for the cutting stock problem / K.K. Lai, J.W.M. Chan // Computers & industrial engineering. - 1997. - Vol. 32, № 1. -P. 115-127.

335. Lei, B. Integrated Optimization of Mixed Cargo Packing and Cargo Location Assignment in Automated Storage and Retrieval Systems / B. Lei, Z. Jiang, H. Mu // Discrete Dynamics in Nature and Society. - 2019. - Vol. 2019. - Article ID 9072847. - 16 p.

336. León, C. 2D cutting stock problem: a new parallel algorithm and bounds / C. León [et al.] // European Conference on Parallel Processing. - Springer, Berlin, Heidelberg. -2007. - P. 795-804.

337. Leung, S.C. A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem / S.C. Leung [et al.] // Computers & Operations Research. - 2012. - Vol. 39, № 1. - P. 64-73.

338. Leung, S.C.H. A fast layer-based heuristic for non-guillotine strip packing / S.C.H. Leung, D. Zhang // Expert Systems with Applications. - 2011. - Vol. 38, № 10. -P. 13032-13042.

339. Leung, T.W. Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem / T.W. Leung, C.K. Chan, M.D. Troutt // European Journal of Operational Research. - 2003. - Vol. 145, № 3. -P. 530-542.

340. Levine, J. Ant colony optimization and local search for bin packing and cutting stock problems / J. Levine, F. Ducatelle // Journal of the Operational Research society. -2004. - Vol. 55, № 7. - P. 705-716.

341. Liu, D. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles / D. Liu, H. Teng // European Journal of Operational Research. - 1999. -Vol. 112, № 2. - P. 413-420.

342. Lodi, A. Heuristic algorithms for the three-dimensional bin packing problem / A. Lodi, S. Martello, D. Vigo // European Journal of Operational Research. - 2002. - Vol. 141, № 2. - P. 410-420.

343. Lodi, A. Models and bounds for two-dimensional level packing problems / A. Lodi, S. Martello, D. Vigo // Journal of Combinatorial Optimization. - 2004. - Vol. 8, № 3. -P. 363-379.

344. Lodi, A. Recent advances on two-dimensional bin packing problems / A. Lodi, S. Martello, D. Vigo // Discrete Applied Mathematics. - 2002. - Vol. 123, № 1-3. -P. 379-396.

345. Lodi, A. Two-dimensional packing problems: A survey / A. Lodi, S. Martello, M. Monaci // European Journal of Operational Research. - 2002. - Vol. 141, № 2. -P. 241-252.

346. Lu, H.C. An efficient genetic algorithm with a corner space algorithm for a cutting stock problem in the TFT-LCD industry / H.C. Lu, Y.H. Huang // European Journal of Operational Research. - 2015. - Vol. 246, № 1. - P. 51-65.

347. Lu, H.C. An integrated algorithm for cutting stock problems in the thin-film transistor liquid crystal display industry / H.C. Lu, Y.H. Huang, K.A. Tseng // Computers & Industrial Engineering. - 2013. - Vol. 64, № 4. - P. 1084-1092.

348. Ma, Y. Packing irregular objects in 3D space via hybrid optimization / Y. Ma [et el.] // Computer Graphics Forum. - 2018. - Vol. 37, № 5. - P. 49-59.

349. Martello, S. An exact approach to the strip-packing problem / S. Martello, M. Monaci, D. Vigo // INFORMS Journal on Computing. - 2003. - Vol. 15, № 3. - P. 310-319.

350. Martello, S. Exact solution of the two-dimensional finite bin packing problem / S. Martello, D. Vigo // Management Science. - 1998. - Vol. 44. - P. 388-399.

351. Martello, S. Knapsack Problems - Algorithms and Computer Implementations / S. Martello, P. Toth. - Chichester: John Wiley & Sons, 1990.

352. Martello, S. The three-dimensional bin packing problem / S. Martello, D. Pisinger, D. Vigo // Operations Research. - 2000. - Vol. 48, № 2. - P. 256-267.

353. Martínez, J.M. Packing optimization for automated generation of complex system's initial configurations for molecular dynamics and docking / J.M. Martínez, L. Martínez // Journal of Computational Chemistry. - 2003. - Vol. 24, № 7. - P. 819-825.

354. Martínez, L. Packmol: a package for building initial configurations for molecular dynamics simulations / L. Martínez [et al.] // Journal of Computational Chemistry. -2009. - Vol. 30, № 13. - P. 2157-2164.

355. Martinez-Sykora, A. Matheuristics for the irregular bin packing problem with free rotations / A. Martinez-Sykora [et al.] // European Journal of Operational Research. -2017. - Vol. 258, № 2. - P. 440-455.

356. Masek, W.J. Some NP-Complete Set Covering Problems: Manuscript / W.J. Masek. -Cambridge: MIT, 1979.

357. Milenkovic, V.J. Translational polygon containment and minimal enclosure using mathematical programming / V.J. Milenkovic, K. Daniels // International Transactions in Operational Research. - 1999. - Vol. 6, № 5. - P. 525-554.

358. Miyazawa, F.K. An algorithm for the three-dimensional packing problem with asymptotic performance analysis / F.K. Miyazawa, Y. Wakabayashi // Algorithmica. -1997. - Vol. 18, № 1. - P. 122-144.

359. Mladenovic, N. Reformulation descent applied to circle packing problems / N. Mladenovic, F. Plastria, D. Urosevic // Computers & Operations Research. - 2005. -Vol. 32, № 9. - P. 2419-2434.

360. Moffitt, M.D. Constraint-driven floorplan repair / M.D. Moffitt [et al.] // In: Proceedings of the 43rd annual Design Automation Conference. - ACM, 2006. - P. 1103-1108.

361. Moon, I. Container packing problem with balance constraints / I. Moon, T.V.L. Nguyen // OR spectrum. - 2014. - Vol. 36, № 4. - P. 837-878.

362. Morabito, R. A simple and effective recursive procedure for the manufacturer's pallet loading problem / R. Morabito, S. Morales // Journal of the Operational research Society. - 1998. - Vol. 49. - P. 819-828.

363. Moura, A. A two-stage packing problem procedure / A. Moura, A. Bortfeldt // International Transactions in Operational Research. - 2017. - Vol. 24, № 1-2. - P. 43-58.

364. Mukhacheva, E.A. Linear one-dimensional cutting-packing problems: numerical experiments with the sequential value correction method (SVC) and a modified branch-and-bound method (MBB) / E.A. Mukhacheva [et al.] // Pesquisa Operacional. - 2000. -Vol. 20, № 2. - P. 153-168.

365. Murata, H. VLSI module placement based on rectangle-packing by the sequence-pair / H. Murata [et al.] // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 1996. - Vol. 15, № 12. - P. 1518-1524.

366. Nahar, S. Fast algorithm for polygon decomposition / S. Nahar, S. Sahni // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 1988. -Vol. 7, № 4. - P. 473-483.

367. Oliveira, O. Resources for Two-Dimensional (and Three-Dimensional) Cutting and Packing Solution Methods Research / O. Oliveira, D. Gamboa, E. Silva // In: Proceedings

of the 16th International Conference on Applied Computing 2019. - IADIS Press. -2019. - Vol. 53. - P. 131-138.

368. Oliveira, О. Библиотека тестовых задач двухмерной и трёхмерной упаковки [Электронный ресурс] / О. Oliveira. - Режим доступа: https://github.com/Oscar-Oliveira/OR-Datasets/tree/master/Cutting-and-Packing (дата обращения: 12.04.2021).

369. Oliveira, О. Тестовые задачи прямоугольной упаковки на полубесконечную полосу (E. Hopper и B.C.H. Turton) [Электронный ресурс] / О. Oliveira. - Режим доступа: https://github.com/Oscar-Oliveira/OR-Datasets/tree/master/Cutting-and-Packing/2D/ Datasets/HT2001 a (дата обращения: 12.04.2021).

370. Oliveira, О. Тестовые задачи прямоугольной упаковки на полубесконечную полосу (E. Pinto и J.F. Oliveira) [Электронный ресурс] / О. Oliveira. - Режим доступа: https://github.com/Oscar-Oliveira/OR-Datasets/tree/master/Cutting-and-Packing/2D/ Datasets/PO (дата обращения: 12.04.2021).

371. Oliveira, О. Тестовые задачи прямоугольной упаковки на полубесконечную полосу Beng [Электронный ресурс] / О. Oliveira. - Режим доступа: https://github.com/ Oscar-Oliveira/OR-Datasets/tree/master/Cutting-and-Packing/2D/Datasets/BENG (дата обращения: 12.04.2021).