Distribuzione ottimale del carico con carico di lavoro massimo

Question

Distribuzione ottimale del carico con carico di lavoro massimo

#1 da (1 voti)

6

Devo trovare una distribuzione ottimale di alcune attività di corrispondenza su più lavori; ogni lavoro è limitato da un carico di lavoro massimo e le attività raggruppate dovrebbero massimizzare il carico di lavoro all'interno dello stesso lavoro.

Tuttavia, le attività con valori simili all'interno della stessa fonte dovrebbero avere una priorità più alta da includere nello stesso lavoro.

Ad esempio: Immettere attività con il carico di lavoro previsto

Task  Source1  Source2  Workload
  1     A        A        40
  2     A        B        15
  3     B        A        48
  4     B        B        18
  5     C        A        32
  6     C        B        24
  7     A        C        8

Se il carico di lavoro massimo è 50, le attività dovrebbero essere distribuite come segue.

Job1
Task  Source1  Source2  Workload
  1     A        A        40
  7     A        C        8

Job2
Task  Source1  Source2  Workload
  2     A        B        15
  6     C        B        24

Job3
Task  Source1  Source2  Workload
  3     B        A        48

Job4
Task  Source1  Source2  Workload
  4     B        B        18
  5     C        A        32

Eventuali indizi?

algorithms load-balancing

posta vanilla 23.07.2016 - 22:42

fonte

1 risposta

Leggi altre domande sui tag algorithms load-balancing

Importazioni comuni tra molti script nel progetto Python Come controllare a livello di programmazione un'applicazione GUI?

score 1 · Answer 1

Nella soluzione di esempio, i lavori 1 e 2 riescono a raggruppare valori simili all'interno della stessa fonte, ma i lavori 3 e 4 no. Tutti i lavori mantengono il loro carico di lavoro totale inferiore a 50.

Questa soluzione di esempio sembra essere il risultato di un algoritmo avido che cattura la prima possibile corrispondenza.

In generale, gli algoritmi avidi hanno cinque componenti:

Un set candidato, da cui viene creata una soluzione
- Attività da 1 a 7
Una funzione di selezione, che sceglie il miglior candidato da aggiungere alla soluzione
- Il migliore qui sembra significare solo sotto i limiti del carico di lavoro che creiamo il maggior numero possibile di corrispondenze di origine con questa prossima scelta
Una funzione di fattibilità, che viene utilizzata per determinare se un candidato può essere utilizzato per contribuire a una soluzione
- Questo è il limite del carico di lavoro
Una funzione obiettivo, che assegna un valore a una soluzione o una soluzione parziale
- Un conteggio del numero di corrispondenze di origine nella soluzione (2 nel tuo esempio)
Una funzione di soluzione, che indicherà quando abbiamo scoperto una soluzione completa
- Quando tutte le attività sono state assegnate ai lavori che abbiamo fatto

L'output di questo algoritmo dipende molto dall'ordine in cui vengono presentate le attività. Il significato di soluzioni migliori può essere trovato permutando l'ordine delle attività e rilanciare avido. Questo è O (n!) Difficile ma dovrebbe essere ottimale. La soluzione completa con la maggior parte delle partite di origine vince.

Questo è poco efficiente ma è una soluzione ottimale. Possono esistere soluzioni più efficienti. Sospetto che si tratti di un problema ottimizzazione combinatoria . Verifica se una di queste soluzioni è applicabile e più efficiente.