Problema de programación de trabajos

Question

Estoy trabajando en una aplicación en la que necesito programar automáticamente trabajos para los miembros en un horario rotativo. No soy muy bueno para explicar las reglas, así que aquí hay algunos datos para ayudar:

Posiciones: Título de un trabajo, con reglas tales como los lunes y los miércoles por semana.
Categorías: Un conjunto de posiciones
Grupos: Otro conjunto de posiciones. Las posiciones en el mismo grupo no se pueden asignar el mismo día
Miembros: usuarios asignados a puestos en una fecha determinada.

Para cada fecha del mes, los miembros se asignan a las posiciones (ambas en orden ascendente). Si un miembro está asignado a un puesto en una categoría, la próxima vez que aparezca un puesto en la misma categoría, se asignará el siguiente miembro alfabéticamente (o el principio de la lista), por ejemplo.

Miembros: M1, M2, M3, M4
Las posiciones en la Categoría C1: P1, P2, P3
miembros en posición P1: M1, M2, M3, M4
miembros en la posición P2: M1, M2, M3
Miembros en la posición P2: M1, M3, M4

Si se asigna M1 para P1, si P2 viene a continuación, se asignará M2. Se introduce una capa adicional de complejidad donde si P3 viene a continuación, se asigna M3. El sistema debe realizar un seguimiento del hecho de que M2 fue 'omitido' y asignar M2 a continuación si está disponible, luego asignar M4 a continuación, o esperar hasta que llegue a una posición donde M2 ​​esté disponible (esto se vuelve adicionalmente complejo cuando hay muchos 'omitidos' 'miembros).

También se omitirá un miembro si él ha indicado que no estará disponible en esa fecha. El sistema necesita dar prioridad a los miembros omitidos, de alguna manera identificarlos cuando aparezcan y luego saltar a la siguiente persona lógica en la lista. La omisión también se aplica a grupos debido a enfrentamientos de fechas.

Ya tengo una solución temporal [y desordenada] que ya no entiendo aunque tengo muchos comentarios explicando cada paso. Sus debilidades están en lidiar con los miembros omitidos.

Si fueras a codificar esto, ¿cómo lo harías? Estoy implementando esto en PHP, pero el pseudocódigo también funcionaría.

Answer 1

Mi solución: Necesita un PriorityQueue (que está disponible en PHP bajo SplPriorityQueue). PriorityQueue le da elementos con prioridad descendente (ordenados por valores, el valor más pequeño tiene la prioridad más alta).

Cada miembro obtiene un valor asignado.Este valor es un número ASCII con n dígitos (puede usar 8 dígitos para mayor comodidad), rellenado con ceros en n posiciones. Después de eso, añada el nombre. También agrega a cada miembro de las posiciones disponibles

SO (n = 5):

• valor M1: 99999Albert P1, P2, P3
• valor M2: 99999Susi P1, P2
valor
• M3 : 99999Bob P1, P3

Esto hace que sea fácil ordenar los miembros por prioridad y nombre.

Preparación:

Un día soleado. Está recuperando los puestos asignados y una categoría para un día determinado. Cada miembro se carga en una larga lista. Cada miembro que no aparece en el trabajo no está cargado, pero obtiene su valor disminuido en menos dos. Bob no está aquí, entonces su nuevo valor obtiene 99997Bob. Esto significa que Bob se seleccionará automáticamente la próxima vez. Todos los demás miembros obtienen su valor disminuido en menos uno.

Las posiciones asignadas para un día específico se asignan (uso SplObjectStorage):

P1-> M1, M2, M3, M4, etc. P2-> etc.

El mapa contiene sólo las posiciones que debe ser asignado este día. Después del

Filtro: Debe buscar los grupos y eliminar las posiciones en el mapa que no se pueden asignar este día. La descripción de tu grupo no está nada clara.

Asignar:

• se elige la posición para asignar
• obtener la lista de miembros que puede ocupar la posición
• remover a los miembros disponibles de la lista y ponerlos en el PriorityQueue
• Asignar la posición por extract() desde PriorityQueue (la asignación correcta se realiza de forma automática). Cada miembro que se le asignará tendrá su valor aumentado en uno (por lo tanto, la disminución y el aumento nivelarán si está aquí y trabajando). Si está aquí y no está asignado a un puesto por el motivo que sea, obtiene una pequeña penalización de uno. Si no estás aquí, obtienes una penalización de dos.
• Después de la finalización, vuelva a colocar los miembros restantes en la lista, borre la PQueue y continúe con la siguiente tarea.

Advertencias:

• hay que tener cuidado de que siempre hay suficiente gente para una posición.

Answer 2

uff. No te sigo la descripción, pero en situaciones similares he usado sql para resolver este tipo de problema. si está usando php, supongo que tiene sql disponible.

lo que sugeriría hacer es encontrar una forma de almacenar esta información en un conjunto de tablas y luego averiguar qué consulta sql le da la respuesta que desea. muy a menudo es mucho más simple de hacer en sql que en un lenguaje de procedimiento.

para la pieza omitida, por ejemplo, es posible que tenga una columna que registra cuándo se asignó por última vez, y luego ordene por eso (para seleccionar a la persona que no se ha asignado durante mucho tiempo). alternativamente, puede tener el número de veces omitido como columna y ordenarlo.

Answer 3

Lo que entiendo es que hay 'm' miembros y 'n' posiciones.

Categoría: un grupo de puestos: ¿un miembro asignado a un puesto en la categoría no puede tener otro?

Grupo: un grupo de posiciones: las posiciones en el mismo grupo deben asignarse en días diferentes.

Última cosa, una posición tiene una lista de miembros que pueden llenarla.

Al considerar esto desde el punto de vista de la estructura de datos, coloque los miembros en una lista vinculada: cada miembro debe tener una lista adicional de [posición, día] que finalmente se les asigne. Luego, para cada posición, tenga una lista de referencias a los miembros que pueden ocupar ese puesto. Implementar categorías como otra lista de referencias para una posición en cuanto a las categorías en las que se encuentra.

La asignación real: tener un contador de días = 0 e iterar por las posiciones. Para cada posición P, recorra los miembros que pueden llenarlo. Un miembro de M puede ocupar el puesto si:

• Cualquier cargo que ha llenado P2 no comparte una categoría con P.
• Cualquier cargo que ha llenado P2 con el día = daycounter no comparte un grupo con P.

Si puede completar la posición, el par de [posición, día] se agrega al miembro, y el nodo del miembro se mueve al FINAL de la lista (es por eso que las referencias son necesarias - todos las referencias siguen siendo válidas aunque el nodo se movió). Esto garantiza que a los miembros "omitidos" se les dé la más alta prioridad, y a los miembros que no fueron contactados se les dio la siguiente prioridad más alta.

Una vez que se completa una posición, vaya a la siguiente posición. Si el puesto comparte un grupo con un puesto ya asignado, sáltelo, recorra todas las posiciones hasta que pueda asignar tantas posiciones como pueda el día 1. Luego, incremente el contador del día y repita el día 2. Esto debería darle una asignación máxima (no estoy seguro del máximo) para todos los trabajos.

Consejo: cuando mueva un miembro al final de la lista de miembros, para evitar tener que atravesar la lista, conserve una referencia al final; para la siguiente posición, debe comenzar desde el principio de todos modos, por lo tanto no tiene sentido pasar por todo el asunto.