Esiste un algoritmo di pianificazione che consenta la pianificazione di n-set di eventi?

Naviga le tue risposte
0

Il problema è una sorta di problema di pianificazione, vorrei identificare che tipo di problema si tratta o, almeno, a che tipo di problemi si riferisce?

Diciamo che abbiamo n serie di eventi S1, S2, ..., Sn, in cui un evento ha la durata di un giorno.
Ogni serie di eventi ha solo una ripetizione a settimana.
Ogni serie di eventi ha un periodo di ripetizione dell'evento, può essere una volta alla settimana, ogni due settimane, una volta al mese, ecc ...
Devo riprogrammare gli insiemi di eventi per ottimizzare la pianificazione.
L'output dell'algoritmo è una riprogrammazione di eventi che ottimizzano le occorrenze degli eventi di ogni insieme al fine di ottenere il numero minimo di eventi distinti tra i set di eventi, virtualmente il risultato dovrebbe essere un evento impostato con il numero di eventi minimo possibile.

Primo esempio

Supponiamo di dover impostare gli eventi S1 e S2, S1 si ripete una volta alla settimana, S2 si ripete ogni due settimane. 

       W1   W2   W3   W4   W5 ... WSK
S1.    x    x    x    x    x  
S2.    x         x         x

La pianificazione risultante è una che gli eventi nella stessa settimana di ogni serie devono essere impostati sullo stesso giorno

Secondo esempio

Supponiamo di dover impostare gli eventi S1 e S2, S1 si ripete ogni due settimane, S2 si ripete ogni tre settimane. 

       W1   W2   W3   W4   W5 ... WSK
S1.    x         x         x  
S2.    x              x

La settimana 1 può essere unita. Ma come posso gestire W3, W4, W5?
S2 nella settimana 4, deve essere unito a S1 nella settimana 3 o nella settimana 5?
Che tipo di regola può essere definita per verificare se la fusione è possibile? Devo definire un intervallo di giorni in cui un evento può essere spostato? Penso che manchi qualcosa nella definizione del problema.

Terzo esempio

Supponiamo di avere più di due set di eventi 

       W1   W2   W3   W4   W5 ... WSK
S1.    x    x    x    x    x  
S2.         x         x
S3.    x              x

Che tipo di regola dovrei applicare?

Esiste un algoritmo generale?

    
posta landal79 27.04.2017 - 16:31
fonte

1 risposta

1

Consente di astrarre ulteriormente la tua domanda: non parliamo di settimane ma di timeslots .

Prenderò questo approccio diretto:

Quando pianifichi K timeslot nel futuro, crea una struttura dati bidimensionale in memoria, in questo modo: 

      TS1  TS2  TS3  TS4  TS5 ... TSK
Sch1.
Sch2.
Sch3.
 ...

Quindi riempi le celle di questa struttura con gli eventi programmati: 

      TS1  TS2  TS3  TS4  TS5  TS6  TS7  TS8  TS9 TS10
Sch1.  X         X         X         X         X    
Sch2.  X              X              X             X
Sch3.  X                   X                   X

Ora puoi espropriare con quello. Definisci un fattore prossimo N . Ogni volta che c'è più di un evento in N timeslot, raggruppali al più presto (o all'ultima - non importa) timeslot. 

Pseudo-Code:
for (index from 0 .. K)
   eventsInNTimeSlots = // find all the events in the current + N - 1 timeslots
   if (eventsInNTimeSlots.size > 1)
       for (event in eventsInNTimeSlots)
           event.timeSlot = index

Puoi quindi scrivere un pezzo di codice che prova un gruppo di% diverso di% co_de, anche: 

rawSchedule = // as defined above
results: Map<Number,Number> // maps N to the number of days with events
for (N in 0..5) {
    schedule = copy rawSchedule
    // optimize schedule as defined above
    nEvents = // count days with events in schedule
    results.put(N, nEvents)
}

// find the minimum value in results and use the associated N

Se è necessario pianificare in anticipo per sempre (fino all'eternità), è possibile utilizzare lo stesso algoritmo: calcolare il numero di timeslot dopo il quale la pianificazione inizia a ripetersi. Se le tue pianificazioni sono tutte semplici come N puoi semplificare calcolare every X days

Utilizza quel numero come lcm(X0 ... Xi)

    
risposta data 27.04.2017 - 18:30
fonte

Leggi altre domande sui tag

Quale fine dovrebbe iniziare per primo? (MVC) Mi si applica una licenza che ho messo sul mio software? Posso cambiare la licenza? (Creative Commons BY-SA 4.0) [duplicato]