, O algoritmo de agendamento de recursos de balanceamento de carga ponderada

Question

A aplicação de software que estou trabalhando nas necessidades de ser capaz de atribuir tarefas a um grupo de usuários com base em quantas tarefas que actualmente tem, onde os usuários com as tarefas de menor número são os mais propensos a receber a próxima tarefa. No entanto, a carga actual tarefa deve ser tratada como um coeficiente de ponderação, em vez de uma definição ordem absoluta. IOW, Eu preciso implementar um algoritmo ponderada, de balanceamento de carga.

Vamos dizer que há cinco usuários, com o seguinte número de tarefas:

A: 4 B: 5 C: 0 D: 7 E: 9

Eu quero priorizar os usuários para a próxima tarefa na CABDE ordem, onde C é mais provável para obter a cessão e E, a menos provável. Há duas coisas importantes a serem observados aqui:

• O número de usuários pode variar de 2 a dezenas.
• O número de tarefas atribuídas a cada usuário pode variar de 1 a centenas de pessoas.

Por enquanto, podemos tratar todas as tarefas como iguais, embora eu não me importaria incluindo tarefa difícil como uma variável que eu posso usar no futuro -. Mas isso é puramente a cereja do bolo

As idéias que eu vim acima com até agora não são muito bons em algumas situações. Eles podem pesar usuários muito juntos, se há um grande número de usuários, ou eles podem fracassar se um usuário não tem tarefas atuais, ou ....

Eu tentei cutucando em torno da web, mas não tive muita sorte. Alguém pode me dar um rápido resumo de um algoritmo que iria funcionar bem? Eu não preciso de uma implementação real - eu fazer essa parte - apenas uma boa descrição. Alternativa, há um bom site que é de acesso livre?

Além disso, embora eu certamente apreciar a qualidade, isso não precisa ser estatisticamente perfeito. Então, se você pode pensar em uma boa, mas não ótima técnica, estou interessado!

Answer 1

Como salienta, este é um problema de balanceamento de carga. Não é realmente um problema de programação, desde que você não está tentando minimizar qualquer coisa (tempo total, número de trabalhadores concorrentes, etc.). Não existem restrições especiais (duração do trabalho, confrontos tempo, conjuntos de habilidades para combinar etc.) Então, realmente o seu problema se resume a seleção de uma função de ponderação apropriado.

Você diz que existem algumas situações que você quer evitar, como ponderações de usuários que estão muito perto juntos. Você pode fornecer mais detalhes? Por exemplo, o que está errado em fazer a possibilidade de atribuição apenas proporcional à carga de trabalho atual, normalizado pela carga de trabalho dos outros trabalhadores? Você pode visualizar isso como uma sequência de blocos de diferentes comprimentos (as tarefas), sendo embalado em um conjunto de bandejas (os trabalhadores), onde você está tentando manter a altura total das caixas o mais uniforme possível.

Com mais informações, poderíamos fazer recomendações específicas de funções que poderiam trabalhar para você.

Edit: exemplo funções de balanceamento de carga

Com base em seus comentários, aqui estão alguns exemplos de funções simples que podem lhe dar o comportamento de equilíbrio diferente. A questão básica é se você quer um comportamento determinístico ou probabilístico. Vou te dar um par de exemplos de cada um.

Para usar o exemplo na questão - há 4 + 5 + 0 + 7 + 9 = 25 postos de trabalho actualmente atribuídas. Você quer escolher quem fica com trabalho 26.

1) simples tarefa fazenda. Para cada trabalho, sempre escolher o trabalhador com o mínimo de postos de trabalho actualmente pendente. trabalhadores rápidas começar mais a fazer, mas acabamentos todos em aproximadamente o mesmo tempo.

2) Garantia justo carga de trabalho. Se os trabalhadores trabalham em velocidades diferentes, e você não quer um pouco fazendo mais do que outros, então controlar o número de concluídas + trabalhos pendentes para cada trabalhador. Atribuir o próximo trabalho de manter este número uniformemente spread (trabalhadores rápidos obter pausas livres).

3) Básico linear normalização. Escolha um número máximo de trabalhos a cada trabalhador pode ter. carga de trabalho de cada trabalhador é normalizado para esse número. Por exemplo, se o número máximo de trabalhos / trabalhador é de 15, em seguida, mais 50 postos de trabalho podem ser adicionados antes de atingir a capacidade. Assim, para cada trabalhador a probabilidade de ser atribuído o próximo trabalho é

P(A) = (15 - 4)/50 = 0.22  
P(B) = (15 - 5)/50 = 0.2  
P(C) = (15 - 0)/50 = 0.3  
P(D) = (15 - 7)/50 = 0.16  
P(E) = (15 - 9)/50 = 0.12

Se você não quiser usar um limite máximo específico, você poderia usar o trabalhador com o maior número atual de trabalhos pendentes como o limite. Neste caso, é trabalhador E, por isso, as probabilidades seria

P(A) = (9 - 4)/20 = 0.25  
P(B) = (9 - 5)/20 = 0.2  
P(C) = (9 - 0)/20 = 0.45 
P(D) = (9 - 7)/20 = 0.1  
P(E) = (9 - 9)/20 = 0

Note que, neste caso, o garante normalização trabalhador E não pode ser atribuído qualquer trabalho - ele já está no limite. Além disso, apenas porque C não tem nada a ver não significa que ele é garantido para ser dado um novo emprego (é apenas mais provável).

Você pode facilmente implementar a função de escolha através da geração de um número aleatório r entre 0 e 1 e comparando-a com esses limites. Então, se r é <0,25, A começa o trabalho, 0,25 < r <0,45, B começa o trabalho, etc.

4) normalização não-linear. Usando uma função de log (em vez da subtração linear) de peso seus números é uma maneira fácil de obter uma normalização não-linear. Você pode usar isso para distorcer as probabilidades, por exemplo, para torná-lo muito mais provável que os trabalhadores sem muitos empregos são dadas mais.

O ponto é, o número de maneiras de fazer isso são praticamente ilimitadas. Que função de ponderação que você usa depende do comportamento específico que você está tentando ativar. Esperemos que isso é-lhe dado algumas idéias que você pode usar como ponto de partida.