Tri des tâches à affecter

Question

J'ai un problème que je ne sais pas par où commencer. J'apprécierais vraiment de l'aide.

Le problème:

J'ai plusieurs tâches T qui doit être fait en quelques jours seulement 1 D par employé (nous allons oublier l'utilisation de plusieurs ressources en ce moment). Chaque tâche peut être effectuée à plusieurs reprises (toutes les tâches ne peuvent pas être effectuées à tout moment). Par exemple: si mon employé commence à travailler à 8 heures et qu'une tâche est «appeler un client». Peut-être que le bureau du client ouvre à 9 heures.

Chaque tâche a également une durée (estimation réelle). On suppose que les jours D sont suffisants pour faire toutes les tâches.

Je dois trier les tâches à l'employé. Par exemple: lundi 8h00, tâche 7, puis 9h30 commence par la tâche 2. Dans l'exemple, la tâche 7 dure 1 heure et demie.

Merci pour l'aide!

Diego

PD: Si quelqu'un a un moyen de faire cela et il est un algorithme jamais esprit, s'il vous plaît répondre et je parviens à penser l'algorithme. Je ne sais pas comment faire face au problème.

Modifier Le projet serait-il utile?

Modifier 2 Tâches/dépendance d'emploi n'est pas nécessaire

Answer 1

S'il s'agit d'une "petite partie d'une application", vous pouvez renégocier avec le client: Job shop scheduling est NP-complete (vulgo: devient réel difficile réel rapidement avec une complexité croissante).
Quelques points à considérer:

• vous devez attribuer une sorte de « capacité » à l'époque, le marquage des intervalles de temps où une sorte de tâche est possible (début des travaux et à la fin de travail de vos employés, les heures d'ouverture de autres bureaux, etc.)
• Vous devez indiquer aux différentes tâches (ou tâches, comme on les appelle) le type de capacités dont elles ont besoin et pendant combien de temps: outils nécessaires, personnes à atteindre, etc.
• vous pourriez avoir besoin d'une sorte de relation directionnelle entre, disons, le travail 17 («appelez le bureau XYZ et demandez l'estimation des coûts») et le travail 18 («estimation du coût prévisionnel du patron»): le travail 17 doit être fait avant le travail n être démarré.

Lorsque vous Google pour « la planification du magasin d'emploi », vous croiserez plus d'articles scientifiques que vous aurez envie de lire pour une « petite partie d'une application » ...

(Divulgation : Je travaille pour une entreprise qui offre differenttools à faire tout ce genre de chose)

Answer 2

Votre problème est une partie de operations research problèmes. Ce sujet a été massivement étudié et il n'y a pas d'algorithme simple à partir de cela. Ce type de problème d'ordonnancement est généralement non polynomial, donc vous devez essayer toutes les combinaisons, mais vous pouvez couper quand une contrainte est cassée. Il n'y a pas besoin d'essayer toutes les combinaisons en commençant par appeler le client à 8h00 si vous savez que vous ne pouvez pas le faire avant 9h00. Donc google truc sur la recherche opérationnelle et les algorithmes de programmation par contraintes et combinatorial optimization.

Answer 3

Vous avez besoin de savoir quelle est l'entrée pour votre algorithme. Une partie de l'entrée est la liste des tâches avec une durée pour chaque tâche. Chaque tâche a aussi des exigences:

• nombre de participants (actuellement toujours 1, mais si cela peut vous changer besoin de penser au début)
• périodes de temps que la tâche peut être effectuée (actuellement le temps de la journée, mais il peut aussi être le jour de la semaine, ou même le jour du mois)
• Les participants peuvent avoir leurs propres exigences (comme les heures de travail, mais cela pourrait être quelque chose de plus)
• La tâche peut dépendre d'une autre tâche ou d'autres tâches à accomplir. complété en premier

Il pourrait y avoir plus d'exigences. Pour découvrir ce dont vous avez besoin, vous devriez essayer de résoudre certains problèmes concrets à la main. Pendant que vous essayez, d'autres exigences peuvent être découvertes. Quelles que soient les exigences, votre algorithme devrait essayer de les satisfaire de la même manière que vous l'avez fait à la main: une exigence à la fois, et si certains entrent en collision, retracer et essayer une route différente. L'algorithme devrait commencer par les exigences les plus restrictives.

Answer 4

Vous pouvez résoudre ce genre de problèmes en utilisant la programmation par contraintes, à condition que le nombre d'éléments ne soit pas trop important.

Jetez un oeil à ECLiPSe (voir http://eclipseclp.org/).

Answer 5

est ici encore une autre bibliothèque pour ce genre de problèmes. Drools Planner (open source, java). Notez qu'il résout toutes les exigences (= contraintes) ensemble, parce que surtout si vous avez des contraintes matérielles et logicielles, vous trouverez qu'il est généralement possible de résoudre toutes les contraintes, mais impossible de résoudre toutes les contraintes souples (vous toujours vouloir les minimiser autant que possible).