как сделать bin packing точно считающий алгоритм а не приблизительный? [закрыт]

for the distribution of computation tasks on the machines, we need to solve the "bin packing problem" -- we have n tasks each of them needs k_i CPUs, and we want to fit them on computing nodes where each node contains m CPUs (depending on the machine we use m can be 24, 40, 64 or 80). Obviously, we would like to reduce the number of nodes we use (we have a limited amount of node-hours assigned to us on each machine). Currently, the task is done using either manual distribution or https://pypi.org/project/binpacking which provides a "greedy" solution, which is not always optimal.

It would be nice to have an optimal solution for the small cases that interest us (n <= 100, k_i <= m <= 100). You can find some links to exact algorithms in https://en.wikipedia.org/wiki/Bin_packing_problem#Exact_algorithm, but maybe there are also separate algorithms, that are practical for these small cases. it is best for me if you can find or write implementation in python, but any programming language would be ok for that.

Источник: https://ru.stackoverflow.com/questions/1232167/%D0%BA%D0%B0%D0%BA-%D1%81%D0%B4%D0%B5%D0%BB%D0%B0%D1%82%D1%8C-bin-packing-%D1%82%D0%BE%D1%87%D0%BD%D0%BE-%D1%81%D1%87%D0%B8%D1%82%D0%B0%D1%8E%D1%89%D0%B8%D0%B9-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D0%B0-%D0%BD%D0%B5-%D0%BF%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B7%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9

Тебе может это понравится...

Добавить комментарий