En este documento, consideramos el problema de programación de una sola máquina con fechas de inicio y penalización de rechazo submodular no monótona. Se nos da una sola máquina y múltiples trabajos con fechas de inicio y tiempos de procesamiento probablemente diferentes. Para cada trabajo, es aceptado y procesado en la máquina o rechazado. El objetivo es minimizar la suma del tiempo de ejecución de los trabajos aceptados y la penalización de rechazo de los trabajos rechazados que es determinada por una función submodular no monótona. Diseñamos un algoritmo combinatorio basado en el marco primal-dual para abordar el problema, y estudiamos sus propiedades bajo dos casos. Para el caso general donde las fechas de inicio pueden ser diferentes, el algoritmo propuesto tiene una relación de aproximación de 2. Cuando todos los trabajos se inician al mismo tiempo, el algoritmo propuesto se convierte en un algoritmo exacto de tiempo polinómico.