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

Question

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

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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

Answer 3

То, что вы описали, действительно классифицируется как проблема Cutting Stock , как упоминается Wheelie , а не как проблема Bin Packing , потому что вы пытаетесь минимизировать отходы (сумма остатков), а не количество использованных выдавливаний.

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

Answer 4

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

Опять же, Википедия на помощь!

(Что-то, что мне может понадобиться и для работы, так что, да!)

Answer 5

Я тоже боролся с этой проблемой (длина моей задачи 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) не только потому, что я одержим, но и продукт не дешев.

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

Answer 6

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

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