Modelando um horário de trabalho complexo

Eu tenho um problema do mundo real que estou tentando representar e automatizar. Simplifiquei e abstraí para o seguinte:

• Existem n locais de trabalho (P1, P2, ..., Pn).
• Cada lugar, Pn tem uma chave, Kn.
• Existem m Trabalhadores, (W1, W2, ..., Wm).
• Para trabalhar em Pn, um trabalhador deve segurar Kn.
• Cada chave pode ser mantida por um trabalhador ou deixada no Exchange, E.

• Um trabalhador pode fazer uma viagem ao Exchange a qualquer momento para pegar algumas chaves não reclamadas ou deixar algumas para serem usadas por outras pessoas.

• Agora, há um cronograma de trabalho exógeno que deve ser concluído em uma ordem estrita. Por exemplo:

  • 2016-04-21 W1 deve trabalhar no P6
  • 2016-04-21 W2 deve trabalhar na P3
  • ** troca de chaves necessária **
  • 22-04-2016 W3 deve funcionar na P3
  • 22-04-2016 O W2 deve funcionar no P6

• Qualquer número de trabalhadores pode ter que trabalhar na Pn em algum momento da programação, embora nunca no mesmo dia

Nós sabemos:

• A localização inicial de todas as chaves, com trabalhadores ou em E
• As futuras ordens de serviço que cada trabalhador terá que cumprir

Então, estou lutando para modelar toda essa situação. Você pode sugerir estruturas e algoritmos de dados que eu deveria examinar, a fim de ter um controle sobre ele e começar a otimizar as viagens à troca para cada trabalhador?

O que eu quero minimizar é o número total de viagens para E. Um objetivo secundário seria garantir que nenhum trabalhador faça um número desproporcional de viagens.

Desde já, obrigado!!

A questão é um pouco ambígua em um ponto-chave: quais elementos estamos tentando resolver. Estamos buscando otimizar a ordem em que os recursos são delegados? Minimizar viagens à bolsa? Maximizar o rendimento da ordem de serviço?

Com isso em mente, vou assumir que poderíamos estar fazendo qualquer mistura dessas coisas e manter a resposta em um nível bastante alto.

A primeira coisa que me vem à mente é que os problemas inter-relacionados que isso tenta resolver se concentram principalmente no gerenciamento de dependências. Trabalhadores, chaves e locais podem ser considerados dependências que devem ser resolvidas para concluir os trabalhos de trabalho.

Levando isso para o próximo nível, eu consideraria uma adaptação da classificação topológica ( https://en.wikipedia.org/wiki/Topological_sorting ). Modele o espaço do problema como um gráfico grande (os bancos de dados de gráficos modernos também podem ser um bom meio para algumas dessas análises) e use várias classificações topológicas para resolver aspectos diferentes do espaço do problema.

Em uma ligeira tangente, isso soa como um projeto muito divertido. Hoje invejo você, senhor.