Qual è un buon algoritmo per l'assegnazione prioritaria delle mansioni lavorative?

Question

Qual è un buon algoritmo per l'assegnazione prioritaria delle mansioni lavorative?

#1 da (6 voti)
#2 da (2 voti)

1

Attualmente sto facendo un progetto (in PHP) che ha i seguenti requisiti:

C'è una lista di persone, ordinate in una certa priorità. I lavori dovrebbero essere assegnati a loro da questa priorità. per esempio. Se la lista è T1, T2, T3, T1 dovrebbe essere assegnato lavoro, prima di T2. E T2 è assegnato lavoro prima di T3. Nel caso in cui ci siano solo 2 pezzi di lavoro, vengono assegnati solo T1 e T2.
Ogni pezzo di lavoro ha determinati requisiti di tempo. Quindi, anche se è il turno di T1 ad essere assegnato lavoro, se nessuno dei lavori è adatto per T1, T1 verrà saltato e non verrà assegnato alcun lavoro a T1.
Alcuni lavori sono più adatti per alcune persone. Per esempio. Ci sono due lavori, W1 e W2. Se T1 è più adatto per W2, W2 sarà assegnato a T1.

La mia idea attuale è quella di allocare il lavoro in base all'elenco delle persone e utilizzare una ricerca A * per identificare quale sia il modo migliore di assegnare il lavoro a ciascuna persona. Ma ho pensato che il mio reqt 1 e reqt 3 sembra avere alcuni conflitti.

È un algoritmo ragionevole o ci sono problemi con esso che non vedo a questo punto?

algorithms search allocation

posta Wee 07.02.2013 - 02:59

fonte

2 risposte

Leggi altre domande sui tag algorithms search allocation

Il percorso nell'URL Set-Cookie è codificato? Dove verificare che una funzione abbia effettivamente fatto ciò che gli ho detto?

score 6 · Answer 1

Il problema che hai qui in generale è chiamato Problema di pianificazione e nella sua forma generale è NP-completo . In altre parole, è un problema ben noto per il quale non esiste un algoritmo efficiente (ancora, o forse mai).

La pagina collegata (già citata in un commento prima) si riferisce a una variante specifica chiamata pianificazione del job shop. Esistono molti problemi di pianificazione diversi, che in qualche modo si riducono a NP-complete.

Nel tuo caso, tuttavia, vorrei seriamente ripensare alla necessità di avere priorità. I problemi di pianificazione del lavoro di solito hanno forti dipendenze (come il lavoro A che deve essere completato affinché il lavoro B possa essere avviato). Le priorità sono una dimensione del problema completamente diversa e complicheranno tremendamente il tuo compito - qualcosa che potrebbe non valerne la pena. È abbastanza difficile, se si dice semplicemente che l'attività T1 può essere eseguita solo dai lavoratori W1 o W2 - senza la necessità di preferire W1.

Una nota se controlli la letteratura: nel tuo caso i lavoratori sono tipicamente macchine in letteratura - pensa alle fabbriche di automazione in cui T1, ..., Tn tiles sono prodotti da M1, ..., macchine Mm.

Anche una delle prime cose da verificare è se devi trovare la soluzione perfetta. Generalmente, la completezza di NP deriva dal requisito che la soluzione migliore deve essere trovata. Nella tua descrizione scrivi cose come T1 verrà saltato , che normalmente non è possibile nelle formulazioni del problema di schedulazione teorica. Dato che non è necessario pianificare tutte le attività, potrebbe anche non essere necessario soddisfare il problema in modo ottimale. In tal caso, puoi provare a scrivere un algoritmo simile a quello di Greedy o esaminare la ricerca effettuata sugli algoritmi di approssimazione per la pianificazione. Questi algoritmi hanno il vantaggio di essere veloci, ma lo svantaggio di non necessariamente trovare una soluzione ottimale.

score 2 · Answer 2

Modellerei questo come un Problema di soddisfazione dei vincoli dove il tuo obiettivo è trovare una configurazione di incarichi che soddisfi i tuoi requisiti . Questo è generalmente un problema NP-completo, ma a seconda delle dimensioni del set di dati potrebbe essere possibile trovare una soluzione.

Ecco una descrizione di come risolvere il problema con un algoritmo Backtracking

Sia W un insieme di assegnazioni di lavoro come {W1, W2, ..., Wn}
Per ogni incarico, assegna l'operatore più adatto ad esso (come da requisito 2)
Per tutti i restanti compiti, prova a programmarlo alla massima priorità disponibile lavoratore
Passa al successivo compito non assegnato fino a quando non sono tutti assegnati o fino a quando non ci sono lavoratori disponibili in quel momento
Se non è stata trovata alcuna soluzione, torna indietro di un passaggio e riprova con il successivo lavoratore disponibile

È molto simile a come vengono risolte le griglie di Sudoku, che sono spesso modellate come CSP stesse. Questo è possibile solo perché le assegnazioni non sono prerequisiti tra loro in base alla descrizione, il che rende meno rilevante la modellazione del problema come problema di pianificazione.

Buona fortuna!