Job scheduling problema

Question

Sto lavorando su un'applicazione in cui ho bisogno di pianificare l'esecuzione automatica di posti di lavoro per i soci su un programma di rotazione.Io non sono molto bravo a spiegare le regole, quindi, ecco alcuni dati per aiutare:

Posizioni:Un titolo di lavoro, con regole come il lunedì e il mercoledì con cadenza settimanale.
Categorie:Un insieme di posizioni
Gruppi:Un'altra serie di posizioni.Posizioni nello stesso gruppo non può essere assegnato lo stesso giorno
Membri:Gli utenti assegnati a posizioni in una determinata data.

Per ogni data nel mese, i membri vengono assegnati a posizioni di (in ordine crescente).Se un membro è assegnato ad una posizione in una categoria, la prossima volta una posizione nella stessa categoria viene in su, il membro successivo in ordine alfabetico (o l'inizio della lista) viene assegnato ad es.

Membri:M1, M2, M3, M4
Posizioni in Categoria C1:P1, P2, P3
Membri in Posizione P1:M1, M2, M3, M4
Membri in Posizione P2:M1, M2, M3
Membri in Posizione P2:M1, M3, M4

Se M1 è assegnato per P1, se P2 è il successivo, M2 verrà assegnato.Un ulteriore livello di complessità è introdotta dove, se il P3 è il passo successivo, invece, M3 viene assegnato.Il sistema deve tenere traccia del fatto che M2 è 'saltato' e assegnare M2 avanti se disponibili, quindi assegnare M4 avanti, o aspettare fino a quando si arriva a una posizione in cui M2 è disponibile questa diventa inoltre complesso quando ci sono molti 'saltato' di membri).

Un membro anche essere saltato se ha indicato di non essere disponibili a tale data.Il sistema ha bisogno di dare la priorità sul saltato membri, in qualche modo identificare loro quando arrivano e poi passare al successivo logico persona nella lista.Saltando vale anche per i gruppi a causa della data di scontri.

Ho già un temporaneo [e disordinato] soluzione che non capisco, anche se ho un sacco di commenti in esso spiegando ogni passaggio.Le sue debolezze sono nel trattare con l'saltato membri.

Se si dovesse andare per il codice di questo come si va su di esso?Sto implementando questo in PHP, ma pseudocodice avrebbe funzionato così bene.

Answer 1

La mia soluzione:Avete bisogno di un PriorityQueue (che è disponibile in PHP sotto SplPriorityQueue).Il PriorityQueue fornisce elementi con priorità discendente (ordinati per valori, il più piccolo valore ha la priorità più alta).

Ogni membro ha un valore assegnato.Questo valore è un ASCII numero di n cifre (si potrebbe utilizzare 8 cifre per comodità), riempito con zeri di n posizioni.Dopo di che si accoda il nome.Puoi anche aggiungere a ciascun socio, le posizioni disponibili

Quindi (n=5):

• Valore M1:99999Albert P1,P2,P3
• M2 valore:99999Susi P1,P2
• M3 valore:99999Bob P1,P3

Questo rende più facile per ordinare i membri in base alla priorità e il nome.

Preparazione:

Una giornata di sole.Si recuperano le posizioni assegnate e una categoria per un dato giorno.Ogni membro è caricato di un lungo elenco.Ogni membro che non appaiono sul lavoro non viene caricato, ma ottiene il suo valore è diminuito da meno di due.Bob non è qui, quindi, il nuovo valore viene 99997Bob.Questo significa che Bob verrà selezionata automaticamente la volta successiva.Tutti gli altri membri che ottengono il loro valore è diminuito da meno uno.

Le posizioni assegnate per un Giorno specifico sono mappati (uso SplObjectStorage):

P1->M1,M2,M3,M4 etc.P2-> etc.

La mappa contiene solo le posizioni che devono essere assegnati a questo giorno.Dopo il

Filtro:È necessario cercare i gruppi ed eliminare qualsiasi posizione sulla mappa che non può essere assegnato a questo giorno.La tua descrizione del gruppo è un po ' poco chiaro.

