Licenze per dispositivo e utente: calcolare la migliore assegnazione

Per ottimizzare, dobbiamo trovare il minimo sottoinsieme di costo dei nodi che copre tutti gli archi (nella figura, i nodi in blu possono coprire tutto).

Si tratta di un noto problema matematico conosciuto come “copertura minima ponderata dei vertici” (minimum weighted vertex coverage) che, sfortunatamente, è un problema NP-difficile. Ovvero che richiede molto tempo per il calcolo della sua soluzione (ore, giorni, settimane).

E forse è questo il motivo per cui non abbiamo trovato uno strumento che implementi nativamente questa funzione.

Manteniamo la calma e usiamo l’euristica

In informatica c’è una tecnica progettata per risolvere un problema più velocemente rispetto ai metodi classici e lo si fa privilegiando la velocità rispetto all’ottimalità, alla completezza, all’accuratezza e alla precisione. Questa tecnica è nota come euristica.

Per nostra fortuna questo tipo di problema ha un ampio studio in letteratura, quindi abbiamo avuto una vasta gamma di euristiche disponibili tra cui scegliere e abbiamo iniziato la nostra “selezione euristica”. Cosa abbiamo fatto?

• Abbiamo creato uno scenario reale con un numero relativamente piccolo di utenti e dispositivi (circa 500). Così siamo stati in grado di calcolare il “reale” costo minimo della licenza usando un approccio di forza bruta (in pratica, abbiamo testato tutte le possibili assegnazioni e trovato la migliore)

• Successivamente, abbiamo testato vari tipi di euristica il cui scopo è quello di raggiungere la soluzione ottimale per un dato problema

• Abbiamo trovato un algoritmo Greedy (un algoritmo che esegue l’euristica di risoluzione del problema facendo la scelta migliore per ogni fase) che è stato in grado di calcolare in pochi secondi una buona combinazione di assegnazione della licenza utente/dispositivo.

Come si presenta l’algoritmo?

L’algoritmo che abbiamo scelto lavora in questo modo:

1. Va creata una coda di Utenti (ordinati in base al numero di dispositivi utilizzati)
2. Va creata una coda di Dispositivi (ordinati in base al numero di utenti)
3. Fino a quando entrambe le code non sono vuote, l’algoritmo procede in questo modo:
– Sceglie dall’alto di entrambe le code l’utente/dispositivo che ci permette di risparmiare di più
– Assegna una licenza a quell’utente/dispositivo
– Rimuove quell’elemento dalla sua coda
– Rimuove dall’altra coda tutti gli elementi correlati

Risultato

Applicando questo algoritmo, si ottiene una combinazione di assegnazione di licenze utente/dispositivo con un costo uguale alla soluzione ottimale, che utilizziamo di solito per alimentare lo strumento SAM.

Con questa combinazione, riusciamo a ottimizzare periodicamente (trimestralmente) l’assegnazione delle licenze con uno sforzo manuale pari a zero.

Sfruttando il basso tempo di calcolo dell’algoritmo, è possibile essere sempre aggiornati sulla situazione attuale dell’utilizzo dei dispositivi da parte degli utenti e scegliere sempre l’assegnazione che meglio si adatta alle esigenze dell’organizzazione.

*Un articolo co-firmato da Jary Busato (Consulente SAM/ITAM), Claudio Guarisco (Lead Developer) e Camilla Bottin (Marketing Specialist) di WEGG.