Estudiamos un problema de programación de una sola máquina para minimizar el tiempo total de finalización del conjunto de trabajos dados, los cuales deben procesarse sin interrupciones de trabajos. Los límites inferiores y superiores de la duración del trabajo son la única información disponible antes de la programación. Los valores exactos de las duraciones de los trabajos permanecen desconocidos hasta la finalización de los trabajos. Utilizamos la región de optimalidad para la permutación de trabajos como medida de optimalidad del horario óptimo. Investigamos las propiedades de la región de optimalidad y derivamos un algoritmo para calcular un cuasi-perímetro del conjunto de optimalidad (es decir, la suma de longitudes de los segmentos de optimalidad para los trabajos dados). Desarrollamos un algoritmo rápido para encontrar una permutación de trabajos que tenga el cuasi-perímetro más grande del conjunto de optimalidad. Los resultados computacionales en la construcción de tales permutaciones muestran que están cerca de las óptimas, las cuales pueden construirse para las duraciones reales de todos los trabajos dados.