Algoritmo calendario / pianificazione

Algoritmi genetici e reti neurali non sono adatti qui. Sono meta-euristiche per trovare una soluzione abbastanza buona e approssimativa a un problema. In particolare, entrambi richiedono di trovare una funzione di costo per valutare le soluzioni candidate. Una volta che hai una tale funzione di costo, potrebbe essere più facile ottenere manualmente un algoritmo che ottimizzi per questo costo.

Questo è un pensiero importante: dati due programmi, abbiamo bisogno di un modo per decidere se la pianificazione A o la pianificazione B è "migliore". Hai elencato vari criteri, ma non è chiaro in che modo si riferiscono. Non riuscire a soddisfare un criterio fallisce l'intera soluzione? Oppure fallisce parzialmente un vincolo rendendolo una soluzione peggiore di altri?

A un livello più elementare, puoi semplicemente dividere la settimana in intervalli di tempo discreti e brute-forzare tutte le combinazioni di slot-doctor. Tuttavia, è possibile utilizzare vincoli di hard-failing per ridurre questo spazio di ricerca a una dimensione più gestibile. Le restrizioni relative al tempo di lavoro e ai turni notturni sembrano essere adatte per tale limitazione dello spazio di ricerca. Vieni quindi con centinaia di soluzioni candidate.

Per selezionare la soluzione migliore, è necessario classificarle. Questo è abbastanza facile se un vincolo soft ha una chiara precedenza su tutti gli altri vincoli soft, ad es. se un medico non può lavorare a un certo turno, a questo viene data più importanza di un medico che non vuole lavorare in quel turno. Ma non posso decidere queste regole per te - questa è una decisione manageriale. È più difficile se due vincoli soft non hanno una chiara precedenza, nel qual caso dovrai inventare una sorta di funzione di costo che unifica l'importanza di due vincoli in una singola metrica.

Probabilmente costruirò un algoritmo avido che riempie una tabella di tempo vuota secondo alcuni criteri prioritari. Questa potrebbe non essere la soluzione ottimale, ma è molto più semplice del filosofare su cosa sia in realtà "ottimale".

Come primo passo, potresti completare i turni notturni durante il fine settimana e cercare di selezionare quei medici che non hanno svolto un turno notturno di fine settimana per il più lungo tempo, tenendo anche conto del fatto che "Non posso lavorare lì "Desideri dell'utente. Supponendo che questi desideri siano settimanali e non continui, questo significa che un medico che non può lavorare nelle notti del fine settimana per una settimana verrà scelto la prossima settimana.

Una procedura simile può essere utilizzata per le altre notti: dopo aver cercato di rispettare i desideri degli utenti, devi compilare i medici in base a chi non ha effettuato turni notturni per il periodo di tempo più lungo. La procedura si ripete in modo simile per il terzo tipo di fascia oraria, il giorno cambia. Se due desideri dell'utente non possono essere riconciliati, puoi tenere traccia di quanto spesso gli utenti desiderano essere esauditi e quindi dare la priorità al medico con meno desideri concessi.

Sfortunatamente, posso vedere un paio di modi per giocare a questo sistema: ad es. se un medico venisse scelto per lavorare un turno di notte durante il fine settimana ma inserisse una richiesta "non può lavorare lì", la sua scelta sarebbe ritardata di una settimana, riducendo la frequenza dei turni di notte del fine settimana a spese dei colleghi. Se viene implementata una procedura di risoluzione dei desideri che analizza il numero di richieste rifiutate, un utente potrebbe inserire un paio di richieste impossibili per aumentare una richiesta che desidera passare. Tuttavia, assumendo buona fede (e la flessibilità per i medici di scambiare gli spostamenti tra loro), tale algoritmo dovrebbe risultare in una soluzione sufficientemente buona.

Puoi utilizzare ricottura simulata .

Ho fatto qualcosa del genere prima di finire il mio primo lavoro - vedi link (demo a partire da 2:50, algoritmo spiegato da 6: 15).

