Sto lavorando su un algoritmo di scheduling sportivo con diversi vincoli, uno (due) di questi è un tempo di attesa minimo e / o massimo tra i giochi. Della stessa squadra, cioè.
Quindi, se il Team Blue è programmato alle 16:00 (finisce alle 17:00) nel Campo 1, e abbiamo un'attesa massima di 3 ore e un minimo di 1, allora il suo prossimo gioco dovrebbe essere programmato:
-
tra le 18:00 e le 20:00 o
-
tra le 12:00 e le 14:00
Visivamente, dove M è la corrispondenza pianificata di cui stiamo parlando e X gli slot idonei:
+------+------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 11am | 12pm | 1pm | 2pm | 3pm | 4pm | 5pm | 6pm | 7pm | 8pm | 9pm |
+------+------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | X | X | X | | M | | X | X | X | |
+------+------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Questo vincolo è complicato perché ogni volta che viene programmato un nuovo gioco, vengono pubblicate due nuove limitazioni: una per ogni squadra che compone il gioco.
Lo scenario in cui viene utilizzato questo algoritmo di pianificazione del calendario consiste in un elenco di giochi (ad esempio round-robin) a cui è necessario assegnare uno qualsiasi degli slot disponibili. Uno slot è composto da un campo, una data di inizio e una data di fine. Un esempio di competizione sarebbe:
Weekend Tournament: 8 teams playing a double round-robin (14 games each). The Club provides 3 fields and is open Saturday all day (9am-9pm) and Sunday morning (9am-14pm). Additional constraints may be posted.
L'algoritmo di pianificazione corrente funziona in modo non complicato: itera l'elenco di corrispondenze e tenta di programmarlo nel primo spazio idoneo.
for game in games:
for slot in slots:
if eligible(game, slot):
schedule(game, slot)
In pratica l'algoritmo fa più cose, mirando a obiettivi diversi, ma questa è l'essenza del modo in cui opera.
Se non tutti i giochi possono essere programmati (a causa di vincoli), viene avviato un ulteriore processo per cercare di migliorare il risultato. Poiché questi giochi non possono essere programmati nelle slot aperte, guardiamo alle slot usate. Se qualcuna di queste slot è idonea, proviamo a riprogrammare l'altro gioco attualmente occupato, esaminando prima gli slot aperti, quindi gli slot usati (il processo viene ripetuto fino a una certa profondità). Se quell'altro gioco è stato riprogrammato, la precedente slot è ora aperta e assegnata al gioco non programmato.
Forse lo pseudocodice fornisce un'immagine migliore:
for unscheduled_game in unscheduled_games:
for used_slot in used_slots:
if eligible(unscheduled_game, used_slot) and (reschedule(used_slot.game, open_slots) or reschedule(used_slot.game, used_slots)):
schedule(unscheduled_game, used_slot)
E questo è tutto. Il punto di questo post sta cercando di capire come cercare di gestire il vincolo del tempo di attesa. È un vincolo davvero punitivo, ed è un enorme danno per l'efficacia dell'algoritmo.
Qual è lo scopo di questo post? Alla ricerca di suggerimenti, algoritmi di pianificazione noti, tutto ciò che potrebbe aiutarmi a lavorare con il vincolo tempo di attesa minimo / massimo.
Ho bisogno di implementare questa soluzione oltre all'algoritmo esistente, quindi la programmazione dei vincoli non sarebbe una soluzione fattibile (gioco di parole non previsto) perché richiederebbe la modellazione e la riformulazione del problema interamente da zero, e non ho il risorse per questo.
Anche l'introduzione di una funzione di punteggio non funzionerebbe. In questo momento i vincoli funzionano in un modo bianco o nero: o li passi o non li fai. Non ci sono grigi.
Vorrei aggiungere che ho provato dei modi per risolverlo da solo, ma nessuno ha avuto successo. Uno di questi è:
Per ogni gioco non pianificato, esaminiamo qualsiasi spazio idoneo, ignorando il vincolo del tempo di attesa. Quindi proviamo ad eliminare il "blocco" riprogrammando i giochi che lo stanno causando. Se riusciamo a riprogrammarli tutti, il conflitto scompare e lo slot ora diventa idoneo per il gioco, programmandolo in modo efficace. In pseudocode:
for unscheduled_game in unscheduled_games:
for slot in slots:
if eligible(unscheduled_game, slot, except=WAIT_TIME):
conflicting_games = find_conflicts(unscheduled_game, slot, constraint=WAIT_TIME)
if all([reschedule(g) for g in conflicting_games]):
schedule(unscheduled_game, slot)
break
Ma come ho detto, questo non è molto utile. Nessun miglioramento è osservato da nessuna parte, perché riprogrammare i conflitti è molto difficile. Penso che ciò avvenga per gli stessi motivi per cui non è possibile pianificare i giochi non pianificati in primo luogo. Il blocco dei vincoli è troppo stretto e troppo diffuso.
Infine, voglio aggiungere che sto lavorando in Python. Menzionalo nel caso in cui ciò sia pertinente.