🔢 mathematics

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

Este artículo aborda el problema de la programación dinámica en una cola M/G/N con tiempos de servicio generales y tiempos de abandono IHR mediante la demostración de la indexabilidad del problema de tiempo discreto asociado, la derivación de un índice de Whittle explícito y la demostración, a través de simulaciones, de que la política resultante supera sistemáticamente a la regla estándar $c\mu/\theta$ .

Autores originales: Samuli Aalto

Publicado 2026-07-28

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Samuli Aalto

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina una cafetería con mucha actividad donde los clientes hacen fila para recibir sus bebidas, pero hay un giro: cada cliente tiene un temporizador secreto. Si esperan demasiado, se frustran y se van sin comprar nada. Los baristas (los servidores) tienen que decidir a quién atender a continuación. ¿Deberían atender a la persona que lleva esperando más tiempo? ¿A la que solo necesita un espresso rápido? ¿O a la que está a punto de rendirse y marcharse? Este es el corazón de un problema llamado "programación" (scheduling), una rama de las matemáticas y la informática que determina la mejor manera de organizar tareas cuando los recursos son limitados y el tiempo corre en contra.

En el mundo de la programación, hay dos tipos principales de costos que preocupan. Primero, está el "costo de mantenimiento" (holding cost), que es como la energía y la paciencia perdidas mientras un cliente espera en la fila. Segundo, está la "penalización por abandono", que es la venta perdida y la mala reputación cuando un cliente se va enfadado. Durante décadas, los matemáticos han intentado resolver este rompecabezas, pero generalmente hacían una gran simplificación: asumían que los tiempos de servicio (cuánto tarda una bebida) y los tiempos de paciencia (cuánto espera un cliente) seguían un patrón simple y predecible llamado "distribución exponencial". Piensa en esto como asumir que cada lanzamiento de moneda es perfectamente aleatorio e independiente. Aunque esto facilita las matemáticas, no refleja la vida real, donde algunas tareas toman muchísimo tiempo y algunas personas son increíblemente pacientes o increíblemente impacientes.

Este artículo, escrito por Samuli Aalto, aborda la versión desordenada y real de este problema. En lugar de asumir patrones simples y predecibles, el autor permite cualquier tipo de tiempo de servicio (como un latte complejo que tarda una eternidad) y un tipo específico de impaciencia llamado "IHR" (Tasa de Riesgo Creciente). IHR es una forma elegante de decir que cuanto más esperas, más probable es que te hartes y te vayas, tal como un ser humano real se enfada más cuanto más lento avanza la fila. El artículo utiliza una herramienta matemática ingeniosa llamada "índice de Whittle" para determinar el mejor orden de atención. El principal hallazgo es que este nuevo método, que maneja estos escenarios complejos del mundo real, supera consistentemente a la vieja regla de oro (llamada regla $c\mu/\theta$ ) en simulaciones por computadora. El autor demuestra que su nueva fórmula es matemáticamente sólida para una versión simplificada del problema y luego muestra, mediante simulaciones, que ahorra más dinero y mantiene a más clientes contentos que los métodos anteriores.

La historia de la fila impaciente

Imagina una caótica fila de seguridad en un aeropuerto. Tienes un equipo de oficiales de seguridad (los servidores) y un flujo de viajeros (los clientes). Cada viajero tiene dos relojes invisibles funcionando. Un reloj cuenta hacia atrás su tiempo de servicio —cuánto tarda en escanear su maleta y revisar su identificación—. El otro reloj cuenta hacia atrás su tiempo de paciencia —cuánto tiempo está dispuesto a permanecer allí antes de decidir saltarse el vuelo e irse a casa—.

En los viejos tiempos, los matemáticos que modelaban esta fila asumían que ambos relojes bajaban de una manera muy específica y "sin memoria". Era como decir que, sin importar cuánto tiempo hayas estado allí, tu probabilidad de irte en el próximo minuto es exactamente la misma que cuando acababas de llegar. Esta es la suposición "exponencial". Es un truco útil para las matemáticas, pero no es cómo se comportan las personas reales. En la realidad, si has estado esperando 20 minutos, es mucho más probable que te marches enfadado en el siguiente minuto que si acabaras de llegar. Esto es lo que el artículo llama IHR (Tasa de Riesgo Creciente): cuanto más esperas, mayor es el riesgo de que te rindas.

El autor también se dio cuenta de que los tiempos de servicio reales no siempre son sencillos. A veces un escaneo de equipaje es instantáneo; otras veces, toma una eternidad debido a un cierre extraño en una maleta. El artículo permite tiempos de servicio generales, lo que significa que las matemáticas pueden manejar cualquier forma de tiempo de espera, desde lo rápido y fácil hasta lo largo y complicado.

La fórmula mágica: El índice de Whittle

Entonces, ¿cómo decides a quién atender? El artículo introduce un "índice de Whittle" como una tarjeta de puntuación para cada persona en la fila. Esta puntuación no se trata solo de quién ha esperado más tiempo (x). Es un cálculo complejo que observa:

