Resumen

En (1998), Kovalyov y Kubiak estudiaron el problema de programar n trabajos deteriorados en una sola máquina para minimizar el tiempo de ejecución. Presentaron un esquema de aproximación totalmente polinómico basado en una programación dinámica. Desafortunadamente, su programación dinámica es incorrecta. Por tanto, el esquema de aproximación en tiempo polinomial tampoco es válido. En este artículo, construimos una instancia para mostrar cómo su programación dinámica no funciona y proporcionar una programación dinámica correcta, basada en la cual se deriva un nuevo esquema de aproximación totalmente polinomial.

• 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:esquema de aproximación temporal, programación dinámica, programación dinámica correcta, máquina única, kovalyov, kubiak, instancia, trabajos, makespan, paper
• Keywords:time approximation scheme, dynamic programming, correct dynamic programming, single machine, kovalyov, kubiak, instance, jobs, makespan, paper