Alguém reconhece esse problema de agendamento? Existe um algoritmo para isso?

Question

Alguém reconhece esse problema de agendamento? Existe um algoritmo para isso?

#1 resposta do (1 votos)

5

Considere o seguinte problema:

Descrição :

Existem n trabalhos J ₁ ... J _n com tempos de ciclo C ₁ .... C _n. Encontre um quantum de tempo e uma tabela de agendamento considerando que:

qualquer elemento da tabela contém no máximo um trabalho
o manipulador de trabalho processará um elemento de cada vez, ou seja, executará o trabalho (se houver algum) e, depois de passar um quantum de tempo , passará para o próximo elemento.
o manipulador de tarefas retornará em loop, ou seja, após o último elemento, ele continuará com o primeiro.
a ciclicidade deve ser mantida, ou seja, a distância entre duas ocorrências consecutivas (incluindo loopback) do trabalho J _k (k = 1, n) deve ser igual a C _k / quantum de tempo .
a tabela deve ser a mais curta possível.

Exemplo :

J ₁ - 4 segundos de ciclicidade
J ₂ - 6 segundos de ciclicidade
J ₃ - ciclicidade de 8 segundos

Exemplo de solução :

quantum de tempo = 1s

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 seconds
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|J1|J2|J3|  |J1|  |  |J2|J1|  |J3|  |J1|J2|  |  |J1|  |J3|J2|J1|  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Meu sentimento é que isso pertence à família de problemas de agendamento e que pode ser um caso especial de um problema mais geral. Isto é assim? Tentei procurá-lo on-line, mas não encontrei nada parecido. Como não tenho experiência com problemas de agendamento, não sei ao certo o que pesquisar.

Pelo que vejo:

a duração total da tabela de planejamento deve ser o menor múltiplo comum de C ₁ ... C _n.
o quantum de tempo deve ser pelo menos GCD (C ₁, ..., C _n) / n. - Esta não é necessariamente a solução ideal.

Isso me leva a acreditar que existe uma solução direta e não uma envolvendo programação dinâmica. Isto é assim?

Alguém pode me indicar alguns recursos, talvez até um algoritmo, para esse problema?

Também estou curioso sobre as variações em que os trabalhos podem ser distribuídos entre mais de uma tabela de agendamento.

GCD = Maior Divisor Comum

Editar : não estou perguntando como agendar N trabalhos com tempos de ciclo fornecidos; Tenho certeza de que existem maneiras mais dinâmicas de fazer isso, como alguns sugeriram. Meu problema é " Encontre um quantum de tempo e uma tabela de agendamento considerando que: [...] ". É até possível que isso tenha raízes em algumas partes da matemática.

algorithms problem-solving scheduling

por DonComo 20.05.2014 / 15:42

fonte

1 resposta

Tags algorithms problem-solving scheduling

Scripts para executar programas Java - por exemplo, Formiga Quais são os benefícios da maneira Android de “salvar memória” - explicitamente passando objetos Contexto para todos os lugares?

score 1 · Answer 1

Você pode determinar a melhor programação usando uma fila de prioridades . Onde estão os momentos de decisão no agendamento? É quando você tem mais de um ciclo para começar em qualquer segundo.

Você precisará ter um tipo de dados de "agendamento" que represente uma possível programação (os dados que você escreveu acima são um exemplo perfeito dos dados que você representa aqui).

Portanto, o pseudo-algoritmo deve ser o seguinte:

Adicione cada tipo de ciclo ao seu próprio agendamento e empurre cada agendamento para uma fila de prioridade, priorizando pelo menor valor GCD * (C1, ..., Cn) / n.

Em seguida, começando com o agendamento com o menor valor de GCD * (C1, ..., Cn) / n, crie novos agendamentos do antigo adicionando novos ciclos ao lançamento.

Continue o quanto quiser.

Você decide quando a programação deve terminar e, como é uma fila de prioridade, você tem a garantia de que o primeiro elemento é o ideal em termos de GCD * (C1, ..., Cn) / n em um determinado ponto .

Espero que ajude.