Algoritmo genético para composição de horários de aula - algoritmo, otimização, genética

Eu estou escrevendo uma aplicação para composição automática de programação universitária e usando para este algoritmo genético. Mas agora eu enfrentei alguns problemas com a realização.

No começo eu assumi que nós temosclasses com duração de 1 time slot (time slot = 1 hora) e podemos simplesmente colocá-lo em array (representa grid schedule: 1-d array com capacidade de numberOfRooms * numberOfDays * numberOfTimeslots) e pode realizar mutação e crossover também sem problemas.

Mas sei que quero melhorar a aplicação e permitir aulas com duração de vários intervalos de tempo. Aqui vem um monte de problemas:

Como podemos colocar um objeto de classe em uma matriz epreenche todos os slots (várias células do array) que classe deve ocupar (um objeto - várias células)? E em conformidade com a forma como vamos colocá-lo na matriz, como a operação de mutação e crossover pode ser executada? Desde já, obrigado! Eu realmente aprecio sua ajuda!

Respostas:

Uma boa regra pode estar atravessando apenas classes que possuem intervalos de tempo iguais. Por exemplo, você pode atravessar uma classe que usa dois espaços de tempo com duas classes que ocupam um intervalo de tempo.

Representar classes com duração de muitos temposslots, a maneira mais simples, mas complicada, é ter um sinalizador que, para cada intervalo de tempo, informará se o intervalo de tempo é ocupado por uma nova classe ou apenas por uma continuação de uma classe iniciada antes. Quando você cruzar, verá a bandeira para se certificar de que não está cruzando partes das classes.

Outro (melhor) caminho é criar uma estrutura de dados mais complexa: DailyRoomOccupation. Essa estrutura de dados conterá:

• a capacidade diária da sala, expressa em número de intervalos de tempo;
• uma lista (dupla ligação) de classes agendadas para esse dia nessa sala;
• uma função que calcula se as classes na lista se encaixam nos intervalos de tempo;
• uma função que permite cruzar dois diferentes DailyRoomOccupations, cuidando de atravessar apenas quantidades iguais de faixas horárias.