Расчет оптимальной длины склада

Question

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

Потенциальные осложнения:

1. Статья в Википедии, посвященная проблеме режущего материала, находится у меня над головой. Я подозреваю, что понимание того, как решить эту проблему, может иметь решающее значение для решения моей собственной проблемы.

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

Answer 1

Правильно ли я понимаю: у вас разные длины реза (3.6, 10.2, 8.3, 7.3, ...) и вы хотите узнать, какая длина запаса является наилучшей, чтобы дать вам наименьшее количество отходов? Хотите найти только одну длину или несколько? есть ли максимальная длина, минимальная длина? Если у вас нет максимальной длины, лучший выбор - использовать одну очень длинную заготовку, где все отрезанные отрезки точно вписываются, но я не думаю, что это то, что вам нужно ..

ОБНОВЛЕНИЕ Я некоторое время работал над этой проблемой, как часть моей работы, у нас есть продукт, который делает это (и даже больше). Для простого решения вы можете реализовать эвристику First Fit Decreasing , которая работает с заданной длиной заготовки. Затем случайным образом используйте несколько длин заготовок и каждый раз используйте эвристику для их заполнения. Запомните длину запаса с минимальными отходами.

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

Answer 2

Кажется, у вас есть "онлайн" версия этой или подобной проблемы оптимизации. Онлайн означает, что вы не знаете всю информацию заранее, то есть вы должны принимать решения при поступлении заказов.

Answer 3

Проблема также зависит от количества акций S, которые вы хотите использовать.

Если S = ​​1, то длина заготовки должна быть суммой размеров всех срезов.

Если S> 1, вы хотите разделить размер срезов на S групп и минимизировать разницу между суммами размеров срезов в каждой группе. Это очень близко к проблеме раздела , которая является NP-трудной.