Problema da Alocação de Professores

Dada as seguintes tabelas:

- Tabela tipo 1: Curso(disciplina);
- Tabela tipo 2: Disponibilidade_Professor (disciplina, professor);
- Tabela tipo 3: Disponibilidade_Tempo (professor, hora);
- Tabela tipo 4: Disciplina[i]_Professor_Tempo(professor-horario, horario)


Como achar as possíveis soluções para o problema com operações de banco de dados?

Contribuição de Wellington:

----------------

"Esse problema é um problema clássico em computação conhecido como "Problema de Alocação" e tem aplicabilidade em vários

ramos da Economia. Ele não é trivial e acho que é um pouco difícil resolver só com BD. Tradicionalmente, é considerado

NP-difícil e é resolvido de forma aproximada com meta-heurísticas como algoritmos genéticos, busca tabu, recozimento

simulado. Ou, de maneira exata com PLI (programação linear inteira)."

Dá uma olhada nesses caras aqui, por exemplo. São problemas similares:

Nurse Scheduling Problem
Job Shop Scheduling

---------------

Minha solução usando banco de dados MySQL:


disciplinas_curso =

SELECT disciplina FROM Curso;

Da primeira a última disciplina de disciplinas_curso faça:

Disciplina[i]_Professor_Tempo =

SELECT concat(dt.professor,'-', dt.hora) as P_H, dt.hora
FROM Disponibilidade_Tempo dt, Disponibilidade_Professor dp
WHERE dp.professor=dt.professor
AND dp.disciplina = $disciplina_curso;

Vamos supor que o Curso tem 3 disciplinas, para resolver o problema, temos que fazer um produto cartesiano condicional:

Soluções =
SELECT d1.P_H, d2.P_H, d3.P_H
FROM Disciplina[1]_Professor_Tempo d1, Disciplina[2]_Professor_Tempo d2, Disciplina[3]_Professor_Tempo d3
WHERE d1.hora <> d2.hora
AND d1.hora <> d3.hora
AND d2.hora <> d3.hora

A Quantidade de verificações são Qtde_LinhasD1*Qtde_LinhasD2*Qtde_LinhasD3

Uma forma de diminuir o número de verificações é garantir que o produto cartesiano é feito de 2 em 2 tabelas de disciplinas, por exemplo produzir soluções1= Select de D1,D2 e Soluções2= Select de D3, D4. A solução final é

Soluçõesf=Select de Soluções1, Soluções2.

Com isso, a quantidade de verificações são: 2* (Qtde_LD1*QtdeLD2 + Qtde_LD3*QtdeLD4)

Espero que tenham gostado dessas soluções :-)