Cuánto tiempo han esperado ya (x).
Cuánta atención/servicio han recibido ya (y).
Cuánto cuesta mantenerlos esperando (costo de mantenimiento).
Cuánto cuesta si se van (penalización por abandono).

El autor demuestra que para una versión simplificada de este problema (un sistema "cerrado" donde no llegan personas nuevas), esta tarjeta de puntuación es matemáticamente perfecta. Es "indexable", una forma elegante de decir que puedes clasificar a todos desde un "¡atiéndeme ahora!" hasta un "esperaré un poco".

El artículo luego toma esta tarjeta de puntuación y la adapta para el mundo real y continuo donde la gente llega constantemente. La fórmula resultante, $W_k(x, y)$ , es un poco intimidante de ver, pero esencialmente pregunta: "Si atiendo a esta persona durante un tiempo ínfimo, ¿cuánto dinero ahorraré en comparación con el riesgo de que se vaya?".

El enfrentamiento: Nuevo vs. Viejo

Para ver si este nuevo "Política de Índice de Whittle" (WHI) realmente funciona, el autor realizó miles de simulaciones por computadora. Configuró un aeropuerto virtual con dos tipos de viajeros:

Clase 1: Trabajos cortos (escaneos rápidos) pero con niveles de paciencia variables.
Clase 2: Trabajos largos (escaneos complejos) con diferentes niveles de paciencia.

Probaron cuatro escenarios diferentes mezclando los tipos de tiempos de servicio (algunos eran uniformes, otros eran "Pareto", lo que significa que unos pocos tardan una eternidad) y el costo de abandono (a veces es barato perder a un cliente, otras veces es una pérdida enorme).

Los resultados fueron claros. La política del Índice de Whittle superó sistemáticamente a la antigua norma estándar, conocida como la regla $c\mu/\theta$ .

En el escenario "Uniforme-Uniforme" (donde todos son algo predecibles), la nueva política ahorró entre un 12% y un 19% más en costos que la vieja regla.
En el escenario "Uniforme-Pareto" (donde algunas personas tienen tiempos de servicio muy largos e impredecibles), la brecha se amplió. La nueva política ahorró entre un 33% y un 42% más que la vieja regla.
Incluso en los escenarios más complicados, la nueva política fue consistentemente mejor, superando a veces la vieja regla por un 52%.

El artículo también comparó el nuevo método con otras estrategias comunes como "Primero en llegar, primero en ser atendido" (First-Come-First-Served, atender primero a la persona más antigua) y "Distribución de Procesador" (Processor-sharing, dividir el tiempo del servidor equitativamente entre todos). El Índice de Whittle venció a todos.

Por qué esto importa

La idea clave es que al dejar ir las suposiciones de "perfección aleatoria" y abrazar la realidad desordenada de cómo las personas realmente se impacientan, podemos construir sistemas mucho mejores. Ya sea una cafetería, un centro de llamadas o una red informática procesando datos, usar esta nueva fórmula significa menos clientes enfadados que se van, menos tiempo desperdiciado y más dinero ahorrado. El autor no solo lo supuso; demostró que las matemáticas funcionan para la versión simplificada y mostró, mediante rigurosas simulaciones, que funciona de maravilla en la compleja versión del mundo real. Es un recordatorio de que, a veces, la mejor manera de resolver un problema es dejar de pretender que el mundo es más simple de lo que realmente es.

Resumen Técnico: Programación casi óptima con tiempos de servicio generales y tiempos de abandono IHR

Planteamiento del Problema
Este artículo aborda el problema de la programación dinámica dentro de un sistema de colas $M/G/N$ de múltiples clases que presenta clientes impacientes. El sistema consta de $N$ servidores paralelos homogéneos y múltiples clases de clientes. Cada cliente posee un tiempo de servicio aleatorio y un tiempo de abandono aleatorio; si un cliente permanece en el sistema (esperando o en servicio) más allá de su tiempo de abandono, se retira sin completar el servicio.

El objetivo es determinar una política de programación no anticipatoria (que permita la preemción) que minimice el costo esperado total. Esta función de costo comprende dos componentes:

Costos de mantenimiento: Acumulados a una tasa $h_k$ para los clientes de la clase- $k$ mientras permanecen en el sistema.
Penalizaciones por abandono: Una penalización de suma fija $d_k$ incurrida si un cliente de la clase- $k$ abandona el sistema antes de completar el servicio.

Aunque la literatura existente suele asumir distribuciones exponenciales tanto para los tiempos de servicio como para los de abandono, las soluciones exactas siguen siendo esquivas excepto en casos especiales. Los enfoques casi óptimos previos, como los métodos de escalado de fluidos que derivan en la regla $c\mu/\theta$ , dependen fuertemente de estas restrictivas suposiciones exponenciales. Este artículo pretende generalizar el problema permitiendo distribuciones de tiempo de servicio generales y tiempos de abandono de Tasa de Riesgo Creciente (IHR, por sus siglas en inglés), una suposición natural donde la probabilidad de abandono aumenta con el tiempo transcurrido en el sistema.

