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

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

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

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

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

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

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

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

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

22.08.2008 11:58:56
6 ОТВЕТОВ
РЕШЕНИЕ

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

15
22.08.2008 12:10:17

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

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

1
22.08.2008 12:09:56

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

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

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

5
22.08.2008 12:17:52

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

Опять википедия на помощь!

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

2
3.07.2012 15:07:17

То, что вы описали, действительно классифицируется как проблема режущего материала , как упомянул Уилли , а не проблема упаковки в бункер, потому что вы пытаетесь свести к минимуму количество отходов (сумма остатков), а не количество используемых выдавливаний.

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

3
23.05.2017 12:08:51

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

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

1
19.11.2009 17:10:18