¿Existe un algoritmo para conseguir que un equipo de personas complete un determinado número de tareas lo más rápido posible, donde el tiempo que se tarda en completar una determinada tarea es diferente para diferentes personas? Cada tarea debe ser realizada en su totalidad por una sola persona (por ejemplo, no puede ser que la persona A haga la primera mitad de la tarea 1 y luego la persona B haga la segunda mitad de la tarea 1), y todos los miembros del equipo deben trabajar simultáneamente y de forma continua.
Para dar un ejemplo, hay tareas 1-5 y personas A-D.
- La persona A tarda a1 minutos en completar la tarea 1, a2 para la tarea 2, etc.
- Sea tA el tiempo total que la persona A dedica a las tareas, es decir, si A debe realizar las tareas 3 y 4, tA = a3+a4.
- Cada tarea debe ser completada por una persona, ninguna tarea requiere que otras sean completadas previamente.
- Las 4 personas pueden trabajar simultáneamente para completar todas las tareas, el tiempo total viene dado por T = max{tA,tB,tC,tD}, que queremos minimizar.
Obviamente, el algoritmo sería idealmente generalizable a m tareas y n personas.
Además, si no existe un algoritmo de este tipo, ¿cómo sugieres que se construya uno? Actualmente sólo se me ocurre asignar la tarea relativa a la mayor diferencia entre el tiempo más rápido y el segundo más rápido para completarla, y no sé muy bien a dónde ir a partir de ahí.
Tengo la sensación de que esto es similar a algún algoritmo de empaquetado de contenedores, sin embargo cada trozo de "basura" tiene un tamaño diferente dependiendo del contenedor en el que se coloque. También creo que esto es similar a lo que encontré aquí Problema de asignación con tareas y horas divisibles pero aquí la gente puede dividir las tareas, y la pregunta no fue respondida completamente.
Espero haber aclarado lo suficiente el problema, puedo responder a cualquier pregunta si es necesario.
