Dynamic Scheduling of a Parallel-Server Queueing System: A Computational Method for High-Dimensional Problems

Resumo Técnico: Agendamento Dinâmico de um Sistema de Filas com Servidores Paralelos

Definição do Problema
O artigo aborda o desafio operacional do roteamento baseado em habilidades em sistemas de filas com servidores paralelos em grande escala, como call centers. O problema central envolve tomar decisões em tempo real sobre qual classe de clientes em espera deve ser atendida por qual agente disponível. Em sistemas com muitas classes de clientes e estações de serviço, o espaço de estados torna-se de alta dimensão, tornando os métodos padrão de programação dinâmica computacionalmente intratáveis devido à "maldição da dimensionalidade". Os autores concentram-se no regime de tráfego intenso Halfin–Whitt e em um critério de custo descontado de horizonte infinito, visando desenvolver um método computacional escalável para esses cenários de alta dimensão.

Metodologia
A abordagem proposta preenche a lacuna entre limites teóricos de tráfego intenso e computação prática através das seguintes etapas:

1. Aproximação por Difusão: Os autores formulam um problema de controle browniano aproximado (BCP) derivado do modelo original de filas de fluxo discreto sob o regime assintótico Halfin–Whitt. Isso envolve escalar o estado do sistema e os processos de controle para derivar um processo de difusão limite governado por uma equação diferencial estocástica.
2. Formulação Hamilton-Jacobi-Bellman (HJB): O problema de controle ótimo para o BCP é caracterizado por uma equação diferencial parcial semilinear (EDP), especificamente a equação HJB. A solução dessa EDP fornece a função valor e seu gradiente, que são necessários para construir uma política ótima.
3. Solução Baseada em Aprendizado Profundo: Reconhecendo que métodos numéricos tradicionais (por exemplo, métodos de elementos finitos) falham em altas dimensões, os autores adaptam o framework de aprendizado profundo de Han et al. (2018) para resolver EDPs semilineares.
   • Identidade Estocástica: Eles derivam uma identidade estocástica específica (Proposição 1) equivalente à equação HJB. Essa identidade liga a função valor e seu gradiente aos termos de deriva, difusão e custo do sistema através de uma representação de equação diferencial estocástica reversa (EDSR).
   • Aproximação por Rede Neural: A função valor $V(x)$ e seu gradiente $\nabla V(x)$ são aproximados por redes neurais profundas.
   • Função de Perda: Uma função de perda é construída com base na discrepância na identidade estocástica derivada sobre trajetórias de amostra simuladas de uma política de referência. Os parâmetros da rede são otimizados usando descida de gradiente estocástica para minimizar essa perda.
   • Construção da Política: Uma vez treinada a rede de gradiente, a política para o sistema original (pré-limite) é construída resolvendo um programa linear em cada estado. Esse programa linear maximiza um termo derivado do supremo da equação HJB, utilizando os valores de gradiente aprendidos como coeficientes.

Principais Contribuições

• Framework Computacional Escalável: A contribuição principal é um método computacional capaz de resolver problemas de agendamento dinâmico em sistemas de servidores paralelos de alta dimensão (até 100 classes de clientes), um regime onde as técnicas padrão de MDP são inviáveis.
• Tratamento de Atividades Não Básicas: Ao contrário de trabalhos teóricos anteriores (por exemplo, Atar, 2005a) que frequentemente restringem a análise a atividades "básicas" e assumem conservação conjunta de trabalho (JWC), este método acomoda redes gerais de servidores paralelos onde atividades não básicas podem ser utilizadas e a JWC pode não valer.
• Calibração Orientada por Dados: O método é calibrado e testado usando dados do mundo real de um grande call center de um banco dos EUA, garantindo que as instâncias de teste reflitam parâmetros operacionais realistas, incluindo taxas de chegada, taxas de serviço, taxas de abandono e estruturas de custo.
• Integração de Conhecimento de Domínio: A abordagem incorpora insights específicos do domínio, como a geração de trajetórias de amostra representativas e a imposição de restrições de forma na função valor e em seu gradiente, para melhorar a qualidade da solução.

Resultados
Os autores avaliam a política proposta contra políticas de referência (incluindo as regras $c\mu$, $c\mu/\theta$, Fastest-Server-First e G-$c\mu$) em vários problemas de teste:

• Problemas de Baixa Dimensão: Para problemas de teste bidimensionais onde políticas ótimas podem ser computadas via técnicas padrão de MDP, a política baseada em rede neural proposta desempenha-se em par com a política ótima, com lacunas de otimalidade inferiores a 1%.
• Problemas de Alta Dimensão: Para o principal problema de teste de 13 dimensões (baseado nos dados do banco) e um problema de teste de 100 dimensões, onde políticas ótimas são desconhecidas, a política proposta supera consistentemente os melhores benchmarks disponíveis.
  • Na variante de 13 dimensões, a política proposta melhora o desempenho em aproximadamente 2% sobre o melhor benchmark.
  • No problema de 100 dimensões, a melhoria é de aproximadamente 7% sobre o melhor benchmark.
• Insights Comportamentais: O estudo revela que em topologias de rede esparsas, políticas ótimas podem violar a propriedade de conservação conjunta de trabalho e utilizar atividades não básicas significativamente. O método proposto captura esses comportamentos naturalmente, enquanto restringir políticas a atividades básicas ou impor JWC pode excluir estratégias ótimas.

Significado e Alegações
O artigo alega fornecer um framework computacional escalável e orientado por dados para gerenciar sistemas de serviço de alta dimensão que são grandes demais para métodos exatos. Oferece aos gestores uma ferramenta para melhorar decisões de roteamento em tempo real e avaliar políticas antes da implementação. Os autores posicionam seu trabalho como uma generalização significativa da literatura existente, movendo-se de modelos teóricos de baixa dimensão e restritivos para aplicações práticas de alta dimensão. Eles enfatizam que seu método não assume conservação conjunta de trabalho nem restringe atividades a conjuntos "básicos", oferecendo assim uma representação mais flexível e potencialmente mais precisa de sistemas de serviço complexos. O artigo conclui que a abordagem proposta é computacionalmente viável para sistemas com 100 ou mais classes distintas de clientes, uma escala anteriormente inatingível para otimização dinâmica neste contexto.