Metodología
Los autores emplean el enfoque del índice de Whittle, un método heurístico diseñado originalmente para problemas de bandidos sin descanso (restless bandits), que son generalmente intratables desde el punto de vista matemático. La metodología procede a través de las siguientes etapas:

Formulación en Tiempo Discreto: El problema se modela primero en tiempo discreto con costos descontados. El sistema se trata como una versión cerrada (número finito de clientes, sin nuevas llegadas) para facilitar el análisis. El estado de un cliente se define mediante un par bidimensional $(x, y)$ , donde $x$ es el tiempo total transcurrido en el sistema e $y$ es el servicio alcanzado.
Relajación e Indexabilidad: La restricción estricta de capacidad (servir a lo sumo $N$ clientes) se relaja a una restricción de tiempo promedio. Esto transforma el problema en un conjunto de subproblemas separables (uno por cliente). Los autores demuestran que este problema relajado es indexable, lo que significa que existe un umbral (el índice de Whittle) para el "precio del trabajo" $\nu$ tal que es óptimo servir a un cliente si y solo si su índice supera a $\nu$ .
Derivación del Índice: Un desafío teórico significativo es el espacio de estados bidimensional, que carece del orden natural encontrado en los problemas unidimensionales. Los autores derivan una expresión explícita para el índice de Whittle en el entorno de tiempo discreto, denotado como $W_{k,\beta}(x, y)$ , que involucra una maximización sobre un horizonte de tiempo $\Delta$ .
Límite de Tiempo Continuo: Los resultados de tiempo discreto se extienden al sistema abierto original de tiempo continuo. Al hacer que el intervalo de tiempo tienda a cero y escalar las probabilidades, los autores derivan el índice de Whittle en tiempo continuo $W_k(x, y)$ .

Contribuciones Clave

Generalización de Suposiciones: El artículo elimina la restrictiva suposición de tiempos de servicio exponenciales, acomodando distribuciones generales, mientras asume IHR para los tiempos de abandono.
Prueba Teórica de Indexabilidad: Los autores demuestran que la versión cerrada en tiempo discreto del problema es indexable. Este es un resultado no trivial dado el espacio de estados bidimensional $(x, y)$ , que complica las pruebas estándar que dependen del orden de los estados.
Fórmula Explícita del Índice: Se deriva una expresión explícita para el índice de Whittle para el caso general:
$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]}$
El artículo también identifica condiciones específicas bajo las cuales este índice se simplifica a formas conocidas (por ejemplo, cuando los tiempos de servicio son de Tasa de Riesgo Decreciente (DHR) o cuando los tiempos de abandono son exponenciales).
Definición de la Política: Se define una política de índice de Whittle (WHI) para el entorno de tiempo continuo: en cualquier momento $t$ , el programador sirve a los $N$ clientes con los índices de Whittle más altos.

Resultados
El desempeño de la política de índice de Whittle propuesta (WHI) se evalúa frente a la conocida regla $c\mu/\theta$ (CMTH) y otras políticas estándar (FCFS, Procesamiento Compartido, Forward-Backward) mediante simulaciones numéricas en una cola $M/G/1$ de dos clases.

Desempeño Superior Sistemático: A través de varios entornos experimentales que involucran diferentes combinaciones de distribuciones de tiempo de servicio (Uniforme/IHR y Pareto/DHR) y estructuras de costos, la política WHI supera sistemáticamente a la regla $c\mu/\theta$ y a otras políticas base.
Sensibilidad a la Forma de la Distribución: Las simulaciones demuestran que la brecha de desempeño entre WHI y CMTH se amplía significativamente cuando los tiempos de servicio siguen distribuciones de cola pesada (DHR) (por ejemplo, Pareto). En estos escenarios, la regla $c\mu/\theta$ , que asume tiempos de servicio exponenciales, puede desempeñarse sustancialmente peor (por ejemplo, con diferencias de costo relativo que superan el 40-50% en algunos escenarios de carga pesada).
Robustez: La política WHI mantiene un desempeño superior independientemente de si se enfatizan los costos de abandono o los costos de mantenimiento, y a través de diversas cargas del sistema ( $\rho \in [1.0, 2.0]$ ).

Significado
El artículo sostiene que su principal significancia radica en extender la aplicabilidad del enfoque del índice de Whittle a un entorno de programación más realista y complejo. Al demostrar la indexabilidad y derivar el índice para tiempos de servicio generales y abandono IHR, el trabajo proporciona una heurística teóricamente fundamentada para problemas donde las soluciones exactas no están disponibles. Los resultados numéricos sugieren que confiar en suposiciones exponenciales (como en la regla $c\mu/\theta$ ) puede conducir a decisiones de programación subóptimas, particularmente cuando los tiempos de servicio no son exponenciales, y que la política de índice de Whittle derivada ofrece una alternativa robusta y casi óptima.

La historia de la fila impaciente

La fórmula mágica: El índice de Whittle

El enfrentamiento: Nuevo vs. Viejo

Por qué esto importa

Más como este