Algoritmo para criação de horário escolar
https://stackoverflow.com/questions/2177836
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Fiquei me perguntando se existem soluções conhecidas para algoritmos de criação de horários escolares.Basicamente, trata-se de otimizar a "dispersão de horas" (tanto no caso de professores quanto de aulas) para determinadas associações turma-disciplina-professor.Podemos supor que temos conjuntos de aulas, disciplinas e professores associados entre si na entrada e que o horário deve caber entre 8h e 16h.
Acho que provavelmente não existe um algoritmo preciso para isso, mas talvez alguém conheça uma boa aproximação ou dicas para desenvolvê-lo.
Solução
Este problema é NP-Completo!
Em poucas palavras, é necessário explorar todas as combinações possíveis para encontrar a lista de soluções aceitáveis.Devido às variações nas circunstâncias em que o problema surge nas diversas escolas (por exemplo:Existem restrições em relação às salas de aula?, Algumas turmas são divididas em subgrupos algumas vezes?, Este é um horário semanal?etc.) não existe uma classe de problema bem conhecida que corresponda a todos os problemas de escalonamento.Talvez o Problema de mochila tem muitos elementos de semelhança com esses problemas em geral.
Uma confirmação de que este é um problema difícil e para o qual as pessoas buscam perenemente uma solução é verificar isso (longo) lista de ferramentas de agendamento de software (principalmente comerciais)
Devido ao grande número de variáveis envolvidas, cuja maior fonte são, normalmente, os desejos do docente ;-)..., normalmente é impraticável considerar enumerar todas as combinações possíveis.Em vez disso, precisamos escolher uma abordagem que visite um subconjunto dos espaços problema/solução.
- Algorítmos genéticos, citado em outra resposta é (ou, IMHO, parece) bem equipado para realizar este tipo de busca semiguiada (o problema é encontrar uma boa função de avaliação para os candidatos a serem mantidos para a próxima geração)
- Reescrita de gráfico abordagens também são úteis com este tipo de problemas de otimização combinatória.
Em vez de focar em implementações específicas de um programa gerador automático de cronograma, gostaria de sugerir algumas estratégias que podem ser aplicadas, ao nível da definição do problema.
A lógica geral é que na maioria dos problemas de escalonamento do mundo real, serão necessários alguns compromissos, e não todas as restrições, expressas e implícitas:ficará totalmente satisfeito.Portanto, nós nos ajudamos:
- Definir e classificar todas as restrições conhecidas
- Reduzir o espaço do problema, fornecendo manualmente um conjunto de adicional restrições.
Isto pode parecer contra-intuitivo, mas, por exemplo, ao fornecer um calendário inicial parcialmente preenchido (digamos, cerca de 30% dos intervalos de tempo), de uma forma que satisfaça totalmente todas as restrições, e ao considerar este calendário parcial imutável, reduzimos significativamente o tempo/espaço necessário para produzir soluções candidatas.
Outra forma de as restrições adicionais ajudarem é, por exemplo, adicionar "artificialmente" uma restrição que impeça o ensino de algumas disciplinas em alguns dias da semana (se este for um horário semanal...);este tipo de restrições resulta na redução dos espaços problema/solução, sem, tipicamente, excluir um número significativo de bons candidatos. - Garantir que algumas das restrições do problema possam ser calculadas rapidamente.Isto está frequentemente associado à escolha do modelo de dados utilizado para representar o problema;a ideia é poder optar (ou eliminar) rapidamente algumas das opções.
- Redefinir o problema e permitir que algumas das restrições sejam quebradas, algumas vezes, (normalmente nos nós finais do gráfico).A ideia aqui é remover alguns de restrições para preencher os últimos espaços no cronograma, ou fazer com que o programa gerador automático de cronograma pare de completar todo o cronograma, fornecendo-nos, em vez disso, uma lista de cerca de uma dúzia de candidatos plausíveis.Um ser humano está muitas vezes em melhor posição para completar o quebra-cabeça, conforme indicado, possivelmente quebrando algumas das restrições, usando informações que normalmente não são compartilhadas com a lógica automatizada (por exemplo, a regra "Não há matemática à tarde" pode ser quebrada ocasionalmente para a aula de “matemática e física avançadas”;ou "É melhor quebrar um dos requisitos do Sr. Jones do que um dos requisitos da Sra. Smith...;-))
Ao revisar esta resposta, percebo que é bastante tímido em fornecer uma resposta definitiva, mas mesmo assim é cheia de sugestões práticas.Espero que isto ajude, com o que é, afinal, um "problema difícil".
Outras dicas
É uma bagunça.uma bagunça real.Para complementar as respostas, já muito completas, quero destacar minha experiência familiar.Minha mãe era professora e participava do processo.
Acontece que ter um computador para fazer isso não é apenas difícil de codificar em si, mas também porque há condições que são difíceis de especificar para um programa de computador pré-preparado.Exemplos:
- um professor ensina na sua escola e em outro instituto.É claro que se ele terminar a aula lá às 10h30, não poderá começar nas suas instalações às 10h30, porque precisa de algum tempo para se deslocar entre os institutos.
- dois professores são casados.Em geral, é considerada uma boa prática não ter dois professores casados na mesma turma.Esses dois professores devem, portanto, ter duas turmas diferentes
- dois professores são casados e seus filhos frequentam a mesma escola.Novamente, você tem que evitar que os dois professores dêem aula na turma específica onde seu filho está.
- a escola tem instalações separadas, como se um dia a aula fosse em um instituto e outro dia a aula fosse em outro.
- a escola tem laboratórios partilhados, mas estes laboratórios estão disponíveis apenas em determinados dias da semana (por razões de segurança, por exemplo, quando é necessário pessoal adicional).
- alguns professores têm preferências pelo dia livre:alguns preferem na segunda-feira, alguns na sexta-feira, alguns na quarta-feira.Alguns preferem vir de manhã cedo, outros preferem vir mais tarde.
- você não deveria ter situações em que tenha uma aula, digamos, de história na primeira hora, depois três horas de matemática e depois mais uma hora de história.Não faz sentido para os alunos, nem para o professor.
- você deve espalhar os argumentos uniformemente.Não faz sentido ter os primeiros dias da semana apenas matemática e depois o resto da semana apenas literatura.
- você deve dar a alguns professores duas horas consecutivas para fazer testes de avaliação.
Como você pode ver, o problema não é NP-completo, é NP-insano.
Então o que eles fazem é ter uma mesa grande com pequenas inserções de plástico e mover as inserções até obter um resultado satisfatório.Eles nunca começam do zero:normalmente partem do calendário do ano anterior e fazem ajustes.
o Concurso Internacional de Timetable 2007 Tive uma faixa de agendamento de lições e pista de agendamento de exames. Muitos pesquisadores participaram dessa competição. Muitas heurísticas e metaheurísticas foram tentadas, mas no final as metaheurísticas de pesquisa local (como a pesquisa de tabu e o recozimento simulado) derrotam claramente outros algoritmos (como algoritmos genéticos).
Dê uma olhada nas duas estruturas de código aberto usadas por alguns dos finalistas:
- Jboss OptAplanner (Java, código aberto)
- Unitime (Java, código aberto) - Mais para universidades
Uma das minhas tarefas de meio período foi uma geração de mesa escolar genética-algoritmo.
Tabela inteira é um "organismo". Houve algumas mudanças e advertências na abordagem genética genética de algoritmos:
Foram feitas regras para "tabelas ilegais": duas aulas na mesma sala de aula, um professor ensinando dois grupos ao mesmo tempo etc. Essas mutações foram consideradas letais imediatamente e um novo "organismo" foi brotado no lugar do "falecido" imediatamente. O inicial foi gerado por uma série de tentativas aleatórias para obter uma (se sem sentido). A mutação letal não foi contada para a contagem de mutações na iteração.
Mutações "trocas" foram muito mais comuns do que as mutações "modificar". As mudanças foram apenas entre partes do gene que faziam sentido - sem substituir um professor por uma sala de aula.
Pequenos bônus foram designados para agrupar certas 2 horas, por atribuir a mesma sala de aula genérica em sequência para o mesmo grupo, para manter o horário de trabalho do professor e a carga da aula contínua. Os bônus moderados foram atribuídos por fornecer salas de aula corretas para determinado assunto, mantendo o horário de aula dentro dos títulos (manhã ou tarde) e tal. Grandes bônus foram para atribuir um número correto de determinado assunto, dada a carga de trabalho para um professor etc.
Os professores podem criar seus horários de carga de trabalho de "Want to Work, então", "Ok para trabalhar então", "não gosta de trabalhar então", "não pode funcionar então", com pesos adequados atribuídos. 24 horas inteiras eram horas legais de trabalho, exceto que a noite era muito indesejada.
A função de peso ... ah sim. A função de peso era enorme e monstruoso produto (como na multiplicação) de pesos atribuídos a recursos e propriedades selecionados. Era extremamente íngreme, uma propriedade facilmente capaz de alterá -la por uma ordem de magnitude para cima ou para baixo - e havia centenas ou milhares de propriedades em um organismo. Isso resultou em números absolutamente enormes como pesos e, como resultado direto, precisam usar uma biblioteca Bignum (GMP) para executar os cálculos. Para um pequeno teste de cerca de 10 grupos, 10 professores e 10 salas de aula, o conjunto inicial começou com a nota de 10^-200Soming e terminou com 10^+300Soming Alling. Era totalmente ineficiente quando era mais plano. Além disso, os valores cresceram uma distância muito maior, com "escolas" maiores.
Tempo de computação Em termos de computação, houve pouca diferença entre uma pequena população (100) por um longo tempo e uma grande população (10k+) por menos gerações. A computação ao mesmo tempo produziu a mesma qualidade.
O cálculo (em cerca de 1 GHz de CPU) levaria cerca de 1H para se estabilizar perto de 10^+300, gerando horários que pareciam bastante agradáveis, para o referido caso de teste de 10x10x10.
O problema é facilmente paralelizável, fornecendo instalações de rede que trocariam melhores espécimes entre computadores que executam o cálculo.
O programa resultante nunca viu a luz do dia do lado de fora, conseguindo uma boa nota para o semestre. Ele mostrou alguma promessa, mas nunca recebi motivação suficiente para adicionar qualquer GUI e torná -lo utilizável ao público em geral.
Esse problema é mais difícil do que parece.
Como outros mencionaram, esse é um problema prematuro de NP, mas vamos analisar o que isso significa.
Basicamente, isso significa que você precisa examinar todas as combinações possíveis.
Mas "OLHAR" não diz muito o que você precisa fazer.
É fácil gerar todas as combinações possíveis. Isso pode produzir uma enorme quantidade de dados, mas você não deve ter muitos problemas para entender os conceitos dessa parte do problema.
O segundo problema é o de julgar se uma determinada combinação possível é boa, ruim ou melhor que a solução "boa" anterior.
Para isso, você precisa de mais do que apenas "é uma solução possível".
Por exemplo, o mesmo professor que trabalha 5 dias por semana para x semanas seguidas? Mesmo que seja uma solução de trabalho, pode não ser uma solução melhor do que alternar entre duas pessoas, para que cada professor faça uma semana cada. Oh, você não pensou nisso? Lembre -se, são as pessoas com as quais você está lidando, não apenas um problema de alocação de recursos.
Mesmo que um professor possa trabalhar em período integral por 16 semanas seguidas, essa pode ser uma solução subótima em comparação com uma solução em que você tenta alternar entre professores, e esse tipo de equilíbrio é muito difícil de construir em software.
Para resumir, a produção de uma boa solução para esse problema valerá muito a muitas pessoas. Portanto, não é um problema fácil de quebrar e resolver. Esteja preparado para realizar alguns objetivos que não são 100% e chamá -los de "bons o suficiente".
ATUALIZAÇÃO: A partir de comentários ... deve ter heurística também!
Eu iria com o Prolog ... depois usaria Ruby ou Perl ou algo para limpar sua solução em uma forma mais bonita.
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].
Estou (ainda) no processo de fazer algo semelhante a esse problema, mas usando o mesmo caminho que acabei de mencionar. O Prolog (como linguagem funcional) realmente facilita a solução de problemas de NP.
Algoritmos genéticos são frequentemente usados para tal agendamento.
Encontrado este exemplo (Fazendo cronograma de aula usando algoritmo genético) o que corresponde muito bem às suas necessidades.
Aqui estão alguns links que encontrei:
Horário escolar - lista alguns problemas envolvidos
Meu algoritmo de tabela de horários, implementado em FET (Free Timetabling Software, http://lalescu.ro/liviu/fet/ , uma aplicação bem sucedida):
O algoritmo é heurístico.Eu chamei isso de "troca recursiva".
Entrada:um conjunto de atividades A_1...A_n e as restrições.
Saída:um conjunto de horários TA_1...TA_n (o intervalo de tempo de cada atividade.Os quartos estão excluídos aqui, por simplicidade).O algoritmo deve colocar cada atividade em um intervalo de tempo, respeitando as restrições.Cada TA_i está entre 0 (T_1) e max_time_slots-1 (T_m).
Restrições:
C1) Básico:uma lista de pares de atividades que não podem ser simultâneas (por exemplo, A_1 e A_2, porque têm o mesmo professor ou os mesmos alunos);
C2) Muitas outras restrições (excluídas aqui, por simplicidade).
O algoritmo de tabela de horários (que chamei de "troca recursiva"):
- Classifique as atividades, começando pelas mais difíceis.Não é uma etapa crítica, mas acelera o algoritmo talvez 10 vezes ou mais.
Procure colocar cada atividade (A_i) em um horário permitido, seguindo a ordem acima, uma de cada vez.Procure um slot disponível (T_j) para A_i, no qual esta atividade possa ser colocada respeitando as restrições.Se houver mais slots disponíveis, escolha um aleatório.Se nenhum estiver disponível, faça troca recursiva:
a.Para cada intervalo de tempo T_j, considere o que acontece se você colocar A_i em T_j.Haverá uma lista de outras atividades que não concordam com esta mudança (por exemplo, a atividade A_k está na mesma vaga T_j e tem o mesmo professor ou os mesmos alunos que A_i).Mantenha uma lista de atividades conflitantes para cada intervalo de tempo T_j.
b.Escolha um slot (T_j) com menor número de atividades conflitantes.Digamos que a lista de atividades neste slot contenha 3 atividades:A_p, A_q, A_r.
c.Coloque A_i em T_j e torne A_p, A_q, A_r não alocados.
d.Tente recursivamente colocar A_p, A_q, A_r (se o nível de recursão não for muito grande, digamos 14, e se o número total de chamadas recursivas contadas desde a etapa 2) em A_i começou não for muito grande, digamos 2*n), como na etapa 2).
e.Se A_p, A_q, A_r forem colocados com sucesso, retorne com sucesso, caso contrário tente outros intervalos de tempo (vá para o passo 2 b) e escolha o próximo melhor intervalo de tempo).
f.Se todos (ou um número razoável de) intervalos de tempo foram tentados sem sucesso, retorne sem sucesso.
g.Se estamos no nível 0 e não tivemos sucesso na colocação de A_i, coloque-o como nos passos 2 b) e 2 c), mas sem recursão.Temos agora mais 3 - 1 = 2 atividades para realizar.Vá para a etapa 2) (alguns métodos para evitar ciclismo são usados aqui).
Eu projetei algoritmos comerciais para o cronograma de classes e o cronograma de exames. Pelo primeiro, usei programação inteira; Para o segundo, uma heurística com base na maximização de uma função objetiva escolhendo swaps de slot, muito semelhante ao processo manual original que foi evoluído. Eles principais para obter essas soluções aceitas são a capacidade de representar todas as restrições do mundo real; e para que os horários humanos não possam ver maneiras de melhorar a solução. No final, a parte algorítmica foi bastante direta e fácil de implementar em comparação com a preparação dos bancos de dados, a interface do usuário, a capacidade de relatar estatísticas como utilização de salas, educação do usuário e assim por diante.
Este artigo descreve o problema do cronograma da escola e sua abordagem ao algoritmo muito bem: "O desenvolvimento do plano de estudos-um agendador interativo e baseado em restrições para escolas e faculdades.[PDF
O autor me informa que o software do plano de estudos ainda está sendo usado/desenvolvido aqui: http://www.scientia.com/uk/
Eu trabalho em um mecanismo de agendamento amplamente utilizado que faz exatamente isso.Sim, é NP-Completo;as melhores abordagens procuram aproximar uma solução ótima.E, claro, existem muitas maneiras diferentes de dizer qual é a “melhor” solução – é mais importante que os seus professores estejam satisfeitos com os seus horários, ou que os alunos participem em todas as aulas, por exemplo?
A questão mais importante que você precisa resolver desde o início é o que torna uma forma de programar este sistema melhor que outra?Ou seja, se eu tenho um horário com a Sra. Jones ensinando Matemática às 8 e o Sr. Smith ensinando Matemática às 9, isso é melhor ou pior do que um com ambos ensinando Matemática às 10?É melhor ou pior do que aquele com a Sra. Jones ensinando aos 8 anos e o Sr. Jones ensinando aos 2?Por que?
O principal conselho que daria aqui é dividir o problema tanto quanto possível - talvez curso por curso, talvez professor por professor, talvez sala por sala - e trabalhar primeiro na resolução do subproblema.Lá você deve ter várias soluções para escolher e escolher uma como a ideal mais provável.Em seguida, trabalhe para fazer com que os subproblemas “anteriores” levem em consideração as necessidades dos subproblemas posteriores na pontuação de suas soluções potenciais.Então, talvez trabalhe em como sair de situações complicadas (supondo que você não possa antecipar essas situações em subproblemas anteriores) quando chegar a um estado de "sem soluções válidas".
Uma passagem de otimização de pesquisa local costuma ser usada para "polir" a resposta final para obter melhores resultados.
Observe que normalmente estamos lidando com sistemas com recursos altamente limitados na programação escolar.As escolas não passam o ano com muitas salas vazias ou professores sentados na sala 75% do dia.As abordagens que funcionam melhor em ambientes ricos em soluções não são necessariamente aplicáveis na programação escolar.
Geralmente, a programação de restrições é uma boa abordagem para esse tipo de problema de agendamento. Uma pesquisa sobre "programação de restrições" e agendamento ou "agendamento baseado em restrições", tanto no Stack Overflow quanto no Google, gerará algumas boas referências. Não é impossível - é apenas um pouco difícil de pensar ao usar métodos de otimização tradicionais, como otimização linear ou inteira. Uma saída seria - existe um cronograma que atende a todos os requisitos? Isso, por si só, é obviamente útil.
Boa sorte !
Você pode levá -lo com algoritmos genéticos, sim. Mas você não deveria :). Pode ser muito lento e o ajuste dos parâmetros pode ser muito seguinte, etc.
Existem outras abordagens de sucesso. Todos implementados em projetos de código aberto:
- Abordagem baseada em restrições
- Implementado em Unitime (não é realmente para escolas)
- Você também pode ir além e usar programação inteira. Com sucesso em Universidade de Udine E também na University Bayreuth (eu estava envolvido lá) usando o software comercial (ILOG CPLEX)
- Abordagem baseada em regras com heuristisc - ver Drools Planner
- Heurísticas diferentes - FET e meu próprio
Veja aqui para um Lista de software de cronograma
Eu acho que você deveria usar o algoritmo genético porque:
- É mais adequado para grandes instâncias de problemas.
- Ele produz redução da complexidade do tempo no preço da resposta imprecisa (não o melhor melhor)
- Você pode especificar restrições e preferências facilmente ajustando as punições de fitness para não atendem.
- Você pode especificar o limite de tempo para a execução do programa.
A qualidade da solução depende de quanto tempo você pretende gastar resolvendo o programa.
Definição de algoritmos genéticos
Dê uma olhada também:uma pergunta semelhante e outro
Não sei que ninguém concordará com este código, mas desenvolvi esse código com a ajuda do meu próprio algoritmo e está trabalhando para mim em Ruby. Espero que os ajudarão a eles que estão procurando no código a seguir, o período do período, DayFlag Assunto Flag e o Professorflag são o hash com o ID correspondente e o valor do sinalizador que é booleano. Qualquer problema entre em contato comigo ....... (-_-)
periodflag.ach 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
