Risoluzione dei conflitti di appuntamenti automatici

Question

Risoluzione dei conflitti di appuntamenti automatici

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

5

Sto cercando di capire un algoritmo per la risoluzione dei tempi degli appuntamenti.

Al momento ho un algoritmo ingenuo che abbatte ripetutamente gli appuntamenti in conflitto, fino a quando non ci sono più appuntamenti.

# The appointment list is always sorted on start time
appointment_list = [
   <Appointment: 10:00 -> 12:00>,
   <Appointment: 11:00 -> 12:30>,
   <Appointment: 13:00 -> 14:00>,
   <Appointment: 13:30 -> 14:30>,
]

I vincoli sono quegli appuntamenti:

non può essere dopo le 15:00
non può essere prima delle 9:00

Questo è l'algoritmo ingenuo

for i, app in enumerate(appointment_list):
    for possible_conflict in appointment_list[i+1:]:
        if possible_conflict.start < app.end:
           difference = app.end - possible_conflict.start
           possible_conflict.end   += difference
           possible_conflict.start += difference
        else:
           break

Ciò comporta la seguente risoluzione, che ovviamente rompe quei vincoli e l'ultimo appuntamento dovrà essere spinto al giorno successivo.

appointment_list = [
   <Appointment: 10:00 -> 12:00>,
   <Appointment: 12:00 -> 13:30>,
   <Appointment: 13:30 -> 14:30>,
   <Appointment: 14:30 -> 15:30>,
]

Ovviamente questo non è ottimale, esegue 3 movimenti di appuntamento quando il conflitto potrebbe essere risolto con uno: se siamo stati in grado di spingere indietro il primo appuntamento, potremmo evitare di spostare tutti gli appuntamenti successivi verso il basso.

Penso che dovrebbe esserci una sorta di approccio a distanza che calcola il numero minimo di appuntamenti da spostare per risolvere il conflitto di scheduling , ma non posso ottenere un controllo sulla metodologia. Dovrebbe essere la ricerca della prima soluzione in profondità o in profondità. Quando so se la soluzione è "abbastanza buona"?

algorithms

posta Thomas 31.10.2013 - 06:33

fonte

2 risposte

Leggi altre domande sui tag algorithms

Debug di un processo lento [chiuso] Per i programmatori interni (gestori non di progetto), normalmente ricevete le istruzioni di progetto scritte in anticipo?

score 1 · Answer 1

Questo è un problema classico da risolvere con un algoritmo di pianificazione, molti documenti di ricerca e di PHd sono stati scritti su questo tipo di problema. Pertanto è impossibile fornire una risposta breve e una risposta lunga ti costerà giorni del mio tempo.

Innanzitutto controlla quante opzioni possibili di appuntamenti hai, se questo è abbastanza basso, puoi usare il tracciamento posteriore per esaminare tutte le opzioni e scegliere il migliore. Altrimenti aspettatevi di passare settimane a leggere sulla ricerca, a meno che non si sia fortunati. Inizia con la lettura di Soddisfazione dei vincoli

Ci vuole solo una piccola limitazione come "i punti non vengono spostati in giorni diversi" per cambiare un problema molto difficile, in qualcosa che puoi risolvere osservando tutti i possibili risultati. Pertanto, come definisci il tuo problema è molto importante.

Vedi la domanda " Algorithm per la creazione di un orario scolastico " per i lotti di puntatore, guarda anche optaplanner in quanto è open source e può essere configurato per risolvere la maggior parte dei problemi di soddisfazione dei vincoli.

score 0 · Answer 2

Non sono sicuro di aver capito il tuo problema (se non del tutto) e / o il tuo tipo di soluzione desiderata, ma ...

Vorrei iniziare ordinando e riassegnandomi sulle lunghezze degli appuntamenti, anziché sull'ora di inizio.

Ad esempio, consideriamo un altro scenario "ancora peggiore" di sovrapposizione;

come nel tuo esempio, ma per l'ultimo appuntamento, invece, impiegheremo 2 ore:

Appointment #1: 10:00 -> 12:00 (2 hour-long)
Appointment #2: 11:00 -> 12:30 (1.5 hour-long)
Appointment #3: 13:00 -> 14:00 (1 hour-long)
Appointment #4: 13:30 -> 15:30 (2 hour-long)

Per prima cosa, riassegniamo le lunghezze (decrescenti) anziché i tempi di inizio:

Appointment #1: 10:00 -> 12:00 (2 hour-long)
Appointment #2: 13:30 -> 15:30 (2 hour-long)
Appointment #3: 11:00 -> 12:30 (1.5 hour-long)
Appointment #4: 13:00 -> 14:00 (1 hour-long)

Quindi, torniamo ai vincoli (dove il più grande intervallo di tempo consentito è comunque dalle 9:00 alle 15:00).

Già sappiamo che non saremo in grado di adattare 6,5 ore di appuntamenti in sole 6 ore totali.

Quindi, possiamo "rilasciare" (ad esempio, spingere al giorno successivo) l'appuntamento n. 4.

Ci rimane:

Appointment #1: 10:00 -> 12:00 (2 hour-long)
Appointment #2: 13:30 -> 15:30 (2 hour-long)
Appointment #3: 11:00 -> 12:30 (1.5 hour-long)

Quindi, finalmente, possiamo riprogrammare mettendo il primo appuntamento all'inizio di quel periodo di tempo, e accodando gli altri (con o senza spazi vuoti, purché non superiamo le 15:00) ...

Appointment #1: 10:00 -> 12:00 (2 hour-long) => move to 9:00 -> 11:00
Appointment #2: 13:30 -> 15:30 (2 hour-long) => move after appointment #1
Appointment #3: 11:00 -> 12:30 (1.5 hour-long) => move after appointment #2

Per finire con:

Appointment #1: 9:00 -> 11:00
Appointment #2: 11:00 -> 13:00
Appointment #3: 13:00 -> 14:30

o, perché no,

Appointment #1: 9:00 -> 11:00
Appointment #2: 11:00 -> 13:00
Appointment #3: 13:30 -> 15:00

'HTH,