Identifica l'algoritmo per le mie esigenze di allocazione delle risorse

Question

Identifica l'algoritmo per le mie esigenze di allocazione delle risorse

#1 da (3 voti)

5

Sto cercando di automatizzare un'attività e mi manca il vocabolario giusto per cercare l'algoritmo corretto. Sembra davvero un problema comune che è stato probabilmente risolto molte volte prima.

Tutto quello che sto cercando è che qualcuno mi indichi la direzione giusta o mi aiuti con i giusti termini di ricerca per cercare una soluzione / algoritmo. Se ti capita di sapere di una libreria actuall (javascript), allora ancora meglio.

Scenario creato

Dire che ho 3 "secchi", Bucket A , Bucket B e Bucket C . Ognuno di questi può contenere un certo numero di "palle".

Bucket A : Capacity 10 balls.
Bucket B : Capacity 15 balls.
Bucket C : Capacità 5 palline.

Ora, ho anche un inventario di palle e ognuno può solo essere messo in certi "secchi". Una palla può andare solo in Bucket 2 , la palla successiva può entrare Bucket 1 OR Bucket 3 e così via.

Ora ... ho bisogno di determinare il modo migliore per posizionare le palle per cercare di riempire ogni "secchio" alla sua capacità (o il più vicino possibile).

Scenario reale

Il mio vero motivo è di pianificare people (palle) per visitare locations (bucket) per un numero di ore richiesto (capacità del bucket). Però, a causa dei seguenti motivi tutte le librerie / algoritmi che ho trovato durante la ricerca di "pianificazione" finora non funziona nel mio scenario.

Non mi interessa affatto le ore di inizio / fine, solo person - > %codice%
Le mie persone (palle) hanno tutte un elenco rigoroso di luoghi che possono visitare. Ognuno è unico.
Ogni persona è disponibile per un numero arbitrario di intere ore (intere) che possono trascorrere a esattamente una location . Utilizzare qualcuno disponibile per 8 ore solo per 7 di queste ore è OK.
Ogni posizione (bucket) richiede un certo numero di ore che cerco di soddisfare al meglio delle mie capacità con qualsiasi combinazione di persone.

Ho ~ 50 località e ~ 100 persone. Non è un requisito che ottengo una soluzione perfect , ma "abbastanza vicino".

Ho trovato schedule.js che sembra fantastico, ma non sono riuscito ad abusarne per soddisfare le mie esigenze.

algorithms scheduling

posta Luggage 10.07.2014 - 06:32

fonte

1 risposta

Leggi altre domande sui tag algorithms scheduling

Redex e strategie di riduzione Dove collocare la convalida del formato in un modello di dominio "elegante" di CQRS?

score 3 · Accepted Answer

Se il numero di ore che ogni persona è disponibile è costante (ad esempio, è sempre 1 ora), allora il tuo problema può essere modellato come Flusso di rete , facilmente risolvibile in tempo polinomiale con l'algoritmo di Ford-Fulkerson .

Per costruire la tua rete di flusso, crea due livelli di nodi; il primo livello rappresenta le tue palle, il secondo livello rappresenta i tuoi secchi. Aggiungi un bordo dalla sorgente a ciascuna sfera con capacità 1. Aggiungi un bordo da ogni sfera a ciascun contenitore compatibile con capacità 1. Aggiungi un bordo da ciascun secchio al lavandino con capacità corrispondente alla capacità del secchio. Il flusso massimo rappresenta l'assegnazione ottimale.

Altrimenti, se il numero di ore che ogni persona può contribuire varia, allora l'algoritmo di cui sopra non funziona a causa del vincolo che ogni persona può visitare solo una posizione. (Il flusso di rete risolverebbe il problema, ma potrebbe dividere le ore di una persona in più postazioni.) In questo caso si ha qualcosa di relativo a un Problema di Knapsack o Bin Packing .

Se il numero di ore che ogni persona può contribuire è un numero intero, puoi risolverlo tramite la programmazione dinamica pseudo-polinomiale. Altrimenti, devi:

Implementa un algoritmo di backtracking a forza bruta. Questo ti darà una soluzione esatta ma non funzionerà se il numero di persone o luoghi supera i 50 circa.
Implementare un metodo euristico combinatorio, come suggerito da Doc Brown. Hill Climbing o Ricottura simulata funzionerà molto bene per questo problema e ti darà risultati ottimali o quasi ottimali molto rapidamente.