Андрианова А.А., Мухтарова Т.М., Фазылов В.Р.
Казанский Приволжский федеральный университет, г. Казань, 420008, Россия
Аннотация
В статье для решения задачи прямоугольной ортогональной упаковки предложено расширение понятия функции гильотинного размещения, которое представляет собой функцию, ставящую в соответствие ширине листа тройку значений. Помимо стандартного для функции гильотинного размещения результата – минимальной длины листа заданной ширины, достаточного для размещения гильотинным образом заданного набора прямоугольников, используется два дополнительных значения. Они представляют собой информацию о способе раскроя этого листа, с помощью которой можно однозначно построить карты гильотинного раскроя листа и гильотинного размещения набора прямоугольников на нем. Этой информацией являются характеристики первого разреза листа, а также соответствующее разрезу разбиение набора прямоугольников на два поднабора, которое однозначно определяется номером одного из поднаборов разбиения.
Описание первого разреза моделируется одной числовой величиной, которая отражает как размер отступа от левого нижнего угла листа, так и ориентацию разреза – вдоль или поперек листа требуется производить разрез. Показано, что этой информации достаточно для восстановления карты гильотинного раскроя листа и карты гильотинного размещения набора прямоугольников.
Для определения дополнительной информации о первом разрезе и вычисления расширения функции гильотинного размещения предложены модификации алгоритмов получения суммы двух ступенчатых полунепрерывных справа монотонно невозрастающих функций с конечным числом ступеней, а также минимума двух таких функций. Предложен также алгоритм формирования карт гильотинного раскроя и гильотинного размещения прямоугольников на листе, использующий вычисленные расширения функций гильотинного размещения для всех поднаборов требуемого набора прямоугольников.
Ключевые слова: прямоугольная ортогональная упаковка, гильотинный раскрой, расширение функции гильотинного размещения
Литература
1. Канторович Л.В., Залгаллер В.А. Расчет рационального раскроя промышленных материалов. – Л.: Лениздат, 1951. – 198 с.
2. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. – Новосибирск: Наука, 1971. – 198 с.
3. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ – Новосибирск: Наука, 1987. – 274 с.
4. Lodi A., Martello S., Monaci M. Two-dimensional packing problems: A survey // Eur. J. Oper. Res. – 2002. – V. 141, No 2. – P. 241–252. – doi: 10.1016/S0377-2217(02)00123-6.
5. Zhang D.F., Kang Y., Deng S. A new heuristic recursive algorithm for the strip rectangular packing problem // Comput. Operat. Res. – 2006. – V. 33, No 8. – P. 2209–2217. – doi: 10.1016/j.cor.2005.01.009.
6. Chen M., Huang W. A two-level search algorithm for 2D rectangular packing problem // Comput. Ind. Eng. – 2007. – V. 53, No 1. – P. 123–136. – doi: 0.1016/j.cie.2007.04.007.
7. Мухачева Э.А, Валеева А.Ф., Картак В.М., Мухачева А.С. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур // Информ. технологии. Приложение. – 2004. – № 5. – 31 c.
8. Валеева А.Ф. Конструктивная эвристика для задачи прямоугольной упаковки // Вестн. Башкир. ун-та. – 2006. – № 3. – С. 5–6.
9. Романовский И.В. Решение задачи гильотинного раскроя методом переработки списка состояний // Кибернетика. – 1969. – № 1. – С. 102–103.
10. Грибов А.Б. Алгоритм решения задачи плоского раскроя // Кибернетика. – 1973. – № 6. – С. 110–115.
11. Романовский И.В. Алгоритмы решения экстремальных задач. – М.: Наука, 1977. – 352 с.
12. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. – Новосибирск: Наука, 1987. – 274 с.
13. Лернер Э.Ю., Фазылов В.Р. Функция гильотинного размещения // Исслед. по приклад. матем. – Казань: Унипресс, 1999. – Вып. 21. – С. 187–196.
14. Андрианова А.А., Мухтарова Т.М., Фазылов В.Р. Модели негильотинного размещения набора прямоугольных деталей на листе и полуполосе // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2013. – Т. 155, кн. 2. – С. 5–18.
15. Андрианова А.А., Мухтарова Т.М., Фазылов В.Р. Модель задачи негильотинного размещения набора прямоугольников на полуполосе // Материалы. XVII Междунар. конф. <<Проблемы теоретической кибернетики>>. – Казань: Отечество, 2014. – С. 23–26.
16. Андрианова А.А., Мухтарова Т.М., Фазылов В.Р. Модель компактного размещения набора прямоугольников на листе // Тез. докл. XVI Байкальской междунар. школы-семинара <<Методы оптимизации и их приложения>>. – Иркутск: ИСЭМ СО РАН, 2014. – C. 33.
17. Лернер Э.Ю., Фазылов В.Р. Квазиобратные функции и их свойства // Исслед. по приклад. матем. – Казань: Казан. матем.о-во, 1997. – Вып. 22. – С. 63–74.
18. Хамби Э. Программирование таблиц решений. – М.: Мир, 1976. – 86 с.
Поступила в редакцию
11.04.16
Андрианова Анастасия Александровна, кандидат физико-математических наук, доцент кафедры системного анализа и информационных технологий
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: Anastasiya.Andrianova@kpfu.ru
Мухтарова Татьяна Маратовна, старший преподаватель кафедры анализа данных и исследования операций
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: Tatyana.Moukhtarova@kpfu.ru
Фазылов Валерий Рауфович, доктор физико-математических наук, профессор кафедры информационных технологий поиска
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: vfazylov@gmail.com
Для цитирования: Андрианова А.А., Мухтарова Т.М., Фазылов В.Р. Формирование карты гильотинного раскроя листа по функциям гильотинного размещения // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2017. – Т. 159, кн. 2. – С. 161–173.
For citation: Andrianova A.A., Mukhtarova T.M., Fazylov V.R. Formation of the guillotine cutting card of a sheet by the guillotine layout functions. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2017, vol. 159, no. 2, pp. 161–173. (In Russian)
Контент доступен под лицензией Creative Commons Attribution 4.0 License.