Алгоритм распределения ресурсов по проекту (Bin Packing?)

Пожалуйста, дайте мне знать, какой алгоритм подходит для проблемы ниже:

У нас есть конечное количество проектов за заданный 3-месячный период (обычно ‹ 50). Каждый проект рассчитан на определенное количество часов.

У нас есть конечное количество ресурсов (обычно ‹ 100) за тот же 3-месячный период.

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

Можно выделить один ресурс для нескольких проектов.

Я думаю, что это похоже на проблему упаковки контейнеров, перевернутую с ног на голову, если мы рассматриваем проекты как контейнеры, ресурсы как объекты, а часы как объем объектов. По крайней мере две вещи заставляют его отклоняться от формальной задачи упаковки в контейнеры:

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

Я чувствую, что могу гоняться за гусями с углом упаковки мусорного ведра. Есть ли более подходящий для этого алгоритм?


algorithm bin-packing allocation
person Roman    schedule 12.04.2012    source источник
comment
Но в чем на самом деле проблема? Какой результат вы хотите? Список распределения ресурсов с указанием того, какой ресурс выделяется каждым проектом на каждый час в течение 3 месяцев? Вы хотите узнать, возможно ли такое распределение, или найти наилучшее распределение? Если да, то что делает распределение «лучшим»?   -  person zmbq    schedule 13.04.2012

Ответы (1)


arrow_upward
1
arrow_downward

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

Но все это игнорирует координацию между разработчиками, передачи, зависимости (что нужно сделать в первую очередь, прежде чем можно будет сделать что-то еще), тот факт, что компетентные разработчики имеют разные навыки и опыт, и даже такие же опытные разработчики, не будучи некомпетентными или суперзвездами, могут имеют до 10-кратной разницы в скорости.

person DRVic    schedule 12.04.2012
comment
Спасибо. Я думаю, что очереди будет достаточно. Мы будем назначать один ресурс каждому проекту в первом цикле, чтобы обеспечить покрытие всех проектов, а затем, на каждой последующей итерации, выделять ресурсы проекту в начале очереди, пока его емкость не будет исчерпана. К счастью, наш мир достаточно прост и лишен ограничений. - person Roman; 13.04.2012