En este trabajo, consideramos la programación de máquinas paralelas con tiempos de liberación y penalizaciones submodulares, en la que cada trabajo puede ser aceptado y procesado en una de las máquinas paralelas idénticas o rechazado, pero se debe pagar una penalización si se rechaza un trabajo. Cada trabajo tiene un tiempo de liberación y un tiempo de procesamiento, y el trabajo no puede ser procesado antes de su tiempo de liberación. El objetivo es minimizar el makespan de los trabajos aceptados más la penalización de los trabajos rechazados, donde la penalización está determinada por una función submodular. Este problema generaliza un problema de programación de multiprocesadores con rechazo, la programación de máquinas paralelas con penalizaciones submodulares, y el problema de programación de una sola máquina con fechas de liberación y penalizaciones de rechazo submodulares. En este trabajo, inspirados en el método primal-dual, presentamos un algoritmo de aproximación 2-combinatorial para . Esta proporción coincide con la mejor proporción conocida para la programación de máquinas paralelas con penalizaciones submodulares y el problema de programación de una sola máquina con fechas de liberación y penalizaciones de rechazo submodulares.