algoritmo de programação de tempo do professor

Question

Este é um problema que eu tive em minha mente por um longo tempo. Sendo filho de um professor e um programador, ocorreu-me cedo ... mas eu ainda não encontrei uma solução para ele.

Portanto, este é o problema. É necessário criar um calendário para a escola, usando algumas restrições. Estes são geralmente divididos em duas categorias:

sanidade Cheques

• Um professor não pode ensinar duas classes ao mesmo tempo
• Um estudante não pode seguir duas lições ao mesmo tempo
• Alguns professores devem ter pelo menos um dia de folga durante a semana
• Por todos os dias da semana devem ser cobertos pela tabela de tempo
• Assunto X deve ter exatamente assim e assim por horas a cada semana
• ...

Preferências

• lista de cada professor deve ser o mais compacto possível (ou seja, o professor deve trabalhar todas as horas do dia consecutivo sem pausas se possível)
• Os professores que têm dias de folga deve ser capaz de expressar uma preferência em que dia
• Professores que o trabalho a tempo parcial deve ser capaz de expressar uma preferência se ao trabalho no início ou no final do dia de escola.
• ...

Agora, depois de alguns anos de não encontrar uma solução (e aprender uma coisa ou duas, no entretanto ...), eu percebi que isso cheira a um problema NP-hard.

É comprovado como NP-duro?

Alguém tem uma idéia sobre como quebrar essa coisa?

Olhando para esta questão feita -me pensar sobre este problema, e se algoritmos genéticos seria útil neste caso. No entanto, seria muito difícil de possibilidades de mutação, mantendo as regras de verificação de sanidade. Também não está claro para mim como distinguir requisitos incompatíveis.

---

Um pequeno adendo para especificar melhor o problema. Esta é aplicada às salas de aula escola estilo italiano, onde todos os alunos são associados em diferentes classes (por exemplo: ano 1 secção A) e os professores se mover entre as classes. Todos os alunos da mesma classe têm o mesmo cronograma, e não têm escolha sobre as quais lições a participar.

Answer 1

Eu sou um dos que o desenvolvedor que trabalha na parte programador de um sistema de informação do estudante. Durante a nossa abordagem original do problema de programação, que pesquisou algoritmos genéticos para resolver problema da satisfação de restrições, e mesmo que fomos bem sucedidos inicialmente, percebemos que havia uma solução menos complicado para o problema (depois de participar de uma oficina de agendamento escolar)

A nossa implementação atual funciona muito bem, e usa a força bruta com heurísticas inteligentes para obter um horário válido em um curto espaço de tempo. O plano-mestre (atribuição das classes para os professores) é primeiro construído, levando em consideração todas as restrições que cada professor tem, minimizando a possibilidade de conflitos para os alunos (com base de seus pedidos de curso). Os alunos são então programada nas classes usando o mesmo método.

Isso permite que você tenha a máquina de compilação um plano-mestre em primeiro lugar, e depois ter um ajuste humano-lo se necessário.

A implementação atual programador é escrito em perl, mas outras opções que visitamos no início eram Prolog e clipes (sistema especialista)

Answer 2

Este é um problema de mapeamento: você precisa mapear a cada hora em uma semana e cada professor uma atividade (ensinar a uma determinada classe ou hora livre).

Dividir o problema:

1. Criar a lista de professores, aulas e preferências, em seguida, permitir que o usuário preencher algumas das preferências em um mapa para ter como ponto de partida.
2. Aleatoriamente tomar um elemento da lista e colocá-lo em uma posição livre aleatória no mapa se ele não atravessa qualquer verificação de sanidade até que a lista está vazia. Se a qualquer determinada iteração você não pode colocar um elemento no mapa, sem atravessar um cheque turno sanidade duas posições no mapa e tente novamente.
3. Quando o mapa está cheio, tente mudar de posição no mapa para otimizar o resultado.

Em etapas 2 e 3 mostram cada iteração para o usuário:. Itens deixados na lista, posições no mapa e o próximo movimento computadorizada e permitir que o usuário intervir

Eu não tentei isso, mas esta seria a minha abordagem inicial.

