Аннотация
В статье представлено описание и решение задачи компоновки нестандартных съемов тамбуров, связанной с проблемой обрывов бумажного полотна при работе бумагоделательной машины в течение рабочего производственного процесса, за счет чего возникают так называемые нестандартные тамбуры. Такие случаи не единичны и требуют применения специальных методов для оптимизации производственного процесса в условиях операции склейки съемов тамбуров. Задача заключается в склейке нестандартных съемов и их раскрое в условиях максимизации выхода полезной продукции. При решении поставленной задачи учитывались многочисленные параметры заказов и съемов тамбуров, а также технологические аспекты производства бумаги. Автором статьи представлена математическая модель задачи, которая отражает ограничения и целевую функцию и описывается задачей условной нелинейной оптимизации из класса задачи линейного раскроя на множестве перестановок. Для ее решения применяется хорошо известный метод декомпозиции задачи с целью сведения сложной задачи к решению более простых подзадач. Для решения оптимизационной подзадачи на множестве перестановок применяется генетический метод из класса эволюционных алгоритмов на основе введенной специальной функции расстояния между перестановками. Для решения подзадачи раскроя используется принцип динамического программирования. В статье приведено доказательство правильности работы представленного алгоритма, указана его асимптотическая сложность и практическая оценка точности. В заключении приводятся итоги анализа представленного алгоритма и возможность применения его для решения поставленной задачи.
Ключевые слова: склейка рулонов, декомпозиция задачи, линейный раскрой, динамическое программирование, оптимизация на множестве перестановок, генетический алгоритм, оценка точности алгоритма, сложность алгоритма
Список литературы
1. Урбан А.Р., Кузнецов В.А. Математические модели и методы учета сроков продукции в задаче раскроя тамбуров бумагоделательных машин // Ученые записки Петрозаводского государственного университета. Серия: Естественные и технические науки. – 2014. – № 4 (141). – С. 112–115.
2. Урбан А.Р. Решение задачи поиска оптимального столбца в условиях оптимального раскроя бумажного полотна // Вестник Санкт-Петербургского университета. Серия 10, Прикладная математика. Информатика. Процессы управления. – 2015. – Вып. 1. – С. 100–106.
3. Кузнецов В.А. Математические модели, методы и программные комплексы оптимального раскроя и комплектовки с учетом дополнительных ограничений: автореф. дис. … д-ра техн. наук: 05.13.18 / Петрозаводский государственный университет. – Петрозаводск, 2004. – 30 с.
4. Кузнецов В.А. Задачи раскроя в целлюлозно-бумажной промышленности. – СПб.: Изд-во СПбЛТА, 2000. – 132 с.
5. Dapcevic D., Borthwick K. Paper machine reel optimization – analyses and a case study // Annual Pulp and Paper Industry Technical Conference, 21–25 June 1999. – Seattle, Washington, USA, 1999. – P. 1–10. – doi: 10.1109/PAPCON.1999.779339.
6. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации: учебное пособие. – Н. Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2006. – 136 с.
7. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: учебное пособие. – 2-е изд. – М.: Физматлит, 2006. – 320 c.
8. Goldberg D.E. Genetic algorithms in search, optimization, and machine learning. – Reading, Massachusetts: Addison-Wesley Professional, 1989. – 432 p.
9. Булгаков И.В., Неймарк Е.А. Решение задачи коммивояжера с использованием генетических алгоритмов // Вестник Нижегородского университета им. Н.И. Лобачевского. – 1998. – Вып. 2 (19). – С. 186–192.
10. Ильев В.П. Задачи комбинаторной оптимизации на наследственных системах // Российская конференция «Дискретная оптимизация и исследование операций» DOOR'07: материалы конференции, Владивосток, 7–14 сентября 2007 г. – Новосибирск: Изд-во Ин-та математики, 2007. – С. 41–45.
11. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования: пер. с англ. – М.: Мир, 1965. – 368 с.
12. Беллман Р. Динамическое программирование: пер. с англ. – М.: Мир, 1960. – 424 с.
13. Xедли Д. Нелинейное и динамическое программирование: пер. с англ. – М.: Мир, 1967. – 509 с.
14. Архипов И.В. Математические модели и опыт реализации системы планирования раскроя лесосырья // Вестник Санкт-Петербургского университета. Серия 10, Прикладная математика. Информатика. Процессы управления. – 2014. – Вып. 3. – С. 82–92.
15. Архипов И.В. Математические модели раскроя лесосырья в задачах планирования и управления лесопильным производством // Ученые записки Петрозаводского государственного университета. Серия: Естественные и технические науки. – 2013. – Вып. 8 (137). – С 93–97.
16. Архипов И.В., Кузнецов В.А. Расчет объема опилок при раскрое бревна // Известия высших учебных заведений. Лесной журнал. – 2015. – № 2. – С. 7–16.
17. Грин Д., Кнут Д. Математические методы анализа алгоритмов: пер. с англ. – М.: Мир, 1987. – 120 с.
18. Сэвидж Д.Э. Сложность вычислений: пер. с англ. – М.: Факториал, 1998. – 368 с.
19. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ: пер. с англ. – М.: МЦМНО, 2000. – 955 с.
20. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: пер. с англ. – М.: Мир, 1998. – 703 с.
