Maximizando o rendimento com capacidade variável no tempo

Resultados para a configuração online

A verdadeira complexidade reside no ambiente online, onde os trabalhos chegam dinamicamente e o agendador deve tomar decisões imediatas e irrevogáveis ​​sem saber quais trabalhos chegarão a seguir. Quantificamos o desempenho de um algoritmo online por meio de sua relação competitiva, que é a pior comparação entre o rendimento de nosso algoritmo online e o rendimento de um algoritmo ideal que está ciente de todos os trabalhos a priori.

Os algoritmos não preemptivos padrão falham completamente aqui, pois sua proporção competitiva se aproxima de zero. Isso acontece porque uma única decisão errada de agendar um trabalho longo pode arruinar a possibilidade de agendar muitos trabalhos futuros menores. Neste exemplo, se você imaginar que cada trabalho concluído traz peso igual, independentemente de sua duração, concluir muitos trabalhos curtos é muito mais lucrativo do que concluir um trabalho longo.

Para tornar o problema online solucionável e refletir a flexibilidade do mundo real, estudamos dois modelos que permitem que um trabalho ativo seja interrompido se surgir uma oportunidade melhor (embora apenas os trabalhos reiniciados e posteriormente concluídos de forma não preventiva sejam considerados bem-sucedidos).

Interrupção com reinicializações

Neste modelo, um algoritmo online pode interromper um trabalho em execução no momento. Embora o trabalho parcial já executado no trabalho interrompido seja perdido, o trabalho em si permanece no sistema e pode ser repetido.

Descobrimos que a flexibilidade proporcionada pela permissão de reinicializações de trabalhos é altamente benéfica. Uma variante do Greedy que agenda iterativamente o trabalho que termina mais cedo continua a atingir uma proporção competitiva de 1/2, correspondendo ao resultado na configuração offline.

Interrupção sem reinicializações

Neste modelo mais rigoroso, todo o trabalho realizado no trabalho interrompido é perdido e o trabalho em si é descartado para sempre. Infelizmente, descobrimos que neste modelo estrito, qualquer algoritmo online pode encontrar uma sequência de trabalhos que o força a tomar decisões que o impedem de satisfazer muito mais trabalhos no futuro. Mais uma vez, a proporção competitiva de todos os algoritmos online se aproxima de zero. A análise dos casos difíceis acima nos levou a focar no cenário prático onde todos os trabalhos compartilham um prazo comum (por exemplo, todo o processamento de dados deve terminar na execução noturna do lote). Para esses casos de prazos comuns, desenvolvemos novos algoritmos competitivos constantes. Nosso algoritmo é muito intuitivo e descrevemos aqui o algoritmo para a configuração simples de um perfil de capacidade unitária, ou seja, podemos agendar um único trabalho a qualquer momento.

Nesta configuração, nosso algoritmo mantém um cronograma provisório atribuindo os trabalhos que já chegaram a intervalos de tempo disjuntos. Quando chega um novo trabalho, o algoritmo modifica o cronograma provisório executando a primeira ação aplicável dentre as quatro ações a seguir: