Serve aiuto per identificare un algoritmo di pianificazione della lega

Question

Serve aiuto per identificare un algoritmo di pianificazione della lega

#1 da (3 voti)
#2 da (1 voti)
#3 da (1 voti)

9

Sto cercando di creare uno schedulatore sportivo. Sto riscontrando problemi nell'identificare un algoritmo per aiutarmi a riempire in modo efficiente ogni slot.

I dati di esempio per costruire la pianificazione sarebbero:

10 squadre
Ogni squadra si gioca 1 volta (45 partite totali richiesto)
Ogni squadra gioca non più di 1 volta al giorno
Nel mio test sto usando 9 giorni con 5 slot al giorno.

Tabella combinata (contiene 45 combinazioni)

ID
Team1ID
Team2ID
bitAssigned

Tabella di pianificazione (contiene 45 intervalli di tempo)

scheduleID
homeTeamID
awayTeamID
GameDate
GameTime

In questo momento le mie procedure esistenti riempiono circa il 90% degli slot lasciando il 10% dei miei spazi vuoti a un conflitto di pianificazione basato sulle regole precedenti.

I loop sulla mia tabella di pianificazione in ordine crescente data / ora.
Il mio primo slot potrebbe essere il sabato alle 8 del mattino.
Invito un elenco di squadre che non sono ancora state pianificate. Quindi faccio una serie di possibili combinazioni di quelle squadre. Quindi uso quell'array per estrarre 1 record casuale dalla mia tabella delle combinazioni da combinazioni che non sono ancora state pianificate e metto quelle squadre sul programma. Quindi ho impostato quella combinazione come usato.

Ripeto il ciclo più e più volte e ogni volta il mio elenco di team disponibili si riduce e anche il mio array risulta più piccolo.

Sto scoprendo che alcuni giorni vanno bene, e in altri giorni le ultime ultime 2 squadre rimanenti hanno già giocato in una settimana precedente, quindi non vengono aggiunte di nuovo al programma.

L'unica cosa che non ho ancora provato è di "resettare" i giorni di conflitto e riprovarli per vedere se ottengo posizionamenti migliori.

Qualcuno ha qualche suggerimento?

algorithms scheduling

posta steve 11.09.2014 - 19:11

fonte

3 risposte

Leggi altre domande sui tag algorithms scheduling

Javascript MVC application design (canvas) Come gestire le informazioni sul copyright dai contributori a un progetto con licenza BSD

score 3 · Answer 1

Ecco un algoritmo che ho inventato io stesso. Non so se esiste già o è in realtà l'implementazione del round robin:

1 4    1 5   1 6   1 3   1 2
2 5    4 6   5 3   6 2   3 4
3 6    2 3   4 2   5 4   6 5

in pratica inizi con

e mantieni sempre il 1 nella stessa posizione e ruota il resto.

In questo modo otterrai sempre un programma di partite uniche. Questo è estremamente facile da implementare e ridimensiona con qualsiasi numero di avversari, pari o dispari. Se hai un numero irregolare di avversari, non mettere una squadra nella posizione 1 e hanno un turno libero.

score 1 · Answer 2

Penso che lo stai facendo all'indietro. Non inizia con la tabella degli orari, inizia con una tabella / array / indipendentemente dalle combinazioni di gioco (i 45 giochi). Da lì, è un processo semplice per assegnare i giochi a un giorno, basato su una squadra che gioca solo una volta al giorno. E poiché i matchup avvengono solo una volta (la Squadra A gioca solo la Squadra B una volta), la pianificazione è semplice perché devi solo assicurarti che il matchup non sia già avvenuto (le voci sono "uniche" in quel modo).

score 1 · Answer 3

Ho generato il programma di round singolo del team di 10 giocatori di seguito. Mi ci sono voluti circa 3 minuti.

Informazioni sulla pianificazione:

10 squadre - 1 round robin (vengono visualizzate solo le prime 6 settimane)
Data di inizio della stagione 1/6/15 - data di fine 15/5/15
2 giochi ogni martedì, 3 giochi ogni giovedì, 5 partite a settimana nessuna data di salto

