Resumen

Consideramos problemas de programación de una sola máquina con efectos de aprendizaje/deterioro y tiempos de procesamiento dependientes del tiempo, con consideración de la asignación de fechas de vencimiento, y nuestro objetivo es minimizar el número ponderado de trabajos retrasados. Reduciendo todas las versiones del problema a un problema de asignación, los resolvemos en tiempo O(n4). Para algunos casos especiales importantes, la complejidad temporal puede mejorarse hasta O(n2) utilizando técnicas de programación dinámica.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:consideración de la asignación de fechas de vencimiento, problemas de programación de una sola máquina, tiempos de procesamiento dependientes, técnicas de programación dinámica, casos especiales importantes, tiempo, problema de asignación, efectos de deterioro, trabajos retrasados, complejidad temporal
• Keywords:due date assignment consideration, single machine scheduling problems, dependent processing times, dynamic programming techniques, important special cases, time, assignment problem, deterioration effects, tardy jobs, time complexity