El ratio competitivo esperado en un tipo de programación de flujo de tiempo estocástica en línea con máquina sujeta a una avería incierta
Autores: Li, Zhenpeng; Cheng, Congdian
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
El ratio competitivo esperado en un tipo de programación de flujo de tiempo estocástica en línea con máquina sujeta a una avería incierta
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Programación
Trabajos
Desglose
Ratio competitivo
Algoritmo
Optimización
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
Consideramos el problema de programar trabajos en una sola máquina sujeta a una avería incierta para minimizar el tiempo de flujo. Suponiendo que la máquina no está disponible durante la avería, el tiempo de inicio de la avería es una variable aleatoria con función de distribución y el tiempo de finalización de la avería no tiene otra información; los trabajos no son reanudables. Bajo estas suposiciones y partiendo desde la perspectiva de la optimización estadística, primero establecemos el problema de programación HSONRP, que contiene información determinística, información estocástica e información en línea y luego definimos la relación competitiva esperada de un algoritmo para encontrar la solución optimizada del problema HSONRP. Además, luego proponemos y demostramos ciertos resultados sobre la relación competitiva esperada de la regla SPT. En particular, demostramos que la relación competitiva esperada de la regla SPT es menor que cuando es la distribución uniforme en el intervalo , donde es el tiempo de procesamiento del trabajo , , y mostramos que no es más de bajo una condición bastante laxa. Mientras tanto, también realizamos algunas discusiones sobre nuestros estudios. Lo que hemos realizado enriquecerá y mejorará los resultados de investigación en el área de programación para minimizar el tiempo de flujo y avanzará en el desarrollo de la optimización en línea y la optimización estocástica.
Descripción
Consideramos el problema de programar trabajos en una sola máquina sujeta a una avería incierta para minimizar el tiempo de flujo. Suponiendo que la máquina no está disponible durante la avería, el tiempo de inicio de la avería es una variable aleatoria con función de distribución y el tiempo de finalización de la avería no tiene otra información; los trabajos no son reanudables. Bajo estas suposiciones y partiendo desde la perspectiva de la optimización estadística, primero establecemos el problema de programación HSONRP, que contiene información determinística, información estocástica e información en línea y luego definimos la relación competitiva esperada de un algoritmo para encontrar la solución optimizada del problema HSONRP. Además, luego proponemos y demostramos ciertos resultados sobre la relación competitiva esperada de la regla SPT. En particular, demostramos que la relación competitiva esperada de la regla SPT es menor que cuando es la distribución uniforme en el intervalo , donde es el tiempo de procesamiento del trabajo , , y mostramos que no es más de bajo una condición bastante laxa. Mientras tanto, también realizamos algunas discusiones sobre nuestros estudios. Lo que hemos realizado enriquecerá y mejorará los resultados de investigación en el área de programación para minimizar el tiempo de flujo y avanzará en el desarrollo de la optimización en línea y la optimización estocástica.