Встала вот передо мной такая задачка:
раскрой прямоугольных листов на прямоугольные же детали.
Сколько не гуглил, так и не удалось раскопать сколь-нибудь подробное описание алгоритма. Все сплошь рекламы программных продуктов с, якобы, самым оптимальным и экономичным алгоритмом.
По форуму проискал, подобного не нашел.
Паре разработчиков даже писал, они отказались выдавать алгоритм.
Все вышеописанное было проделано после того, как написал свой вариант, который не совсем устроил заказчика.
Слышал я про формальные методы решения данной задачи, однако они идут лесом из-за ограничений, накладываемых оборудованием.
Считаю, что проделал достаточно предварительной работы, чтобы воззвать к коллективному разуму.
(Кстати, это первый раз, когда я прошу публичной помощи).
Итак, что хотелось бы услышать? То, сталкивался ли кто-либо уже с подобной проблемой? Если да, то опишу подробнее то, что уже работает, и то, что хочет отдел конструкторов
Здравствуйте, azrael82, Вы писали:
A>Встала вот передо мной такая задачка: A>раскрой прямоугольных листов на прямоугольные же детали.
А расскажи задачу. Есть прямоугольные листы и прямоугольные же детали, так. Не ориентированные, так? Что фиксировано — количество листов или количество деталей? А оптимизировать нужно использование материала? Есть ли критерий годности? Типа — 75% или более, меньше — алгоритм полохой? Какие детали, одинаковые? Если неодинаковые, то как неодинаковые, как распределены?
A>Сколько не гуглил, так и не удалось раскопать сколь-нибудь подробное описание алгоритма. Все сплошь рекламы программных продуктов с, якобы, самым оптимальным и экономичным алгоритмом.
Кул. А по "целочисленная оптимизация", "дискретная оптимизация" искал? В библиотечку сходить тоже.
A> Итак, что хотелось бы услышать? То, сталкивался ли кто-либо уже с подобной проблемой? Если да, то опишу подробнее то, что уже работает, и то, что хочет отдел конструкторов
Здравствуйте, azrael82, Вы писали:
A>Сколько не гуглил, так и не удалось раскопать сколь-нибудь подробное описание алгоритма. Все сплошь рекламы программных продуктов с, якобы, самым оптимальным и экономичным алгоритмом.
Здравствуйте, George Seryakov, Вы писали:
GS>А расскажи задачу. Есть прямоугольные листы и прямоугольные же детали, так. Не ориентированные, так? Что фиксировано — количество листов или количество деталей? А оптимизировать нужно использование материала? Есть ли критерий годности? Типа — 75% или более, меньше — алгоритм полохой? Какие детали, одинаковые? Если неодинаковые, то как неодинаковые, как распределены?
Введение в задачу: есть фирма, занимающаяся изготовлением софта для проектирования и дизайна мебели.
Есть первая версия программы раскроя, которая вроде бы работает, но она делалась энное количество лет назад,
и делает не все. Мне поручено все это дело переписать "с нуля". Потому что алгоритм той версии сделан то ли на Фортране,
то ли еще на чем-то, исходников нет.
Задача: написать программу, достаточно эффективно раскладыващую детали на листах. Листы могут быть как сплошные (ДВП-18 Белый, скажем),
так и с текстурой (Ольха). Соответственно, детали бывают такие, что их все равно, как резать, так и требующие определенного
ориентирования относительно направления текстуры. Количество деталей, естесственно, фиксировано, определяется заказом.
Количество листов, по идее, должно ограничиваться наличием на складе, но, как показывает практика, туда забивает астрономические
цифры. Так что пока можно считать, что ограничения по листам нет. Оптимизировать нужно всё Использование материала в первую
очередь. Однако, сложность карт раскроя тоже имеет значение. Под сложностью я понимаю количество поворотов листа при засовывании его
в станок. Относительно простые карты получаются, если разрезать лист на поперечные полосы, а потом повернуть такую
полосу и порубать уже ее.
Если же попробовать упаковать ее поплотнее, то получается примерно вот что:
Критерий годности, наверное, будет такой: минимальное количество использованных листов, по возможности избегая построения
слишком сложных карт.
A>> Итак, что хотелось бы услышать? То, сталкивался ли кто-либо уже с подобной проблемой? Если да, то опишу подробнее то, что уже работает, и то, что хочет отдел конструкторов
GS>Ты рассказывай, рассказывай.
Выше я уже что-то накорябал. Еще добавлю, что использование формальных математических методов, вроде линейного программирования,
осложняется дополнительными условиями:
1) Максимальная длина станка. То есть, не всякий лист удастся порезать на продольные полосы (хотя это и не желательно).
2) "Технологический остаток". То есть, сам процесс раскроя происходит так: берут полосу материала и заталкивают под гильотину.
Так вот, этот остаток представляет собой либо деталь, либо остаток (либо поперечную полосу), за которые можно держаться при этом.
Естесственно, задается какое-то минимально допустимое значение.
Примерно вот так:
Мммм.
Ну что тут можно сказать.
Или линейное программирование — тут больших проблем нет — записать мат
модель (и "правила" по которым она конструируется) — а дальше
перемалывать и перемалывать — получится ну очень оптимально.
С другой стороны — можно взять какую-нить эверистику, которая показывает
неплохие результаты (что-нить аля "жадный алгоритм")
Здравствуйте, azrael82, Вы писали:
A> Задача: написать программу, достаточно эффективно раскладыващую детали на листах. Листы могут быть
... A> Критерий годности, наверное, будет такой: минимальное количество использованных листов, по A> возможности избегая построения слишком сложных карт.
Ну что я могу сказать... Математики на такое не напасешься, конечно. Я бы написал целевую функцию и первым приближением оптимизировал бы просто случайным поиском. Вторым приближением бы я оптимизировал конденсацией — сначала оптимизируешь (да тем же случайным поиском) и фиксируешь переменные, связанные с большим вкладом в целевую функцию, потом — с меньшим и т.д. Не знаю, как это по-математически называется.
A>1) Максимальная длина станка. То есть, не всякий лист удастся порезать на продольные полосы (хотя это и не желательно). A>2) "Технологический остаток". То есть, сам процесс раскроя происходит так: берут полосу материала и
Спасибо за помощь. То, что Вы написали, было второй версией моего алгоритма. Потом появились новые требования, и она была отправлена на свалку. Задача — не просто упаковать прямоугольники как можно плотнее. Надо их упаковать с учетом ограничений, предъявляемых оборудованием. Никак не могу сформулировать правила, по которым алгоритм приемлемо хорошо работал бы на всех заказах. Некоторые варианты идеально отрабатывают на одних, и ужасно на других. Сейчас пока что в действии вариант, который создает 20 карт раскроя против человеческих 18ти.
Это недостаточно эффективно.
GS>Ну что я могу сказать... Математики на такое не напасешься, конечно. Я бы написал целевую функцию и первым приближением оптимизировал бы просто случайным поиском. Вторым приближением бы я оптимизировал конденсацией — сначала оптимизируешь (да тем же случайным поиском) и фиксируешь переменные, связанные с большим вкладом в целевую функцию, потом — с меньшим и т.д. Не знаю, как это по-математически называется.
Думал минут двадцать, так и не понял до конца, что Вы имели в виду. По отдельности слова то знакомые...
Здравствуйте, Alex-AKF, Вы писали:
AA>Мммм. AA>Ну что тут можно сказать. AA>Или линейное программирование — тут больших проблем нет — записать мат AA>модель (и "правила" по которым она конструируется) — а дальше AA>перемалывать и перемалывать — получится ну очень оптимально.
Если не трудно, то можно какую-нибудь ссылочку про линейное программирование применительно к задаче раскроя. Учебники, что попадались мне в руки, говорят только про такие задачи как транспортная, производственная (это где надо рассчитать оптимальное использование ресурсов).
AA>С другой стороны — можно взять какую-нить эверистику, которая показывает AA>неплохие результаты (что-нить аля "жадный алгоритм")
Эвристика — это, конечно, наиболее интуитивное решение. Только вот правильные правила ( ) не получается определить. Ну или, на худой конец, подобрать.
Здравствуйте, Cruelty, Вы писали:
A>>Сколько не гуглил, так и не удалось раскопать сколь-нибудь подробное описание алгоритма. Все сплошь рекламы программных продуктов с, якобы, самым оптимальным и экономичным алгоритмом.
C>http://www.google.co.uk/search?hl=en&ie=UTF-8&q=two-dimensional+bin+packing&meta=
Я, конечно, извиняюсь за свою возможную близорукость, но и по этой ссылке я не нашел "сколь-нибудь подробного описания" алгоритма. Только описания задачи раскроя, в лучшем случае — кое-какие намеки.
Здравствуйте, azrael82, Вы писали:
A> Я, конечно, извиняюсь за свою возможную близорукость, но и по этой ссылке я не нашел "сколь-нибудь подробного описания" алгоритма. Только описания задачи раскроя, в лучшем случае — кое-какие намеки.
Хорошо, если ожидалась ссылка на конкретный алгоритм приведу.
Четвертая ссылка в результатах гугла ведет нас на очень хороший сборник статей по Исследованию операций. Внизу открывшейся страницы мы видим ссылку на "Approximation of Two-Dimensional Rectangle Packing — Chen, Chen, Goel, Mang (1999)" и перейдя по ней мы можем почитать саму статью: http://www-cad.eecs.berkeley.edu/~fmang/cs270/report.pdf. Там дается коротенький обзор, какая-то евристика, формулируется задачa линейного программирования и обсуждаются алгоритмы локального поиска.
Здравствуйте, azrael82, Вы писали:
GS>>Ну что я могу сказать... Математики на такое не напасешься, конечно. Я бы написал целевую функцию и первым приближением оптимизировал бы просто случайным поиском. Вторым приближением бы я оптимизировал конденсацией — сначала оптимизируешь (да тем же случайным поиском) и фиксируешь переменные, связанные с большим вкладом в целевую функцию, потом — с меньшим и т.д. Не знаю, как это по-математически называется.
A> Думал минут двадцать, так и не понял до конца, что Вы имели в виду. По отдельности слова то знакомые...
Ну тогда по пунктам.
1. "целевая функция" — знакомое слово? Есть затруднения ее написать? Понятно как ее дальше использовать?
Здравствуйте, George Seryakov, Вы писали:
GS>Здравствуйте, azrael82, Вы писали:
A>> Думал минут двадцать, так и не понял до конца, что Вы имели в виду. По отдельности слова то знакомые...
GS>Ну тогда по пунктам. GS>1. "целевая функция" — знакомое слово? Есть затруднения ее написать? Понятно как ее дальше использовать?
Да, термин "целевая функция" мне знаком.
На данный момент у меня нет основной целевой функции, но зато есть вторичные.
Поясню. В текущее время расчет происходит так:
есть множество листов R (сюда входят как целые листы, так и отпиленные в ходе текущего раскроя куски( и множество нераскроенных еще деталей D.
Также есть множество размещенных деталей P. В начале множество листов сортируется по возрастанию площади (дабы использовать отходы, уже хранящиеся на складе, а только потом использовать целые листы).
шаг 1: выбирается первый доступный лист из множества R.
шаг 2: перебирается множество D в поисках детали, наиболее хорошо "вписывающейся" в обрабатываемый лист. (критерии различны). Если нераскроенные детали еще есть, но ни одна не вписывается в лист, то шаг 3. Если нет деталей, то выход. Если найдена подходящая деталь, то шаг 4.
шаг 3: пометить текущий лист, как неактивный. шаг 1.
шаг 4: поместить выбранную деталь в множество P (снабжая ее геометрической информацией, вроде конретного размещения на листе). Уменьшить количество выбранной детали в множестве D на количество только что размещенных деталей.(в простейшем случае, детали раскладываются по одной, но могут быть размещены и пакетами из нескольких деталей). Используя информацию о геометрии выбранной детали и текущего листа, создать два новых остатка, на которые разобьется текущий лист после размещения детали. Поместить эти остатки в начало множества R. Удалить выбранный лист из множества R. Шаг 1.
Такой алгоритм дает неплохие результаты, но, к сожалению, недосточно хорошие. По идее, наверное, следовало бы завести такую главную целевую функцию, которая будет оценивать эффективность всего раскроя, но пока не представляю как. То есть, я конечно могу тупо посчитать количество карт и эффективность использования материала, но как мне измерить технологичность карт?
