Investigamos las relaciones entre problemas de programación con funciones objetivo de cuello de botella (minimizando el makespan o la tardanza máxima) y problemas de coloraciones óptimas de los grafos mixtos. Los problemas de programación investigados tienen duraciones enteras de las tareas de multiprocesador (operaciones), fechas de inicio enteras y fechas de vencimiento enteras de los trabajos dados. En los problemas de programación estudiados, se requiere encontrar un horario óptimo para procesar las operaciones parcialmente ordenadas, dado que se permiten interrupciones de operaciones y se deben procesar conjuntos indicados de operaciones de tiempo unitario simultáneamente. Primero, mostramos que los datos de entrada para cualquier problema de programación considerado pueden ser completamente determinados por el grafo mixto correspondiente. En segundo lugar, demostramos que los problemas de programación resolubles pueden reducirse a problemas de encontrar coloraciones óptimas de los grafos mixtos correspondientes. En tercer lugar, encontrar una coloración óptima del grafo mixto es equivalente al problema de programación considerado determinado por el mismo grafo mixto. Finalmente, debido a la equivalencia probada de los problemas de optimización considerados, la mayoría de los resultados que se demostraron para las coloraciones óptimas de los grafos mixtos generan resultados similares para los problemas de programación considerados, y viceversa.