Meilleur algorithme de planification des ajustements

Question

J'écris un programme de planification avec un problème de programmation difficile. Il y a plusieurs événements, chacun avec plusieurs temps de réunion. J'ai besoin de trouver un arrangement des heures de réunion de sorte que chaque programme contienne un événement donné exactement une fois, en utilisant l'un des multiples temps de réunion de chaque événement.

De toute évidence, je pourrais utiliser la force brute, mais c'est rarement la meilleure solution. Je suppose qu'il s'agit d'un problème d'informatique relativement basique, que je connaîtrai une fois que je pourrais commencer à suivre des cours d'informatique. En attendant, je préférerais n'importe quels liens où je pourrais lire sur ceci, ou même juste un nom que je pourrais Google.

Answer 1

Je pense que vous devez utiliser un algorithme génétique parce que:

• Il est plus adapté pour les cas de problèmes importants.
• Il donne la complexité du temps réduit sur le prix de la réponse erronée (non le nec plus ultra meilleur)
• Vous pouvez spécifier des contraintes & préférences facilement en ajustant les punitions de conditionnement physique pour les non satisfaits.
• Vous pouvez spécifier une limite de temps pour l'exécution du programme.

• La qualité de la solution dépend de combien de temps vous avez l'intention de passer la résolution du programme ..

  Genetic Algorithms Definition

  Genetic Algorithms Tutorial

  Class scheduling project with GA

Answer 2

Votre description du problème n'est pas tout à fait claire, mais si tout ce que vous essayez de faire est de trouver un calendrier qui n'a pas d'événements qui se chevauchent, alors c'est un problème simple bipartite matching.

Vous avez deux ensembles de noeuds: les événements et les heures. Dessinez un bord de chaque événement à chaque heure de réunion possible. Vous pouvez ensuite construire efficacement la correspondance (le plus grand ensemble d'arêtes possible entre les nœuds) en utilisant augmented paths. Cela fonctionne parce que vous pouvez toujours convertir un graphique bipartite en un graphique de flux équivalent.

Un exemple de code qui fait cela est BIM. Les bibliothèques graphiques standard telles que GOBLIN et NetworkX ont également des implémentations de mise en correspondance bipartites.

Answer 3

Cela ressemble à cela pourrait être un bon candidat pour une solution dynamic programming, en particulier quelque chose de similaire au problème interval scheduling.

Il existe certains éléments visuels here pour le problème de planification d'intervalle, ce qui peut rendre le concept plus clair. Here est un bon tutoriel sur la programmation dynamique globale.

Answer 4

Il y a plusieurs façons de le faire cette

Une approche consiste à faire de la programmation par contraintes. C'est un cas particulier de la programmation dynamique proposée par feanor. Il est utile d'utiliser une bibliothèque spécialisée qui peut faire la délimitation et la ramification pour vous. (Google pour "gecode" ou "comet-online" pour trouver des bibliothèques)

Si vous êtes mathématiquement incliné, vous pouvez également utiliser la programmation entière pour résoudre le problème.L'idée de base ici est de traduire votre problème en un ensemble d'inégalités linéaires. Je pense que la programmation par contraintes est l'approche la plus simple, mais la programmation en nombres entiers est utile si vous utilisez Google pour la programmation "integer programming scheduling" pour trouver des exemples concrets et google pour "Abacus COIN-OR". vouloir inclure des variables réelles dans votre problème à un moment donné.