🔢 mathematics

Near-optimal scheduling with general service times and IHR abandonment times

Este artigo aborda o problema de escalonamento dinâmico em uma fila M/G/N com tempos de serviço gerais e tempos de abandono IHR ao provar a indexabilidade do problema discreto associado, derivar um índice de Whittle explícito e demonstrar, por meio de simulações, que a política resultante supera sistematicamente a regra padrão $c\mu/\theta$ .

Autores originais: Samuli Aalto

Publicado 2026-07-28

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Samuli Aalto

Artigo original sob licença CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine uma cafeteria movimentada onde os clientes estão fazendo fila para pedir suas bebidas, mas há um detalhe: cada cliente tem um cronômetro secreto. Se esperarem demais, ficam frustrados e vão embora sem comprar nada. Os baristas (os atendentes) têm que decidir quem atender em seguida. Devem atender a pessoa que está esperando há mais tempo? A pessoa que só precisa de um expresso rápido? Ou a pessoa que está prestes a desistir e ir embora? Este é o cerne de um problema chamado "escalonamento" (scheduling), um ramo da matemática e da ciência da computação que descobre a melhor maneira de organizar tarefas quando os recursos são limitados e o tempo está correndo.

No mundo do escalonamento, existem dois tipos principais de custos com os quais se preocupar. Primeiro, há o "custo de espera" (holding cost), que é como a energia e a paciência perdidas enquanto um cliente espera na fila. Segundo, há a "penalidade por abandono" (abandonment penalty), que é a venda perdida e a má reputação quando um cliente vai embora irritado. Durante décadas, matemáticos tentaram resolver esse quebra-cabeça, mas geralmente faziam uma grande simplificação: eles assumiam que os tempos de serviço (quanto tempo leva uma bebida) e os tempos de paciência (quanto tempo uma pessoa espera) seguiam um padrão simples e previsível chamado "distribuição exponencial". Pense nisso como assumir que cada lançamento de moeda é perfeitamente aleatório e independente. Embora isso facilite a matemática, não reflete a vida real, onde algumas tarefas levam muito tempo e algumas pessoas são incrivelmente pacientes ou incrivelmente impacientes.

Este artigo, escrito por Samuli Aalto, aborda a versão desordenada e real deste problema. Em vez de assumir padrões simples e previsíveis, o autor permite qualquer tipo de tempo de serviço (como um latte complexo que demora uma eternidade) e um tipo específico de impaciência chamado "IHR" (Taxa de Risco Crescente). IHR é uma forma sofisticada de dizer que, quanto mais você espera, maior a probabilidade de você se cansar e ir embora — exatamente como um ser humano real ficando mais irritado conforme a fila se move lentamente. O artigo utiliza uma ferramenta matemática astuta chamada "índice de Whittle" para descobrir a melhor ordem de atendimento. A principal descoberta é que este novo método, que lida com esses cenários complexos do mundo real, supera consistentemente a antiga regra prática (chamada de regra $c\mu/\theta$ ) em simulações de computador. O autor prova que seu novo método é matematicamente sólido para uma versão simplificada do problema e, em seguida, mostra através de simulações que ele economiza mais dinheiro e mantém mais clientes satisfeitos do que os métodos anteriores.

A História da Fila Impaciente

Imagine uma linha de segurança de aeroporto caótica. Você tem uma equipe de agentes de segurança (os servidores) e um fluxo de viajantes (os clientes). Cada viajante tem dois relógios invisíveis funcionando. Um relógio conta regressivamente seu tempo de serviço — quanto tempo leva para escanear sua bolsa e verificar seu ID. O outro relógio conta regressivamente seu tempo de paciência — quanto tempo eles estão dispostos a ficar parados ali antes de decidirem perder o voo e ir para casa.

Nos velhos tempos, matemáticos que modelavam essa fila assumiam que ambos os relógios diminuíam de uma forma muito específica e "sem memória". Era como dizer que, não importa há quanto tempo você está parado ali, sua chance de sair no próximo minuto é exatamente a mesma de quando você chegou. Esta é a suposição "exponencial". É um truque útil para a matemática, mas não é como as pessoas reais se comportam. Na realidade, se você está esperando há 20 minutos, é muito mais provável que você vá embora furioso no próximo minuto do que se tivesse acabado de chegar. Isso é o que o artigo chama de IHR (Taxa de Risco Crescente): quanto mais você espera, maior o risco de você desistir.

O autor também percebeu que os tempos de serviço reais nem sempre são simples. Às vezes, a inspeção de uma bolsa é instantânea; outras vezes, leva uma eternidade devido a um cadeado estranho em uma mala. O artigo permite tempos de serviço gerais, o que significa que a matemática pode lidar com qualquer formato de tempo de espera, desde o rápido e fácil até o longo e complicado.

A Fórmula Mágica: O Índice de Whittle

Então, como você decide quem atender? O artigo introduz o "índice de Whittle" como uma pontuação para cada pessoa na fila. Essa pontuação não é apenas sobre quem está esperando há mais tempo. É um cálculo complexo que observa:

