Resumo Técnico: Predição de Tempo de Espera Baseada em Aprendizado de Máquina para Filas de Prioridade

Definição do Problema

O artigo aborda o desafio de prever tempos de espera transientes em sistemas de filas de prioridade multiclasse operando sob condições variantes no tempo. Embora a teoria de filas clássica forneça resultados analíticos exatos para sistemas simples e estacionários, aplicações do mundo real (ex: saúde, centros de atendimento, logística) frequentemente envolvem taxas de chegada não estacionárias, distribuições de tempo de serviço complexas e regras de preempção. Em tais ambientes, o tempo de espera de um cliente depende não apenas do estado atual da fila, mas também de futuras chegadas de alta prioridade, tornando a predição analítica difícil.

O estudo investiga especificamente se modelos de aprendizado de máquina (ML) podem prever com precisão os tempos de espera usando dados operacionalmente observáveis limitados — especificamente, o comprimento da fila no momento da chegada e a classe de prioridade do cliente — sem exigir conhecimento detalhado das funções de taxa de chegada subjacentes ou das distribuições de tempo de serviço.

Metodologia

Geração de Dados

Os autores geraram um conjunto de dados sintéticos simulando 200 dias independentes de uma fila de prioridade de duas classes ($G(t)/G/1$) sob um ambiente variante no tempo.

• Processo de Chegada: As chegadas não estacionárias foram modeladas usando intervalos homogêneos por partes com distribuições de Tipo-Fase (PH) para capturar a variabilidade além das suposições exponenciais simples.
• Disciplina de Serviço: Três regras de serviço distintas foram simuladas:
  1. Não-Preemptiva: O serviço continua ininterruptamente uma vez iniciado.
  2. Preemptiva-Repetição (Preemptive-Repeat): Uma chegada de maior prioridade interrompe um trabalho de menor prioridade, que deve reiniciar do início ao retomar.
  3. Preemptiva-Resumo (Preemptive-Resume): Uma chegada de maior prioridade interrompe um trabalho de menor prioridade, que retoma do ponto de interrupção.
• Recursos (Features): Duas configurações de recursos foram testadas:
  1. Conjunto de Quatro Recursos: Tempo de chegada, tempo entre chegadas, classe de prioridade e comprimento da fila na chegada.
  2. Conjunto de Dois Recursos: Classe de prioridade e comprimento da fila na chegada apenas.

Modelos Avaliados

Cinco modelos de aprendizado de máquina foram comparados:

1. Gradient Boosting Machine (GBM): Um ensemble padrão de árvores de decisão.
2. Forced Priority-Split GBM (FS-GBM): Uma variante onde o conjunto de dados é dividido rigidamente por classe de prioridade antes do treinamento de modelos GBM separados.
3. Random Forest (RF): Um ensemble padrão de árvores de decisão decorrelacionadas.
4. Forced Priority-Split RF (FS-RF): Uma variante com modelos RF separados treinados para cada classe de prioridade.
5. Rede Neural Recorrente (RNN): Uma arquitetura baseada em LSTM projetada para capturar dependências temporais na sequência de chegadas de clientes dentro de um dia.

O desempenho foi avaliado usando Erro Médio Absoluto (MAE), Erro Quadrático Médio (MSE), Raiz do Erro Quadrático Médio (RMSE) e o coeficiente de determinação ($R^2$).

Principais Contribuições

• Estrutura Unificada: O estudo fornece um framework de simulação unificado para gerar dados transientes através de disciplinas não-preemptivas, preemptivas-repetição e preemptivas-resumo com chegadas variantes no tempo.
• Avaliação de Estruturas Conscientes de Prioridade: O artigo testa explicitamente se a divisão rígida de dados por classe de prioridade (FS-GBM, FS-RF) melhora a predição em relação aos modelos padrão que tratam a prioridade como um recurso.
• Viabilidade de Informação Mínima: A pesquisa demonstra que a predição precisa do tempo de espera é alcançável usando apenas dois inputs (comprimento da fila e prioridade), desafiando a suposição de que parâmetros detalhados do sistema são necessários para abordagens baseadas em dados.
• Análise Comparativa: Oferece uma comparação abrangente entre ensembles baseados em árvores e modelos de aprendizado profundo baseados em sequências no contexto de filas de prioridade.

