Resolução de conflitos de nomeação automática

5

Estou tentando descobrir um algoritmo para resolver os horários dos compromissos.

Atualmente, tenho um algoritmo ingênuo que reduz repetidamente os compromissos conflitantes, até que não haja mais compromissos.

# The appointment list is always sorted on start time
appointment_list = [
   <Appointment: 10:00 -> 12:00>,
   <Appointment: 11:00 -> 12:30>,
   <Appointment: 13:00 -> 14:00>,
   <Appointment: 13:30 -> 14:30>,
]

Restrições são os compromissos:

  • não pode ser depois das 15:00
  • não pode ser antes das 9:00

Este é o algoritmo ingênuo

for i, app in enumerate(appointment_list):
    for possible_conflict in appointment_list[i+1:]:
        if possible_conflict.start < app.end:
           difference = app.end - possible_conflict.start
           possible_conflict.end   += difference
           possible_conflict.start += difference
        else:
           break

Isso resulta na resolução a seguir, que obviamente quebra essas restrições, e o último compromisso terá que ser enviado para o dia seguinte.

appointment_list = [
   <Appointment: 10:00 -> 12:00>,
   <Appointment: 12:00 -> 13:30>,
   <Appointment: 13:30 -> 14:30>,
   <Appointment: 14:30 -> 15:30>,
]

Obviamente, isso é insatisfatório. Executa 3 movimentos de nomeação quando o conflito pode ter sido resolvido com um: se formos capazes de empurrar o primeiro compromisso para trás, poderemos evitar o deslocamento de todos os compromissos subseqüentes.

Estou pensando que deveria haver um tipo de abordagem de edição-distância que calcularia o menor número de compromissos que deveriam ser movidos para resolver o conflito de agendamento , mas não posso obter o controle sobre a metodologia. Deve ser a primeira pesquisa em profundidade ou a primeira solução em profundidade. Quando sei se a solução é "boa o suficiente"?

    
por Thomas 31.10.2013 / 06:33
fonte

2 respostas

1

Este é um problema clássico a ser resolvido com um algoritmo de programação, muitos trabalhos de PHd e de pesquisa foram escritos sobre esse tipo de problema. Portanto, é impossível fornecer uma resposta curta e uma resposta longa custaria dias do meu tempo.

Em primeiro lugar, verifique quantas opções possíveis de compromissos você tem, se isso for razoável baixo, você pode usar o rastreamento de volta para olhar todas as opções e escolher o melhor. Caso contrário, espere passar semanas lendo sobre a pesquisa, a menos que você tenha sorte. Comece lendo sobre Satisfação da restrição

Leva apenas uma pequena limitação como "as nomeações não são movidas para dias diferentes" para alterar um problema muito difícil, em algo que você pode resolver, observando todos os resultados possíveis. Portanto, como você define seu problema é muito importante.

Veja o " Algoritmo para criar um horário escolar " pergunta para os lotes do ponteiro, também dê uma olhada no optaplanner , pois ele é de código aberto e pode ser configurado para resolver a maioria dos problemas de satisfação com restrições.

    
por 13.04.2016 / 14:30
fonte
0

Não tenho certeza se entendi seu problema (se é que foi) e / ou o tipo de solução desejado, mas ...

Eu começaria classificando e reatribuindo o tamanho do compromisso, em vez do horário de início.

Por exemplo, vamos considerar outro cenário "ainda pior" de sobreposição;

O mesmo que no seu exemplo, mas para o último compromisso, faremos 2 horas em vez disso:

Appointment #1: 10:00 -> 12:00 (2 hour-long)
Appointment #2: 11:00 -> 12:30 (1.5 hour-long)
Appointment #3: 13:00 -> 14:00 (1 hour-long)
Appointment #4: 13:30 -> 15:30 (2 hour-long)

Primeiramente, vamos redesignar nos comprimentos (decrescentes), em vez dos tempos de início:

Appointment #1: 10:00 -> 12:00 (2 hour-long)
Appointment #2: 13:30 -> 15:30 (2 hour-long)
Appointment #3: 11:00 -> 12:30 (1.5 hour-long)
Appointment #4: 13:00 -> 14:00 (1 hour-long)

Em seguida, vamos voltar às restrições (onde o maior período de tempo permitido é das 9:00 às 15:00, de qualquer forma).

Já sabemos que não poderemos ajustar 6,5 horas de compromissos em apenas 6 horas no total.

Então, podemos "descartar" (ou seja, passar para o dia seguinte) o compromisso # 4.

Ficamos com:

Appointment #1: 10:00 -> 12:00 (2 hour-long)
Appointment #2: 13:30 -> 15:30 (2 hour-long)
Appointment #3: 11:00 -> 12:30 (1.5 hour-long)

Então, finalmente, podemos reprogramar colocando o primeiro compromisso no início desse período de tempo e enfileirando os outros (com ou sem lacunas, contanto que não passemos das 15:00) ...

Appointment #1: 10:00 -> 12:00 (2 hour-long) => move to 9:00 -> 11:00
Appointment #2: 13:30 -> 15:30 (2 hour-long) => move after appointment #1
Appointment #3: 11:00 -> 12:30 (1.5 hour-long) => move after appointment #2

Para terminar:

Appointment #1: 9:00 -> 11:00
Appointment #2: 11:00 -> 13:00
Appointment #3: 13:00 -> 14:30

ou, porque não,

Appointment #1: 9:00 -> 11:00
Appointment #2: 11:00 -> 13:00
Appointment #3: 13:30 -> 15:00

'HTH,

    
por 12.04.2016 / 21:17
fonte

Tags