Algoritmo di pianificazione del tempo dell'insegnante

https://stackoverflow.com/questions/210635

03-07-2019
|

Domanda

Questo è un problema che mi viene in mente da molto tempo. Essendo figlio di un insegnante e un programmatore, mi è venuto in mente presto ... ma non ho ancora trovato una soluzione.

Quindi questo è il problema. È necessario creare un orario per una scuola, usando alcuni vincoli. Questi sono generalmente divisi in due categorie:

Controlli di integrità

Un insegnante non può insegnare due lezioni contemporaneamente
Uno studente non può seguire due lezioni contemporaneamente
Alcuni insegnanti devono avere almeno un giorno libero durante la settimana
Tutti i giorni della settimana dovrebbero essere coperti dall'orario
Il soggetto X deve avere esattamente ore così ogni settimana
...

Preferenze

Il programma di ogni insegnante dovrebbe essere il più compatto possibile (cioè l'insegnante dovrebbe lavorare tutte le ore del giorno di fila senza pause se possibile)
Gli insegnanti che hanno giorni liberi dovrebbero essere in grado di esprimere una preferenza in quale giorno
Gli insegnanti che lavorano a tempo parziale dovrebbero essere in grado di esprimere una preferenza se lavorare all'inizio o alla fine della giornata scolastica.
...

Ora, dopo alcuni anni in cui non ho trovato una soluzione (e nel frattempo ho imparato qualcosa o due ...), ho capito che questo puzza di un problema NP-difficile.

È dimostrato NP-difficile?

Qualcuno ha un'idea su come risolvere questa cosa?

Guardando questa domanda fatta penso a questo problema e se gli algoritmi genetici sarebbero utilizzabili in questo caso. Tuttavia, sarebbe piuttosto difficile mutare le possibilità mantenendo le regole di controllo della sanità mentale. Inoltre non mi è chiaro come distinguere i requisiti incompatibili.

Un piccolo addendum per specificare meglio il problema. Questo si applica alle classi in stile scuola italiana in cui tutti gli studenti sono associati in classi diverse (ad esempio: sezione 1 anno A) e gli insegnanti si spostano tra le classi. Tutti gli studenti della stessa classe hanno lo stesso orario e non hanno scelta su quali lezioni frequentare.

Soluzione

Sono uno degli sviluppatori che lavora sulla parte scheduler di un sistema informativo per studenti. Durante il nostro approccio originale al problema della pianificazione, abbiamo studiato algoritmi genetici per risolvere i problemi di soddisfazione dei vincoli e, sebbene inizialmente avessimo successo, ci siamo resi conto che c'era una soluzione meno complicata al problema (dopo aver frequentato un seminario di programmazione scolastica)

La nostra attuale implementazione funziona benissimo e usa la forza bruta con l'euristica intelligente per ottenere un programma valido in breve tempo. Il programma principale (assegnazione delle lezioni agli insegnanti) viene prima costruito, tenendo conto di tutti i vincoli che ogni insegnante ha, riducendo al minimo la possibilità di conflitti per gli studenti (in base alle loro richieste di corso). Gli studenti vengono quindi programmati nelle classi utilizzando lo stesso metodo.

In questo modo puoi fare in modo che la macchina costruisca prima un programma principale e poi lo modifichi, se necessario.

L'implementazione corrente dello scheduler è scritta in perl, ma altre opzioni che abbiamo visitato all'inizio erano Prolog e CLIPS (sistema esperto)

Altri suggerimenti

Questo è un problema di mappatura: devi mappare ogni ora in una settimana e ogni insegnante un'attività (insegnare a una determinata classe o ora gratuita).

Dividi il problema:

Crea l'elenco di insegnanti, classi e preferenze, quindi lascia che l'utente compili alcune delle preferenze su una mappa da utilizzare come punto di partenza.
Prendi casualmente un elemento dall'elenco e mettilo in una posizione libera casuale sulla mappa se non attraversa alcun controllo di integrità fino a quando l'elenco è vuoto. Se in una determinata iterazione non è possibile posizionare un elemento sulla mappa senza attraversare un controllo di integrità, spostare due posizioni sulla mappa e riprovare.
Quando la mappa è piena, prova a spostare le posizioni sulla mappa per ottimizzare il risultato.

Nei passaggi 2 e 3 mostra ogni iterazione per l'utente: gli elementi lasciati nell'elenco, le posizioni sulla mappa e la mossa calcolata successiva e consentono all'utente di intervenire.

Non ho provato questo, ma questo sarebbe il mio approccio iniziale.

Ho affrontato problemi di pianificazione / pianificazione simili in passato e la tecnica di intelligenza artificiale che è spesso più adatta per questa classe di problemi è "Ragionamento basato sui vincoli".

È fondamentalmente un metodo di forza bruta come ha suggerito Laurenty, ma l'approccio prevede l'applicazione di vincoli in un ordine efficiente per far fallire rapidamente le soluzioni non realizzabili - per ridurre al minimo il calcolo richiesto.

Googling " Ragionamento basato su vincoli " porta molte risorse sulla tecnica e sulla sua applicazione ai problemi di pianificazione.

Rispondere alla mia domanda:

Il progetto FET menzionato da gnud utilizza questo algoritmo:

Alcune parole sull'algoritmo: FET utilizza un algoritmo euristico, posizionando le attività a loro volta, a partire da i più difficili. Se non può trova una soluzione che ti punta al potenziali attività impossibili, quindi puoi correggere gli errori. L'algoritmo scambia attività in modo ricorsivo se quello è possibile per fare spazio a una nuova attività o, in casi estremi, torna indietro e cambia l'ordine di valutazione. Il codice importante è in src / motore / generate.cpp. Si prega di e-mail per i dettagli o iscriviti alla mailing elenco. L'algoritmo imita il funzionamento di un segnatempo umano, I pensare.

Link

Seguendo il ragionamento basato sui vincoli " guidato da Stringent Software su Wikipedia mi porta a questi pagine che hanno un paragrafo interessante:

Risoluzione di un vincolo di soddisfazione problema su un dominio finito è un Problema NP completo in generale. La ricerca ha dimostrato un numero di sottocasi polinomiali, per lo più ottenuto limitando il domini o vincoli consentiti o modo in cui i vincoli possono essere posizionati sopra variabili. La ricerca ha anche rapporto stabilito del problema di soddisfazione del vincolo con problemi in altri settori come finito teoria dei modelli e database.

Questo mi ricorda questo post sul blog sulla pianificazione di una conferenza , con un spiegazione video qui .

Come lo farei:

Chiedi alla popolazione di includere due cose:

Chi insegna in quale classe (mi aspetto che gli insegnanti insegnino una materia).
Cosa assume una classe in una fascia oraria specifica.

In questo modo non possiamo avere conflitti (un insegnante in 2 posti o una classe che ha due materie contemporaneamente).

La funzione fitness includerebbe:

Quante fasce orarie offre ogni insegnante alla settimana.
Quante fasce orarie ha un insegnante nello stesso giorno (non possono avere un giorno intero di insegnamento, anche questo deve essere bilanciato).
Quante fasce orarie della stessa materia ha una lezione nello stesso giorno (non possono avere un giorno intero di matematica!).

Forse prendere la deviazione standard per tutti loro poiché dovrebbero essere bilanciati.

Non sono sicuro che questo copra lo stesso terreno di Software @Stringent risposta (dato che il nome è leggermente diverso), ma ho un paio di ottimi amici che stanno ricercando l'area di Programmazione vincoli . La creazione di orari è un'applicazione della loro ricerca.

Dr Chris Jefferson ha creato un programma chiamato Minion che puoi scaricare da SourceForge ed è un risolutore di problemi di forza bruta molto veloce scritto in C ++

Penso che potresti non avere alcuni vincoli.

Uno preferirebbe, ove possibile, che gli insegnanti fossero programmati per le classi per le quali sono certificati.

Si potrebbe sospettare che le classi richieste e il numero di dipendenti previsto in ciascuna sia significativo.

Penso che il punto di partenza sarebbe elencare tutti i tuoi vincoli, capire una struttura di dati per rappresentarli.

Quindi crea una sorta di motore per creare una soluzione di prova, quindi valuta l'idoneità in base ai vincoli.

Potresti quindi lanciarvi la parte divertente degli algoritmi genetici e vedere se riesci ad aumentare la forma fisica nel tempo mentre i geni si mescolano.

Inizia con un piccolo insieme di vincoli e aumentali quando vedi il successo (se vedi il successo)

Potrebbe esserci un modo per prendere i vincoli e metterli insieme con qualcosa come un algoritmo di programmazione lineare.

Sono d'accordo. Sembra una sfida divertente

Una delle peggiori pagine web open source di sempre, ma il progetto sembra promettente: http://www.lalescu.ro/liviu/fet/

Un approccio basato sul web:
phpScheduleIt (non specifico della scuola)

Guardare questa domanda mi ha fatto riflettere su questo problema e se algoritmi genetici sarebbero utilizzabili in questo caso. Tuttavia sarebbe carino possibilità di mutare difficile mentre mantenendo le regole di controllo della sanità mentale. Inoltre non mi è chiaro come distinguere requisiti incompatibili.

Gli algoritmi genetici sono molto adatti a problemi come questo. Una volta che hai trovato una buona rappresentazione del cromosoma (in questo caso, probabilmente un vettore che rappresenta tutti gli slot di classe disponibili) sei quasi arrivato lì.

Non preoccuparti di mantenere i controlli di integrità durante la fase di mutazione. La mutazione è casuale. I controlli di sanità e preferenze appartengono entrambi alla fase di selezione. Un controllo di sanità mentale fallito ridurrebbe drasticamente la forma fisica di un individuo, mentre una preferenza fallita ridurrebbe solo leggermente la forma fisica.

I requisiti incompatibili rappresentano un problema completamente diverso. Se sono completamente incompatibili, otterrai una popolazione che non converge su nulla di utile.

Buona fortuna. Essere il figlio di un padre con questo tipo di problema è ciò che mi ha portato al gruppo di ricerca in cui sono finito in ...

Quando ero bambino, mio ??padre aveva programmato delle partite ufficiali in una lega sportiva locale, questo aveva un elenco di vincoli altrettanto lungo e ho cercato di scrivere qualcosa per aiutare. Quando sono arrivato all'università l'ho persino usato come progetto del mio ultimo anno alla fine stabilendo un'implementazione di Monte Carlo (usando un modello di ricottura simulata).

L'idea di base è che se non è NP, è piuttosto vicino, quindi piuttosto che supporre che ci sia una soluzione, vorrei partire per trovare il meglio entro un determinato periodo di tempo. Peserei tutti i vincoli con i costi per romperli: i controlli di sanità pubblica avrebbero costi enormi, le preferenze avrebbero costi più bassi (ma aumentando per più interruzioni, quindi rompendola una volta sarebbe meno della metà del costo di romperla due volte).

L'idea di base è che ho iniziato con una soluzione 'casuale' e l'ho costata; quindi apportato le modifiche scambiando un numero limitato di incarichi, rivalutandolo e quindi accettando o rifiutando probalisticamente la modifica.

Dopo migliaia di iterazioni ti avvicini a una soluzione accettabile.

Credetemi, tuttavia, che questa classe di problemi ha gruppi di ricerca che sfornano dottorandi, quindi siete in ottima compagnia.

Potresti anche trovare un certo interesse nell'arena della programmazione lineare, ad es. simplex e così via.

Sì, penso che questo sia NP completo - o almeno per trovare la soluzione ottimale è NP completo.

Ho lavorato su un problema simile al college quando ho detto al padre di un amico (che era un insegnante) che avrei potuto risolvere i suoi problemi di programmazione per lui se non avesse trovato un programma adatto per questo (questo era nel 1990 circa )

Non avevo idea di cosa mi fossi preso. Fortunatamente per noi tutto ciò che dovevo fare era trovare una soluzione che corrispondesse ai vincoli. Ma nei miei test ero sempre preoccupato di determinare se esistesse una soluzione. Non ha mai avuto troppi vincoli e il programma ha utilizzato diverse euristiche e back tracking. E 'stato molto divertente.

Penso che Bill Gates abbia anche lavorato su un sistema come questo al liceo o al college per il suo liceo. Non sono sicuro però.

Buona fortuna. Tutti i miei appunti sono spariti e non sono mai riuscito a implementare una soluzione che potevo commercializzare. È stato un progetto speciale che ho ricodificato mentre apprendevo nuove lingue (Basic, Scheme, C, VB, C ++)

Divertiti con esso

Vedo che questo problema può essere risolto dal programma Prolog collegandolo a un database e il programma può rendere il programma dato un insieme di vincoli leggi circa "Soddisfazione dei vincoli Problema prologo"

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow