Algoritmo per l'assegnazione di persone a intervalli di tempo in base alle preferenze

5

Sto tentando di capire se esiste attualmente un algoritmo per realizzare ciò che sto cercando di realizzare.

Ho una serie di fasce orarie nel corso di una settimana in cui desidero assegnare un numero approssimativamente uguale di persone ad ogni fascia oraria durante la settimana. A differenza di questa domanda , le fasce orarie sono fornite come intervalli di ore e i membri della popolazione devono solo essere piccione rastrellato in modo approssimativamente equamente distribuito.

La maggior parte della popolazione ha fornito una prima, seconda e terza scelta per la fascia oraria desiderata. Le persone che elencano una fascia oraria come preferenze multiple sono considerate compilate in modo errato e la preferenza verrà considerata una sola volta e le loro preferenze rimanenti verranno considerate come non avere preferenze.

Inoltre, parte della popolazione potrebbe non fornire una risposta o dire che non hanno preferenze. Dovrà ancora essere assegnato un intervallo di tempo, ma può essere assegnato a qualsiasi intervallo di tempo necessario per soddisfare l'algoritmo.

Tuttavia, le fasce orarie non hanno alcuna preferenza su chi va dove, a parte il fatto che vogliono che le persone siano distribuite in modo approssimativo, il che significa che non si tratta solo del problema del matrimonio stabile / residente ospedaliero. Differisce ulteriormente dal problema del matrimonio stabile in quanto i membri della popolazione non hanno una preferenza per ogni fascia oraria, che sembra essere necessaria per il funzionamento di quell'algoritmo.

L'obiettivo dell'algoritmo è il seguente (in ordine di importanza):

  1. Assicurati che a tutti sia assegnato un intervallo di tempo.
  2. Assicurati che tutti quelli che offrono una 1ª, 2a e 3a scelta separata siano assegnati ad almeno uno di essi.
  3. Distribuisci la popolazione in modo che siano approssimativamente uguali tra le fasce orarie.
  4. Se la popolazione risultasse distribuita in modo più uniforme, elimina le fasce orarie spostando le persone fuori da esse.
  5. Massimizza il numero di persone che ottengono la loro prima scelta.
  6. Massimizza il numero di persone che ottengono la loro seconda scelta.
  7. Massimizza il numero di persone che ottengono la loro terza scelta.
  8. Riduci al minimo le risorse e il tempo di esecuzione richiesto per l'algoritmo.

Nella mia ricerca, ho anche scoperto che il problema del matrimonio stabile può avere esiti diversi a seconda di quale sia la prima parte delle loro proposte. Spero che lo stato iniziale non influenzi l'esito dell'algoritmo, ma se necessario posso semplicemente eseguirlo più volte e ottenere il miglior risultato. Vorrei anche evitare di assegnare costanti arbitrarie alle preferenze a meno che non sia assolutamente necessario.

Questo è un problema abbastanza complesso, quindi non mi aspetto di ottenere un algoritmo completo da qui a meno che non esista già per risolvere questo problema esatto. La mia domanda riguarda principalmente l'esistenza di algoritmi o aree di studio simili da cui partire. Qualcuno può aiutarmi a indicarmi la direzione giusta?

Inoltre, sto ignorando l'SMP come punto di partenza in modo errato?

    
posta Rob Rose 01.01.2018 - 21:59
fonte

1 risposta

2

Sembra che dovresti fare quanto segue:

  1. dare a tutti la loro fascia oraria di prima scelta.
  2. Se la distribuzione è "approssimativamente uguale tra le fasce orarie" (qualunque cosa significhi), allora hai finito.

Se non sono approssimativamente uguali, dovrai spostare una o più persone dalla prima alla seconda scelta. Probabilmente sarebbe meglio concentrarsi sulla fascia oraria più richiesta, anche se potresti scegliere le persone a caso invece.

Se sono ancora non approssimativamente uguali anche dopo che ognuno è impostato sulla seconda richiesta, inizia a dare alla gente la terza richiesta.

Quanto sopra non funzionerà se stai effettivamente cercando di distribuire le persone in modo uniforme tra una serie di fasce orarie. In tal caso, quindi, dare a tutti la prima scelta. Quindi in qualsiasi fascia oraria che ha troppe persone, trova l'individuo nello slot che è la seconda scelta meno popolare e spostalo lì. Se tutti nello slot sono già alla loro seconda scelta, allora trova l'individuo che è la terza scelta meno popolare e spostalo.

    
risposta data 02.01.2018 - 03:52
fonte

Leggi altre domande sui tag