La programación estocástica se refiere a problemas de programación que involucran atributos aleatorios, como tiempos de procesamiento aleatorios, fechas de vencimiento aleatorias, pesos aleatorios y averías estocásticas de la máquina. Las principales aplicaciones surgen en sistemas de fabricación, sistemas informáticos, sistemas de comunicación, logística y transporte, aprendizaje automático, etc.
Introducción
El objetivo de los problemas de programación estocásticos pueden ser objetivos regulares, como minimizar el tiempo de flujo total, el tiempo de espera o el costo total de tardanza por no cumplir con las fechas de vencimiento; o pueden ser objetivos irregulares, como minimizar los costos de anticipación y tardanza para completar los trabajos, o el costo total de programar tareas ante la probable llegada de un evento desastroso como un tifón severo. [1]
El desempeño de dichos sistemas, evaluado por una medida de desempeño regular o una medida de desempeño irregular, puede verse significativamente afectado por la política de programación adoptada para priorizar en el tiempo el acceso de los trabajos a los recursos. El objetivo de la programación estocástica es identificar políticas de programación que puedan optimizar el objetivo.
Los problemas de programación estocástica se pueden clasificar en tres grandes tipos: problemas relacionados con la programación de un lote de trabajos estocásticos, problemas de bandidos de múltiples brazos y problemas relacionados con la programación de sistemas de colas [2] . Estos tres tipos se basan generalmente en el supuesto de que se dispone de información completa en el sentido de que las distribuciones de probabilidad de las variables aleatorias involucradas se conocen de antemano. Cuando tales distribuciones no están completamente especificadas y hay múltiples distribuciones en competencia para modelar las variables aleatorias de interés, el problema se denomina información incompleta. El método bayesiano se ha aplicado para tratar problemas de programación estocástica con información incompleta.
Programación de un lote de trabajos estocásticos
En esta clase de modelos, un lote fijo de Los trabajos con tiempos de proceso aleatorios, cuyas distribuciones son conocidas, deben ser completados por un conjunto de máquinas para optimizar un determinado objetivo de rendimiento.
El modelo más simple de esta clase es el problema de secuenciar un conjunto de trabajos en una sola máquina para minimizar el tiempo de flujo ponderado esperado. Los tiempos de procesamiento del trabajo son variables aleatorias independientes con una distribución general con media para trabajo . Las políticas admisibles deben ser no anticipativas (las decisiones de programación se basan en el historial del sistema hasta el momento actual inclusive) y no preventivas (el procesamiento de un trabajo debe continuar ininterrumpidamente hasta su finalización una vez iniciado).
Dejar denotar la tasa de costo incurrida por unidad de tiempo en el sistema para el trabajo , y deja denotar su tiempo de finalización aleatorio. Dejar denotar la clase de todas las políticas admisibles, y dejar denotar expectativa bajo la política . El problema se puede plantear como
La solución óptima en el caso determinista especial viene dada por la regla del tiempo de procesamiento ponderado más corto de Smith: [3] secuencia de trabajos en orden no creciente del índice de prioridad. La extensión natural de la regla de Smith también es óptima para el modelo estocástico anterior. [4]
En general, la regla que asigna mayor prioridad a los trabajos con un tiempo de procesamiento esperado más corto es óptima para el objetivo de tiempo de flujo bajo los siguientes supuestos: cuando todas las distribuciones del tiempo de procesamiento del trabajo son exponenciales; [5] cuando todos los trabajos tienen una distribución general del tiempo de procesamiento común con una función de tasa de riesgo no decreciente; [6] y cuando las distribuciones del tiempo de procesamiento del trabajo se ordenan estocásticamente. [7]
Problemas de bandidos armados múltiples
Los modelos de bandidos de múltiples brazos forman un tipo particular de asignación óptima de recursos (generalmente trabajando con asignación de tiempo), en el que se asignan varias máquinas o procesadores para servir a un conjunto de proyectos en competencia (denominados armas). En el marco típico, el sistema consta de una sola máquina y un conjunto de proyectos estocásticamente independientes, que contribuirán con recompensas aleatorias de forma continua o en determinados puntos de tiempo discretos, cuando sean atendidos. El objetivo es maximizar las recompensas descontadas totales esperadas sobre todas las pólizas revisables dinámicamente. [1]
La primera versión de los problemas de múltiples bandidos fue formulada en el área de diseños secuenciales por Robbins (1952). [8] Desde entonces, no había habido ningún progreso esencial en dos décadas, hasta que Gittins y sus colaboradores obtuvieron logros de investigación celebrados en Gittins (1979), [9] Gittins y Jones (1974), [10] Gittins y Glazebrook (1977) ), [11] y Whittle (1980) [12] en los entornos de Markov y semi-Markov. En este primer modelo, cada brazo está modelado por un proceso de Markov o semi-Markov en el que los puntos de tiempo para realizar las transiciones de estado son épocas de decisión. La máquina puede en cada época elegir un brazo para servir con una recompensa representada en función del estado actual del brazo que se está procesando, y la solución se caracteriza por índices de asignación asignados a cada estado que depende solo de los estados de los brazos. Por lo tanto, estos índices se conocen como índices de Gittins y las políticas óptimas generalmente se denominan políticas de índice de Gittins , debido a sus respetables contribuciones.
Poco después del artículo fundamental de Gittins, Whittle (1981) investigó la extensión del problema del bandido ramificado para modelar las llegadas estocásticas (también conocido como el bandido abierto o el problema del bandido que adquiere el brazo). [13] Otras extensiones incluyen los modelos de bandido inquieto, formulado por Whittle (1988), [14] en el que cada brazo evoluciona inquieto de acuerdo con dos mecanismos diferentes (moda inactiva y moda ocupada), y los modelos con costos de cambio / retrasos por Van Oyen y col. (1992), [15] quienes demostraron que ninguna política de índice es óptima cuando el cambio de brazo genera costos / demoras.
Programación de sistemas de colas
Los modelos de esta clase se ocupan de los problemas de diseño de disciplinas de servicio óptimas en sistemas de colas, donde los trabajos que deben completarse llegan en épocas aleatorias a lo largo del tiempo, en lugar de estar disponibles al principio. La clase principal de modelos en este entorno es la de las redes de colas multiclase (MQN), ampliamente aplicadas como modelos versátiles de comunicaciones informáticas y sistemas de fabricación.
Los tipos más simples de MQN implican la programación de varias clases de trabajo en un solo servidor. De manera similar, como en las dos categorías de modelos discutidas anteriormente, se ha demostrado que las reglas simples de índice de prioridad son óptimas para una variedad de tales modelos.
Los modelos MQN más generales involucran características tales como tiempos de cambio para cambiar el servicio de una clase de trabajo a otra (Levy y Sidi, 1990), [16] o múltiples estaciones de procesamiento, que brindan servicio a los correspondientes subconjuntos de clases de trabajo que no se superponen. Debido a la intratabilidad de tales modelos, los investigadores se han propuesto diseñar políticas heurísticas relativamente simples que logren un desempeño cercano al óptimo.
Programación estocástica con información incompleta
La mayoría de los estudios sobre modelos de programación estocásticos se han establecido en gran medida sobre la base del supuesto de información completa, en el sentido de que las distribuciones de probabilidad de las variables aleatorias involucradas, como los tiempos de procesamiento y los tiempos de parada / parada de la máquina, están completamente especificadas a priori. .
Sin embargo, hay circunstancias en las que la información solo está disponible parcialmente. Se pueden encontrar ejemplos de programación con información incompleta en limpieza ambiental, [17] gestión de proyectos, [18] exploración de petróleo, [19] programación de sensores en robots móviles, [20] y modelado de tiempo de ciclo, [21] entre muchos otros. .
Como resultado de la información incompleta, puede haber múltiples distribuciones en competencia para modelar las variables aleatorias de interés. Un enfoque eficaz es desarrollado por Cai et al. (2009), [22] para abordar este problema, basándose en la actualización de la información bayesiana. Identifica cada distribución competidora mediante la realización de una variable aleatoria, digamos. Inicialmente,tiene una distribución previa basada en información histórica o suposición (que puede no ser informativa si no hay información histórica disponible). Información sobrepuede actualizarse después de que se observen las realizaciones de las variables aleatorias. Una preocupación clave en la toma de decisiones es cómo utilizar la información actualizada para refinar y mejorar las decisiones. Cuando la política de programación es estática en el sentido de que no cambia con el tiempo, se identifican secuencias óptimas para minimizar la recompensa con descuento esperada y minimizar estocásticamente el número de trabajos tardíos en una fecha de vencimiento exponencial común. [22] Cuando la política de programación es dinámica en el sentido de que puede hacer ajustes durante el proceso basándose en información actualizada, se desarrolla un índice de Gittins posterior para encontrar la política óptima que minimice la recompensa con descuento esperada en la clase de dinámica políticas. [22]
Referencias
- ^ a b Cai, XQ; Wu, XY; Zhou, X. (2014). Programación estocástica óptima . Springer EE. UU. págs. 49, pág. 95. ISBN 978-1-4899-7405-1.
- ^ Nino-Mora, J. (2009). "Programación estocástica". En Floudas, C .; Pardalos, P. (eds.). Enciclopedia de Optimización . NOSOTROS: Springer. págs. 3818–3824. ISBN 978-0-387-74758-3.
- ^ Smith, Wayne E. (1956). "Varios optimizadores para la producción de una sola etapa". Trimestral de Logística de Investigación Naval . 3 (1–2): 59–66. doi : 10.1002 / nav.3800030106 .
- ^ Rothkopf, Michael (1966). "Programación con horarios de servicio aleatorios". Ciencias de la gestión . 12 (9): 707–713. doi : 10.1287 / mnsc.12.9.707 .
- ^ Weiss, Gideon; Pinedo, Michael (1980). "Programación de tareas con tiempos de servicio exponenciales en procesadores no idénticos para minimizar diversas funciones de coste". Revista de probabilidad aplicada . 17 (1): 187–202. doi : 10.2307 / 3212936 . JSTOR 3212936 .
- ^ Weber, Richard R. (1982). "Programación de trabajos con requisitos de procesamiento estocástico en máquinas paralelas para minimizar el tiempo de fabricación o el tiempo de flujo". Revista de probabilidad aplicada . 19 (1): 167–182. doi : 10.2307 / 3213926 . JSTOR 3213926 .
- ^ Weber, Richard; Varaiya, P .; Walrand, J. (1986). "Programación de trabajos con tiempos de procesamiento ordenados estocásticamente en máquinas paralelas para minimizar el tiempo de flujo esperado". Revista de probabilidad aplicada . 23 (3): 841–847. doi : 10.2307 / 3214023 . JSTOR 3214023 .
- ^ Robbins, H. (1952). "Algunos aspectos del diseño secuencial de experimentos" . Boletín de la American Mathematical Society . 58 (5): 527–535. doi : 10.1090 / s0002-9904-1952-09620-8 .
- ^ Gittins, JC (1979). "Procesos bandidos e índices de asignación dinámica (con discusión)". Revista de la Sociedad Real de Estadística, Serie B . 41 : 148-164. doi : 10.1111 / j.2517-6161.1979.tb01068.x .
- ^ Gittins, JC; Jones, D. "Un índice de asignación dinámica para la asignación secuencial de experimentos". En Gani, J .; et al. (eds.). Avances en estadística . Amsterdam: Holanda Septentrional.
- ^ Gittins, JC; Glazebrook, KD (1977). "Sobre modelos bayesianos en programación estocástica". Revista de probabilidad aplicada . 14 (3): 556–565. doi : 10.2307 / 3213458 . JSTOR 3213458 .
- ^ Whittle, P. (1980). "Bandidos armados múltiples y el índice de Gittins". Revista de la Sociedad Real de Estadística, Serie B . 42 (2): 143-149. doi : 10.1111 / j.2517-6161.1980.tb01111.x .
- ^ Whittle, P. (1981). "Bandidos que adquieren armas" . Los anales de la probabilidad . 9 (2): 284-292. doi : 10.1214 / aop / 1176994469 .
- ^ Whittle, P. (1988). "Bandidos inquietos: asignación de actividad en un mundo cambiante". Revista de probabilidad aplicada . 25 : 287-298. doi : 10.2307 / 3214163 . JSTOR 3214163 .
- ^ van Oyen, diputado; Pandelis, DG; Teneketzis, D. (1992). "Optimidad de las políticas de índice para la programación estocástica con penalización de cambio". Revista de probabilidad aplicada . 29 (4): 957–966. doi : 10.2307 / 3214727 . JSTOR 3214727 .
- ^ Levy, H .; Sidi, M. (1990). "Sistemas de sondeo: aplicaciones, modelado y optimización". Transacciones IEEE sobre comunicaciones . 38 (10): 1750-1760. doi : 10.1109 / 26.61446 .
- ^ Lee, SI; Kitanidis, PK (1991). "Estimación y programación óptimas en la remediación de acuíferos con información incompleta". Investigación de recursos hídricos . 27 (9): 2203–2217. doi : 10.1029 / 91wr01307 .
- ^ Gardoni, P .; Reinschmidt, KF; Kumar, R. (2007). "Un marco probabilístico para el pronóstico adaptativo bayesiano del progreso del proyecto". Ingeniería Civil y de Infraestructuras Asistida por Computadora . 22 (3): 182-196. doi : 10.1111 / j.1467-8667.2007.00478.x .
- ^ Glazebrook, KD; Niños, RJ (1995). "Una clase de modelos bayesianos para una exploración óptima". Revista de la Sociedad Real de Estadística, Serie B . 57 (4): 705–720. doi : 10.1111 / j.2517-6161.1995.tb02057.x .
- ^ Gage, A .; Murphy, RR (2004). "Programación de sensores en robots móviles utilizando información incompleta a través de Min-Conflict with Happiness". Transacciones IEEE sobre sistemas, hombre y cibernética - Parte B: Cibernética . 34 (1): 454–467. doi : 10.1109 / tsmcb.2003.817048 . PMID 15369086 .
- ^ Chen, CYI; Ding, Q .; Lin, BMT (2004). "Una encuesta concisa de la programación con tiempos de procesamiento dependientes del tiempo". Revista europea de investigación operativa . 152 : 1-13. doi : 10.1016 / s0377-2217 (02) 00909-8 .
- ^ a b c Cai, XQ; Wu, XY; Zhou, X. (2009). "Programación estocástica sujeta a averías repetidas con información incompleta". Investigación operativa . 57 (5): 1236-1249. doi : 10.1287 / opre.1080.0660 .