Supongamos que hay un número ilimitado de trabajadores, cada uno de los cuales puede completar una tarea, cada uno de los cuales toma algún tiempo. También hay restricciones de precedencia donde una tarea no se puede completar hasta que se termina otra. ¿Cuál es la cantidad mínima de tiempo necesaria para que se complete cada tarea respetando el orden de prioridad?

Como ejemplo, digamos que tienes 3 tareas.

La primera tarea tarda 10 unidades de tiempo en completarse, la segunda tarda 5 unidades de tiempo en completarse y la tercera toma 6 unidades de tiempo en completarse.

La restricción es que la segunda tarea no puede iniciarse hasta que la tercera tarea finalice.

Dado esto, puede concluir que el tiempo mínimo necesario para que se completen todas las tareas respetando la prioridad es 11.

Esto se debe a que puede realizar las tareas 1 y 3 (que toman los tiempos 10 y 6 respectivamente) simultáneamente, y una vez finalizada la tarea 3, puede comenzar con la tarea 2 (que lleva 5 unidades de tiempo). Así, todas las tareas terminarán en el momento 11.

Parece que esto podría resolverse con un ordenamiento topológico, que le daría el orden en el que debe completar las tareas para satisfacer las restricciones.

Por ejemplo, en el problema, después de clasificar topológicamente las tareas que terminaría con

Task 1 (10 Units of time) -> Task 3 (6 Units of time) -> Task 2 (5 Units of time)

Sin embargo, una vez que obtenga este orden en el que se ocupa de las tareas, ¿cómo determina cuáles se pueden hacer simultáneamente y cuáles se deben hacer una después de la otra? Además, ¿cómo calcula el tiempo mínimo necesario para que todos ellos terminen?