Assegnare:

• Si sceglie la posizione di assegnare
• Ottenere l'elenco dei soci, che può riempire la posizione
• Rimuovere membri disponibili dall'elenco e metterli in PriorityQueue
• Di assegnare la posizione da estrarre() da PriorityQueue (corretta assegnazione è fatto automaticially).Ogni membro è assegnato prende il suo valore è aumentato uno (Così la diminuzione e l'aumento dei livelli se sei qui e di lavoro).Se sei qui e non assegnato ad una posizione per qualsiasi motivo, si ottiene una piccola penalità di uno.Se non qui, si ottiene una penalità di due.
• Dopo il completamento, mettere i restanti membri della lista, cancellare la PQueue e continuare con la successiva assegnazione.

Avvertenze:

• È necessario fare attenzione che ci sono sempre abbastanza persone per una posizione.

Answer 2

uff.non seguo descrizione, ma in situazioni simili ho usato sql per risolvere questo tipo di problema.se si utilizza php credo si dispone di sql disponibili.

quello che io consiglio di fare è trovare un modo di memorizzare le informazioni in un insieme di tabelle e di scoprire cosa query sql che dà la risposta che si desidera.molto spesso è molto più semplice da fare in sql che è in un linguaggio procedurale.

per l'saltato parte, per esempio, si potrebbe avere una colonna che ricorda quando qualcuno ultima assegnazione, e poi l'ordine da che (in modo da selezionare la persona che non ha ancora ricevuto per un lungo periodo di tempo).in alternativa, si potrebbe avere il numero di volte saltato come una colonna e l'ordine con che.

Answer 3

Quello che ho capito è che ci sono 'm' membri, e 'n' posizioni.

Categoria:un gruppo di posizioni-un membro a cui è assegnata una posizione nella categoria non può avere un altro?

Gruppo:un gruppo di posizioni -- posizioni nel gruppo stesso deve essere ricevuto, in giorni diversi.

Ultima cosa, una Posizione che ha una lista di membri che può riempire.

Guardando questo da un punto di vista della struttura, mettere i membri in una lista collegata -- ogni membro deve disporre di un ulteriore elenco di [posizione, giorno] si sono finalmente ricevuto.Quindi, per ogni posizione, dispone di un elenco di riferimenti per i membri che possono riempire quella posizione.Implementare categorie come un altro elenco di riferimenti per una posizione come la categoria a cui esso appartiene.

L'effettiva assegnazione:un giorno il contatore = 0, e scorrere le posizioni.Per ogni posizione P, scorrere i membri che possono riempire.Un membro M è in grado di riempire la posizione se:

• Ogni posizione ha riempito il P2 non condividere una categoria con P.
• Ogni posizione ha riempito il P2 con giorno = daycounter non la condivisione di un gruppo con P.

Se riesce a riempire la posizione, la [posizione, giorno] coppia è aggiunto il membro e membro del nodo viene spostato alla FINE della lista (questo è il motivo per cui riferimenti sono necessari -- tutti i riferimenti sono ancora validi, anche se il nodo spostato).Questo assicura che il 'salto' membri sono assegnata la massima priorità, e i membri che non sono state raggiunte sono dato priorità successivo.

Una volta che una posizione è pieno, passare alla posizione successiva.Se la posizione e le azioni di un gruppo con una posizione già ricevuto, saltare, scorrere tutte le posizioni fino a quando è possibile assegnare tutte le posizioni, come si può su 1 giorno.Quindi, incrementare il contatore e ripetere per tutto il giorno 2.Questo dovrebbe dare un massimo di assegnazione (non è certo il massimo) per tutti i lavori.

Suggerimento:quando lo spostamento di un membro alla fine dell'elenco dei membri, per evitare di dover scorrere l'elenco, di mantenere un riferimento alla fine, per la posizione successiva, è necessario cominciare dall'inizio, comunque, quindi non c'è nessun punto di passare attraverso l'intera cosa.