Resultados

Desempenho dos Modelos

• Superioridade da RNN: A Rede Neural Recorrente (LSTM) alcançou consistentemente a maior precisão em todas as três disciplinas de serviço e ambas as configurações de recursos. Demonstrou capacidade de modelar dinâmicas temporais complexas, particularmente em cenários preemptivos onde interrupções de serviço criam dependências intrincadas.
  • No cenário não-preemptivo (4 recursos), a RNN alcançou um $R^2$ de 0,987, comparado a ~0,94 para os modelos baseados em árvores.
  • No cenário de preemptiva-resumo (o cenário mais complexo), a RNN manteve um $R^2$ de 0,987, enquanto os modelos baseados em árvores caíram para ~0,927.
• Estabilidade dos Modelos Baseados em Árvores: Os modelos GBM e Random Forest forneceram um desempenho estável e competitivo, particularmente em cenários não-preemptivos. No entanto, mostraram redução de precisão em cenários preemptivos em comparação com a RNN.
• Ineficácia da Divisão Forçada: As variantes "Forced Priority-Split" (FS-GBM e FS-RF) ofereceram melhorias apenas marginais e inconsistentes sobre seus respectivos modelos padrão. Os autores concluem que modelos de árvore padrão já são capazes de aprender implicitamente não-linearidades específicas de prioridade quando a prioridade é incluída como um recurso de entrada, tornando a divisão rígida explícita desnecessária.

Redução de Recursos

A redução dos recursos de entrada de quatro para dois (removendo o tempo de chegada e o tempo entre chegadas) resultou em apenas uma diminuição moderada no desempenho.

• A RNN manteve um forte poder preditivo mesmo com inputs mínimos, alcançando um $R^2$ de 0,974 no caso não-preemptivo e 0,972 no caso preemptivo-resumo com apenas dois recursos.
• Os modelos baseados em árvores também permaneceram estáveis, sugerindo que o comprimento da fila e a prioridade codificam a maior parte da informação preditiva necessária.

Significância e Alegações

O artigo afirma que o aprendizado de máquina, particularmente modelos baseados em sequências como RNNs, oferece uma alternativa prática e poderosa aos métodos analíticos tradicionais para a predição de tempo de espera em tempo real em sistemas de serviço baseados em prioridade.

• Implementabilidade Prática: A descoberta de que predições precisas são possíveis usando apenas o comprimento da fila e a prioridade é destacada como uma grande vantagem prática. Em muitos sistemas do mundo real (ex: hospitais, centros de atendimento), funções de taxa de chegada detalhadas ou distribuições de serviço são desconhecidas ou difíceis de estimar, mas o comprimento da fila e a prioridade são prontamente observáveis.
• Lidando com Preempção: O estudo demonstra que modelos de ML podem capturar efetivamente os efeitos complexos da preempção (tanto repetição quanto resumo) sem a necessidade de modelar explicitamente a lógica de interrupção, uma tarefa analiticamente desafiadora.
• Seleção de Modelo: Embora as RNNs sejam identificadas como as mais eficazes para capturar dinâmicas temporais em sistemas preemptivos, os modelos baseados em árvores são apresentados como alternativas confiáveis, estáveis e computacionalmente eficientes, especialmente quando a interpretabilidade ou uma arquitetura mais simples é preferida.
• Limitações de Modificações Estruturais: O artigo conclui modestamente que forçar explicitamente divisões de prioridade não melhora significativamente o desempenho, sugerindo que os métodos de ensemble modernos são robustos o suficiente para lidar com a heterogeneidade de prioridade através da inclusão padrão de recursos.

Os autores enfatizam que seu trabalho faz a ponte entre a teoria de filas clássica e a predição moderna baseada em dados, oferecendo um framework adequado para sistemas com disponibilidade limitada de dados e condições operacionais dinâmicas.