Tutti i team vengono distribuiti per giocare allo stesso modo nelle 5 fasce orarie.
Tutti giocano a 9 giochi.
Tutti si giocano a vicenda una volta.
Tutti sono distribuiti uniformemente come home & visitatore (5/4 o 4/5). Nota: alla fine del round robin 2 tutte le squadre giocano 18 partite (9 come casa e 9 come visitatore) e tutte le squadre hanno 2 byte.
Tutti sono distribuiti per giocare in modo uniforme nelle 5 fasce orarie ogni settimana.

Abbiamo usato un vecchio computer con frame principale di Honeywell e poco meno di 3 anni per mettere insieme tutto questo. Una volta eseguito il debug del nostro software di pianificazione, il computer del frame principale ha impiegato molte ore alla ricerca di milioni di permutazioni e amp; combinazioni per calcolare e creare modelli bilanciati per 4 o 22 squadre che stavamo cercando.

10 Team Division Schedule   DATE 12/20/14

DATE   DAY TIME    LOCATION  GM  HOME vs VISITOR

Jan  6 Tue 6:00pm  Field #1   1  # 1 vs #10 
Jan  6 Tue 6:00pm  Field #2   1  # 2 vs # 9 
Jan  8 Thu 6:30pm  Field #3   1  # 3 vs # 8 
Jan  8 Thu 6:30pm  Field #4   1  # 4 vs # 7 
Jan  8 Thu 6:30pm  Field #5   1  # 5 vs # 6

Jan 13 Tue 6:00pm  Field #1   2  # 6 vs # 3 
Jan 13 Tue 6:00pm  Field #2   2  #10 vs # 8 
Jan 15 Thu 6:30pm  Field #3   2  # 7 vs # 2 
Jan 15 Thu 6:30pm  Field #4   2  # 9 vs # 1 
Jan 15 Thu 6:30pm  Field #5   2  # 4 vs # 5

Jan 20 Tue 6:00pm  Field #1   3  # 7 vs # 9 
Jan 20 Tue 6:00pm  Field #2   3  # 5 vs # 2 
Jan 22 Thu 6:30pm  Field #3   3  # 6 vs #10 
Jan 22 Thu 6:30pm  Field #4   3  # 3 vs # 4 
Jan 22 Thu 6:30pm  Field #5   3  # 8 vs # 1

Jan 27 Tue 6:00pm  Field #1   4  # 9 vs # 5 
Jan 27 Tue 6:00pm  Field #2   4  # 1 vs # 7 
Jan 29 Thu 6:30pm  Field #3   4  # 2 vs # 3 
Jan 29 Thu 6:30pm  Field #4   4  # 8 vs # 6 
Jan 29 Thu 6:30pm  Field #5   4  #10 vs # 4

Feb  3 Tue 6:00pm  Field #1   5  # 4 vs # 8 
Feb  3 Tue 6:00pm  Field #2   5  # 7 vs # 5 
Feb  5 Thu 6:30pm  Field #3   5  # 1 vs # 6 
Feb  5 Thu 6:30pm  Field #4   5  #10 vs # 2 
Feb  5 Thu 6:30pm  Field #5   5  # 3 vs # 9

Feb 10 Tue 6:00pm  Field #1   6  # 3 vs # 7 
Feb 10 Tue 6:00pm  Field #2   6  # 6 vs # 4 
Feb 12 Thu 6:30pm  Field #3   6  # 5 vs # 1 
Feb 12 Thu 6:30pm  Field #4   6  # 9 vs #10 
Feb 12 Thu 6:30pm  Field #5   6  # 8 vs # 2

Non esiste un algoritmo che risolva i problemi generali di pianificazione associati alle centinaia o migliaia di tipi diversi di campionati, sport e situazioni potenziali. Quello che abbiamo fatto per risolvere questo problema è stato quello di adottare un approccio diverso per calcolare gli orari. Si inizia con la matematica molto complessa per determinare le giuste coppie di round robin (match-up), ma quello era solo l'inizio. Sono necessari altri pezzi per creare un utile programma bilanciato che possa essere pubblicato e distribuito. Giocatori, allenatori, genitori, ecc., Tutti hanno bisogno di sapere non solo chi stanno giocando ; ma dove stanno giocando ; a che ora stanno giocando ; se sono casa o visitatore ; e per molti campionati, un numero di gioco .

Spero che questo aiuti voi e gli altri a capire cosa ci ha portato 3 anni a capire.