Answer 3

Eu já abordou problemas de planejamento / programação similares na técnica AI que muitas vezes é mais adequado para esta classe de problema é "Based Reasoning restrição" passado e.

É basicamente um método de força bruta como LAURENTY sugeriu, mas a abordagem envolve a aplicação de restrições em uma ordem eficiente para fazer com que as soluções inviáveis ??para falhar rapidamente -. Para minimizar o cálculo necessário

Googling "Constraint Based Reasoning" traz uma grande quantidade de recursos sobre a técnica e sua aplicação a problemas de programação.

Answer 4

Respondendo a minha própria pergunta:

O projeto FET mencionado por gnud usa este algoritmo:

Algumas palavras sobre o algoritmo: FET usa um algoritmo heurístico, colocando as atividades, por sua vez, começando com a maioria dos mais difíceis. Se não puder encontrar uma solução que aponta para o potenciais atividades impossíveis, de modo você pode corrigir erros. o algoritmo atividades swaps de forma recursiva, se isso É possível, a fim de abrir espaço para uma nova atividade, ou, em casos extremos, Backtracks e interruptores de ordem avaliação. O código importante é em src / motor / generate.cpp. Por favor enviar e-mail me para mais informações ou participar do mailing Lista. O algoritmo imita os operação de um TimeTabler humano, eu pensa.

Fazer a ligação

---

Na sequência do chumbo "Constraint Based Reasoning" por rigorosos Software na Wikipedia me levar a estes páginas que têm um ponto interessante:

Resolver uma satisfação restrição problema em um domínio finito é um problema NP-completos em geral. A pesquisa mostrou um número de subcasos de tempo polinomial, principalmente obtido através da restrição, quer o domínios ou constrangimentos permitidos ou o constrangimentos maneira pode ser colocado sobre o variáveis. A pesquisa tem também relação estabelecida do problema de satisfação de restrições com problemas em outras áreas, tais como finita teoria e bancos de dados modelo.

Answer 5

Isso me faz lembrar este blog sobre o agendamento de uma conferência, com um explicação vídeo aqui .

Como eu faria isso:

Tenha a população incluem duas coisas:

• Quem ensina que classe (I esperar que os professores para ensinar um assunto).
• Que uma classe assume um horário específico.

Desta forma, não podemos ter conflitos (um professor em 2 lugares, ou uma classe ter dois assuntos ao mesmo tempo).

A função de fitness que incluem:

• Quantos slots de tempo de cada professor dá por semana.
• Quantos slots vez que um professor tem no mesmo dia (Eles podem não ter um dia cheio de ensino, isso também deve ser equilibrada).
• Quantos slots do mesmo assunto vez que uma classe tem no mesmo dia (Eles podem não ter um dia cheio de matemática!).

Talvez tomar o desvio padrão para todos eles, uma vez que deve ser equilibrado.

Answer 6

Eu não tenho certeza se este cobre o mesmo terreno como do @Stringent Software resposta (como o nome é um pouco diferente), mas eu tenho um par de muito bons amigos que estão pesquisando a área de restrição de Programação . Criando horários é uma aplicação de suas pesquisas.

Dr Chris Jefferson criou um programa chamado Minion que você pode baixar a partir de SourceForge, e é um problema muito rápido força bruta restrição solver escrito em C ++

Answer 7

Eu acho que você pode estar faltando algumas restrições.

Um preferiria sempre que possível ter professores programados para as classes para as quais são certificadas.

Um suspeito que as classes que são solicitadas, e o número de funcionários esperado em cada seria significativo.

Eu acho que o lugar para começar seria listar todas as suas limitações, descobrir uma estrutura de dados para representá-los.

Em seguida, criar algum tipo de motor para que construa uma solução de teste, em seguida, avalia-lo para a aptidão de acordo com as restrições.

Você pode então jogar a parte divertida algoritmos genéticos para ele, e veja se você pode obter a aptidão para aumentar ao longo do tempo como os genes se misturam.

Comece com um pequeno conjunto de restrições, e aumentá-los como você vê o sucesso (se você ver o sucesso)

