Линейная оптимизация раскроя (порезки) материала

← →
PEAKTOP © (2006-11-04 12:49) [0]

Доброе время суток ! Ув. Мастера, подскажите пожалуйста идеи линейной оптимизации раскроя материала.
Внедряем ERP систему на FireBird v2.0, дошло вот до оптимизации заказов.
Заказ - документ вроде расходной накладной, где несколько позиций из изделий. Изделие - сложный объект базы данных, который состоит из узлов и операционного времени сборки; узлы из: узлов, деталей и операционного времени сборки; детали из: деталей, заготовок и операционного времени сборки и т.д. Есть документ, "производственная программа" (или задание в цех на смену, если угодно), детальными позициями которого являются заказы. Требуется выбрать из всех заказов заготовки и сформировать задание на раскрой линейного материала. Есть хранимая процедура, которая по ID документа "производственная программа" возвращает список заготовок на смену в виде:
ID_ZAG INTEGER,
LENGTH_ NUMERIC(15,6) (мм)
Материал линейный, длина исходного материала 10 000 мм (10 метров). Длина заготовок колеблеться строго от 200 до 2500 мм, обрезки выбрасываются. Надо сделать оптимальный раскрой, при котором отход будет минимальный. Проблема в том, что база "двусторонняя", т.е. работа с ней идет не только с клиентского ПО в административном офисе, но и через ВЭБ-интерфейс, т.е. оптимизацию надо будет делать только на SQL с помощью хранимых процедур.

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

← →
PEAKTOP © (2006-11-04 13:03) [1]

По условию задачи вполне допустимо ЗАКАЗЧИКОМ, что оптимизация - это сложная процедура, которая будет колбасится минут 5-10. Средние статистические данные: 3000 - 5000 заготовок в одной производственной программе.
На текущий момент идея пока такая.
Создать таблицы-регистры из
CREATE TABLE RASKROY_VARIANTS(
ID_DOC INTEGER, -- код документа производственной программы
ID INTEGER -- Код варианта раскроя
)
CREATE TABLE RASKROY_PALKI(
ID_VAR INTEGER NOT NULL FOREIGN KEY REFRENCES RASKROY_VARIANTS(ID) -- Код варианта раскроя
ID INTEGER -- Код палки, которую будем резать на заготовки
)
CREATE TABLE RASKROY_PALKI_ZAG(
ID_PALKA INTEGER NOT NULL FOREIGN KEY REFRENCES RASKROY_PALKI(ID) -- Код палки, которую будем резать на заготовки
ID_ZAG INTEGER -- Код заготовки
)
В общем идея пока такая: перебрать в хранимой процедуре все варианты раскроя и заполнить регистры. А потом выбрать из всех вариантов тот, где потери будут минимальные.

Но сразу видно, что идея даст офигенный прирост базы, чего в общем-то не хотелось бы. Правда, вычислительные мощности сервака ЗАКАЗЧИКА позволяют сделать это (четыре двухядерных проца, 1ТБ ЖД). Но что-то подсказывает, что потом будут проблемы :)))

← →
TUser © (2006-11-04 13:06) [2]

Какая-то смесь всего - БД, ERP и оптимизация. Вопрос алгоритмический? Какая тогда разница, как там что-то в БД хранится? Или вопрос про БД и прочие технологии? Какое тогда отношение сюда имеет какая-то оптимизация?

← →
Alexis © (2006-11-04 13:09) [3]

Мастера, подскажите пожалуйста идеи линейной оптимизации раскроя материала

Посмотри в Интернете по ключевым словам
2D bin packing problem
rectangle packing in two dimensions
two dimensional bin packing problem
NP-hard problems

← →
PEAKTOP © (2006-11-04 13:11) [4]

> Посмотри в Интернете по ключевым словам
> 2D bin packing problem

Скорее, это даже 1D.

← →
Ученик чародея © (2006-11-04 13:32) [5]

> PEAKTOP © (04.11.06 13:11) [4]
>
>
> > Посмотри в Интернете по ключевым словам
> > 2D bin packing problem
>
> Скорее, это даже 1D.

Тогда "жадный алгоритм"? Выбираем максимальный элемент не более куска ткани, потом максимальный который не более отреза и так до минимально возможного - самый простой алгоритм.

Если сложнее, то там уже эвристика.

> Тогда "жадный алгоритм"? Выбираем максимальный элемент не
> более куска ткани, потом максимальный который не более отреза
> и так до минимально возможного

Ну, в приципе, так и устроена хранимая процедура заполнения регистров.
Проблема в том, что максимальная длина заготовки (2500) намного меньше исходной длины материала (10000), следовательно - очень много вариантов вставки туда остальных заготовок.
Думаю, необходимо так называемо Лагранжево ослабление, когда "отсекаются" заведомо плохие решения и похожие решения. Скажем, отличие в потрях в вариантах раскроя на всей производственной программе на десятую процента не инетерсуют. А вот хотя бы процент - это уже интересует.
Спасибо Alexis © (04.11.06 13:09) [3] за подсказку, где у буржуев почитать.

> PEAKTOP © (04.11.06 13:11) [4]

> Скорее, это даже 1D.

Так что, то есть все детали (или узлы, как вы их там называете) по ширине равны?

Ну, насколько я сейчас в состоянии понимать правльно задачу (с обеда уже 1б коньяка), то она сводится в оптимальном расположении линейных отрезков заготовок на линейных отрезках материала, т.е. 1D
2D следовательно в оптимальном расположение фигур заготовок на листах материала.
3D в оптимальном распложения заготовок памятников в кусках материала гранита. :))))

Линейная оптимизация раскроя (порезки) материала Найти похожие ветки