Resumen

En esta nota, revisamos dos tipos de problemas de programacin con criterios ponderados de trabajo temprano/tarde y una fecha de vencimiento comn. Para un entorno de mquinas paralelas idnticas, presentamos un enfoque de programacin dinmica que se ejecuta en tiempo pseudopolinomial, para clasificar el problema considerado en el conjunto de NP-duros binarios. Tambin proponemos un algoritmo de enumeracin para la comparacin. Para los sistemas flow shop de dos mquinas, nos centramos en un mtodo de programacin dinmica anterior, pero con un anlisis ms preciso, para mejorar el rendimiento prctico durante su ejecucin. Para cada modelo, verificamos nuestros estudios mediante experimentos computacionales, en los que mostramos las ventajas de nuestras tcnicas, respectivamente.

• Materias:Matemáticas Lógica matemática Ingeniería Algoritmos (Matemáticas) Algebra
• Subjects:mathematics Mathematical logic Engineering Agorithms (Math) Algebra
• Palabras claves:problema de programación; criterios ponderados de trabajo temprano/tardío; fecha de vencimiento común; máquinas idénticas paralelas; enfoque de programación dinámica; NP-difícil binario
• Keywords:scheduling problem; weighted early/late work criteria; common due date; parallel identical machines; dynamic programming approach; binary NP-hard