Proponemos un algoritmo de aproximación para programar trabajos con tiempos de liberación y entrega en una sola máquina con el objetivo de minimizar el makespan. El algoritmo se basa en una enumeración implícita del conjunto de soluciones completas en un árbol de búsqueda. Al analizar propiedades estructurales específicas de las soluciones creadas en cada rama del árbol de soluciones, se calcula un cierto factor de aproximación de cada solución de esa rama. Nuestro algoritmo garantiza un factor de aproximación para una solución generada si hay trabajos con una propiedad especificada en esa solución (típicamente, cuanto mayor sea la longitud del camino desde la raíz hasta el nodo que representa esa solución en el árbol de soluciones, mayor será el valor). Hemos llevado a cabo un estudio computacional extenso para verificar el rendimiento práctico de nuestro algoritmo y la efectividad del factor de aproximación proporcionado por nosotros. Mientras que nuestras instancias del problema se generan al azar, hemos descartado un número considerable de instancias, aquellas que ya se resolvieron de manera óptima mediante las reglas de dominancia conocidas anteriormente. Para la gran mayoría de las instancias del problema probadas, dentro de un tiempo de ejecución corto de nuestro algoritmo, el parámetro se vuelve lo suficientemente grande como para que el factor de aproximación que garantiza el algoritmo sea mejor que el proporcionado por los algoritmos de aproximación conocidos anteriormente.