Quale algoritmo per l'assegnazione dei turni (problema di ottimizzazione discreta)

Question

Sto sviluppando un'applicazione che assegna in modo ottimale i turni agli infermieri in un ospedale.Credo che questo sia un programmazione lineare problema con variabili discrete, e quindi probabilmente NP-difficile:

• Per ogni giorno, ogni infermiera (ca.15-20) viene assegnato un turno
• Esiste un piccolo numero (ca.6) di turni diversi
• Esistono numerosi vincoli e criteri di ottimizzazione, sia riguardanti una giornata, sia riguardanti un dipendente, ad esempio:
  • Ogni giorno deve essere assegnato un numero minimo di persone a ciascun turno
  • Alcuni turni si sovrappongono, quindi va bene avere una persona in meno nel turno iniziale se c'è qualcuno che fa il turno intermedio
  • Alcune persone preferiscono il turno anticipato, altri il turno tardivo, ma è necessario un minimo di cambi di turno per ottenere comunque la retribuzione più elevata per il lavoro a turni.
  • Non è consentito a una persona lavorare il turno tardi un giorno e il turno anticipato il giorno successivo (a causa delle norme sul tempo minimo di riposo)
  • Durata della settimana lavorativa assegnata alla riunione (diversa per persone diverse)
  • ...

Quindi fondamentalmente c'è un gran numero (circa 20*30 = 600) variabili che ciascuna può assumere un piccolo numero di valori discreti.

Attualmente, il mio piano è di utilizzare un file modificato Algoritmo dei conflitti minimi

• iniziare con incarichi casuali
• avere una funzione fitness per ogni persona e ogni giorno
• seleziona la persona o il giorno con il valore di fitness peggiore
• seleziona a caso uno degli incarichi per quel giorno/persona e impostalo sul valore che risulta nel valore di fitness ottimale
• ripetere finché non viene raggiunto il numero massimo di iterazioni o non viene trovato alcun miglioramento per il giorno/persona selezionato

Qualche idea migliore?Sono un po’ preoccupato che possa rimanere bloccato in un ottimo locale.Dovrei usare qualche forma di ricottura simulata?Oppure considerare non solo i cambiamenti in una variabile alla volta, ma specificamente i cambi di turno tra due persone (il componente principale nell’attuale algoritmo manuale)?Voglio evitare di adattare l'algoritmo ai vincoli attuali poiché questi potrebbero cambiare.

Modificare: non è necessario trovare una soluzione strettamente ottimale;il roster è attualmente fatto manualmente, e sono abbastanza sicuro che il risultato sia considerevolmente sub-ottimale per la maggior parte del tempo - non dovrebbe essere difficile batterlo.Saranno sicuramente necessari anche aggiustamenti a breve termine e interventi manuali, ma non credo che questo sarà un problema;Contrassegnare le assegnazioni passate e manuali come "fissi" dovrebbe effettivamente semplificare l'attività riducendo lo spazio della soluzione.

Answer 1

Questo è un problema difficile da risolvere bene.Ci sono stati molti articoli accademici su questo argomento, in particolare nel Ricerche operative campo - vedi ad esempio documenti sull'elenco degli infermieri 2007-2008 o semplicemente cercare su Google "ricerca operativa sull'elenco degli infermieri".La complessità dipende anche da aspetti quali:quanti giorni risolvere;che tipo di “richieste” può fare l'infermiere;il roster è "ciclico";è un piano a lungo termine o deve gestire la "riparazione" del roster a breve termine come malattia e scambi ecc. Ecc.

L'algoritmo che descrivi è a euristico approccio.Potresti scoprire di poterlo modificare per farlo funzionare bene per una particolare istanza del problema, ma non appena "qualcosa" viene cambiato potrebbe non funzionare così bene (ad es.ottimi locali, scarsa convergenza).

Tuttavia, tale approccio può essere adeguato a seconda delle particolari esigenze aziendali, ad es.quanto è importante ottenere il ottimale soluzione, lo schema del problema che descrivi dovrebbe rimanere lo stesso, qual è il potenziale risparmio (denaro e risorse), quanto è importante la percezione degli infermieri della qualità dei loro turni, qual è il budget per questo lavoro, ecc.

Answer 2

Umm, sapevi che alcuni risolutori ILP fanno un ottimo lavoro?Prova AIMMS, Mathematica o il kit di programmazione GNU!600 variabili sono ovviamente molto più di quanto il teorema di Lenstra risolverà facilmente, ma a volte questi solutori ILP hanno una buona gestione e in AIMMS è possibile modificare leggermente la strategia di ramificazione.Inoltre, esiste un'approssimazione al 100% molto rapida per gli ILP.

Answer 3

Recentemente ho risolto un problema di assegnazione dei turni per un grande stabilimento produttivo.Per prima cosa abbiamo provato a generare pianificazioni puramente casuali e a restituire quelle che hanno superato il file is_schedule_valid test: l'algoritmo di fallback.Questo, ovviamente, è stato lento e indeterminato.

