My<cod/>.net
Расчет списка обрезки с наименьшим количеством обрезанных отходов
Я работаю над проектом, где я произвожу алюминиевый экструзионный режущий лист.
Алюминиевые штранг-прессования приходят в длины 5m.
У меня есть список меньших длин, которые нужно вырезать из 5-миллиметровой длины алюминиевых профилей.
Меньшие длины должны быть обрезаны в том порядке,который производит наименьшее количество обрезанных отходов из 5-миллиметровых длин алюминиевых профилей.
В настоящее время я упорядочиваю список сокращений таким образом, что обычно самая длинная из меньших длин отрезается первой, а самая короткая из меньших длин-последней. Исключение из этого правила состоит в том, что когда более короткая длина не подходит к тому, что осталось от 5-метровой длины алюминиевой экструзии, я использую самую длинную короткую длину, которая подойдет.
Это, по-видимому, дает очень эффективный (очень мало отрубных отходов) список сокращений и не занимает много времени для расчета. Однако я полагаю, что даже если список сокращений очень эффективен, он не обязательно является самым эффективным.
Кто-нибудь знает способ рассчитать наиболее эффективный список резки, который может быть рассчитан за разумное время?
EDIT: Спасибо за ответы, я продолжу использовать подход "greedy", поскольку он, похоже, делает очень хорошую работу (из всех человеческих попыток создать эффективный список сокращений) и очень быстр.
Это классическая, трудная задача, которую нужно решать эффективно. Алгоритм, который вы описываете, звучит как жадный алгоритм . Взгляните на эту статью Википедии для получения дополнительной информации: проблема разделочного материала
Боюсь, что никаких конкретных идей по этой проблеме нет - но вы можете заглянуть в "генетический алгоритм" (который будет выглядеть примерно так)...
Разместите отрезки длины в случайном порядке и дайте этому порядку оценку, основанную на том, насколько хорошо он соответствует вашему идеальному решению (0% отходов, предположительно).
Затем итеративно вносите случайные изменения в порядок и повторно оценивайте его. Если оценка выше, то бросьте результат. Если оценка ниже, сохраните ее и используйте в качестве основы для следующего расчета. Продолжайте идти, пока вы не получите ваш счет в приемлемых пределах.
То, что вы описали, действительно классифицируется как проблема режущего материала , как упоминал Уилли, а не проблема упаковки бункера , потому что вы пытаетесь минимизировать отходы (сумму остатков), а не количество используемых экструдеров.
Обе эти проблемы могут быть очень трудными для решения, но упомянутый вами алгоритм 'best fit' (с использованием самого длинного 'small length', который соответствует текущей экструзии), вероятно, даст вам очень хорошие ответы с очень низкой сложностью.
На самом деле, поскольку размер материала фиксирован, но запросы не являются, это проблема упаковки бункера.
И снова Википедия пришла на помощь!
(Кое-что, что мне, возможно, тоже придется искать для работы, так что ура!)
Я боролся с этой точной (длина для моей проблемы составляет 6 м) проблемой и здесь.
Решение, над которым я работаю, немного уродливо, но я не соглашусь на ваше решение. Позвольте мне объяснить:
Размер запаса 5 м
Нужно разрезать по размерам(по 1 от каждого):
**3,5
Один
1,5**
Ваше решение:
3,5 | 1 с отходом 0,5
1,5 с остатком 3,5
Видите в чем проблема?
Решение, над которым я работаю - > грубая сила
1-протестируйте все возможные решения
2-Заказать растворение по их отходам
3-Выберите самое лучшее решение
4-Удалите элементы в растворе из "Universe"
5-Гото 1
Я знаю, что это отнимает много времени (но я беру 1 час 30 минут на обед... так... :) )
Мне действительно нужно оптимальное решение (я делаю почти оптимальное решение вручную ( + - ) в excel) не только потому, что я навязчивый, но и продукт не дешевый.
Если у кого-то есть простое лучшее решение, я бы с удовольствием
Это интересная проблема, потому что я полагаю, что она зависит от количества каждой длины, которую вы производите. Если они все одинаковое количество, и вы можете получить каждую разную длину на один 5м экструзии, то у вас есть оптимальное решение.
Однако если они не все подходят для одного экструзии, то у вас есть большая проблема. Чтобы сохранить одинаковое количество вырезов для каждой длины, вам нужно рассчитать, сколько длин (не обязательно по порядку) может поместиться на одной экструзии, а затем пройти в определенном порядке через каждую экструзию.