Consideramos la programación de trabajos con múltiples pesos en una sola máquina para minimizar el número total ponderado de trabajos tardíos. En esta configuración, cada trabajo tiene pesos (o equivalentemente, los trabajos tienen vectores de ponderación), y así tenemos criterios, cada uno de los cuales es minimizar el número total ponderado de trabajos tardíos bajo un vector de ponderación correspondiente de los trabajos. Para este modelo de programación, el problema de viabilidad tiene como objetivo encontrar un horario viable de modo que cada criterio esté acotado superiormente por su valor umbral, y el problema de programación de Pareto tiene como objetivo encontrar todos los puntos de Pareto óptimos y para cada uno un horario de Pareto óptimo correspondiente. Aunque los dos problemas no han sido estudiados antes, se da a entender en la literatura que ambos son NP-duros unarios cuando es un número arbitrario. Mostramos en este documento que, en el caso en que es un número fijo, los dos problemas son resolubles en tiempo pseudo-polinómico, el problema de viabilidad admite un esquema de aproximación de tiempo polinómico dualmente completo, y el problema de programación de Pareto admite un esquema de aproximación de tiempo polinómico completo.