Problemas con un problema

[merymartin]

Tengo algún problemilla para plantear este problema:
En la empresa Losa Preta, O.S. andan escasos de espacio y necesitan distribuir los trabajadores de una forma óptima. Disponen de M puestos de trabajo y N trabajadores. Cada trabajador i tiene unas restricciones horarias ri, una carga de trabajo ci y una preferencia pip por cada puesto p de trabajo. Naturalmente en un puesto no pueden estar trabajando al mismo tiempo dos trabajadores distintos.
Diseñe heurísticas voraces para resolver los problemas que siguen.
Se trata de determinar el horario de tal forma que todos los trabajadores cubran su carga de trabajo y se maximice la preferencia del conjunto.
Naturalmente puede ocurrir que las restricciones sean demasiado fuertes y el problema no tenga solución en los términos planteados. En tal caso, determine cuál es el mínimo número de puestos de trabajo necesarios para satisfacer las restricciones horarias, y supuesto que los empleados tienen una preferencia nula por los nuevos puestos añadidos determine la distribución que maximice la preferencial global.
NOTA: La carga de trabajo es el número de horas semanales que tiene que trabajar. Las restricciones horarias se entiende que son las horas a las que puede trabajar durante la semana.

¿Cada trabajo tiene que tener su horario para así poder compararlo con las restricciones horarias de cada trabajador y así poder asignarle un trabajo a un trabajador? ¿Qué pasaría si no todos los trabajadores pueden cubrir sus cargas de trabajo? ¿Si la carga de trabajo de un trabajador es muy elevada se le puede asignar a un trabajador más de un trabajo? ¿En cada franja horaria del horario semanal solo puede estar trabajando un trabajador?