La ricottura simulata è un tipo di algoritmo genetico, e forse non era adatto in teoria (come @amon mantiene in suo risposta ), ma in pratica ha funzionato molto bene e riguardava lo stesso caso d'uso del tuo.

Il codice sorgente è disponibile (C #), ma mentre funziona è terribile, ho paura, è stato qualche anno fa ed essendo un autodidatta, non sapevo nulla della manutenibilità. Però ha prodotto risultati molto belli.

Come funziona in poche parole:

• Genera 1 possibile (potrebbe non essere molto buono, ma fisicamente possibile) il programma orario come punto di partenza. L'algoritmo genetico non è necessario a questo punto: puoi solo rinforzarti la tua strada verso la prima soluzione che riesci a trovare. Ho usato backtracking . La complessità computazionale può essere superata risolvendo separatamente il rota per ogni giorno. Se non esiste alcuna soluzione (a seconda dei casi), è a questo punto che la rilevi.

• Crea un pool di soluzioni: ad esempio, 100 copie di questa soluzione entry-level.

• Mutate ogni soluzione a caso: i medici scambiano i cambiamenti tra loro, prendono un medico a caso dal loro turno e mettono su di esso una persona disponibile a caso ecc.

• Valuta ogni soluzione con una funzione fitness che determina quanto è buono. Un ragazzo lavora più notti di un altro? Sottrai punti di penalità. Qualcuno voleva fare lunedì ma non lo fa? Sottrai di nuovo i punti di penalità.

• Prendi - diciamo - 20 soluzioni migliori e copia ognuna di esse 5 volte, sovrascrivendo le restanti 80 con loro, portandole quindi alla generazione successiva. Sopravvivenza del più adatto.

• Risciacquo & ripetere.

I numeri sono ovviamente arbitrari, potresti aver bisogno di giocare con i parametri per trovare le impostazioni ottimali per il tuo scenario.

Come per la mutazione di una soluzione, la ricottura simulata introduce qualcosa chiamato temperatura. Fondamentalmente significa che all'inizio dovresti mutare le tue soluzioni piuttosto dure (ad esempio, fai sempre 10 tentativi di cambiare turno in una volta sola) e gradualmente diventare meno aggressivo con le iterazioni successive, in modo che diventino più di un fine-tuning (ad esempio, giù a solo 2 tentativi di modifica per generazione).

Algoritmi di genetica si applicano qui. Durante il mio corso di laurea, uno dei miei colleghi ha scritto un articolo su un tuo problema molto simile.

Puoi cercare Job Shop Scheduling e anche Open Shop Scheduling o La pianificazione del flusso di lavoro può essere un punto di partenza interessante

Per utilizzare un algoritmo genetico non hai bisogno di una soluzione perfetta, puoi iniziare con N candidati casuali e applicare una funzione fitness a ciascuno di essi, ad esempio:

• La differenza di notti assegnate tra il medico più occupato e il meno occupato è una penalizzazione nella funzione di costo
• Ogni volta che un medico lavora più di 5 giorni a settimana o 1 notte a settimana, applica una penalità
• Ciascuno dei tuoi vincoli, ecc.

Generando N candidati che vorresti scegli la X migliore tra loro , sarebbero quelli che infliggeranno i vincoli meno. Lavorando con loro, attraversando e muting su più generazioni si può finire con una buona soluzione.

Avendo parlato di tutto ciò, ogni volta che usavo un Algoritmo Genetico che si basava più sulla mutazione che sull'incrocio, potevo sviluppare una Ricottura Simulata che avrebbe funzionato molto meglio, con un'implementazione più semplice. Il costo / idoneità e la funzione di mutazione per l'algoritmo genetico saranno probabilmente molto simili a quelli usati in una Ricottura simulata. Vorrei iniziare lì, guarda la risposta @Konrad Morawski

Ricerca Google trova buoni risultati per Job Shop e GA