Optimale changement d'algorithme de planification
J'ai essayé pendant un certain temps à résoudre un problème d'ordonnancement pour une piscine que j'ai utilisé pour travailler. Ce problème est comme suit...
Il y a X nombre de sauveteurs qui travaillent à la piscine, et chacun a un nombre spécifique d'heures qu'ils aimeraient travailler. Nous espérons continuer à le nombre moyen d'heures de chaque sauveteurs souhaité nombre d'heures le plus bas possible, et aussi équitable que possible pour tous. Chaque sauveteur est aussi un étudiant de collège, et donc auront un horaire différent de disponibilité.
Chaque semaine à la piscine du calendrier des événements est différente de la dernière, un nouveau programme doit être créé chaque semaine.
À l'intérieur de chaque journée, il y aura donc beaucoup de sauveteurs requis pour certains intervalles de temps (ex: 3 gardes de 8h-10h, 4 gardes de 10am-3pm, et de 2 gardes de 3pm-10h). C'est là la partie la plus difficile. Il n'y a pas clairement défini quarts de travail (machines à sous) pour chacun des sauveteurs en (en raison du fait que la création d'un document peut ne pas être possible qu'à condition que la disponibilité des sauveteurs en plus de l'évolution hebdomadaire de la piscine calendrier des événements).
Par conséquent, un programme doit être créé à partir d'une ardoise vierge fournie avec...
- Les Sauveteurs et leurs informations (nombre d'heures, de disponibilité)
- La piscine du calendrier des événements, plus le nombre de gardes à être en service à tout moment
Le problème peut maintenant être définies comme des "Créer un horaire possible qui couvre le nombre de gardes à tout moment chaque jour de la semaine ET être aussi équitable que possible pour tous les sauveteurs dans la programmation."
La création possible d'un calendrier qui couvre le nombre de gardes à tout moment chaque jour de la semaine est la partie du problème qui est une nécessité et doit être complètement résolu. La seconde moitié, au sujet d'être aussi équitable que possible pour tous les sauveteurs qui complique singulièrement le problème m'a conduit à croire que j'ai besoin d'une approximation de la démarche, puisque le nombre possible de façon à diviser une journée de travail peut être ridicule, mais peut parfois être nécessaire, comme le seul possible, le calendrier peut être ridicule pour l'équité.
Modifier: l'Un des plus couramment proposé des algorithmes j'ai trouver est le "Hôpitaux/Résidents problème", mais je ne crois pas que cela sera applicable car il n'y a pas clairement défini fentes pour les travailleurs.
OriginalL'auteur yiati | 2013-06-17
Vous devez vous connecter pour publier un commentaire.
Vous avez besoin pour transformer votre critère de l'équité dans une fonction objective. Ensuite, vous pouvez choisir à partir de n'importe quel nombre de lieu de travail les outils de planification.Par exemple, vous décrivez vouloir minimiser la différence moyenne entre le souhaité et les heures. Cependant, j'aimerais vous suggérons de tenir compte de la réduction de la différence maximale. Cela semble juste (pour moi) et il donnera généralement lieu à un horaire différent.
Le problème, cependant, est un peu plus complexe. Par exemple, si un garde est toujours en court-circuit, tandis que les autres reçoivent tous leurs heures, que c'est injuste. De sorte que vous pouvez introduire des variables dans votre équité modèle qui représentent le cumul de la différence pour chaque garde depuis des semaines précédentes. Aussi, à une heure de différence pour une garde qui veut travailler quatre heures par semaine, peut être plus injuste que pour un gardien qui veut travailler vingt. Pour gérer ce genre de choses, vous pourriez poids aux écarts.
Vous pourriez avoir à introduire de contraintes, telles que les que les pas de garde est attribué plus d'un certain nombre d'heures, ou que chaque garde a une certaine quantité de temps entre les quarts de travail, ou que le nombre de logements affectés à un garde dans une semaine ne doit pas dépasser un certain seuil. De nombreux outils de programmation ont des capacités pour gérer ces types de contraintes, mais vous devez les ajouter au modèle.
Quels types d'outils de planification ont déjà ces capacités et/ou de ce sont ces capacités afin que je n'ai pas recréer la roue ici, si il n'est pas nécessaire?
Je ne sais pas trop sur les outils existants, et je certainement ne peut pas recommander l'une sur l'autre. À partir de cette discussion, il semble que whentowork.com la plupart de ce que vous voulez. D'autres outils sont répertoriés ici (ils ont tendance à être de plus en plus lourds personnel de gestion des paquets) et vous pouvez Google "sauveteur planification" de trouver d'autres ressources.
OriginalL'auteur Ted Hopp
Une façon de résoudre ce est avec programmation par contraintes - l'article de Wikipédia fournit des liens vers plusieurs de contrainte de langages de programmation et des bibliothèques. Voici un papier décrivant comment utiliser la programmation par contraintes pour résoudre des problèmes de planification.
Une autre option est d'utiliser un algorithme glouton pour trouver un (éventuellement nul) de la solution, et ensuite utiliser la recherche locale pour rendre la solution non valide valide, ou encore pour améliorer la qualité de la sous-optimale gourmand solution. Par exemple, commencer par l'affectation de chaque maître-nageur préféré heures, ce qui va donner lieu à de trop nombreux gardes étant prévue pour quelques fentes et aussi quelques gardes étant affecté d'un nombre ridicule d'heures; puis utiliser la recherche locale pour l'onu-pour attribuer la garde avec le plus d'heures de jeux qui ont de trop nombreux gardes affectés.
C'est la généralisation de l'attribution, ce qui signifie qu'il est NP-dur, à moins que la fonction de coût est trivial
J'ai un problème similaire de planification des ressources pour un travail de patron, j'ai 5 employés, qu'ils travaillent tous sous un fixe cycliques 4 3 3 4, soit 4 jours de travail, 3 jours de repos, 3 jours de travail, 4 jours de congé, maintenant la contrainte est chaque jour un minimum de 3 employés. J'ai eu mal à la tête depuis quelques jours mais ne savez pas par où commencer, pourriez-vous nous donner un guide, une grâce.
Ministère actuel est un petit ministère, seulement quelques personnes, dans le pire des cas, on peut itérer sur tous les cas de trouver la solution optimale, mais pour d'autres ministères (ils ont leur propre modèle de travail), certains d'entre eux ont plus de 60 ans de travail sur les ressources en vertu de changement, nous devons donc trouver un moyen de résoudre ce tirer les cheveux de problème.
Je soupçonne que, dans une de 14 jours de la période de travail la meilleure solution pour avoir N/14 employés commencent leur période de travail sur n'importe quel jour donné, par exemple, avec 28 employés ont 2 début de leur période de travail sur les jours 1, 2 démarrez le jour 2, etc. Je vous suggère d'écrire un simple algorithme glouton qui attribue une répartition égale ainsi qu'un algorithme qui affecte une distribution aléatoire, exécutez l'algorithme aléatoire quelques milliers de fois, et voir si elle bat l'égalité de la distribution; si ce n'est pas le cas, utilisez l'égalité de la distribution, si c'est le cas alors un meilleur solution peut être appelé à
OriginalL'auteur Zim-Zam O'Pootertoot