Gli altri algoritmi

La particolarità del metodo attualmente analizzato consiste nel fatto che riesce a racchiudere più algoritmi diversi, corrispondenti a diverse regole di priorità, come accennato all’inizio del paragrafo 3.2, pertanto risulta essere molto più completo del metodo precedentemente definito. E’ possibile passare da un algoritmo all’altro tramite la matrice riportata in seguito.

Fig. 3.12 Matrice per il passaggio tra i vari algoritmi

La matrice riportata in figura 12 contiene infatti tutti gli elementi riassuntivi necessari per l’implementazione dei diversi algoritmi: cambiando il numero presente nella cella F3 pertanto, è possibile implementare un algoritmo piuttosto che un altro, in particolare, per ogni numero:

1. Largest Candidate Rule (LCR): E’ l’algoritmo descritto fino a questo momento, pertanto le informazioni necessarie riguardano i tempi di esecuzione di ogni singola attività;

2. Most Following Tasks (MFT): La regola di priorità in questo caso si basa sulla selezione tra le varie attività in relazione al numero di operazioni che rimangono da effettuare per il completamento del prodotto;

3. Ranked Positional Weight (RPW): Il metodo è ampiamente descritto nel capitolo 2 e si basa sull’ordinamento delle attività in relazione al valore dell’indice RPW, il cui calcolo verrà descritto in seguito;

4. Smallest Candidate Rule (SCR): Consente di organizzare le operazioni in ordine decrescente in base al reciproco del tempo di esecuzione di ogni attività. Pertanto nelle celle da J6 a J12 saranno presenti le seguenti formule:

con tempo di esecuzione dell’operazione k-esima, indicato per ogni attività nella colonna

G.

5. Least Following Tasks (LFT): L’algoritmo si basa sulla classificazione delle operazioni in base al reciproco del numero di operazioni mancanti per ultimare il prodotto, sommato ad 1. Pertanto, nelle celle da K6 a K12 saranno presenti le seguenti funzioni:

Con r pari al numero di successori diretti e indiretti dell’operazione k, indicato nella colonna H.

Mentre gli algoritmi 4 e 5 si appoggiano ad altri e pertanto risultano essere di immediata comprensione, meritano una più dettagliata analisi gli algoritmi RPW e MFT, per la cui inizializzazione sono stati necessari un numero maggiore di step, che verranno trattati nel paragrafo successivo.

3.2.2.1. Algoritmi MFT e RPW

In questo paragrafo è mostrato il procedimento attraverso cui si arriva ad avere tutti i dati necessari per l’implementazione dei due algoritmi MFT e RPW, suddiviso in vari step da analizzare singolarmente.

 Step 1: Entrambi gli algoritmi si basano sulla costruzione di una matrice delle precedenze

iniziale, nella quale si inserisce il valore 1 se l’elemento in riga è un precedente diretto di quello in colonna. Questa fase viene implementata tramite la formula seguente, valida per la cella D63, ma che deve essere copiata con opportuni aggiustamenti in tutte le celle da C63 a I69 appartenenti alla suddetta matrice.

parentesi successiva, quella verde: questa restituisce VERO se l’uguaglianza è valida, altrimenti restituisce FALSO. Pertanto i risultati possibili sono 3:

o Se la precedenza viene trovata, la parentesi rossa restituisce un valore pari a 0 perché non c’è errore, mentre la parentesi verde ha come risultato 0 perché l’uguaglianza non è valida. Pertanto il risultato finale è 1;

o Se la precedenza non viene trovata ma si sta analizzando la diagonale della matrice, la parentesi rossa vale 1 e annulla la prima parte della formula, ma la relazione contenuta nella parentesi verde risulta verificata, pertanto restituisce un valore pari a 1;

o Se la precedenza non viene trovata e non ci si trova sulla diagonale, entrambe le parti della formula si annullano, pertanto il risultato totale è pari a 0

La matrice delle precedenze relativa al caso in esame è riportata nella figura sottostante.

Fig. 3.13 Step 1 inizializzazione metodi MFT e RPW

 Step 2: Questo passo contiene la costruzione delle matrici rappresentate in figura 14, il cui

numero varia a seconda delle attività da compiere. Ogni matrice raffigurata è il quadrato della matrice precedente, pertanto in ogni cella, con opportune modifiche, deve essere riportata la seguente formula, che è valida per la cella C73.

=MATR.PRODOTTO(C63:I69;C63:I69)

Il foglio excel svolge in automatico i calcoli per quanto riguarda ogni intera matrice, ma il numero stesso delle matrici deve essere stabilito in relazione a quante operazioni si devono svolgere. Nel caso in questione, dato che le operazioni sono 7 in totale, al massimo possono essere necessari 6 passi per arrivare dalla prima all’ultima attività da svolgere, ovvero fino a p6, pertanto, dato che ogni volta si eleva al quadrato e che 6 non è un elevamento a potenza di 2, è impossibile arrivare a p6 ma sarà necessario arrivare fino a p8, elevando la matrice al quadrato per 3 volte. E’ possibile a questo punto fare 2 osservazioni sulle matrici che si generano:

o Alla fine dei calcoli, la matrice risulterà essere triangolare, dato che di solito le operazioni vengono nominate in sequenza e risulta anomalo che l’operazione F preceda l’operazione A;

o Ad ogni passo, aumentano le celle contenenti valori maggiori di 0, che indicano una precedenza tra due operazioni, perché ad ogni passo alle precedenze dirette si aggiungono quelle indirette, distribuite in più passaggi. Ad esempio, se nella matrice iniziale la cella associata a “RIGA A-COLONNA E” era nulla, perché A non era diretta precedente di E, nella seconda matrice si ha invece un valore pari a 2, come è possibile notare in figura, perché A diventa precedente di E tramite le operazioni C e D.

3.15, nella quale sono riportati nella riga 100 tutti i valori dei tempi di esecuzione delle varie operazioni.

Fig. 3.15 Calcolo indici relativi agli algoritmi RPW e MFT

Per l’algoritmo MFT si identifica il numero di attività che seguono, tramite la formula sotto riportata, valida per la cella J93 ma da copiare, con opportune modifiche, nelle celle da J94 a J99.

=CONTA.SE(C93:I93;">0")-1

La suddetta formula conta tutti i valori della riga che contengono numeri maggiori di 0 e alla fine sottrae 1, dato che un’operazione non può seguire se stessa, anche se il suddetto tipo di “precedenza” era stato accettato nel calcolo delle precedenti matrici. I valori così ottenuti vengono riportati nella tabella iniziale riassuntiva dei dati, rappresentata in figura 12, nelle celle da H6 a H12. Per l’algoritmo RPW, invece, è necessario calcolare il relativo indice come descritto nel capitolo 2, tramite la formula riportata in seguito, valida per la cella K93 ma da adattare per il resto della colonna.

=SOMMA(SE(C93:I93;C$100:I$100;0))

La suddetta formula, somma i valori dei tempi di esecuzione relativi alle celle contenenti numeri diversi da 0, pertanto alla fine somma i tempi di completamento relativi alle operazioni da quella corrente fino alla fine. Anche questi valori, verranno riportati nell’opportuna colonna della tabella riassuntiva di figura 12, nelle celle da I6 a I12.