Quanto tempo eles já esperaram (x).
Quanto serviço eles já receberam (y).
Quanto custa mantê-los esperando (custo de espera).
Quanto custa se eles forem embora (penalidade de abandono).

O autor prova que, para uma versão simplificada deste problema (um sistema "fechado" onde ninguém novo chega), essa pontuação é matematicamente perfeita. Ela é "indexável", que é uma forma elegante de dizer que você pode classificar todos, desde "atenda-me agora!" até "eu espero um pouco".

O artigo então pega essa pontuação e a adapta para o mundo contínuo e real, onde pessoas estão constantemente chegando. A fórmula resultante, $W_k(x, y)$ , é um pouco intimidante de se olhar, mas ela essencialmente pergunta: "Se eu atender esta pessoa por um tempo ínfimo, quanto dinheiro eu economizarei em comparação ao risco de ela ir embora?"

O Confronto: Novo vs. Antigo

Para ver se este novo "Políticas de Índice de Whittle" (WHI) realmente funciona, o autor realizou milhares de simulações de computador. Ele configurou um aeroporto virtual com dois tipos de viajantes:

Classe 1: Trabalhos curtos (scans rápidos), mas com níveis variados de paciência.
Classe 2: Trabalhos longos (scans complexos) com diferentes níveis de paciência.

Ele testou quatro cenários diferentes misturando os tipos de tempos de serviço (alguns eram uniformes, outros eram "Pareto", o que significa que algumas pessoas levam uma eternidade) e o custo de abandono (às vezes é barato perder um cliente, às vezes é uma perda enorme).

Os resultados foram claros. A política do Índice de Whittle superou sistematicamente a antiga regra padrão, conhecida como a regra $c\mu/\theta$ .

No cenário "Uniforme-Uniforme" (onde todos são um tanto previsíveis), a nova política economizou cerca de 12% a 19% mais em custos do que a regra antiga.
No cenário "Uniforme-Pareto" (onde algumas pessoas têm tempos de serviço muito longos e imprevisíveis), a diferença aumentou. A nova política economizou de 33% a 42% mais do que a regra antiga.
Mesmo nos cenários mais difíceis, a nova política foi consistentemente melhor, às vezes em até 52%.

O artigo também comparou o novo método com outras estratégções comuns, como "Primeiro a Chegar, Primeiro a Ser Atendido" (servir a pessoa mais antiga primeiro) e "Compartilhamento de Processador" (dividir o tempo do servidor igualmente entre todos). O novo Índice de Whittle venceu todos eles.

Por Que Isso Importa

A principal lição é que, ao abandonar as suposições de "perfeição aleatória" e abraçar a realidade desordenada de como as pessoas realmente ficam impacientes, podemos construir sistemas muito melhores. Seja uma cafeteria, uma central de atendimento ou uma rede de computadores processando dados, usar esta nova fórmula significa menos clientes irritados indo embora, menos tempo desperdiçado e mais dinheiro economizado. O autor não apenas supôs isso; ele provou que a matemática funciona para a versão simplificada e mostrou, através de simulações rigorosas, que ela funciona maravilhas na versão complexa do mundo real. É um lembrete de que, às vezes, a melhor maneira de resolver um problema é parar de fingir que o mundo é mais simples do que realmente é.

Resumo Técnico: Escalonamento quase ótimo com tempos de serviço gerais e tempos de abandono IHR

Definição do Problema
Este artigo aborda o problema de escalonamento dinâmico em um sistema de filas $M/G/N$ de múltiplas classes apresentando clientes impacientes. O sistema consiste em $N$ servidores paralelos homogêneos e múltiplas classes de clientes. Cada cliente possui um tempo de serviço aleatório e um tempo de abandono aleatório; se um cliente permanecer no sistema (esperando ou em serviço) além de seu tempo de abandono, ele sai sem concluir o serviço.

O objetivo é determinar uma política de escalonamento não antecipatória (permitindo preempção) que minimize o custo esperado total. Esta função de custo compreende dois componentes:

Custos de retenção (holding costs): Acumulados a uma taxa $h_k$ para clientes da classe- $k$ enquanto permanecem no sistema.
Penalidades de abandono: Uma penalidade de valor fixo $d_k$ incorrida se um cliente da classe- $k$ abandonar o sistema antes da conclusão do serviço.

Embora a literatura existente frequentemente assuma distribuições exponenciais tanto para os tempos de serviço quanto de abandono, soluções exatas permanecem elusivas, exceto em casos especiais. Abordagens de quase-otimalidade anteriores, como métodos de escala fluida que resultam na regra $c\mu/\theta$ , dependem fortemente dessas suposições exponenciais restritivas. Este artigo visa generalizar o problema permitindo distribuições de tempo de serviço gerais e tempos de abandono com Taxa de Risco Crescente (IHR - Increasing Hazard Rate), uma suposição natural onde a probabilidade de abandono aumenta com o tempo passado no sistema.

Metodologia
Os autores empregam a abordagem do índice de Whittle, um método heurístico originalmente projetado para problemas de bandido inquieto (restless bandit problems), que são geralmente matematicamente intratáveis. A metodologia procede através das seguintes etapas:

