Algoritmo di pianificazione delle risorse ponderato e con bilanciamento del carico

Question

Un'applicazione software su cui sto lavorando deve essere in grado di assegnare attività a un gruppo di utenti in base al numero di attività che hanno attualmente, dove gli utenti con il minor numero di attività hanno maggiori probabilità di ottenere l'attività successiva.Tuttavia, il carico di attività corrente dovrebbe essere trattato come una ponderazione, piuttosto che come una definizione di ordine assoluto.IOW, devo implementare un algoritmo ponderato di bilanciamento del carico.

Supponiamo che ci siano cinque utenti, con il seguente numero di attività:

UN:4 B:5 C:0 D:7 E:9

Voglio dare la priorità agli utenti per l'attività successiva nell'ordine CABDE, dove C ha maggiori probabilità di ottenere l'incarico ed E, il meno probabile.Ci sono due cose importanti da notare qui:

• Il numero di utenti può variare da 2 a decine.
• Il numero di attività assegnate a ciascun utente può variare da 1 a centinaia.

Per ora, possiamo considerare tutte le attività allo stesso modo, anche se non mi dispiacerebbe includere l'attività difficile come variabile che posso utilizzare in futuro, ma questa è puramente la ciliegina sulla torta.

Le idee che mi sono venute finora non sono molto buone in alcune situazioni.Potrebbero assegnare un peso eccessivo agli utenti se è presente un numero elevato di utenti oppure potrebbero risultare piatti se un utente non ha attività correnti oppure...

Ho provato a curiosare sul web, ma non ho avuto molta fortuna.Qualcuno può darmi un breve riassunto di un algoritmo che funzionerebbe bene?Non ho bisogno di un'implementazione vera e propria, farò quella parte, solo una buona descrizione.In alternativa, esiste un buon sito web liberamente accessibile?

Inoltre, anche se apprezzo sicuramente la qualità, non è necessario che questa sia statisticamente perfetta.Quindi, se riesci a pensare a una tecnica buona ma non eccezionale, mi interessa!

Answer 1

Come hai sottolineato, questo è un problema di bilanciamento del carico.Non è davvero un problema di pianificazione, dal momento che non stai cercando di minimizzare nulla (tempo totale, numero di lavoratori simultanei, ecc.).Non ci sono vincoli speciali (durata del lavoro, coincidenze temporali, serie di competenze da abbinare, ecc.). Quindi in realtà il tuo problema si riduce alla selezione di una funzione di ponderazione appropriata.

Dici che ci sono alcune situazioni che vuoi evitare, come le ponderazioni degli utenti che sono troppo vicine tra loro.Puoi fornire maggiori dettagli?Ad esempio, cosa c'è di sbagliato nel rendere le possibilità di incarico proporzionali al carico di lavoro attuale, normalizzato dal carico di lavoro degli altri lavoratori?Puoi visualizzarlo come una sequenza di blocchi di diverse lunghezze (le attività), imballati in una serie di contenitori (i lavoratori), dove stai cercando di mantenere l'altezza totale dei contenitori il più uniforme possibile.

Con ulteriori informazioni, potremmo formulare consigli specifici sulle funzioni che potrebbero funzionare per te.

Modificare:esempio di funzioni di bilanciamento del carico

In base ai tuoi commenti, ecco alcuni esempi di semplici funzioni che possono darti comportamenti di bilanciamento diversi.Una domanda fondamentale è se si desidera un comportamento deterministico o probabilistico.Darò un paio di esempi per ciascuno.

Per usare l'esempio nella domanda: ci sono 4 + 5 + 0 + 7 + 9 = 25 lavori attualmente assegnati.Vuoi scegliere chi otterrà il lavoro 26.

1) Task farm semplice. Per ogni lavoro, scegli sempre il lavoratore con il minor numero di lavori attualmente in sospeso.I lavoratori veloci riescono a fare di più, ma tutti finiscono più o meno nello stesso momento.

2) Garantire un carico di lavoro equo. Se i lavoratori lavorano a velocità diverse e non vuoi che alcuni facciano più degli altri, tieni traccia del numero di lavori completati e in sospeso per ciascun lavoratore.Assegna il lavoro successivo per mantenere questo numero distribuito equamente (i lavoratori veloci ottengono pause gratuite).

3) Normalizzazione lineare di base. Scegli un numero massimo di lavori che ogni lavoratore può avere.Il carico di lavoro di ciascun lavoratore è normalizzato su quel numero.Ad esempio, se il numero massimo di lavori/lavoratore è 15, è possibile aggiungere altri 50 lavori prima di raggiungere la capacità.Quindi per ogni lavoratore la probabilità che gli venga assegnato il lavoro successivo è

P(A) = (15 - 4)/50 = 0.22  
P(B) = (15 - 5)/50 = 0.2  
P(C) = (15 - 0)/50 = 0.3  
P(D) = (15 - 7)/50 = 0.16  
P(E) = (15 - 9)/50 = 0.12

Se non desideri utilizzare una soglia massima specifica, puoi utilizzare come limite il lavoratore con il numero corrente di lavori in sospeso più elevato.In questo caso, quello è il lavoratore E, quindi le probabilità sarebbero

P(A) = (9 - 4)/20 = 0.25  
P(B) = (9 - 5)/20 = 0.2  
P(C) = (9 - 0)/20 = 0.45 
P(D) = (9 - 7)/20 = 0.1  
P(E) = (9 - 9)/20 = 0

Si noti che in questo caso la normalizzazione garantisce che al lavoratore E non possa essere assegnato alcun lavoro: è già al limite.Inoltre, solo perché C non ha niente da fare non significa che gli sia garantito un nuovo lavoro (è semplicemente più probabile).

Puoi facilmente implementare la funzione di scelta generando un numero casuale R compreso tra 0 e 1 e confrontandolo con questi limiti.Quindi se R è < 0,25, A ottiene il lavoro, 0,25< R < 0,45, B ottiene il lavoro, ecc.

4) Normalizzazione non lineare. Utilizzare una funzione di registro (invece della sottrazione lineare) per ponderare i numeri è un modo semplice per ottenere una normalizzazione non lineare.Puoi usarlo per distorcere le probabilità, ad es.per rendere molto più probabile che i lavoratori senza molti posti di lavoro ricevano di più.

Il punto è che il numero di modi per farlo è praticamente illimitato.La funzione di ponderazione utilizzata dipende dal comportamento specifico che stai tentando di abilitare.Spero che questo ti abbia dato alcune idee che puoi usare come punto di partenza.