Сагун А.В.,

Черкаський державний технологічний університет, аспірант

ХАРАКТЕРИСТИКА АЛГОРИТМУ БЕЗПЕРЕРВНОЇ РЕЛАКСАЦІЇ ЗАДАЧІ ЗАЛИШКУ ЛІНІЙНОГО РОЗКРОЮ

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

Постановка задачі. Евристична комбінація безперервної релаксації nf точного розв’язку задачі залишку, що відома для задач з одним типом лінійного матеріалу [1, 2].

Позначимо найкращий відомий розв’язок як початкову ЛП - границю та максимальну ціну прутка матеріалу. Розрив оптимальності по відношенню до складає в середньому 30 %.

В даному методі, як показує графічний аналіз продуктивності, цей розрив вже на початкових ітераціях складає у гіршому випадку 12 %, а через 100 секунд розрив по відношенню до не перевищує 2 %, де - найкраща нижня границя, яка посилена перерізами [1]. Аналогічний висновок був зроблений по відношенню з генетичним груповим алгоритмом, який реалізується на ЗАТ Кіровоградський завод «Дозуючих автоматів».

Ціль експерименту - порівняння генетичного алгоритму (GGA) та методу січних площин (СРА). Для проведення експерименту використовувався генератор BPPGEN [4].

На протязі експерименту для кожного класу генерувалось по 100 прикладів. Обчислення проводились для наступних параметрів: довжини стрижнів ; кількість предметів ; нижнє обмеження довжини предметів ; верхнє обмеження довжини предметів: . Кількість стрижнів кожного типу є не обмеженоюЯк видно з таблиці GGA достатньо серйозно поступається методу січних площин на класах з розмірами заготовок від 0,25 до 0,5 та 0,25 до 0,6 розміру максимального стрижня. Відомо, що дані класи є складними для евристичних алгоритмів, якими є GGA. Перевага GGA та CPA, як для будь-якої метаевристики над точним алгоритмом, проявляється при дефіциті часу, результати яких з генетичними алгоритмом поступаються методу січних.

Більш відомий точний метод для одномірної задачі розкрою – це branch-and-price [3]. В кожному вузлі дерева розв’язку до безперервної релаксації додається обмеження гілок, для здійснення яких необхідна умова:

або , (1)

де - округлення до нижніх значень в безперервному розв’язку цього вузла, а - деяка множина індексів, які зачасту створють тільки один елемент. Іноді до формулювання безперервної релаксації добавляються ще деякі прості відсікання. Поки ще не відомі результати застосування branch-and-price до задачі з деякими типами прутка. При цьому порівняння виконуються тільки для випадку .

Реалізація симплекс-методу декілька відрізняється від інших досліджень, які застосовують комерційне програмне забезпечення для розв’язку задач лінійного програмування, за допомогою якого зручно зберігати всі стовпці та розглядати їх як матрицю обмежень (restricted master problem). Це веде до зменшення кількості генеруючих стовпців.

Наведене порівняння з найбільш ефективною релаксацією branch-and-price, розбіжності яких у обчислених потужностях приходиться вирівнювати за допомогою множення часу на відповідний коефіцієнт.

Детально: для майже нічого не потрібно було робити після початкової релаксації в обох методах; для , метод відсікань приблизно в 3 рази повільніше; для клас зайняв такий же проміжок часу, як і в інших класах відсікання не знадобилися через ефективну евристики для розв’язку задачі залишку SVC без опції розширення задачі залишку, яка знаходила оптимум після початкової релаксації. Час за ітераціями з перерізами був меншим 20 секунд для в цій програмі, а 1 приклад не був розв’язаний за 15 хвилин, але в найбільше часу було витрачено в межах 5 хвилин. Всі приклади в [2] були розв’язані тільки спеціальною реалізацією алгоритму, значення параметрів кожні 5 хвилин змінювалися і відлік починався спочатку.

Для кожного класу прикладів (тобто для кожної комбінації ) були розв’язані 100 прикладів. Максимальний час після початкової релаксації були 60 секунд ().

Висновки. Виконавши порівняльний аналіз різних методів оцінки моделей розкрою, що різняться як вхідними параметрами, так і реалізацією моделей можна зробити висновок, що модель на основі алгоритму Гоморі з використанням січних площин є найбільш оптимальною для реалізації в умовах практичного виробництва.

Література

1. Белов Г.Н. Псевдослучайное генерирование тестовых задач раскроя-упаковки: методы и последовательности эксперимента. /Принятие решений в условиях неопределённости: - Сборник научных трудов. - Уфа.: УГАТУ, 1998. С.23-27.

2. E. Falkenauer. A hybrid grouping genetic algo rithm for bin packing. Journal of heuristics. 2 (1). 1998. – P. 5 – 13.

3. G. Scheithauer and J. Terno. A branch-and-bound algorithm for solving one-dimensional cutting stock problems exactly. Applicationes Mathematicae, 23 (2), 1995. – P. 151 – 167.

4. Holthaus. Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths. Eur. Jour. of Op. Res. 141 (2002) – P. 295 – 312.