La teoria dello scheduling è una branca della ricerca operativa che si concentra sul calcolo delle date ottimali di esecuzione delle attività. Per questo, molto spesso è necessario allo stesso tempo allocare le risorse necessarie per l'esecuzione di questi compiti. Un problema di pianificazione può essere pensato come un sottoproblema di pianificazione in cui si tratta di decidere sull'esecuzione operativa delle attività pianificate.
Un problema di schedulazione consiste nell'organizzare lo svolgimento delle attività nel tempo, tenendo conto dei vincoli temporali (scadenze, vincoli di sequenziamento) e dei vincoli relativi alla disponibilità delle risorse richieste.
Nella produzione (manifattura, beni, servizi) può presentarsi come un problema laddove è necessario innescare e controllare l'avanzamento di un insieme di ordini attraverso i diversi centri che compongono il sistema.
La pianificazione è una soluzione al problema della pianificazione. È definito dalla pianificazione per l'esecuzione dei compiti ("ordine" e "calendario") e l'allocazione delle risorse e mira a raggiungere uno o più obiettivi. Una pianificazione è molto spesso rappresentata da un diagramma di Gantt .
Un compito è un'entità elementare situata nel tempo da una data di inizio e / o fine, la cui realizzazione richiede una durata, e che consuma mezzi secondo una certa intensità. Alcuni modelli includono la nozione di data di scadenza, una data in cui l'attività deve essere completata; in questi casi il ritardo induce una penalità.
A seconda del problema, le attività possono essere eseguite in blocchi o devono essere eseguite senza interruzioni; si parla quindi rispettivamente di problemi preventivi e non preventivi. Quando le attività non sono soggette a vincoli di coerenza, si dice che sono indipendenti.
Diverse attività possono costituire un'attività e diverse attività possono definire un processo .
La risorsa è un mezzo tecnico o umano destinato ad essere utilizzato per il raggiungimento di un compito e disponibile in quantità limitata, la sua capacità.
Occorre distinguere diversi tipi di risorse. Una risorsa è rinnovabile se, dopo essere stata assegnata a una o più mansioni, è nuovamente disponibile nella stessa quantità (uomini, macchine, attrezzature in genere); la quantità di risorse utilizzabili in qualsiasi momento è limitata. Altrimenti, è consumabile (materie prime, budget); il consumo (o accumulo) complessivo nel tempo è limitato. Una risorsa è doppiamente vincolata quando sia il suo utilizzo istantaneo che il consumo complessivo sono limitati (il denaro è un buon esempio).
Che sia rinnovabile o consumabile, la disponibilità di una risorsa può variare nel tempo. La sua curva di disponibilità è generalmente nota a priori, tranne nei casi in cui dipende dal posizionamento di determinate attività generatrici.
Nel caso delle risorse rinnovabili, si distingue anche principalmente tra risorse disgiuntive che possono eseguire un solo compito alla volta (macchina utensile, robot manipolatore) e risorse cumulative che possono essere utilizzate da più attività contemporaneamente ma in numero limitato (team dei lavoratori, posto di lavoro).
I vincoli esprimono restrizioni sui valori che le variabili decisionali possono assumere simultaneamente. Distinguiamo:
Nella risoluzione di un problema di schedulazione si può scegliere tra due principali tipologie di strategie, mirate rispettivamente all'ottimalità delle soluzioni, o più semplicemente alla loro ammissibilità.
L'approccio di ottimizzazione presuppone che le soluzioni candidate a un problema possano essere ordinate razionalmente secondo uno o più criteri di valutazione numerica, costruiti sulla base di indicatori di performance. Cercheremo quindi di minimizzare o massimizzare tali criteri. Notiamo ad esempio quelli
La pianificazione della ricerca si è spesso basata sul presupposto di un universo prevedibile in cui tutti i dati del problema sono noti in anticipo e nessun problema della vita reale compromette la pianificazione. In pratica possono verificarsi disturbi di varia natura: guasti alle macchine, assenze dei dipendenti, ritardi nelle consegne. In questo caso è necessario rivedere la schedulazione e una schedulazione molto buona calcolata in base ai dati iniziali potrebbe perdere la sua qualità.
La pianificazione robusta è una branca abbastanza recente della pianificazione, che non mira più solo a fornire pianificazioni ottimali (o quasi ottimali), ma soprattutto pianificazioni robuste. Il punto di forza è la capacità di mantenere una pianificazione delle prestazioni nonostante il verificarsi di disturbi.
Esistono diversi tipi di approcci robusti: