Algoritmo per trovare le ore in cui le risorse sono disponibili

Question

Algoritmo per trovare le ore in cui le risorse sono disponibili

#1 da (4 voti)
#2 da (0 voti)

3

Sto scrivendo un'applicazione di pianificazione semi-automatica. Date alcune prenotazioni esistenti e alcuni requisiti di risorse, è necessario trovare gli orari in cui è possibile pianificare un nuovo evento. Un utente umano valuterà quindi i risultati e sceglierà una delle opzioni. Non è necessario ottimizzare un orario per più eventi e quindi non è il solito problema di orario NP-Hard.

Il sistema ha un numero di risorse (istruttori, sale, attrezzature) ognuna delle quali ha un tipo (ad es. insegnante di francese, sala per seminari, proiettore ...). Le risorse sono prenotate per eventi ognuno dei quali ha un'ora di inizio e di fine.

Ora, devo dire che ho bisogno di programmare una lezione francese di 2 ore usando un proiettore in una sala per seminari, quali sono le volte in cui almeno una risorsa di ciascun tipo di risorsa richiesto è disponibile?

Per limitare lo spazio del problema, è accettabile considerare solo 9-17, da lunedì a venerdì a intervalli di 15 minuti per i prossimi 90 giorni. Numero totale di risorse nell'ordine di 1000.

Come posso fare questo senza dover confrontare ogni risorsa con ogni altra risorsa?

algorithms scheduling

posta Tamlyn 23.12.2013 - 23:27

fonte

2 risposte

Leggi altre domande sui tag algorithms scheduling

Post-mortem di un progetto Le chiamate al server veloci e ottimizzate possono comprimere un server?

score 4 · Answer 1

Vorrei provare a utilizzare un algoritmo di sweep-line unidimensionale per questo. Innanzitutto, per ogni parte di risorsa di una prenotazione, individua i punti nel tempo in cui il suo stato passa da "disponibile" a "prenotato", o viceversa (limitato, ad esempio, per ogni momento dopo ora ). Metti ognuno di questi punti nel tempo in un record di dati contenente

data / ora
tipo di interruttore di stato (su "prenotato" o "disponibile")
riferimento alla risorsa

Crea un elenco di tutti quei record e ordinalo per data e ora. Successivamente, si crea un array booleano con un flag "disponibile" per ciascuna risorsa, inizializzandolo con lo stato di disponibilità corrente. Infine, lo "sweep" ha luogo: attraversa l'elenco ordinato da un record a quello successivo, cambia lo stato di disponibilità nel tuo array booleano della risorsa correlata, finché ciascuno dei flag ha lo stato "disponibile". Spostare un record ulteriormente e ottenere il timestamp, questo vi dirà per quanto tempo le risorse sono tutte disponibili in un intervallo di tempo contiguo (potreste aver cura di non superare i limiti del giorno qui). Se l'intervallo di tempo è abbastanza lungo, hai trovato una soluzione in un intervallo di tempo. Continui fino a raggiungere la fine della lista o hai trovato abbastanza intervalli.

Come bonus, questo funziona bene con o senza i vincoli "15 minuti" e "90 giorni".

score 0 · Answer 2

Si presume che abbiate tre tavoli: allenatori, stanze, attrezzature. Hai un "blocco" di 2 ore. Pertanto, il primo risultato temporaneo impostato dall'utente (in questo caso per i formatori) elenca i formatori disponibili e i relativi orari di inizio blocco, in cui sono inclusi solo quelli che hanno almeno due ore disponibili. Si crea un altro set di risultati per le stanze e un altro per le attrezzature. A questo punto unisci gli orari disponibili di tutte e tre le categorie in un'unica lista e assegna a ogni intervallo un'identità, quindi giorno 1 ora 1 è 1, giorno 1 ora 2.5 è 2, giorno 3 ora 3.25 è 3, ecc. combinato) elenco di tutti i tempi disponibili in tutte le categorie. Questi ID vengono aggiornati di nuovo nei rispettivi set intermedi. Quindi la prima fascia oraria disponibile per una stanza potrebbe essere 2, la prima per un allenatore potrebbe essere 5, e la prima per l'attrezzatura potrebbe essere 7. Ora si interroga sul set di tutti i record dove "trainertimeid = roomtimeid and trainertimeid = equipmenttimeid" . Ciò che viene restituito è l'insieme di tutti i record in cui è disponibile la disponibilità in tutte e tre le categorie.