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