Programación estocástica

Problemas que involucran atributos aleatorios

La programación estocástica se ocupa de 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 máquinas. Las principales aplicaciones surgen en sistemas de fabricación, sistemas informáticos, sistemas de comunicación, logística y transporte, y aprendizaje automático, entre otros. ^{[ cita requerida ]}

Introducción

El objetivo de los problemas de programación estocástica pueden ser objetivos regulares, como minimizar el tiempo total de flujo, el tiempo de realización 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 en 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 mediante una medida de desempeño regular o una medida de desempeño irregular, puede verse afectado significativamente 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 multiarmados y problemas relacionados con la programación de sistemas de colas ^[2] . Estos tres tipos suelen basarse en el supuesto de que se dispone de información completa en el sentido de que las distribuciones de probabilidad de las variables aleatorias implicadas se conocen de antemano. Cuando dichas 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 conjunto fijo de trabajos con tiempos de proceso aleatorios, cuyas distribuciones son conocidas, deben ser completados por un conjunto de máquinas para optimizar un objetivo de rendimiento dado. ${\displaystyle n}$ ${\displaystyle m}$

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 de los trabajos son variables aleatorias independientes con una distribución general con media para el trabajo . Las políticas admisibles deben ser no anticipatorias (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). ${\displaystyle n}$ ${\displaystyle G_{i}(\cdot )}$ ${\displaystyle p_{i}}$ ${\displaystyle i}$

Sea la tasa de costo incurrida por unidad de tiempo en el sistema para el trabajo y sea su tiempo aleatorio de finalización. Sea la clase de todas las políticas admisibles y sea la expectativa bajo la política . El problema puede formularse como ${\displaystyle w_{i}\geq 0}$ ${\displaystyle i}$ ${\displaystyle {\tilde {C}}_{i}}$ ${\displaystyle \Pi }$ ${\displaystyle E_{\pi }[\cdot ]}$ ${\displaystyle \pi \in \Pi }$

$${\displaystyle \min _{\pi \in \Pi }w_{1}E_{\pi }[{\tilde {C}}_{1}]+\cdots +w_{n}E_{\pi }[{\tilde {C}}_{n}].}$$

La solución óptima en el caso determinista especial viene dada por la regla de Smith del tiempo de procesamiento ponderado más corto: ^[3] secuenciar los 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] ${\displaystyle w_{i}p_{i}}$

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 de tiempo de procesamiento de trabajos son exponenciales; ^[5] cuando todos los trabajos tienen una distribución de tiempo de procesamiento general común con una función de tasa de riesgo no decreciente; ^[6] y cuando las distribuciones de tiempo de procesamiento de trabajos están ordenadas estocásticamente. ^[7]

Problemas con las máquinas tragamonedas

Los modelos de bandidos multiarmados forman un tipo particular de asignación óptima de recursos (que normalmente funciona con asignación de tiempo), en el que se debe asignar una cantidad de máquinas o procesadores para atender a un conjunto de proyectos en competencia (denominados brazos). 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 ciertos puntos temporales discretos, cuando se los atienda. El objetivo es maximizar las recompensas descontadas totales esperadas en todas las políticas revisables dinámicamente. ^[1]

La primera versión de los problemas multi-bandit 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 hicieron logros de investigación celebrados en Gittins (1979), ^[9] Gittins y Jones (1974), ^[10] Gittins y Glazebrook (1977), ^[11] y Whittle (1980) ^[12] bajo los entornos de Markov y semi-Markov. En este modelo temprano, cada brazo es modelado por un proceso de Markov o semi-Markov en el que los puntos de tiempo de hacer transiciones de estado son épocas de decisión. La máquina puede en cada época elegir un brazo para servir con una recompensa representada como una 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 dependen solo de los estados de los brazos. Por lo tanto, estos índices se conocen como índices de Gittins y las políticas óptimas suelen denominarse políticas de índices de Gittins , debido a sus prestigiosas contribuciones.

Poco después del artículo seminal de Gittins, Whittle (1981) investigó la extensión del problema del bandido de ramificación para modelar llegadas estocásticas (también conocido como el problema del bandido abierto o del bandido de adquisición de brazo). ^[13] Otras extensiones incluyen los modelos del bandido inquieto, formulados por Whittle (1988), ^[14] en el que cada brazo evoluciona inquietamente de acuerdo con dos mecanismos diferentes (modo inactivo y modo ocupado), y los modelos con costos/demoras de cambio de Van Oyen et al. (1992), ^[15] quienes demostraron que ninguna política de índice es óptima cuando el cambio entre brazos incurre en 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 contexto 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 a las dos categorías de modelos analizadas anteriormente, se ha demostrado que las reglas de índice de prioridad simples son óptimas para una variedad de dichos modelos.

Los modelos MQN más generales incluyen características como tiempos de cambio para cambiar el servicio de una clase de trabajo a otra (Levy y Sidi, 1990), ^[16] o estaciones de procesamiento múltiples, que brindan servicio a subconjuntos no superpuestos de clases de trabajo correspondientes. Debido a la imposibilidad de manejar estos modelos, los investigadores han tratado de diseñar políticas heurísticas relativamente simples que logren un rendimiento cercano al óptimo.

Programación estocástica con información incompleta

La mayoría de los estudios sobre modelos de programación estocástica 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 actividad/parada de la máquina, están completamente especificadas a priori.

