Pré agendamento tarefas recorrentes

Question

No trabalho, é dado um conjunto de restrições de forma (taskname, frequência) onde a frequência é um número inteiro que significa que o número de tiques entre cada invocação da tarefa "taskname". Duas tarefas não podem ser executados simultaneamente, e cada invocação de tarefa leva um carrapato para ser concluído. Nosso objetivo é encontrar o melhor horário em termos de combinar o conjunto de restrições.

Por exemplo, se estamos dadas as restrições {(a, 2), (b, 2)} o melhor horário é "ab ab ab ..." Por outro lado, se forem dadas as restrições ({a, 2}, {B, 5}, {c, 5}) o melhor horário é provavelmente "abaca abaca abaca ..."

Atualmente nós encontrar o melhor horário, executando um algoritmo genético que tenta minimizar a distância entre as frequências reais e as restrições dadas. Ele realmente funciona muito bem, mas gostaria de saber se há algum algoritmo que melhor se adequa a este tipo de problema. Eu tentei pesquisar no Google, mas parece-me faltam as palavras certas (programação é geralmente de cerca de completar tarefas :(). Você pode ajudar?

Answer 1

Em primeiro lugar, considerar os méritos de comentário de jldupont! :)

Em segundo lugar, eu acho 'período' é a descrição exata do segundo elemento da tupla, por exemplo, {Nome, Período [icidade]}.

Dito isso, olhar para algoritmos de rede. alguma variante do enfileiramento ponderado é provavelmente o caso aqui.

Por exemplo, tendo em conta as tarefas N, N criar filas correspondentes às tarefas T0...Tn, e em cada ciclo ( "tick") com base no período da tarefa, a fila um item para a fila correspondente.

O algoritmo programador, então, apontar para minimizar (em média) o número total de garçons nas filas. de partida simples fora do ponto seria a de simplesmente dequeue do quene Qx que tem o maior número de itens. (Um parâmetro no item na fila para indicar 'idade' iria ajudar na priorização.)