Algoritmo para atribuir pessoas a intervalos de tempo com base na preferência

5

Estou tentando descobrir se existe atualmente um algoritmo para realizar o que estou tentando realizar.

Eu tenho uma série de intervalos de tempo ao longo de uma semana onde desejo atribuir um número aproximadamente igual de pessoas a cada período de tempo durante a semana. Ao contrário da esta questão , os intervalos de tempo são fornecidos como apenas intervalos de horas, e os membros da população só precisam de ser pombo encurralado de maneira igualmente distribuída.

A maioria da população forneceu uma primeira, segunda e terceira opção para o horário desejado. As pessoas que listam um intervalo de tempo como múltiplas preferências são consideradas preenchidas incorretamente e a preferência será considerada apenas uma vez e as preferências restantes serão consideradas sem preferência.

Além disso, parte da população pode não responder ou dizer que não tem preferência. Eles ainda precisam ser atribuídos a um intervalo de tempo, mas podem ser atribuídos a qualquer intervalo de tempo necessário para satisfazer o algoritmo.

No entanto, os intervalos de tempo propriamente ditos não têm preferência sobre quem vai para onde, a não ser que eles querem que as pessoas sejam distribuídas uniformemente, significando que este não é apenas um caso do problema do casamento estável / residente no hospital. Além disso, difere do problema do casamento estável em que os membros da população não têm preferência por cada intervalo de tempo, o que parece ser necessário para que o algoritmo funcione.

O objetivo do algoritmo é o seguinte (em ordem de importância):

  1. Certifique-se de que todos estejam atribuídos a um horário.
  2. Assegure-se de que todos que fornecem uma 1ª, 2ª e 3ª escolha separadas sejam atribuídos a pelo menos um deles.
  3. Distribua a população para que eles sejam aproximadamente iguais entre os horários.
  4. Se isso tornasse a população mais uniformemente distribuída, eliminaria os horários, tirando as pessoas deles.
  5. Maximize o número de pessoas que têm a primeira opção.
  6. Maximize o número de pessoas que recebem sua segunda opção.
  7. Maximize o número de pessoas que conseguem sua terceira opção.
  8. Minimize os recursos e o tempo de execução necessários para o algoritmo.

Em minha pesquisa, também descobri que o problema do casamento estável pode ter resultados diferentes dependendo de qual lado está em primeiro lugar em suas propostas. Espero que o estado inicial não afete o resultado do algoritmo, mas, se necessário, posso simplesmente executá-lo várias vezes e obter o melhor resultado. Eu também gostaria de evitar atribuir constantes arbitrárias às preferências, a menos que seja absolutamente necessário.

Este é um problema bastante complexo, então não estou esperando obter um algoritmo completo daqui a menos que já exista um para resolver este problema exato. Minha pergunta é principalmente sobre se existem algoritmos ou áreas de estudo similares que eu deveria começar. Alguém pode me ajudar a apontar na direção certa?

Além disso, estou descartando o SMP como ponto de partida incorretamente?

    
por Rob Rose 01.01.2018 / 21:59
fonte

1 resposta

2

Parece que você deve fazer o seguinte:

  1. dê a todos o seu horário de primeira escolha.
  2. Se a distribuição for "praticamente igual entre os horários" (o que quer que isso signifique), então você está pronto.

Se eles não forem aproximadamente iguais, você terá que mover uma ou mais pessoas da primeira para a segunda opção. Provavelmente seria melhor se concentrar no horário mais solicitado, embora você pudesse escolher pessoas aleatoriamente.

Se eles ainda não forem aproximadamente iguais, mesmo depois que todos estiverem configurados para a segunda solicitação, comece a dar às pessoas sua terceira solicitação.

O acima não funcionará se você estiver realmente tentando distribuir as pessoas uniformemente entre um conjunto de intervalos de tempo. Nesse caso, dê a todos a primeira escolha. Então, em qualquer intervalo de tempo que tenha muitas pessoas, encontre o indivíduo no slot que é a segunda opção menos popular e mova-o para lá. Se todos no slot já estiverem em sua segunda escolha, encontre o indivíduo que é a terceira opção menos popular e mova-o.

    
por 02.01.2018 / 03:52
fonte

Tags