Sin embargo, existen circunstancias en las que la información solo está parcialmente disponible. Se pueden encontrar ejemplos de programación con información incompleta en la limpieza ambiental, ^[17] la gestión de proyectos, ^[18] la exploración petrolera, ^[19] la programación de sensores en robots móviles, ^[20] y el modelado del 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. Cai et al. (2009), ^[22] desarrollaron un enfoque eficaz para abordar este problema, basado en la actualización de información bayesiana. Identifica cada distribución en competencia mediante una 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). La información sobre puede actualizarse después de que se observen 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 descontada esperada y minimizar estocásticamente el número de trabajos tardíos bajo 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 en función de información actualizada, se desarrolla el índice de Gittins posterior para encontrar la política óptima que minimice la recompensa descontada esperada en la clase de políticas dinámicas. ^[22] ${\displaystyle \Theta }$ ${\displaystyle \Theta }$ ${\displaystyle \Theta }$

Referencias

1. Cai, XQ; Wu, XY; Zhou, X. (2014). Programación estocástica óptima . Springer US. pp. 49, p. 95. ISBN 978-1-4899-7405-1.
2. Nino-Mora, J. (2009). "Stochastic Scheduling". En Floudas, C.; Pardalos, P. (eds.). Enciclopedia de optimización . EE. UU.: Springer. págs. 3818–3824. ISBN 978-0-387-74758-3.
3. Smith, Wayne E. (1956). "Varios optimizadores para la producción en una sola etapa". Naval Research Logistics Quarterly . 3 (1–2): 59–66. doi :10.1002/nav.3800030106.
4. Rothkopf, Michael (1966). "Programación con tiempos de servicio aleatorios". Management Science . 12 (9): 707–713. doi :10.1287/mnsc.12.9.707.
5. Weiss, Gideon; Pinedo, Michael (1980). "Programación de tareas con tiempos de servicio exponenciales en procesadores no idénticos para minimizar varias funciones de costo". Journal of Applied Probability . 17 (1): 187–202. doi :10.2307/3212936. JSTOR  3212936. S2CID  34396501.
6. Weber, Richard R. (1982). "Programación de trabajos con requisitos de procesamiento estocástico en máquinas paralelas para minimizar el tiempo de ejecución o el tiempo de flujo". Journal of Applied Probability . 19 (1): 167–182. doi :10.2307/3213926. JSTOR  3213926. S2CID  9363363.
7. 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". Journal of Applied Probability . 23 (3): 841–847. doi :10.2307/3214023. JSTOR  3214023. S2CID  9253615.
8. Robbins, H. (1952). "Algunos aspectos del diseño secuencial de experimentos" (PDF) . Boletín de la American Mathematical Society . 58 (5): 527–535. doi : 10.1090/s0002-9904-1952-09620-8 .
9. Gittins, JC (1979). "Procesos bandidos e índices de asignación dinámica (con discusión)". Journal of the Royal Statistical Society, Serie B. 41 : 148–164. doi :10.1111/j.2517-6161.1979.tb01068.x. S2CID  17724147.
10. Gittins, JC; Jones, D. "Un índice de asignación dinámica para la asignación secuencial de experimentos". En Gani, J.; et al. (eds.). Progreso en estadística . Ámsterdam: Holanda Septentrional.
11. Gittins, JC; Glazebrook, KD (1977). "Sobre modelos bayesianos en programación estocástica". Journal of Applied Probability . 14 (3): 556–565. doi :10.2307/3213458. JSTOR  3213458. S2CID  123637036.
12. Whittle, P. (1980). "Bandidos multiarmados y el índice de Gittins". Revista de la Royal Statistical Society, Serie B . 42 (2): 143–149. doi :10.1111/j.2517-6161.1980.tb01111.x.
13. Whittle, P. (1981). "Bandidos que adquieren armas". Anales de probabilidad . 9 (2): 284–292. doi : 10.1214/aop/1176994469 .
14. Whittle, P. (1988). "Bandidos inquietos: asignación de actividades en un mundo cambiante". Journal of Applied Probability . 25 : 287–298. doi :10.2307/3214163. JSTOR  3214163. S2CID  202109695.
15. van Oyen, MP; Pandelis, DG; Teneketzis, D. (1992). "Optimalidad de las políticas de índices para la programación estocástica con penalización por cambio". Journal of Applied Probability . 29 (4): 957–966. doi :10.2307/3214727. JSTOR  3214727. S2CID  7809829.
16. Levy, H.; Sidi, M. (1990). "Sistemas de sondeo: aplicaciones, modelado y optimización". IEEE Transactions on Communications . 38 (10): 1750–1760. doi :10.1109/26.61446.
17. Lee, SI; Kitanidis, PK (1991). "Estimación óptima y programación en la remediación de acuíferos con información incompleta". Investigación de recursos hídricos . 27 (9): 2203–2217. Código Bibliográfico :1991WRR....27.2203L. doi :10.1029/91wr01307.
18. Gardoni, P.; Reinschmidt, KF; Kumar, R. (2007). "Un marco probabilístico para la previsión adaptativa bayesiana del progreso del proyecto". Ingeniería civil y de infraestructura asistida por ordenador . 22 (3): 182–196. doi : 10.1111/j.1467-8667.2007.00478.x . S2CID  205572781.
19. Glazebrook, KD; Boys, RJ (1995). "Una clase de modelos bayesianos para la exploración óptima". Journal of the Royal Statistical Society, Serie B . 57 (4): 705–720. doi :10.1111/j.2517-6161.1995.tb02057.x.
20. Gage, A.; Murphy, RR (2004). "Programación de sensores en robots móviles utilizando información incompleta a través de Min-Conflict con Happiness". IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics . 34 (1): 454–467. doi :10.1109/tsmcb.2003.817048. PMID  15369086. S2CID  8405346.
21. Chen, CYI; Ding, Q.; Lin, BMT (2004). "Un estudio conciso 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.
22. Cai, XQ; Wu, XY; Zhou, X. (2009). "Programación estocástica sujeta a desgloses de repetición con información incompleta". Investigación de operaciones . 57 (5): 1236–1249. doi :10.1287/opre.1080.0660.