Pode haver uma maneira de levar as restrições e calçadeira-los juntamente com algo como um algoritmo de programação linear.

Eu concordo. Soa como um desafio divertido

Answer 8

Um dos piores código aberto páginas da web que nunca, mas os olhares projeto promissor: http://www.lalescu.ro/liviu/fet/

aproach web-based A:
phpScheduleIt (não escolar específico-)

Answer 9

Olhando para esta pergunta me fez pensar sobre este problema, e se algoritmos genéticos seria utilizável em este caso. No entanto, seria muito difícil de possibilidades de mutação enquanto mantendo as regras de verificação de sanidade. Também não está claro para mim como distinguir requisitos incompatíveis.

Algoritmos Genéticos são muito bem adaptado a problemas como este. Uma vez que você venha com uma representação decente do cromossomo (neste caso, provavelmente um vetor representando todos os slots de classe disponíveis) Você é a maior parte do caminho até lá.

Não se preocupe com a manutenção de checagens durante a fase de mutação. A mutação é aleatória. checagens e de preferência ambos pertencem na fase de selecção. A verificação de sanidade falhou iria diminuir drasticamente a aptidão de um indivíduo, enquanto uma preferência não seria apenas levemente menor de fitness.

requisitos incompatíveis são um problema completamente diferente. Se eles são completamente incompatíveis, você terá uma população que não convergem para algo útil.

Answer 10

Boa sorte. Sendo filho de um pai com este tipo de problema é o que me levou para o grupo de pesquisa que acabei em ...

---

Quando eu era criança, meu pai programada árbitros em uma liga esportiva local, isso teve um semelhante longa lista de restrições e eu tentei escrever alguma coisa para ajudar. Quando cheguei à Universidade Eu até usei-o como meu projeto final do ano, eventualmente, de se estabelecer em uma implementação de Monte Carlo (usando um modelo de Simulated Annealing).

A idéia básica é que, se não é NP, é muito perto, tão ao invés de assumir que há uma solução, eu expor para encontrar o melhor dentro de um determinado prazo. Eu peso todas as restrições com custos para quebrá-los: checagens teria custos enormes, as preferências teria custos mais baixos (mas aumentando para mais pausas, então quebrá-lo uma vez seria menos de metade do custo de quebrá-lo duas vezes).

A idéia básica é que eu comecei com uma solução 'aleatória' e custou-lo; Em seguida, fez alterações trocando um pequeno número de atribuições, re-valorizado e depois, probalistically aceita ou recusada a mudança.

Depois de milhares de iterações você polegada mais perto de uma solução aceitável.

Acredite-me, porém, que esta classe de problemas tem grupos de pesquisa produzindo PhDs então você está em muito boa companhia.

Você também pode encontrar algum interesse na arena programação linear, por exemplo, simplex e assim por diante.

Answer 11

Sim, eu acho que isso é NP completa - ou, pelo menos, para encontrar a solução ideal é NP completa.

Eu trabalhei em um problema semelhante na faculdade quando eu disse o pai de um amigo (que era um professor) que eu poderia resolver seus problemas de agendamento para ele se ele não encontrar um programa adequado para ele (isso foi em 1990 ou assim )

Eu não tinha idéia do que eu me meti. Felizmente para nós tudo o que eu tinha a fazer era encontrar uma solução que se encaixam as restrições. Mas no meu teste eu estava sempre preocupado sobre como determinar se havia uma solução. Ele nunca teve muitas limitações e o programa usado diferentes heurísticas e rastreamento de volta. Foi muito divertido.

Eu acho que Bill Gates também trabalhou em um sistema como este na escola ou faculdade para sua escola. Não tenho certeza embora.

Boa sorte. Todas as minhas notas sumiram e eu nunca cheguei a implementação de uma solução que eu poderia mercado. Foi um projeto especialidade que eu re-codificado como eu aprendi novas línguas (básicas, do esquema C, VB, C ++)

se divertir com ele

Answer 12

i ver que este problema pode ser resolvido pelo programa Prolog conectando-o a um banco de dados eo programa pode fazer a programação dado um conjunto de restrições leia abt "satisfação Restrição Problema prólogo"