Come fare una tabella di marcia

Si devono esplorare tutte le combinazioni possibili per trovare la lista delle soluzioni
accettabili. A causa delle variazioni delle circostanze in cui il problema si presenta nelle varie scuole (per esempio: Ci sono
costrizioni per quanto riguarda le aule? O alcune classi sono divise
in sottogruppi per una parte del tempo? Si tratta di un orario settimanale? ecc.) Non c'è una classe di problemi ben nota che corrisponda a tutti i problemi di programmazione. Forse, il problema Knapsack ha molti elementi di somiglianza con questi problemi in generale.

Una conferma che questo è sia un problema difficile che uno per il quale la gente cerca perennemente una soluzione, è controllare questa (lunga) lista di strumenti di programmazione software (per lo più commerciali).

A causa del gran numero di variabili coinvolte, la più grande fonte
di cui sono, tipicamente, i desideri del membro della facoltà, è
tipicamente poco pratico considerare di enumerare tutte le possibili combinazioni. Abbiamo invece bisogno di scegliere un approccio che visiti un sottoinsieme degli spazi problema/soluzione.

- Gli algoritmi genetici, citati in un'altra risposta, sono ben attrezzati per eseguire questo tipo di ricerca semi-guidata (il problema è trovare una buona funzione di valutazione per i candidati da tenere per la prossima generazione).

- Gli approcci di riscrittura dei grafici sono anche utili con questo tipo di problemi di ottimizzazione combinatoria.

Piuttosto che concentrarsi su particolari implementazioni di un programma generatore di schedulazione 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 schedulazione del mondo reale,
saranno necessari alcuni compromessi, non tutti i vincoli, espressi e
impliciti: saranno soddisfatti pienamente. Quindi ci aiutiamo:

• Definendo e classificando tutti i vincoli conosciuti
• Riducendo lo spazio del problema, fornendo manualmente un insieme di vincoli aggiuntivi.
• Assicurando che alcuni dei vincoli del problema possano essere rapidamente
  computati. Questo è spesso associato alla scelta del modello di dati usato
  per rappresentare il problema; l'idea è di essere in grado di optare rapidamente per (o
  pruntare) alcune delle opzioni.
• Rifinendo il problema e permettendo che alcuni dei vincoli siano
  rotti, alcune volte, (tipicamente verso i nodi finali del grafico).
  L'idea qui è di rimuovere alcuni dei vincoli per
  riempire gli ultimi slot del programma, o di avere il programma automatico di generazione di
  programmi che si ferma prima di completare l'intero programma,
  invece ci fornisce una lista di una dozzina di candidati plausibili.
  Un umano è spesso in una posizione migliore per completare il puzzle, come
  indicato, possibilmente rompendo alcuni dei vincoli, usando informazioni
  che non sono tipicamente condivise con la logica automatica.
  

Fonte: Ansver da Algoritmo per la creazione di un orario scolastico con un paio di correzioni grammaticali.