Estudiamos un problema de programación en el que los trabajos con tiempos de liberación y fechas de vencimiento deben ser procesados en una sola máquina. Con el objetivo principal de minimizar la máxima tardanza de los trabajos, el problema es fuertemente NP-duro. Describimos un esquema algorítmico general para minimizar la máxima tardanza de los trabajos, con el objetivo secundario de minimizar el tiempo de finalización máximo de los trabajos. El problema de encontrar el conjunto Pareto-óptimo de soluciones factibles con estos dos criterios objetivos es fuertemente NP-duro. Damos las propiedades de dominancia y las condiciones en las que el conjunto Pareto-óptimo puede formarse en tiempo polinómico. Estas propiedades, junto con nuestro marco general, proporcionan el fundamento teórico, de modo que el marco básico puede expandirse a algoritmos de enumeración implícita (de tiempo exponencial) y algoritmos de aproximación de tiempo polinómico (generando la frontera subóptima de Pareto con un equilibrio justo entre los dos objetivos). Algunos resultados experimentales disponibles en la literatura confirman la eficiencia práctica del marco propuesto.