Расчет списка раскроя с наименьшим количеством отходов обрезки

Question

Я работаю над проектом, в котором создаю список для резки экструзии алюминия.

Алюминиевые профили имеют длину 5 м.

У меня есть список отрезков меньшей длины, которые нужно вырезать из 5-метровых алюминиевых профилей.

Маленькие отрезки необходимо разрезать в том порядке, в котором образуется наименьшее количество обрезков алюминиевых профилей длиной 5 м.

В настоящее время я упорядочиваю список резки таким образом, что обычно сначала отрезается самый длинный из меньших отрезков, а последним — самый короткий из меньших отрезков.Исключением из этого правила является тот случай, когда более короткая длина не помещается в то, что осталось от 5-метрового алюминиевого профиля, я использую самую длинную и короткую длину, которая подходит.

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

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

РЕДАКТИРОВАТЬ:Спасибо за ответы, я продолжу использовать «жадный» подход, поскольку он, кажется, делает очень хорошую работу (превосходит любые попытки человека создать эффективный список вырезок) и работает очень быстро.

Answer 1

Это классическая проблема, которую трудно решить эффективно.Алгоритм, который вы описываете, звучит как Жадный алгоритм.Взгляните на эту статью в Википедии для получения дополнительной информации: Проблема сокращения запасов

Answer 2

Боюсь, у меня нет конкретных идей по этой проблеме, но вы могли бы поискатьгенетический алгоритм' (что пойдет что-нибудь так)...

Разместите отрезки, которые нужно отрезать, в случайном порядке и присвойте этому порядку оценку в зависимости от того, насколько хорошо он соответствует вашему идеальному решению (предположительно, 0% отходов).

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

Answer 3

То, что вы описали, действительно классифицируется как Резка запаса проблема, как Вилли упомянуто, а не Бин Упаковка Проблема, потому что вы пытаетесь свести к минимуму отходы (сумму остатков), а не количество используемых экструзий.

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

Answer 4

На самом деле, поскольку размер материала фиксирован, а запросы — нет, это проблема с упаковкой корзины.

Снова, википедия в помощь!

(Мне, возможно, тоже придется заняться чем-то по работе, так что ура!)

Answer 5

Это интересная проблема, потому что я полагаю, что она зависит от количества продукции каждой длины.Если все они имеют одинаковое количество и вы можете упаковать каждую разную длину в один 5-метровый профиль, то у вас есть оптимальное решение.

Однако, если они не все помещаются в одну экструзию, у вас возникает более серьезная проблема.Чтобы сохранить одинаковое количество разрезов для каждой длины, вам нужно подсчитать, сколько отрезков (не обязательно по порядку) может поместиться на одном выдавливании, а затем пройти по порядку через каждый выдавливание.

Answer 6

Я тоже боролся с этой точной проблемой (длина моей проблемы - 6 м).

Решение, над которым я работаю, немного некрасиво, но ваше решение меня не устраивает.Позволь мне объяснить:

Размер запаса 5 м

Необходимо разрезать по размерам (по 1 штуке):

**3,5

1

1,5**

Ваше решение:

3,5 | 1 с отходом 0,5

1,5 с остатком 3,5

Видите проблему?

Решение, над которым я работаю -> Грубая сила

1. Проверьте все возможные решения.

2 - Заказать решение своими отходами

3 - Выберите лучшее решение

4 - Удалить предметы в решении из "Вселенной"

5 – Перейти к 1

Я знаю, что это отнимает много времени (но на обед у меня уходит 1 час 30 минут...так...:) )

Мне действительно нужно оптимальное решение (я делаю почти оптимальное решение вручную (+-) в Excel) не только потому, что я навязчив, но и потому, что продукт не из дешевых.

Если у кого-то есть простое лучшее решение, мне бы это понравилось.