Necesito ideas para unos problemas

[merymartin]

Hola!!!!!! Necesito algunas ideas para poder solucionar estos problemas.

1) 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 siguientes.
Se trata de determinar el horario de tal forma que todos los trabajadores cubran su carga de trabajo y 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 tiene una preferencia nula por los nuevos puestos añadidos determine la distribución que maximice la preferencia global.

2) Tenemos un procesador que debe realizar una serie de N trabajos. De cada trabajo i sabemos el instante exacto ci en que debe comenzar, su duración di y el beneficio bi que proporciona si se realiza. El procesador sólo puede realizr una tarea la mismo tiempo. Supuesto que el procesador está operatico entre los instantes C y F, diseñe algoritmos basados en Programación dinámica que resulevan los siguientes problemas:
A)Maximizar el beneficio de los trabajos que se procesen
B)Maximizar el número de trabajos procesados

Gracias

[_Lucifer_]

Bueno, puedes comenzar por pensar como resolver los problemas y publicar luego tus dudas, asi te damos la orientacion que requieras.

Saludos

[merymartin]

Bueno, ese es el problema, que no se me ocurre nada, bueno casi nada.

Para el primero, por ejemplo, no se como considerar las restricciones horarias, como turnos, por ejemplo el turno 1, 2, 3 etc.. Y también como considero las preferencias del puesto, también identifico cada puesto con un número.

Después como coloco los trabajadores, comparando primero las preferencias y después las restricciones.

En fin todo es un casos.

Para el segundo tengo un poco más claras las ideas, pero poco....

Me falta por concretar la función de maximización del beneficio, y no se si el método de programación dinámica tiene que ir recorriendo los trabajos o el tiempo hasta que el procesador llegue al final de su tiempo.

Como ves tengo muchas dudas, solo quiero que alguien me de alguna idea de como plantearlos, por el profesor, no ha dado ninguna explicación.

Gracias

[Developer9]

Iniciado por merymartin

Bueno, ese es el problema, que no se me ocurre nada, bueno casi nada...

Tienes serios problemas