Конференция VBStreets

Привет! Подходящего раздела не нашел, напишу здесь.
Есть следующая задача:
Имеем D-деталей различной длины, большое кол-во. Имеем набор упаковок с заготовками. В каждой упаковке по N-штук заготовок длиной L, заготовки в каждой упаковки равной длины, но в разных упаковках длины могут различаться.
Необходимо выполнить раскрой с минимальными отходами. По условию, все неиспользованные заготовки из распечатанной упаковки так-же считаются отходами.

У меня есть несколько вариантов.
1. Полный перебор вариантов кроя и выбор наилучшего. Дает 100% оптимальный результат, но не пригоден при большом кол-ве деталей.
2. Жадный алгоритм, когда сортируем детали от большей к меньшей и каждую деталь отрезаем от заготовки минимальной длины на которую он помещается. Часто результат не совсем хороший, скорость работы очень высокая.
3. Еще вариант, тасовать порядок деталей как в картах, чем больше деталей тем больше вариантов растасовки. В подавляющем числе случаев дает более чем хороший результат, скорость работы высокая, но медленнее чем во втором случае.

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

Все задачи раскроя решаются перебором. Но простой перебор занимает невероятно много времени и малоэффективен, поэтому рационально вычислять «подсказчки» и «ограничения» для алгоритма.

Найди книжки Э. А. Мухачёвой, там целая научная работа на эту тему.

Хакер писал(а):Найди книжки Э. А. Мухачёвой, там целая научная работа на эту тему.

Спасибо! Сейчас поищу.

Посмотри стандартную схему Линейного программирования и иже с ним . . .
http://eqworld.ipmnet.ru/ru/library/boo ... 968ru.djvu

Joo писал(а):В каждой упаковке по N-штук заготовок длиной L

Т. е. N одинаковое во всех коробках?

Qwertiy писал(а):Т. е. N одинаковое во всех коробках?

нет, может и разное быть

Joo писал(а):Необходимо выполнить раскрой с минимальными отходами. По условию, все неиспользованные заготовки из распечатанной упаковки так-же считаются отходами.

Необходимо выполнить означает именно выполнить или только найти объём отходов?

Вообще, дай целое условие со всеми ограничениями.

И описания не очень понял про упаковки и заготовки (как соотносятся и что есть отходы: все неиспользованные заготовки по количеству / по суммарной длине или "огрызки" заготовок в т.ч), можешь изобразить схематически процесс получения деталей из заготовок+упаковок?
Ну и из вариантов имхо нужно развивать первый, чтобы он стал в итоге пригодным (из условий может быть возможно найти полезные закономерности, но пока я не совсем однозначно понял условия).
Задача немного похожа на олимпиадную, т.к. упаковки одинаковых по размеру заготовок, одномерные размерности — это какой-то сферический конь в вакууме. Даже кажется, что нечто подобное встречал (хотя это какой-то ад, даже походу при таких условиях сложнее, чем задача с вычислением количества 3D шаров в ёмкости заданной формы, там хотя бы не тупо перебор, который проваливается на большом количестве). Если действительно олимпиадная, то стало быть надо смотреть прошлогодние/аналогичные демонстрационные, т.к. у организаторов вечно свои тараканы в голове и своё представление о верном решении (и корректности и однозначности условий). И в этом случае некоторые неявные условия могут подразумеваться, хотя не описаны.
Ну а в сторону эвристики двигаться как минимум не интересно, это чаще всего богомерзкие полумеры, весь выигрыш от которых сводится на нет количеством промахов. Эвристика имеет смысл только там, где что-либо мешает провести детальный анализ области и создать адекватный алгоритм (ограничение мат.обеспечения, ограничение вычислительных ресурсов и т.д, хотя второе тоже как бы не повод, т.к. в том же классическом "коммивояжере" эвристику использовали только потому, что сложно иной алгоритм придумать).

Qwertiy писал(а):Необходимо выполнить означает именно выполнить или только найти объём отходов?

