Modélisation d'un horaire de travail complexe

9

J'ai un problème réel que j'essaie de représenter et d'automatiser. Je l'ai simplifié et résumé comme suit:

  • Il existe n lieux de travail (P1, P2, ..., Pn).
  • Chaque endroit, Pn a une clé, Kn.
  • Il y a m Ouvriers (W1, W2, ..., Wm).
  • Pour travailler chez Pn, un travailleur doit détenir Kn.
  • Chaque clé peut être détenue par un travailleur ou laissée à la Bourse, E.
  • Un travailleur peut se rendre à la Bourse à tout moment pour récupérer des clés non réclamées ou déposer certaines clés pour que d'autres puissent les utiliser.

  • Maintenant, il y a un calendrier de travail exogène qui doit être complété dans un ordre strict. Par exemple:

    • 2016-04-21 W1 doit travailler à P6
    • 2016-04-21 W2 doit travailler à P3
    • ** échange de clés requis **
    • 2016-04-22 W3 doit travailler à P3
    • 2016-04-22 W2 doit travailler à P6
  • Un certain nombre de travailleurs peuvent devoir travailler chez Pn à un moment donné de leur horaire, mais jamais le même jour

Nous savons:

  • L'emplacement de départ de toutes les clés, soit avec les travailleurs ou à E
  • Les futurs ordres de travail que chaque travailleur devra exécuter

Donc, j'ai du mal à modéliser toute cette situation. Pouvez-vous suggérer des structures de données et des algorithmes que je devrais examiner afin de les maîtriser et de commencer à optimiser les déplacements vers l'échange pour chaque travailleur?

Ce que je veux minimiser, c'est le nombre total de voyages vers E. Un objectif secondaire serait de s'assurer qu'aucun travailleur n'effectue un nombre disproportionné de voyages.

Merci d'avance!!

Gareth Lloyd
la source
2
Nombre moyen de déplacements vers E par travailleur = "nombre total de déplacements" / m. Donc, si m est constant, vos deux buts sont le même but. Plus intéressant: je suppose que chaque travailleur peut transporter plus d'une clé en même temps?
Doc Brown
Oui, les travailleurs peuvent transporter n'importe quel nombre de clés. Concernant le "moyen" je pense que je me suis mal exprimé. Je pensais plus à l'équité, qu'aucun travailleur ne devrait avoir à effectuer un nombre disproportionné de déplacements, donc une faible variance. (question modifiée pour correspondre)
Gareth Lloyd
Étant donné que les travailleurs sont évidemment confiés aux clés et peuvent garder les clés pendant la nuit et aussi longtemps que nécessaire - tant qu'un échange n'est pas nécessaire - pourquoi ne pas faire un jeu de clés pour chaque travailleur qu'ils conservent en permanence? Alternativement, créez un jeu de clés pour chaque travailleur pour tous les endroits où il se rend pendant une période donnée, disons une semaine. Les clés sont dupliquées au besoin pour créer un ensemble de semaines pour chaque travailleur. Tous les travailleurs échangent leurs clés une fois par semaine.
radarbob
Y a-t-il un coût (temps ou argent) pour aller à la bourse?
Dan Pichelman
Oui, plus de voyages à l'échange est un résultat pire.
Gareth Lloyd

Réponses:

1

La question est un peu ambiguë sur un point clé: pour quels éléments essayons-nous de résoudre. Cherchons-nous à optimiser l'ordre dans lequel les ressources sont déléguées? Minimiser les déplacements vers la bourse? Maximiser le débit des bons de travail?

Dans cet esprit, je vais supposer que nous pourrions faire n'importe quel mélange de ces choses et garder la réponse à un niveau assez élevé.

La première chose qui me vient à l'esprit est que les problèmes interdépendants que cela tente de résoudre sont principalement centrés sur la gestion des dépendances. Les travailleurs, les clés et les emplacements peuvent être considérés comme des dépendances qui doivent être résolues afin de terminer les travaux.

Prenant cela au niveau suivant, j'examinerais une adaptation du tri topologique ( https://en.wikipedia.org/wiki/Topological_sorting ). Modélisez l'espace du problème sous la forme d'un grand graphique (les bases de données de graphiques modernes peuvent également être un bon moyen pour certaines de ces analyses), puis utilisez divers types topologiques pour résoudre différents aspects de l'espace du problème.

Sur une légère tangente, cela ressemble à un projet vraiment amusant. Aujourd'hui, je vous envie monsieur.

Michael
la source
Jetez un œil aux graphiques dans mon github github.com/MatheusArleson/Graphs
linuxunil
L'algorithme de coloration aide-t-il dans cette situation? en.m.wikipedia.org/wiki/Graph_coloring
linuxunil