Quel algorithme d'attribution des quarts de travail (problème d'optimisation discrète)

StackOverflow https://stackoverflow.com/questions/573670

Question

Je développe une application qui affecte de façon optimale les changements aux infirmières dans un hôpital. Je crois que ce problème est un avec des variables discrètes, et donc NP-fort probablement:

  • Pour chaque jour, chaque infirmière (environ 15 à 20) se voit attribuer un décalage
  • Il y a un petit nombre (environ 6) de différents quarts de travail
  • Il y a un grand nombre de contraintes et critères d'optimisation, que ce soit au sujet d'un jour, ou au sujet d'une emplyoee, .: par exemple
    • Il doit y avoir un nombre minimum de personnes affectées à chaque quart de travail chaque jour
    • Certains changements se chevauchent de sorte qu'il est normal d'avoir une personne de moins en changement plus tôt s'il y a quelqu'un qui fait changement intermédiaire
    • Certaines personnes préfèrent changement précoce, certains préfèrent changement en retard, mais un minimum de changements de quarts est nécessaire pour obtenir encore le salaire-travail posté plus élevé.
    • Il est pas permis pour une personne de travailler un jour changement fin et au début de passer le lendemain (en raison de la réglementation du temps minimum de repos)
    • réunion assignée longueurs de semaine de travail (différentes pour différentes personnes)
    • ...

Donc, fondamentalement, il y a un grand nombre (20 * 30 aout = 600) des variables que chacun peut prendre un petit nombre de valeurs discrètes.

À l'heure actuelle, mon plan est d'utiliser un href="http://en.wikipedia.org/wiki/Min_conflicts_algorithm" algorithme Min-conflits

  • commencer par assignation aléatoire
  • une fonction de remise en forme pour chaque personne et chaque jour
  • sélectionnez la personne ou par jour avec la plus mauvaise valeur de remise en forme
  • choisir au hasard une des missions pour ce jour / personne et le mettre à la valeur qui résulte de la valeur de remise en forme optimale
  • répétition jusqu'à ce que soit un nombre maximum d'itérations est atteint ou pas d'amélioration peut être trouvée pour le jour sélectionné / personne

Les meilleures idées? Je suis un peu inquiet qu'il se coincer dans un optimum local. Dois-je utiliser une certaine forme de recuit simulé ? Ou envisager non seulement des changements dans une variable à la fois, mais commute spécifiquement des déplacements entre deux personnes (le composant principal de l'algorithme manuel actuel)? Je veux éviter d'adapter l'algorithme aux contraintes actuelles car ceux qui pourraient changer.

Modifier il est pas nécessaire de trouver une solution strictement optimale; la liste est actuellement fait manuel, et je suis assez sûr que le résultat est considérablement sous-optimale la plupart du temps - ne devrait pas être difficile à battre que. ajustements à court terme et commandes manuelles seront aussi certainement nécessaires, mais je ne crois pas que ce sera un problème; Le marquage du passé et les affectations manuelles « fixe » devrait simplifier effectivement la tâche en réduisant l'espace de solution.

Autres conseils

Umm, saviez-vous que certains ILP-solveurs font un très bon travail? Essayez AIMMS, Mathematica ou le kit de programmation GNU! 600 variables est bien sûr beaucoup plus que le théorème Lenstra résoudra facilement, mais parfois ces solveurs ILP ont une bonne poignée et AIMMS, vous pouvez modifier la stratégie de branchement un peu. De plus, il y a un 100% -approximation vraiment rapide pour ILP.

Je résolu un problème d'affectation de décalage pour une grande usine de fabrication récente. Tout d'abord, nous avons essayé de générer des calendriers purement aléatoires et en retournant une qui a réussi le test de is_schedule_valid - l'algorithme de repli. Ce fut, bien sûr, lent et indéterminé.

