Che cosa hanno in comune la pianificazione della costruzione di un edificio, la produzione industriale, la gestione degli ordini limitando i ritardi o persino la preparazione dello zaino da parte di un’escursionista, o anche la ripartizione equa di alcune monete fra bambini? Ciascuna di queste attività richiede la risoluzione di un problema di schedulazione. Occorre decidere quando svolgere ogni attività affinché tutto proceda nel migliore dei modi.
Costruire un edificio: cosa fare e quando? ------------------------------------------
Prendiamo l’esempio della costruzione di un edificio. Una responsabile di cantiere deve organizzare l’intervento di ciascuna categoria professionale in base all’avanzamento dei lavori. Conosce le attività da svolgere, le rispettive durate e i loro vincoli di precedenza, cioè quali attività devono essere terminate prima che se ne possa iniziare un’altra (vedi la tabella). Per esempio, la muratura deve essere terminata prima di iniziare l’impianto idraulico.
Possiamo rappresentare la situazione con un grafo delle precedenze, come illustrato di seguito, in cui i numeri sugli archi indicano le durate.