¿Qué tienen en común la planificación de la construcción de un edificio, la producción industrial, la gestión de pedidos limitando los retrasos o incluso la preparación de una mochila por parte de una excursionista, o el reparto equitativo de unas cuantas monedas entre niños? Cada una de estas tareas exige resolver un problema de planificación de tareas. Hay que decidir cuándo debe realizarse cada tarea para que todo salga lo mejor posible.
Construir un edificio: ¿qué hacer y cuándo? ------------------------------------------
Tomemos el ejemplo de la construcción de un edificio. Una jefa de obra debe organizar la llegada de cada gremio según avancen los trabajos. Conoce las tareas que hay que realizar, sus respectivas duraciones y sus precedencias, es decir, qué tareas deben terminarse antes de poder comenzar otra (véase la tabla). Por ejemplo, la albañilería debe terminarse antes de empezar la fontanería.
Podemos representar esto mediante un grafo de precedencias, como se muestra a continuación, donde los números sobre los arcos indican las duraciones.