Ensuite, nous avons essayé des algorithmes génétiques (comme vous le suggérez), mais ne pouvait pas trouver une bonne fonction de fitness qui a fermé sur une solution viable (car le plus petit changement peut faire l'ensemble de la programmation Tort ou à raison - pas de points pour presque).

Enfin, nous avons choisi la méthode suivante (qui fonctionnait très bien!):

  1. randomiser l'ensemble d'entrée (à savoir l'emploi, décalage, personnel, etc.).
  2. Créer un tuple valide et l'ajouter à votre calendrier provisoire.
  3. Dans le cas contraire tuple valide peut être créé, rollback (et incrément) le dernier tuple ajouté.
  4. Faites passer le programme partiel à une fonction qui teste could_schedule_be_valid, qui est, pourrait ce programme valable si les tuples restants ont été remplis de manière possible
  5. Si !could_schedule_be_valid, rollback simplement (et incrément) tuple ajouté en (2).
  6. Si schedule_is_complete, return schedule
  7. Goto (2)

Vous construisez progressivement un changement partiel de cette façon. L'avantage est que certains tests pour le calendrier valide peut facilement être fait à l'étape 2 (pré-tests), et d'autres doivent rester à l'étape 5 (tests post-).

Bonne chance. Nous avons perdu deux jours à essayer les premiers algorithmes, mais nous avons eu l'algorithme recommandé de générer des horaires valides instantanément en moins de 5 heures de développement.

En outre, nous avons soutenu pré-fixation et après fixation des missions que l'algorithme respecterait. Il vous suffit de ne randomisez pas ces fentes à l'étape 1. Vous trouverez que les solutions ne doivent pas être qu'optimales. Notre solution est O (N * M) au minimum, mais exécute en PHP (!) En moins d'une demi-seconde pour une usine de fabrication dans son ensemble. La beauté est en excluant les horaires mauvais rapidement à l'aide d'un bon test de could_schedule_be_valid.

Les gens qui sont utilisés pour le faire ne se soucient pas manuellement si cela prend une heure -. Ils savent juste qu'ils ne doivent pas le faire manuellement plus

Mike,

Je ne sais pas si vous avez jamais une bonne réponse à cette question, mais je suis assez sûr que la programmation par contraintes est le ticket. Même si un GA peut vous donner une réponse, CP est conçu pour vous donner beaucoup de réponses ou vous dire s'il n'y a pas de solution possible. Une recherche sur « la programmation par contraintes » et la planification devrait afficher beaucoup d'informations. Il est une des méthodes de la région et CP relativement nouvelles fonctionnent bien sur de nombreux types de problèmes où les méthodes traditionnelles d'optimisation enliser.

programmation dynamique a la Bell? sons un peu comme il y a une place pour elle. chevauchement sous-problèmes, sous-structures optimales

Une chose que vous pouvez faire est d'essayer de chercher des symétries dans le problème. Par exemple. pouvez-vous traiter toutes les infirmières comme équivalentes aux fins du problème? Si oui, alors vous ne devez considérer les infirmières dans un ordre arbitraire - vous pouvez éviter de considérer des solutions telles que toute infirmière i est prévue avant toute infirmière j où i > j . (Vous avez dit que les infirmières individuelles ont préféré des temps de changement, ce qui contredit cet exemple, bien que peut-être est un objectif moins important?)

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

  • Il est le mieux 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 (Pas le meilleur final)
  • Vous pouvez spécifier des contraintes et préférences facilement en ajustant les punitions de conditionnement physique pour les non rencontrés.
  • Vous pouvez spécifier délai 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 ..

    algorithmes génétiques Définition

    algorithmes génétiques Tutorial

    projet de planification de classe avec GA

Jetez aussi un coup d'oeil à: une question similaire et un autre

En utilisant la programmation CSP I fait programms pour shitfs automatique rostering. par exemple:

  1. système 2-quarts - testé pour les infirmières, 100+ 30 jours l'horizon temporel, 10+ règles
  2. système 3 équipes - testé pour les infirmières, 80+ 30 jours l'horizon temporel, 10+ règles
  3. système 3 équipes, 4-équipes - testé pendant 365 jours horizon, 10+ règles,

et deux systèmes similiar. Ils ont tous été testés sur mon PC à domicile (1.8GHz, dual-core). Les temps d'exécution ont toujours été-à-dire acceptable. pour 3 / il a fallu environ 5 min et RAM 300Mo.

La partie la plus difficile de ce problème a été la sélection solveur appropriée et une stratégie appropriée de résolution.

Métaheuristiques a très bien au international Infirmière Rostering Concours 2010 .

Pour une implémentation, consultez cette vidéo avec une infirmière continue rostering (java) .

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top