En este documento, consideramos el problema de programación de una sola máquina con fechas de inicio dadas y el objetivo de minimizar la penalización máxima, que es NP-duro en el sentido estricto. Para este problema, presentamos un problema dual y uno inverso y mostramos que ambos problemas pueden resolverse en tiempo polinómico. Dado que el problema dual proporciona una cota inferior sobre el valor óptimo de la función objetivo del problema original, utilizamos el valor de la función óptima de un subproblema del problema dual en un algoritmo de ramificación y acotación para el problema original de programación de una sola máquina. Presentamos algunos resultados computacionales iniciales para instancias con hasta 20 trabajos.