Algoritmo per la creazione di un calendario scolastico
https://stackoverflow.com/questions/2177836
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Mi chiedevo se ci sono soluzioni note per l'algoritmo di creazione di un calendario scolastico. Fondamentalmente, si tratta di ottimizzare la "dispersione dell'ora" (sia nel caso degli insegnanti che delle classi) per le associazioni di classificazioni di classe. Possiamo supporre che abbiamo serie di classi, materie di lezione e insegnanti associati tra loro all'input e che il calendario dovrebbe adattarsi tra le 8:00 e le 16:00.
Immagino che probabilmente non esiste un algoritmo accurato per questo, ma forse qualcuno conosce una buona approssimazione o suggerimenti per svilupparlo.
Soluzione
Questo problema è NP-Complete!
In breve, è necessario esplorare tutte le possibili combinazioni per trovare l'elenco di soluzioni accettabili. A causa delle variazioni delle circostanze in cui il problema appare in varie scuole (ad esempio: ci sono vincoli per quanto riguarda le aule?, Alcune delle classi sono divise in sottogruppi un po 'di tempo?, È un programma settimanale? ecc.) Non esiste una classe di problema ben nota che corrisponde a tutti i problemi di pianificazione. Forse il Problema dello zaino Ha molti elementi di somiglianza con questi problemi in generale.
Una conferma che questo è sia un problema difficile che per il quale le persone cercano perennemente una soluzione, è verificare questo (lungo) Elenco di strumenti di pianificazione del software (per lo più commerciali)
A causa del gran numero di variabili coinvolte, la cui fonte più grande è, in genere, i desideri del membro della facoltà;-) ..., in genere è impraticabile considerare di elencare tutte le possibili combinazioni. Invece dobbiamo scegliere un approccio che visita un sottoinsieme degli spazi problematici/soluzione.
- Algoritmi genetici, citato in un'altra risposta è (o, iMho, sembra) ben attrezzato per eseguire questo tipo di ricerca semi-guidata (il problema è trovare una buona funzione di valutazione per i candidati da conservare per la generazione successiva)
- Riscritazione del grafico Gli approcci sono anche utili con questo tipo di problemi di ottimizzazione combinatoria.
Invece di concentrarmi su particolari implementazioni di un programma di generatore di pianificazione automatica, vorrei suggerire alcune strategie che possono essere applicate, a livello della definizione del problema.
La logica generale è che nella maggior parte dei problemi di programmazione del mondo reale, saranno necessari alcuni compromessi, non tutti i vincoli, espressi e impliciti: saranno soddisfatti pienamente. Quindi ci aiutiamo a:
- Definire e classificare tutti i vincoli noti
- Ridurre lo spazio problematico, fornendo manualmente una serie di aggiuntivo vincoli.
Ciò può sembrare controintuitivo ma per esempio fornendo un programma iniziale, parzialmente pieno (diciamo circa il 30% dei slot temporali), in un modo che soddisfa pienamente tutti i vincoli e considerando questo programma parziale immutabile, riduciamo significativamente il Tempo/spazio necessario per produrre soluzioni candidate.
Un altro modo in cui ulteriori vincoli sono ad esempio "artificialmente" aggiungendo un vincolo che impedisce di insegnare alcune materie in alcuni giorni della settimana (se questo è un programma settimanale ...); Questo tipo di vincoli si traduce nella riduzione degli spazi problema/soluzione, senza, in genere, escludendo un numero significativo di buoni candidati. - Garantire che alcuni dei vincoli del problema possano essere rapidamente calcolati. Questo è spesso associato alla scelta del modello di dati utilizzato per rappresentare il problema; L'idea è quella di essere in grado di optare rapidamente (o di eliminare) alcune delle opzioni.
- Ridefinendo il problema e permettendo di rompere alcuni dei vincoli, alcune volte (in genere verso i nodi finali del grafico). L'idea qui è di rimuovere alcuni di vincoli per compilare gli ultimi slot nel programma o per far fermare il programma del generatore di pianificazione automatica di completare l'intero programma, fornendo invece un elenco di una dozzina di candidati plausibili. Un essere umano è spesso in una posizione migliore per completare il puzzle, come indicato, eventualmente rompere alcuni dei controint, usando le informazioni che in genere non sono condivise con la logica automatizzata (ad esempio "Nessuna matematica nel pomeriggio" può essere infuriata a volte Per la classe "Matematica e fisica avanzata" o "è meglio rompere uno dei requisiti di Mr Jones rispetto a uno di Smith ... ;-))
Nella lettura delle prove di questa risposta, mi rendo conto che è abbastanza timido nel fornire una risposta definita, ma non è comunque pieno di suggerimenti pratici. Spero che questo aiuto, con quello che è, dopo tutto, un "problema difficile".
Altri suggerimenti
È un casino. un casino reale. Per aggiungere alle risposte, già molto completa, voglio sottolineare la mia esperienza familiare. Mia madre era un'insegnante e era coinvolta nel processo.
Si scopre che avere un computer per farlo non è solo difficile da codificare per sé, ma è anche difficile perché ci sono condizioni difficili da specificare per un programma per computer pre-cotto. Esempi:
- Un insegnante insegna sia nella tua scuola che in un altro istituto. Chiaramente, se termina la lezione lì alle 10.30, non può iniziare dai tuoi locali alle 10.30, perché ha bisogno di un po 'di tempo per spostarsi tra gli istituti.
- Due insegnanti sono sposati. In generale, è considerato una buona pratica non avere due insegnanti sposati nella stessa classe. Questi due insegnanti devono quindi avere due classi diverse
- Due insegnanti sono sposati e il loro figlio frequenta la stessa scuola. Ancora una volta, devi impedire ai due insegnanti di insegnare nella classe specifica dove si trova il loro bambino.
- La scuola ha strutture separate, come un giorno la classe è in un istituto e un altro giorno in cui la classe è in un altro.
- La scuola ha laboratori condivisi, ma questi laboratori sono disponibili solo in determinati giorni feriali (per motivi di sicurezza, ad esempio, dove è richiesto il personale aggiuntivo).
- Alcuni insegnanti hanno preferenze per il giorno libero: alcuni preferiscono lunedì, altri venerdì, altri mercoledì. Alcuni preferiscono venire la mattina presto, alcuni preferiscono venire più tardi.
- Non dovresti avere situazioni in cui hai una lezione di dire, storia alla prima ora, quindi tre ore di matematica, poi un'altra ora di storia. Non ha senso per gli studenti, né per l'insegnante.
- Dovresti diffondere gli argomenti in modo uniforme. Non ha senso avere i primi giorni della settimana solo matematica, e poi il resto della settimana solo letteratura.
- Dovresti dare ad alcuni insegnanti due ore consecutive per eseguire test di valutazione.
Come puoi vedere, il problema non è NP-completo, è NP-Insane.
Quindi quello che fanno è che hanno un grande tavolo con piccoli inserti in plastica e spostano gli inserti fino a quando non si ottiene un risultato soddisfacente. Non iniziano mai da zero: normalmente iniziano dal calendario dell'anno precedente e apportano regolazioni.
Il International TimeTabling Competition 2007 Ho avuto una traccia di pianificazione delle lezioni e una traccia di pianificazione degli esami. Molti ricercatori hanno partecipato a quella concorrenza. Molte euristiche e metaheuristiche sono state provate, ma alla fine la metaheuristica della ricerca locale (come la ricerca di tabu e la ricottura simulata) hanno chiaramente battuto altri algoritmi (come gli algoritmi genetici).
Dai un'occhiata ai 2 quadri open source usati da alcuni finalisti:
- Jboss optaplanner (Java, open source)
- Unitime (Java, open source) - Altro per le università
Uno dei miei incarichi a mezzo termine era una generazione di tabelle della scuola di algoritmo genetico.
L'intero tavolo è un "organismo". Ci sono stati alcuni cambiamenti e avvertimenti all'approccio generico degli algoritmi genetici:
Sono state stabilite regole per "tavoli illegali": due classi nella stessa classe, un insegnante che insegnava due gruppi contemporaneamente ecc. Queste mutazioni sono state immediatamente considerate letali e un nuovo "organismo" è stato spuntato al posto del "defunto" immediatamente. Quello iniziale è stato generato da una serie di tentativi casuali di ottenere una (se senza senso). La mutazione letale non è stata contata per il conteggio delle mutazioni in iterazione.
Le mutazioni di "scambio" erano molto più comuni delle mutazioni di "modifica". I cambiamenti erano solo tra parti del gene che aveva senso - nessuna sostituzione di un insegnante con un'aula.
Sono stati assegnati piccoli bonus per raggruppare alcune 2 ore insieme, per assegnare la stessa classe generica in sequenza per lo stesso gruppo, per mantenere il carico di lavoro degli insegnanti e il carico di classe continuo. I bonus moderati sono stati assegnati per dare aule corrette per il soggetto determinato, mantenendo le ore di lezione all'interno delle obbligazioni (mattina o pomeriggio) e simili. I grandi bonus erano per l'assegnazione del numero corretto di argomento dato, dato carico di lavoro per un insegnante ecc.
Gli insegnanti potrebbero creare i loro programmi di carico di lavoro di "Want Ow funzionare allora", "Okay per funzionare allora", "non piace lavorare allora", "non posso funzionare allora", con i pesi adeguati assegnati. L'intero 24 ore era ora legale, tranne la notte molto indesiderata.
La funzione di peso ... Oh sì. La funzione di peso era un prodotto enorme e mostruoso (come nella moltiplicazione) dei pesi assegnati a caratteristiche e proprietà selezionate. Era estremamente ripido, una proprietà facilmente in grado di cambiarlo da un ordine di grandezza su o giù - e c'erano centinaia o migliaia di proprietà in un organismo. Ciò ha comportato numeri assolutamente enormi poiché i pesi e, come risultato diretto, devono utilizzare una libreria Bignum (GMP) per eseguire i calcoli. Per una piccola prova di circa 10 gruppi, 10 insegnanti e 10 aule, il set iniziale è iniziato con una nota di 10^-200something e rifinito con 10^+300something. Era totalmente inefficiente quando era più piatto. Inoltre, i valori sono aumentati molto più ampi con "scuole" più grandi.
Per quanto riguarda il tempo di calcolo, c'era poca differenza tra una piccola popolazione (100) per un lungo periodo e una grande popolazione (10K+) per meno generazioni. Il calcolo nello stesso tempo ha prodotto circa la stessa qualità.
Il calcolo (su una CPU da 1 GHz) richiederebbe circa 1 ora per stabilizzarsi vicino a 10^+300, generando programmi che sembravano piuttosto belli, per detto custodia di prova 10x10x10.
Il problema è facilmente paralensibile fornendo una struttura di networking che scambia i migliori campioni tra i computer che eseguono il calcolo.
Il programma risultante non ha mai visto la luce del giorno fuori portarmi un buon voto per il semestre. Ha mostrato qualche promessa ma non ho mai avuto abbastanza motivazione per aggiungere alcuna GUI e renderlo utilizzabile al pubblico in generale.
Questo problema è più duro di quanto sembri.
Come altri hanno accennato, questo è un problema di NP-completo, ma analizziamo cosa significa.
Fondamentalmente, significa che devi guardare tutte le possibili combinazioni.
Ma "guarda" non ti dice molto cosa devi fare.
Generare tutte le possibili combinazioni è facile. Potrebbe produrre un'enorme quantità di dati, ma non dovresti avere molti problemi a comprendere i concetti di questa parte del problema.
Il secondo problema è quello di giudicare se una data possibile combinazione è buona, cattiva o migliore della precedente soluzione "buona".
Per questo hai bisogno di più di "è una possibile soluzione".
Ad esempio, lo stesso insegnante lavora 5 giorni alla settimana per x settimane di fila? Anche se questa è una soluzione funzionante, potrebbe non essere una soluzione migliore che alternare tra due persone in modo che ogni insegnante faccia una settimana ciascuno. Oh, non ci hai pensato? Ricorda, queste sono persone con cui hai a che fare, non solo un problema di allocazione delle risorse.
Anche se un insegnante potrebbe lavorare a tempo pieno per 16 settimane di fila, potrebbe essere una soluzione non ottimale rispetto a una soluzione in cui si tenta di alternare tra insegnanti e questo tipo di bilanciamento è molto difficile da costruire nel software.
Riassumendo, produrre una buona soluzione a questo problema varrà molto, a molte persone. Quindi, non è un problema facile da abbattere e risolvere. Preparati a raggiungere alcuni obiettivi che non sono al 100% e chiamarli "abbastanza bravi".
Aggiornamento: dai commenti ... dovrebbe anche avere l'euristica!
Andrei con Prolog ... quindi userei Ruby o Perl o qualcosa per pulire la soluzione in una forma più bella.
teaches(Jill,math).
teaches(Joe,history).
involves(MA101,math).
involves(SS104,history).
myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
predsort(myHeuristic,Classes,ClassesNew),
createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].
Sono (ancora) nel processo di fare qualcosa di simile a questo problema, ma usando lo stesso percorso che ho appena menzionato. Prolog (come linguaggio funzionale) semplifica la risoluzione dei problemi di NP-hard.
Gli algoritmi genetici sono spesso utilizzati per tale programmazione.
Fondare Questo esempio (creando il programma di classe usando l'algoritmo genetico) che corrisponde abbastanza bene alle tue esigenze.
Ecco alcuni link che ho trovato:
Orario scolastico - Elenca alcuni problemi coinvolti
Il mio algoritmo di calendario, implementato in FET (software di orario gratuito, http://lalescu.ro/liviu/fet/ , un'applicazione di successo):
L'algoritmo è euristico. L'ho chiamato "scambio ricorsivo".
Input: un insieme di attività a_1 ... a_n e i vincoli.
Output: un set di volte ta_1 ... ta_n (la fascia oraria di ogni attività. Le stanze sono escluse qui, per semplicità). L'algoritmo deve mettere ogni attività in una fascia oraria, rispettando i vincoli. Ogni ta_i è tra 0 (t_1) e max_time_slots-1 (t_m).
Vincoli:
C1) BASIC: un elenco di coppie di attività che non possono essere simultanee (ad esempio, A_1 e A_2, perché hanno lo stesso insegnante o gli stessi studenti);
C2) Molti altri vincoli (esclusi qui, per semplicità).
L'algoritmo del calendario (che ho chiamato "scambiamento ricorsivo"):
- Ordina le attività, prima più difficili. Passaggio non critico, ma accelera l'algoritmo forse 10 volte o più.
Prova a posizionare ogni attività (A_I) in una fascia oraria consentita, seguendo l'ordine sopra, uno alla volta. Cerca uno slot disponibile (T_J) per A_I, in cui questa attività può essere posizionata rispettando i vincoli. Se sono disponibili più slot, scegli uno casuale. Se nessuno è disponibile, lo scambio ricorsivo:
un. Per ogni fascia oraria t_j, considera cosa succede se si mette a_i in t_j. Ci sarà un elenco di altre attività che non sono d'accordo con questa mossa (ad esempio, l'attività A_K è sullo stesso slot T_J e ha lo stesso insegnante o gli stessi studenti di A_I). Conservare un elenco di attività contrastanti per ogni fascia oraria T_J.
b. Scegli uno slot (T_J) con il numero più basso di attività contrastanti. Supponiamo che l'elenco delle attività in questo slot contiene 3 attività: A_P, A_Q, A_R.
c. Posiziona A_i su t_j e fai a_p, a_q, a_r non allocato.
d. Cerca ricorsivamente di posizionare A_P, A_Q, A_R (se il livello di ricorsione non è troppo grande, diciamo 14 e se il numero totale di chiamate ricorsive contate dal passaggio 2) su A_I non è stato troppo grande, diciamo 2*n) come nel passaggio 2).
e. Se posizionato correttamente A_P, A_Q, A_R, restituisci con successo, altrimenti prova altri fasce orarie (vai al passaggio 2 B) e scegli lo slot temporale migliore successivo).
f. Se tutti (o un numero ragionevole di) fasce di tempo sono stati provati senza successo, restituire senza successo.
g. Se siamo al livello 0 e non abbiamo avuto successo nel posizionare A_I, posizionarlo come nei passaggi 2 b) e 2 c), ma senza ricorsione. Ora abbiamo 3 - 1 = 2 altre attività da posizionare. Vai al passaggio 2) (alcuni metodi per evitare il ciclo vengono utilizzati qui).
Ho progettato algoritmi commerciali sia per il calendario della classe che per gli orari di esame. Per il primo ho usato la programmazione intera; Per il secondo un'euristica basata sulla massimizzazione di una funzione oggettiva scegliendo slot swap, molto simile al processo manuale originale che si era evoluto. Le cose principali per accettare tali soluzioni sono la capacità di rappresentare tutti i vincoli del mondo reale; E affinché gli orari umani non siano in grado di vedere modi per migliorare la soluzione. Alla fine, la parte algoritmica è stata abbastanza semplice e facile da implementare rispetto alla preparazione dei database, all'interfaccia utente, alla capacità di riferire su statistiche come l'utilizzo della stanza, l'educazione degli utenti e così via.
Questo documento descrive abbastanza bene il problema degli orari della scuola e il loro approccio all'algoritmo: "Lo sviluppo del programma: uno scheduler interattivo basato su vincoli per scuole e college.[PDF
L'autore mi informa che il software Syllabus è ancora utilizzato/sviluppato qui: http://www.scientia.com/uk/
Lavoro su un motore di pianificazione ampiamente utilizzato che fa esattamente questo. Sì, è NP-completo; Gli approcci migliori cercano di approssimare una soluzione ottimale. E, naturalmente, ci sono molti modi diversi per dire quale è la soluzione "migliore" - è più importante che i tuoi insegnanti siano soddisfatti dei loro programmi o che gli studenti entrano in tutte le loro classi, per esempio?
La domanda più importante in assoluto che devi risolvere all'inizio è Cosa rende un modo per pianificare questo sistema meglio di un altro? Cioè, se ho un programma con la signora Jones che insegna matematica alle 8 e il signor Smith che insegna matematica a 9 anni, è migliore o peggiore di uno con entrambi che insegnano matematica a 10 anni? È meglio o peggio di uno con la signora Jones che insegna alle 8 e il signor Jones che insegna a 2? Come mai?
Il consiglio principale che darei qui è di dividere il problema il più possibile - forse corso per corso, forse insegnante di insegnante, forse stanza per stanza - e lavorare prima per risolvere il sotto -problema. Lì dovresti finire con più soluzioni tra cui scegliere e devi sceglierne una come il più probabile ottimale. Quindi, lavorare per rendere i sotto-problemi "precedenti" tengono conto delle esigenze dei successivi sotto-problemi nel segnare le loro potenziali soluzioni. Quindi, forse lavora su come tirarti fuori dalle situazioni dipinto-in-the-corrie (supponendo che non puoi anticipare quelle situazioni in precedenti sotto-problemi) quando arrivi a uno stato "senza soluzioni valide".
Un passaggio di ottimizzazione della ricerca locale viene spesso utilizzato per "lucidare" la risposta finale per risultati migliori.
Si noti che in genere abbiamo a che fare con sistemi altamente vincolati dalle risorse nella programmazione scolastica. Le scuole non passano durante l'anno con molte stanze vuote o insegnanti seduti nel salone il 75% della giornata. Approcci che funzionano meglio in ambienti ricchi di soluzione non sono necessariamente applicabili nella programmazione scolastica.
In generale, la programmazione dei vincoli è un buon approccio a questo tipo di problema di pianificazione. Una ricerca sulla "programmazione dei vincoli" e sulla pianificazione o sulla "pianificazione basata sui vincoli" sia all'interno di Stack Overflow che su Google genererà alcuni buoni riferimenti. Non è impossibile: è solo un po 'difficile pensare quando si utilizzano metodi di ottimizzazione tradizionali come l'ottimizzazione lineare o intero. Un output sarebbe: esiste un programma che soddisfa tutti i requisiti? Questo, di per sé, è ovviamente utile.
Buona fortuna !
Puoi farcela con algoritmi genetici, sì. Ma non dovresti :). Può essere troppo lento e la messa a punto dei parametri può essere troppo temporale ecc.
Ci sono altri approcci di successo. Tutti implementati nei progetti open source:
- Approccio basato sui vincoli
- Implementato in Unitime (non proprio per le scuole)
- Potresti anche andare oltre e utilizzare la programmazione interi. Fatto con successo a Udine University e anche all'Università Bayreuth (ero coinvolto lì) usando il software commerciale (Ilog Cplex)
- Approccio basato sulle regole con Heuristisc - vedi Pianificatore sbava
- Euristica diversa - Fet e il mio
Vedi qui per un Elenco software per il calendario
Penso che dovresti usare l'algoritmo genetico perché:
- È più adatto a grandi casi di problemi.
- Produce una complessità di tempo ridotta sul prezzo della risposta imprecisa (non il meglio finale)
- È possibile specificare facilmente vincoli e preferenze regolando le punizioni di fitness per non soddisfatte.
- È possibile specificare il limite di tempo per l'esecuzione del programma.
La qualità della soluzione dipende da quanto tempo intendi dedicare a risolvere il programma ..
Definizione degli algoritmi genetici
Dai un'occhiata anche a:una domanda simile e un altro
Non so che nessuno sarà d'accordo con questo codice, ma ho sviluppato questo codice con l'aiuto del mio algoritmo e sta lavorando per me in Ruby. SoggetFlag e TeacherFlag sono l'hash con l'ID corrispondente e il valore della flag che è booleano. Qualsiasi problema contattami ....... (-_-)
periodflag.each do | k2, v2 |
if(TimetableDefinition.find(k2).period.to_i != 0)
subjectflag.each do |k3,v3|
if (v3 == 0)
if(getflag_period(periodflag,k2))
@teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
@teacherlists=Employee.find(@teachers)
teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle]
teacherflag.each do |k4,v4|
if(v4 == 0)
if(getflag_subject(subjectflag,k3))
subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
if subjectperiod.blank?
issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
if issubjectpresent.blank?
isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
if isteacherpresent.blank?
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@timetable_struct.id
@finaltt.employee_id=k4
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=k3
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
else
@subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
@finaltt.employee_id=@subjectdetail.employee_id
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=@subjectdetail.subject_id
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
end
end
end
end
end
end
end
end
end
