Статья

Название статьи ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАЦИОНАЛЬНОГО РАСКРОЯ РУЛОННОГО МАТЕРИАЛА
Автор В.Н. Балабанов, Ю.А. Скобцов
Рубрика РАЗДЕЛ II. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ И САПР
Месяц, год 01, 2014
Индекс УДК 519.854.2
DOI
Аннотация Представлен новый метаэвристический метод решения многокритериальной задачи рационального раскроя рулонных материалов, выполняемого на линиях продольной резки. Математическая модель рассматриваемой задачи комбинаторной оптимизации разработана на основе существующей модели целочисленного линейного программирования. Сформулированы частные критерии эффективности использования материала и технологичности искомого плана раскроя. Предложенный метод основан на оптимизационном аппарате эволюционных вычислений и адаптивной генерации раскройных карт. При выборе способа представления решений в эволюционном алгоритме учтены комбинаторные свойства исходной задачи. Отличительной особенностью предложенного эволюционного метода является использование составного пятикомпонентного оператора мутации. При разработке целевой функции выполнено сведение исходной многокритериальной задачи к задаче скалярной оптимизации с заменой векторного критерия линейной сверткой частных критериев. Для генерации раскройных карт приспособлен существующий рандомизированный метод решения задачи ранцевого типа. Подготовлены тестовые задачи и поставлен ряд вычислительных экспериментов. Полученные результаты подтверждают состоятельность избранного подхода к построению эволюционного алгоритма, который может быть адаптирован для решения других задач рационального раскроя в схожей постановке.

Скачать в PDF

Ключевые слова Рациональный раскрой; рулонные материалы; многокритериальная модель; комбинаторная оптимизация; эволюционный алгоритм.
Библиографический список 1. Канторович Л.В. Математические методы в организации и планировании производства. – Л.: Изд-во ЛГУ, 1939. – 68 с.
2. Скобцов Ю.А., Балабанов В.Н. К вопросу о применении метаэвристик в решении задач рационального раскроя и упаковки // Вестник Хмельницкого национального университета. – 2008. – Т. 1, № 4. – С. 205-217.
3. Haessler R.W. Selection and design of heuristic procedures for solving roll trim problems // Management Science. – 1988. – Vol. 34, № 12. – P. 1460-1471.
4. Vahrenkamp R. Random search in the one-dimensional cutting stock problem // European Journal of Operational Research. – 1996. – Vol. 95, № 1. – P. 191-200.
5. Скобцов Ю.А. Основы эволюционных вычислений: Учебное пособие. – Донецк: ДонНТУ, 2008. – 326 с.
6. Michalewicz Z. Genetic algorithms + data structures = evolution programs. – 3rd ed. – Berlin [etc.]: Springer-Verlag, 1998. – 387 p.
7. Deb K. An efficient constraint handling method for genetic algorithms // Computer Methods in Applied Mechanics and Engineering. – 2000. – Vol. 186, № 2–4. – P. 311-338.
8. Martello S., Toth P. Knapsack problems: algorithms and computer implementations. – Chichester [etc.]: John Wiley & Sons Ltd., 1990. – 318 p.
9. GitHub: EA-based solver for 1.5D MSSCSP [Electronic resource]. – 2013. – [Cited 2013, 1 June]. – Available from: https://github.com/akavrt/csp.
10. Mladenovic N., Hansen P. Variable neighborhood search // Computers & Operations Research. – 1997. – Vol. 24, № 11. – P. 1097-1100.

Comments are closed.