Здравствуйте, George Seryakov, Вы писали:

GS>А расскажи задачу. Есть прямоугольные листы и прямоугольные же детали, так. Не ориентированные, так? Что фиксировано — количество листов или количество деталей? А оптимизировать нужно использование материала? Есть ли критерий годности? Типа — 75% или более, меньше — алгоритм полохой? Какие детали, одинаковые? Если неодинаковые, то как неодинаковые, как распределены?

Введение в задачу: есть фирма, занимающаяся изготовлением софта для проектирования и дизайна мебели.
Есть первая версия программы раскроя, которая вроде бы работает, но она делалась энное количество лет назад,
и делает не все. Мне поручено все это дело переписать "с нуля". Потому что алгоритм той версии сделан то ли на Фортране,
то ли еще на чем-то, исходников нет.
Задача: написать программу, достаточно эффективно раскладыващую детали на листах. Листы могут быть как сплошные (ДВП-18 Белый, скажем),
так и с текстурой (Ольха). Соответственно, детали бывают такие, что их все равно, как резать, так и требующие определенного
ориентирования относительно направления текстуры. Количество деталей, естесственно, фиксировано, определяется заказом.
Количество листов, по идее, должно ограничиваться наличием на складе, но, как показывает практика, туда забивает астрономические
цифры. Так что пока можно считать, что ограничения по листам нет. Оптимизировать нужно всё Использование материала в первую
очередь. Однако, сложность карт раскроя тоже имеет значение. Под сложностью я понимаю количество поворотов листа при засовывании его
в станок. Относительно простые карты получаются, если разрезать лист на поперечные полосы, а потом повернуть такую
полосу и порубать уже ее.


Если же попробовать упаковать ее поплотнее, то получается примерно вот что:


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

A>> Итак, что хотелось бы услышать? То, сталкивался ли кто-либо уже с подобной проблемой? Если да, то опишу подробнее то, что уже работает, и то, что хочет отдел конструкторов

GS>Ты рассказывай, рассказывай.

Выше я уже что-то накорябал. Еще добавлю, что использование формальных математических методов, вроде линейного программирования,
осложняется дополнительными условиями:
1) Максимальная длина станка. То есть, не всякий лист удастся порезать на продольные полосы (хотя это и не желательно).
2) "Технологический остаток". То есть, сам процесс раскроя происходит так: берут полосу материала и заталкивают под гильотину.
Так вот, этот остаток представляет собой либо деталь, либо остаток (либо поперечную полосу), за которые можно держаться при этом.
Естесственно, задается какое-то минимально допустимое значение.
Примерно вот так: