Effective Timetabling Algorithm

Question

J'ai un travail qui m'a été demandé de faire qui consiste à écrire un programme pour déterminer où différentes personnes doivent travailler un jour donné.

Par exemple, l'entrée peut être:
4-6pm, site
1-2pm, le site B
9-11am & Site 2-4pm A

Essentiellement, il peut y avoir de nombreux sites et personnes peut travailler pendant plusieurs blocs. J'ai l'impression que ce genre de problème a été résolu il y a longtemps, alors plutôt que de réinventer la roue, j'espérais que quelqu'un pourrait me diriger vers une solution élégante. Editer: Lire des questions similaires J'ai l'impression que le problème peut être NP complet. Je n'ai pas besoin de la solution la plus efficace seulement quelque chose qui fonctionne et est raisonnablement ok.

Édition 2: Pour clarifier, la sortie devrait être un emploi du temps avec des personnes allouées telles que les écarts (les cas où personne ne travaille) soient aussi petits que possible.

Answer 1

On dirait que vous essayez de résoudre un problème pour lequel il existe des applications logicielles assez spécialisées. Si votre problème est assez petit, vous pouvez essayer de faire une approche de force brute comme ceci:

• Déterminez la granularité de votre problème. Par exemple. si c'est pour un emploi du temps scolaire, votre granularité peut être d'une heure.
• Créer des instances pour chaque intervalle de temps divisé par la granularité. Ainsi, pour le site B, il y aura une instance (1-2pm), pour la taille A il y aura de nombreuses instances (4-5pm, 5-6pm, 9-10am, 10-11am, ...).
• Créer des instances pour toutes les personnes que vous souhaitez affecter
• Puis, affectez itérativement une personne à un créneau horaire en tenant compte de toutes vos contraintes (comme les vacances, la pause déjeuner, ne pouvant faire qu'une seule chose à la fois , le nombre maximum de personnes par site, ...) jusqu'à ce que:
  • vous avez une solution valable (fin, imprimer et sortir de l'application)
  • vous entrez dans une situation où vous avez encore besoin de placer des personnes, mais il n'est plus un créneau horaire valide. Puis revenez en arrière (annulez la dernière action et essayez de trouver une alternative).

Si votre problème est pas trop grand, vous pouvez trouver une solution dans un délai raisonnable. Toutefois, si le problème commence à s'aggraver, recherchez des logiciels plus spécialisés. Les choses à rechercher sont "l'optimisation basée sur la contrainte" et "la programmation par contraintes".

E.g. l'outil ECLIPSe est un environnement de programmation par contraintes open-source. Vous pouvez trouver quelques exemples sur http://eclipseclp.org/examples/index.html. Un bon exemple que vous pouvez trouver est le problème SEND + MORE = MONEY. Dans ce problème, vous avez l'équation suivante:

S E N D 
+ M O R E 
----------- 
= M O N E Y 

Remplacer chaque lettre par un chiffre pour que la somme est correcte. Cela illustre également que, bien que vous puissiez résoudre cette force brute, il existe des moyens plus intelligents de résoudre ce problème (voir http://eclipseclp.org/examples/sendmore.pl.txt).