Resumen

En este trabajo se investiga un problema estocstico esttico de programacin JIT en una sola mquina en el que los tiempos de procesamiento de los trabajos son estocsticamente independientes y siguen distribuciones geomtricas cuya media se proporciona, las fechas de vencimiento se distribuyen geomtricamente con una media comn, y tanto la penalizacin unitaria de la impuntualidad/retraso como la penalizacin fija de la impuntualidad/retraso son deterministas y diferentes. El objetivo es minimizar las penalizaciones totales esperadas para la impuntualidad cuadrtica, la impuntualidad cuadrtica y los trabajos que llegan pronto y tarde. Demostramos que la programacin ptima para minimizar este problema tiene forma de V con respecto a la relacin entre el tiempo medio de procesamiento y la penalizacin unitaria por tardanza bajo una condicin especfica. Adems, mostramos un caso especial y dos teoremas relacionados con este problema de programacin JIT en situaciones especficas en las que existen soluciones ptimas. Por ltimo, basndonos en la caracterstica en forma de V, se disea un algoritmo de programacin dinmica para conseguir una programacin ptima en forma de V en tiempo pseudopolinomial.

• Materias:Algoritmos (Matemáticas) Algebra Ingeniería Lógica matemática Matemáticas
• Subjects:Agorithms (Math) Algebra Engineering Mathematical logic mathematics
• Palabras claves:Estocástico; Máquina única; Programación JIT; Distribuciones geométricas; Penalizaciones; Programación dinámica
• Keywords:Stochastic; Single machine; JIT scheduling; Geometric distributions; Penalties; Dynamic programming