Modelando un horario de trabajo complejo

Tengo un problema del mundo real que intento representar y automatizar. Lo he simplificado y resumido a lo siguiente:

• Hay n lugares de trabajo (P1, P2, ..., Pn).
• Cada lugar, Pn tiene una llave, Kn.
• Hay m trabajadores, (W1, W2, ..., Wm).
• Para trabajar en Pn, un trabajador debe tener Kn.
• Cada llave puede ser mantenida por un trabajador o dejada en el intercambio, E.

• Un trabajador puede hacer un viaje al Intercambio en cualquier momento para recoger algunas claves no reclamadas o dejar algunas claves para que otras las usen.

• Ahora, hay un horario de trabajo exógeno que debe completarse en un orden estricto. Por ejemplo:

  • 2016-04-21 W1 debe funcionar en P6
  • 2016-04-21 W2 debe funcionar en P3
  • ** se requiere intercambio de llaves **
  • 2016-04-22 W3 debe funcionar en P3
  • 2016-04-22 W2 debe funcionar en P6

• Cualquier número de trabajadores podría tener que trabajar en Pn en algún momento de su horario, aunque nunca el mismo día.

Sabemos:

• La ubicación inicial de todas las claves, ya sea con trabajadores o en E
• Las futuras órdenes de trabajo que cada trabajador deberá cumplir.

Entonces, estoy luchando por modelar toda esta situación. ¿Puede sugerir estructuras de datos y algoritmos que debería analizar para poder controlarlos y comenzar a optimizar los viajes al intercambio para cada trabajador?

Lo que quiero minimizar es el número total de viajes a E. Un objetivo secundario sería asegurar que ningún trabajador realice un número desproporcionado de viajes.

¡¡Gracias por adelantado!!

La pregunta es un poco ambigua en un punto clave: qué elementos estamos tratando de resolver. ¿Estamos buscando optimizar el orden en que se delegan los recursos? ¿Minimizando los viajes al intercambio? ¿Maximizar el rendimiento de la orden de trabajo?

Con eso en mente, voy a suponer que podríamos estar haciendo cualquier combinación de estas cosas y mantener la respuesta a un nivel bastante alto.

Lo primero que me viene a la mente es que los problemas interrelacionados que intenta resolver se centran principalmente en la gestión de la dependencia. Los trabajadores, las claves y las ubicaciones pueden considerarse dependencias que deben resolverse para completar los trabajos.

Llevando esto al siguiente nivel, vería una adaptación de la clasificación topológica ( https://en.wikipedia.org/wiki/Topological_sorting ). Modele el espacio del problema como un gráfico grande (las bases de datos de gráficos modernos también podrían ser un buen medio para algunos de estos análisis) y luego use varios tipos topológicos para resolver diferentes aspectos del espacio del problema.

En una ligera tangente, esto suena como un proyecto muy divertido. Hoy, te envidio señor.