Programar tareas en la nube cuando la capacidad cambia: nuevos algoritmos que garantizan rendimiento

En la práctica diaria de los centros de datos, la capacidad de cómputo no es fija: máquinas se apagan por fallos, mantenimiento o limitaciones de energía, y tareas de alta prioridad pueden reservar recursos en cualquier momento.

Ese paisaje cambiante complica la programación de trabajos “no preemptivos” —aquellos que, si se interrumpen, pierden todo el progreso— y plantea preguntas concretas: ¿cuándo conviene empezar un trabajo largo? ¿es mejor esperar una ventana segura para no desperdiciar tiempo?

El 11 de febrero de 2026, Manish Purohit (Google Research) publicó en el blog de Google Research un trabajo presentado en la conferencia SPAA 2025 que aborda exactamente ese problema: “Non-preemptive Throughput Maximization under Time-varying Capacity”.

El estudio ofrece algoritmos con garantías matemáticas (aproximaciones y razones de competencia) para maximizar el “throughput” —es decir, la suma de los valores o el número de trabajos completados— cuando la capacidad disponible varía con el tiempo.

Qué problema abordan

Los investigadores modelan una máquina o clúster cuya capacidad cambia en el tiempo y un conjunto de trabajos, cada uno con cuatro atributos: tiempo de llegada (release time), fecha límite (deadline), duración (processing time) y valor o peso (weight).

El objetivo es elegir y programar trabajos de manera que cada uno se ejecute de forma continua dentro de su ventana válida y la cantidad de trabajos concurrentes nunca supere la capacidad disponible en cada instante.

Para reflejar situaciones reales se estudian dos entornos: el “offline”, donde se conoce de antemano la llegada de trabajos y los cambios de capacidad, y el “online”, donde los trabajos llegan en tiempo real y las decisiones son irrevocables (aunque la capacidad prevista sí es conocida).

Hallazgos clave

• Offline (planificación con todo conocido): cuando todos los trabajos tienen igual valor, una estrategia simple llamada Greedy —que elige iterativamente el trabajo que terminaría antes— garantiza completar al menos la mitad de los trabajos que completaría una solución óptima (1/2‑aproximación). Si los trabajos tienen valores distintos, el equipo desarrolla un enfoque primal‑dual que alcanza una 1/4‑aproximación.
• Online (decisiones en tiempo real): el reto es mayor. En el modelo estricto sin posibilidad de reiniciar trabajos, algoritmos online pueden fracasar —su rendimiento frente al óptimo puede caer a cero en peores casos. Para hacerlo manejable se analizan dos variantes que permiten interrupciones:
• Interrupción con reinicios: el trabajo interrumpido pierde el progreso pero puede volver a intentarse; aquí una variante de Greedy sigue logrando una razón de competencia de 1/2.
• Interrupción sin reinicios (el trabajo interrumpido se pierde): en general, el problema es imposible de resolver bien online, salvo en el caso práctico en el que todos los trabajos comparten una misma fecha límite (por ejemplo, procesos nocturnos). Para ese escenario los autores diseñan un algoritmo que mantiene una “programación tentativa” y, al llegar cada trabajo nuevo, aplica una de cuatro acciones (añadir, reemplazar otro trabajo futuro si el nuevo es mucho más corto, interrumpir el trabajo en ejecución si conviene, o descartar). Generalizado a perfiles de capacidad arbitrarios, este método obtiene una razón de competencia de 1/11 (~9% del óptimo en el peor caso), la primera garantía constante para este problema en ese modelo.

Cómo funciona, con un ejemplo sencillo

Los autores usan la analogía de un restaurante: mesas reservadas por clientes VIP en distintos momentos dejan “capacidad sobrante” para otros comensales.

Si una mesa es ocupada por un cliente que tarda mucho en comer, puede impedir atender a varios clientes rápidos luego.

El algoritmo debe decidir si sentar a ese cliente largo ahora (riesgo de perder mesas futuras) o esperar una ventana más segura.

En la variante con reinicios, puedes pedirle al comensal que deje la mesa temporalmente y volver a intentarlo; en la variante sin reinicios, si se levanta la mesa y se va, el comensal se pierde.

Relevancia y límites

El trabajo adapta modelos teóricos a la dinámica real de infraestructuras en la nube y proporciona herramientas con garantías formales que pueden servir de base para programadores de recursos en centros de datos.

Los autores reconocen límites: la garantía online de 1/11 está lejos del límite teórico de 1/2, por lo que existen oportunidades para mejorar algoritmos (p. ej., con aleatoriedad o conocimiento imperfecto futuro de la capacidad).

Autoría y colaboración

El artículo fue firmado por Manish Purohit (Research Scientist, Google Research) y es trabajo conjunto con Aniket Murhekar (University of Illinois at Urbana‑Champaign), Zoya Svitkina (Google Research), Erik Vee (Google Research) y Joshua Wang (Google Research).

El estudio fue presentado en SPAA 2025 y tiene versión de artículo disponible (DOI en la nota original).

Nota de Transparencia

Esta nota fue generada 100% con IA. La fuente fue aprobada por Diario Occidente y el contenido final fue revisado por un miembro del equipo de redacción.

🔊 El Resumen de Noticias sobre Inteligencia Artificial e Innovación Tecnológica, aquí 👇🏻

Curaduría editorial

La curaduría y revisión editorial de estas notas está a cargo de Rosa María Agudelo Ayerbe, comunicadora social y periodista, con maestría en Transformación Digital y especialización en Inteligencia Artificial.

Desde su rol como líder del equipo de innovación y transformación digital del Diario Occidente, y a través de la unidad estratégica DO Tech, realiza un seguimiento permanente a las principales novedades en tecnología e inteligencia artificial a nivel global.

Estas notas se apoyan en un agente de investigación basado en inteligencia artificial, diseñado para monitorear semanalmente avances, lanzamientos y debates clave del sector.

El contenido es posteriormente leído, analizado, contextualizado y validado editorialmente antes de su publicación.

Este proceso forma parte del mecanismo de actualización continua que permite interpretar los desarrollos tecnológicos desde una mirada periodística, crítica y comprensible para audiencias no especializadas.

Comments