Identifica o algoritmo para minhas necessidades de alocação de recursos

5

Estou tentando automatizar uma tarefa e não tenho o vocabulário correto para procurar o algoritmo correto. Realmente parece um problema comum que provavelmente foi resolvido muitas vezes antes.

Tudo o que estou procurando é que alguém me aponte na direção certa ou me ajude com os termos de pesquisa certos para procurar uma solução / algoritmo. Se você souber de uma biblioteca real (javascript), então melhor ainda.

Cenário inventado

Digamos que eu tenha 3 'buckets', Bucket A , Bucket B e Bucket C . Cada um deles pode conter um certo número de 'Bolas'.

  • Bucket A : capacidade de 10 bolas.
  • Bucket B : capacidade de 15 bolas.
  • Bucket C : capacidade de 5 bolas.

Agora, também tenho um inventário de bolas e cada uma delas pode ser colocado em certos "baldes". Uma bola só pode ir em Bucket 2 , a próxima bola pode entrar em Bucket 1 OU Bucket 3 e assim por diante.

Agora .. eu preciso determinar a melhor maneira de colocar as bolas para tentar preencher cada 'balde' com a sua capacidade (ou o mais próximo possível).

Cenário real

Meu motivo real para isso é programar people (bolas) para visitar locations (baldes) por um número de horas solicitado (capacidade do balde). Contudo, devido às seguintes razões todas as bibliotecas / algoritmos que encontrei enquanto procurava por "agendamento" até agora não funciona no meu cenário.

  • Eu não me importo com os horários de início / término, somente person - > %código%
  • Todas as pessoas (bolas) têm uma lista restrita de locais que podem visitar. Cada um é único.
  • Cada pessoa está disponível para um número arbitrário de horas inteiras (inteiras) que pode gastar em exatamente uma location . Usar alguém disponível por 8 horas para apenas 7 dessas horas é OK.
  • Cada local (bucket) solicita um determinado número de horas que eu tento preencher da melhor maneira possível com qualquer combinação de pessoas.

Eu tenho ~ 50 locais e ~ 100 pessoas. Não é um requisito que eu tenha uma solução perfeita , mas "muito próxima".

Eu encontrei schedule.js que parece fantástico, mas não consegui abusar dele para atender às minhas necessidades.

    
por Luggage 10.07.2014 / 06:32
fonte

1 resposta

3

Se o número de horas que cada pessoa está disponível for constante (por exemplo, sempre é de 1 hora), seu problema pode ser modelado como Fluxo de Rede , facilmente solucionável em tempo polinomial com o algoritmo de Ford-Fulkerson .

Para construir sua rede de fluxo, crie duas camadas de nós; a primeira camada representa suas bolas, a segunda camada representa seus baldes. Adicione uma aresta da fonte a cada bola com capacidade 1. Adicione uma aresta de cada bola a cada balde compatível com capacidade 1. Adicione uma aresta de cada caçamba ao tanque com capacidade correspondente à capacidade da caçamba. O fluxo máximo representa a atribuição ideal.

Caso contrário, se o número de horas que cada pessoa puder contribuir varia, o algoritmo acima não funciona devido à sua restrição de que cada pessoa pode visitar apenas um local. (O fluxo da rede resolveria o problema, mas poderia dividir as horas de uma pessoa em vários locais.) Nesse caso, você tem algo relacionado a um Mochila ou Problema de embalagem de caixa .

Se o número de horas que cada pessoa puder contribuir for um número inteiro, você poderá resolvê-lo por meio de programação dinâmica pseudo-polinomial. Caso contrário, você precisa:

  1. Implemente um algoritmo de retrocesso de força bruta. Isso fornecerá uma solução exata, mas não funcionará se o número de pessoas ou locais exceder 50 ou mais.
  2. Implemente um método heurístico combinatorial, como sugeriu Doc Brown. Hill Climbing ou Recozimento Simulado funcionará muito bem para este problema e fornecerá resultados ótimos ou quase ótimos muito rapidamente.
por 10.07.2014 / 09:44
fonte