Scheduling

|

Indice

Cenni Storici……………………………………………………………….. 2
Definizione………………………………………………………………….. 2
Introduzione ai problemi di scheduling………………………………….. 3
Elementi di un problema di scheduling…………………………………... 3
1. Informazioni associate ai job……………………………………. 4
2. Caratteristiche rispetto al sistema……………………………… 4
3. Informazione per definire un problema di scheduling………... 114. Funzioni associate ai vari job…………………………………… 12
Esempi problemi di scheduling…………………………………………… 13
1. Scheduling system software Lekin……………………………… 13
2. Macchina singola…………………………………………………. 14
3. Macchine in parallelo……………………………………………. 16
4. Flow shop…………………………………………………………. 18
5. Job shop…………………………………………………………… 20
Bibliografia………………………………………………………………….. 23CENNI STORICI
Lo scheduling nasce con la ricerca operativa durante la seconda guerra mondiale. In questo periodo storico vennero radunati gruppi di scienziati, matematici, economisti, sociologi, strateghi ecc., con il compito di risolvere problemi riguardanti la localizzazione ottima di radar, il controllo del fuoco della contraerea, l’individuazione dei sottomarini nemici ecc.
Terminata laguerra si pensò che l’approccio messo a punto sino a quel momento potesse essere utilizzato anche per risolvere complessi problemi di natura civile e industriale. Nel periodo post-bellico si cominciò a sviluppare, nelle università, fondamenti teorici delle tecniche che avevano empiricamente sviluppato in precedenza, oltre che a ricercarne di nuove.
Le prime applicazioni furono nell’ambito dellapianificazione della produzione dell’industria del petrolio, poiché, all’inizio, solo le grandi industrie potevano permettersi gruppi di specialisti in quest’ambito. Successivamente, quando le categorie dei problemi risolvibili con tali metodi furono chiaramente individuate e le tecniche divennero standardizzanti, anche le medio-piccole imprese si affacciarono a questo mondo.
La disponibilitàdi computer sempre più potenti e veloci ha permesso lo sviluppo e l’affermarsi di questa disciplina.
DEFINIZIONE
Scheduling significa decidere riguardo l’assegnamento di risorse limitate (macchine, denaro, persone) in base alle varie attività e/o operazioni. Il risultato che si ottiene è un piano tempificato e dettagliato, avendo considerato i vari vincoli (restrizione temporale e capacitàdelle risorse) e i criteri di ottimizzazione (makespan, bilanciamento delle risorse, ritardo sui tempi di consegna e costo dell’assegnamento delle risorse). Il compito dello scheduling consiste nel dare indicazioni su ciò che deve essere fatto, quando, da chi e dove (impianto o macchina), andando a ottenere diversi obiettivi in conflitto tra loro: alta efficienza, bassi inventari ed alto servizio aiclienti.
Gli obiettivi principali dello scheduling sono:
1. Fairness (Equità): processi dello stesso tipo devono avere trattamenti simili (evitare l’attesa indefinita);
2. Balance (Bilanciamento): tutte le parti del sistema devono essere utilizzate al massimo;
3. Throughput: massimizzare il numero di job completati in un intervallo di tempo;
4. Turn around time: minimizzare iltempo medio di permanenza dei job nel sistema;
5. Tempo di risposta: minimizzare il tempo di risposta agli eventi;
6. Proporzionalità: assicurare un tempo di risposta proporzionale alla complessità dell’azione.
INTRODUZIONE AI PROBLEMI DI SCHEDULING
SCHEDULING
SCHEDULING

PROJECT SCHEDULING
S
PROJECT SCHEDULING
S
MACHINE SCHEDULING
MACHINE SCHEDULING

DETERMINISTICDETERMINISTIC
FUZZY
FUZZY
STOCHASTIC
STOCHASTIC

MORE OPERATIONS PER JOBS
MORE OPERATIONS PER JOBS
ONE OPERATION PER JOB
ONE OPERATION PER JOB

JOB SHOP
JOB SHOP
FLOW SHOP
FLOW SHOP
OPEN SHOP
OPEN SHOP
PARALLEL MACHINES
PARALLEL MACHINES
SINGLE MACHINE
SINGLE MACHINE

ELEMENTI DI UN PROBLEMA DI SCHEDULING
Nei problemi di scheduling viene indicata con macchina e task rispettivamente...