Successivamente abbiamo provato algoritmi genetici (come hai suggerito), ma non siamo riusciti a trovare una buona funzione di fitness che si chiudesse su una soluzione praticabile (perché il più piccolo cambiamento può rendere l'intero programma GIUSTO o SBAGLIATO - nessun punto per quasi).

Alla fine abbiamo scelto il seguente metodo (che ha funzionato benissimo!):

1. Randomizzare il set di input (ad es.mansioni, turni, personale, ecc.).
2. Crea una tupla valida e aggiungila alla tua pianificazione provvisoria.
3. Se non è possibile creare una tupla valida, eseguire il rollback (e l'incremento) dell'ultima tupla aggiunta.
4. Passa la pianificazione parziale a una funzione che esegue il test could_schedule_be_valid, cioè, questa pianificazione potrebbe essere valida se le restanti tuple fossero riempite in un modo possibile
5. Se !could_schedule_be_valid, è sufficiente eseguire il rollback (e incrementare) della tupla aggiunta in (2).
6. Se schedule_is_complete, return schedule
7. Vai a (2)

In questo modo costruisci in modo incrementale uno spostamento parziale.Il vantaggio è che alcuni test per un programma valido possono essere facilmente eseguiti nella Fase 2 (pre-test), mentre altri devono rimanere nella Fase 5 (post-test).

Buona fortuna.Abbiamo perso giorni provando i primi due algoritmi, ma abbiamo ottenuto l'algoritmo consigliato che generava istantaneamente pianificazioni valide in meno di 5 ore di sviluppo.

Inoltre, abbiamo supportato la fissazione preliminare e successiva delle assegnazioni che l'algoritmo avrebbe rispettato.Semplicemente non randomizzi quegli slot nel passaggio 1.Scoprirai che le soluzioni non devono essere neanche lontanamente ottimali.La nostra soluzione è almeno O(N*M), ma viene eseguita in PHP(!) in meno di mezzo secondo per un intero impianto di produzione.Il bello sta nell'escludere rapidamente i cattivi programmi utilizzandone uno buono could_schedule_be_valid test.

Le persone abituate a farlo manualmente non si preoccupano se ci vuole un'ora: sanno solo che non dovranno più farlo manualmente.

Answer 4

Mike,

Non so se hai mai avuto una buona risposta a questa domanda, ma sono abbastanza sicuro che la programmazione dei vincoli sia la soluzione.Mentre un GA potrebbe darti una risposta, CP è progettato per darti molte risposte o dirti se non esiste una soluzione fattibile.Una ricerca su "programmazione dei vincoli" e pianificazione dovrebbe fornire molte informazioni.Si tratta di un'area relativamente nuova e i metodi CP funzionano bene su molti tipi di problemi in cui i metodi di ottimizzazione tradizionali impantanano.

Answer 5

Programmazione dinamica alla Bell?Sembra che ci sia un posto per questo:sottoproblemi sovrapposti, sottostrutture ottimali.

Answer 6

Una cosa che puoi fare è provare a cercare simmetrie nel problema.Per esempio.si possono trattare tutti gli infermieri come equivalenti ai fini del problema?Se è così, allora devi considerare gli infermieri solo in un ordine arbitrario: puoi evitare di considerare soluzioni come quelle di qualsiasi infermiere io è programmato prima di qualsiasi infermiere J Dove io > J.(Hai detto che i singoli infermieri hanno preferito gli orari dei turni, il che contraddice questo esempio, anche se forse questo è un obiettivo meno importante?)

Answer 7

Penso che dovresti usare l'algoritmo genetico perché:

• È più adatto per casi di problemi di grandi dimensioni.
• Produce una complessità temporale ridotta al prezzo di una risposta imprecisa (non il migliore)
• Puoi specificare facilmente vincoli e preferenze modificando le punizioni di fitness per quelle non soddisfatte.
• È possibile specificare un limite di tempo per l'esecuzione del programma.

• La qualità della soluzione dipende da quanto tempo intendi dedicare alla risoluzione del programma.

  Definizione di algoritmi genetici

  Tutorial sugli algoritmi genetici

  Progetto di pianificazione delle lezioni con GA

Dai un'occhiata anche a:una domanda simile E un altro

Answer 8

Utilizzando la programmazione CSP ho realizzato programmi per il rostering automatico degli merdati.per esempio:

1. Sistema a 2 turni - testato per 100+ infermieri, orizzonte temporale di 30 giorni, 10+ norme
2. Sistema a 3 turni: testato per oltre 80 infermieri, orizzonte temporale di 30 giorni, oltre 10 regole
3. Sistema a 3 turni, 4 squadre: testato per un orizzonte di 365 giorni, oltre 10 regole,

e un paio di sistemi simili.Tutti sono stati testati sul mio PC di casa (1,8 GHz, dual-core).I tempi di esecuzione sono sempre stati accettabili, ad es.per 3/ ci sono voluti circa 5 minuti e 300 MB di RAM.

La parte più difficile di questo problema è stata la selezione del risolutore e della strategia di risoluzione adeguati.

Answer 9

Metaeuristiche ha fatto molto bene al Concorso internazionale per la selezione degli infermieri 2010.

Per un'implementazione, vedere questo video con un elenco continuo degli infermieri (java).