Именно выполнить, т.е. получить схему кроя, при минимальном кол-ве отходов (суммарно)

Proxy писал(а):как соотносятся и что есть отходы

Отходы в данном случае, это суммарная длина огрызков + суммарная длина неиспользованных заготовок из распечатанной упаковки.

Proxy писал(а):Задача немного похожа на олимпиадную

Да, задача похожа на олимпиадную, но в данном случае это задача из жизни

Вот пример расчета по третьему варианту:

Код: Выделить всё

Введите необходимые отрезки через запятую в формате Длина[:Кол-во]
:> 300,300,210,150,19,25,152,214,17,188,160,135,250,250,117,222
-----------------------------------------
Введите имеющиеся варианты упаковок через запятую в формате Длина:Кол-во
:> 200:10,250:10,300:10
-----------------------------------------
Кол-во отрезков: 16
Кол-во растасовок: 272
=========================================
Упаковка 300x10 потери 443
-----------------------------------------
Режем от панели 1 отрезок длиной 19
Режем от панели 1 отрезок длиной 25
Режем от панели 1 отрезок длиной 210
Режем от панели 1 отрезок длиной 17
Режем от панели 2 отрезок длиной 150
Режем от панели 2 отрезок длиной 117
Режем от панели 3 отрезок длиной 300
Режем от панели 4 отрезок длиной 300
Режем от панели 5 отрезок длиной 222
Режем от панели 6 отрезок длиной 250
Режем от панели 7 отрезок длиной 250
Режем от панели 8 отрезок длиной 160
Режем от панели 8 отрезок длиной 135
Режем от панели 9 отрезок длиной 188
Режем от панели 10 отрезок длиной 214
-----------------------------------------
Упаковка 200x10 потери 1848
-----------------------------------------
Режем от панели 1 отрезок длиной 152
-----------------------------------------
Кол-во использованных упаковок: 2
Общие потери: 2291
=========================================


Сейчас изучаю работу Мухачевой и еще пару работ на эту тему, надеюсь по этим материалам сделать "правильный" расчет.

Joo, давай так:

Код: Выделить всё

unsigned n;         // Количество видов отрезков
unsigned m;         // Количество видов коробок

unsigned d[MAXN];   // Требуемые длины отрезков
unsigned с[MAXN];   // Требуемые количества отрезков

unsigned l[MAXM];   // Длины заготовок в коробках
unsigned k[MAXM];   // Количество коробок данного вида

Ограничения:

Код: Выделить всё

1<=n && n<=MAXN
1<=m && m<=MAXM
ForAll i : 1<=d[i] && d[i]<=MAXD
ForAll i : 1<=c[i] && c[i]<=MAXC
sum {i} of d[i]*c[i] <= MAXSUMD
ForAll i : 1<=l[i] && l[i]<=MAXL
ForAll i : 1<=k[i] && k[i]<=MAXK
sum {i} of l[i]*k[i] <= MAXSUML

Чему равны MAXN, MAXM, MAXD, MAXC, MAXSUMD, MAXL, MAXK, MAXSUML?

Макс. кол-во видов отрезков MAXN - можно прикинуть, шаг отрезка 0,1см, на данный момент максимальная длина заготовки 300см, а отрезок не может быть длиннее этого значения, значит кол-во видов 3000.
Макс. кол-во видов упаковок MAXM - в данный момент 3 вида, длины заготовок по 200, 250, 300 сантиметров и по 10 штук в каждом типе упаковки.
Макс. длина требуемого отрезка MAXD - 300см.
Макс. кол-во требуемых отрезков для каждого типа отрезка MAXC - теоретически сколько угодно, по факту более 150 не бывало.
Макс. сумма длин отрезков умноженное на кол-во MAXSUMD - 200000см, больше пока не было.
Макс. длина заготовки MAXL - 300см.
Макс. кол-во упаковок каждого вида MAXK - считать бесконечным.
Макс. сумма длин заготовок умноженное на кол-во штук и кол-во упаковок MAXSUML - исходя из MAXK так-же считать бесконечным.