Алгоритм по расчету оптимального распила листа металла #442984

Люди, не подскажите хороший алгоритм: Есть лист металла. Нужно его распилить так, чтобы получить требуемый перечень листов меньшего размера с заранее заданными размерами. При этом следует максимально минимизировать остатки большого листа.

симплекс метод :)

А вообще есть куча программ для раскроя, с учетом отходов на стружку, технологического оборудования и т. д.

задача имеет кучу решений - можно нарезать много листиков но маленьких а можно нарезать много разных - критерий оптимальности есть?

+ по крайне мере площадь остатка будет одной и той же

Это называется карта раскроя. Задача достаточно сложная, для быстрого решения в лоб, т. к. зависит от специфики производства, оборудования, который этот распил будет производить, трудозатрат и т. д. Если подходить примитивно, то нужно решить задачу линейного программирования, но тут возникает фокус с формой, если форма хитрая, то простого решения не будет. Для упрощения задачи можно рассматривать прямоугольники, ну и т. д.

если прямоугольниками - то просто

(5, 6) Только прямоугольники

jlbyfrjdst&

одинаковые?

1. ЛП не подходит 2. Непросто и для прямоугольников. 3. Лет 5-6 назад пробовал делать для раскроя на продольно-поперечных станках (раскрой из рулона). Если коротко, то решал методом ветвей и границ и алгоритм был разным для "стандартных" деталей и "произвольных". Для стандартных предварительно делался расчет. По реальным заказам (примерно 100-200) статистика была такой: - по стандартным отходы около 2%; - по нестандартным - 12-15%. Пытался "впарить" в несколько фирм (производство кровельных элементов) - оказалось не нужно: "У нас отходы за счет заказчика". В ассоциации металлоторговцев на предложение организовать семинар отреагировали так же. Тема интересует, если не найдете готового решения, готов поучаствовать безвозмездно.

Листики разного размера (но только прямоугольные). Критерий оптимальности - минимальный остаток большого листа. При этом маленькие можем нарезать и не все из того, что требуется (например, если их совокупная площадь требуемых маленьких превышает площадь большого)...

Как происходит раскрой листа: можно ли резать не насквозь (гильотина, болгарка, газовая резка?). Году в 83 был на Уралмаше, в цехе раскроя листов стояла японская установка (газовые резаки), операторы на дисплее формировали раскрой (типа тетриса), их за экономию поощряли.

кури:

если так пошло то вот :) =

не понял критерий

да, с критериями мутно как-то либо есть куча деталей - на несколько листов и надо уложиться в меньшее кол-во листов либо каждый лист индивидуален и интересует выход именно с листа --- говоря проще либо задаем план на несколько листов и обсчитываем общие отходы либо задаем план на каждый лист и считаем отходы с каждого листа

(15, 16) Листов несколько. Цель - минимизировать остатки от "большого" листа. В идеале их не должно быть вообще. Если лист использован не полностью - он может быть использован в последующем раскрое. Последующий раскрой на данный момент не рассматривается...

Нет.

Можно резать не насквозь. Деталей технологии не знаю...

В конце 90-х годов готовые решения для металлистов и мебельщиков лежали как платные программы на (по-моему) download или listsoft. Цена начиналась от 3000 вечнозеленых...

можно что-нибудь из комбинаторики попробовать 1. т.к. фигуры прямоугольные, то каждая деталь может быть либо | либо - 2. сортирум детали по наибольшему измерению 3. кладем деталь1 к краю листа - в угол 4. ищем свободное место для деталь2 5. располагаем дет2 чтобы прикасалась к уже уложенным деталям 6. идем в 4. пока не кончится место или детали ---- собственно "укладка рюкзака" получилась фишка: 7. считаем отходы и запоминаем расположение деталей 8. делаем "шаг назад" и переворачиваем | - детали 9. идем в 7. пока не переберем все позиции деталей проблемы: 4. непросто это будет 5. тоже хитро ну и количество вариантов ... 1с не самый шустрый язык --- все имхо, чисто мысли вслух

2. ну и сортировать можно по площади, а не по наибольшему измерению

Программы из списка в не пробовали погонять на Ваших данных?

В свое время тестил BestCute Pro, для составления карт раскроя в мебельном производстве. Сравнительное тестирование производили на плотнике краснодеревщике :). В принципе процент отхода был сопостовим, но по времени работы, краснодеревщик оказался круче. Хотя и программа весьма неплоха была :)

Странно, что краснодеревщик обогонял по времени. Если бы по качеству решения - было бы понятно. Может в программе перебор организован? Не могли бы вспомнить, как долго считала программа и насколько время расчета зависело от параметров задачи (числа деталей).

Не по времени расчета,  по времени (трудозатраты) на распил. :) Я не закладывал станки, ну и много других параметров. Соответственно зная специфику оборудования, у краснодеревщика получалось лучше. Насколько помню, станки могут быть очень разные и очень много параметров можно учитывать. Простейший прогон был на серии столов, именно серийный выпуск, а не штучное производство. От конструктора получали необходимые размеры, забивали размеры и количество щитов. Получали на выходе карты раскроя. По отходам порядок был практически одинаковый, но трудозатраты по распилу у краснодеревщика получились меньше, за счет более оптимальной нагрузки на оборудование. Ну и еще один момент - никаких фигурных деталей не забивали, только прямоугольные. Из достоинств той системы помню вот что: 1) Учет возвратных отходов 2) Учет ширины распила 3) Учет по видам материалов 4) Учет различной технологии распила 5) Учет обработки кромок 6) Учет стоимости материалов по партиям 7) Ну и много чего еще Система более менее имела дружелюбный интерфейс и мне нравилась, но к сожалению денег на покупку не хватило :(. По скорости работы к сожалению замеров уже не осталось, но помню покурить успевал :) (вообще-то :( - курить вредно!)

Спасибо.

Михаил, просто ради интереса, Вы занимались калькулированием затрат? Если интересно у меня остался достаточно простой алгоритм калькулирования затрат в производстве с коротким, многоступенчатым технологическим циклом. Была мысль сделать ветку, но пока что думаю, будет ли кому это тут нужно.

Нет, не занимался. И производством, по сути, тоже. Так что от меня здесь, как от козла молока.

Ну тогда ладно :). Удачи!

Делай - интересно.