Formulação em Tempo Discreto: O problema é primeiro modelado em tempo discreto com custos descontados. O sistema é tratado como uma versão fechada (número finito de clientes, sem novas chegadas) para facilitar a análise. O estado de um cliente é definido por um par bidimensional $(x, y)$ , onde $x$ é o tempo total passado no sistema e $y$ é o serviço alcançado.
Relaxação e Indexabilidade: A restrição rigorosa de capacidade (atender no máximo $N$ clientes) é relaxada para uma restrição de tempo médio. Isso transforma o problema em um conjunto de subproblemas separáveis (um por cliente). Os autores provam que este problema relaxado é indexável, o que significa que existe um limiar (o índice de Whittle) para o "preço do trabalho" $\nu$ tal que é ótimo atender um cliente se, e somente se, seu índice exceder $\nu$ .
Derivação do Índice: Um desafio teórico significativo é o espaço de estados bidimensional, que carece da ordenação natural encontrada em problemas unidimensionais. Os autores derivam uma expressão explícita para o índice de Whittle no cenário de tempo discreto, denotado por $W_{k,\beta}(x, y)$ , envolvendo uma maximização sobre um horizonte de tempo $\Delta$ .
Limite de Tempo Contínuo: Os resultados de tempo discreto são estendidos ao sistema aberto original de tempo contínuo. Ao fazer o intervalo de tempo tender a zero e escalar as probabilidades, os autores derivam o índice de Whittle de tempo contínuo $W_k(x, y)$ .

Principais Contribuições

Generalização de Suposições: O artigo remove a suposição restritiva de tempos de serviço exponenciais, acomodando distribuições gerais, enquanto assume IHR para tempos de abandono.
Prova Teórica de Indexabilidade: Os autores provam que a versão fechada em tempo discreto do problema é indexável. Este é um resultado não trivial dado o espaço de estados bidimensional $(x, y)$ , que complica as provas padrão que dependem de ordenação de estado.
Fórmula Explícita do Índice: Uma expressão explícita para o índice de Whittle é derivada para o caso geral:
$W_k(x, y) = \sup_{\Delta>0} \frac{E\left[ (h_k((D_k - x) - (S_k - y)) + d_k) \mathbb{1}_{\{S_k - y < \min\{D_k - x, \Delta\}\}} \mid D_k > x, S_k > y \right]}{E[\min\{D_k - x, S_k - y, \Delta\} \mid D_k > x, S_k > y]}$
O artigo também identifica condições específicas sob as quais este índice se simplifica para formas conhecidas (por exemplo, quando os tempos de serviço são de Taxa de Risco Decrescente (DHR) ou quando os tempos de abandono são exponenciais).
Definição da Política: Uma política de índice de Whitte (WHI) é definida para o cenário de tempo contínuo: em qualquer instante $t$ , o escalonador atende os $N$ clientes com os maiores índices de Whittle.

Resultados
O desempenho da política de índice de Whittle proposta (WHI) é avaliado contra a conhecida regra $c\mu/\theta$ (CMTH) e outras políticas padrão (FCFS, Processor-Sharing, Forward-Backward) via simulações numéricas em uma fila $M/G/1$ de duas classes.

Desempenho Superior Sistemático: Em várias configurações experimentais envolvendo diferentes combinações de distribuições de tempo de serviço (Uniforme/IHR e Pareto/DHR) e estruturas de custo, a política WHI supera sistematicamente a regra $c\mu/\theta$ e outras políticas de base.
Sensibilidade à Forma da Distribuição: As simulações demonstram que a lacuna de desempenho entre WHI e CMTH aumenta significativamente quando os tempos de serviço seguem distribuições de cauda pesada (DHR) (ex: Pareto). Nesses cenários, a regra $c\mu/\theta$ , que assume tempos de serviço exponenciais, pode performar substancialmente pior (ex: diferenças de custo relativo excedendo 40-50% em alguns cenários de carga elevada).
Robustez: A política WHI mantém um desempenho superior independentemente de serem enfatizados os custos de abandono ou os custos de retenção, e através de várias cargas do sistema ( $\rho \in [1.0, 2.0]$ ).

Significância
O artigo afirma que sua principal significância reside na extensão da aplicabilidade da abordagem do índice de Whitte para um ambiente de escalonamento mais realista e complexo. Ao provar a indexabilidade e derivar o índice para tempos de serviço gerais e abandono IHR, o trabalho fornece uma heurística teoricamente fundamentada para problemas onde soluções exatas não estão disponíveis. Os resultados numéricos sugerem que confiar em suposições exponenciais (como na regra $c\mu/\theta$ ) pode levar a decisões de escalonamento subótimas, particularmente quando os tempos de serviço não são exponenciais, e que a política de índice de Whitte derivada oferece uma alternativa robusta e quase ótima.

A História da Fila Impaciente

A Fórmula Mágica: O Índice de Whittle

O Confronto: Novo vs. Antigo

Por Que Isso Importa

Mais como este