Qual algoritmo para mudanças atribuindo (problema de otimização discreta)

StackOverflow https://stackoverflow.com/questions/573670

Pergunta

Estou desenvolvendo um aplicativo que otimamente atribui turnos para enfermeiras em um hospital. Eu acredito que este é um problema linear de programação com variáveis ??discretas e, portanto, provavelmente NP-hard:

  • Para cada dia, cada enfermeiro (cerca de 15-20) é atribuída uma mudança
  • Não é um número pequeno (cerca de 6) de diferentes turnos
  • Há um número considerável de restrições e critérios de otimização, seja relativo a um dia, ou a respeito de um emplyoee, por exemplo .:
    • Deve haver um número mínimo de pessoas designadas para cada turno de cada dia
    • Algumas mudanças se sobrepõem de modo que não há problema em ter menos uma pessoa no turno da manhã, se há alguém fazendo turno intermediário
    • Algumas pessoas preferem turno da manhã, alguns preferem turno tarde, mas um mínimo de mudanças de turno é necessário para ainda obter a maior remuneração shift-obra.
    • Não é permitido para uma pessoa para trabalhar turnos tarde um dia e início da mudança no dia seguinte (devido aos regulamentos mínimos de descanso tempo)
    • atribuídos Reunião comprimentos semana de trabalho (diferentes para pessoas diferentes)
    • ...

Basicamente há um número grande (aout 20 * 30 = 600) variáveis ??que cada um pode ter um pequeno número de valores discretos.

Atualmente, o meu plano é usar uma versão modificada Min-conflitos algoritmo

  • começar com atribuição aleatória
  • tem uma função de aptidão para cada pessoa e cada dia
  • selecione a pessoa ou o dia com o pior valor de fitness
  • selecione em um aleatória das atribuições para esse dia / pessoa e configurá-lo para o valor que resulta no valor óptimo de fitness
  • repeat até que um número máximo de iteração é atingido ou nenhuma melhoria pode ser encontrada para o dia / pessoa selecionada

idéias melhor? Estou um pouco preocupado que ele vai ficar preso em um ótimo local. Devo usar alguma forma de simulado recozimento ? Ou considere não só muda em uma variável de cada vez, mas especificamente muda de turnos entre duas pessoas (o principal componente no algoritmo manual do atual)? Eu quero evitar adaptar o algoritmo para as actuais limitações uma vez que aqueles mudança poder.

Editar: não é necessário encontrar uma solução estritamente ideal; a lista é feito atualmente o manual, e eu tenho certeza que o resultado é consideravelmente abaixo do ideal na maioria das vezes - não deve ser difícil de bater isso. ajustes de curto prazo e substituições manuais também será certamente necessário, mas eu não acredito que isso será um problema; Marcação atribuições passadas e manuais como "fixo" realmente deve simplificar a tarefa, reduzindo o espaço de solução.

Foi útil?

Solução

Este é um problema difícil de resolver bem. Tem havido muitos trabalhos acadêmicos sobre este assunto particularmente no campo Operations Research - ver, por exemplo enfermeira rostering papéis 2007-2008 ou apenas google "operações enfermeira rostering pesquisa". A complexidade também depende de aspectos como: quantos dias para resolver; que tipo de "pedidos" pode fazer da enfermeira; é o roster "cíclica"; é um plano de longo prazo ou ele precisa lidar com curto prazo rostering "reparar" tais como doença e swaps etc etc.

O algoritmo que você descreve é ??um href="http://en.wikipedia.org/wiki/Heuristic_(computer_science)" rel="noreferrer"> heurística abordagem . Você pode achar que você pode ajustá-lo para trabalhar bem para uma instância específica do problema, mas, logo que "algo" é alterada ele pode não funcionar tão bem (optima por exemplo local, pobre convergência).

No entanto, essa abordagem pode ser adequada dependendo suas necessidades de negócios particulares - por exemplo, como é que é importante para obter o ideal solução, é o esboço problema que você descreve deverá manter-se o mesmo, o que é o potencial de poupança (dinheiro e recursos), o quão importante é a percepção da enfermeira da qualidade de suas listas, o que é o orçamento para este trabalho etc.

Outras dicas

Umm, você sabia que alguns ILP-solucionadores de fazer um bom trabalho? Tente AIMMS, Mathematica ou o kit de programação GNU! 600 Variáveis ??é, naturalmente, muito mais do que o Lenstra teorema vai resolver facilmente, mas às vezes esses solucionadores de ILP tem uma boa pega e em AIMMS, você pode modificar a estratégia de ramificação um pouco. Além disso, há um -approximation muito rápido de 100% para procedimentos ILP.

Eu resolvi um problema de atribuição de mudança para uma grande fábrica recentemente. Primeiro nós tentamos gerar programações puramente aleatórias e devolver qualquer um que passou no teste is_schedule_valid - o algoritmo de fallback. Este foi, naturalmente, lento e indeterminado.

Em seguida, tentou algoritmos genéticos (como sugerido), mas não conseguiu encontrar uma função boa aptidão que fechou em qualquer solução viável (devido a menor mudança pode fazer toda a DIREITA cronograma ou errado - sem pontos para quase) <. / p>

Finalmente, escolheu o seguinte método (que trabalhou bem!):

  1. Randomize o conjunto de entrada (ou seja, postos de trabalho, mudança, pessoal, etc.).
  2. Criar uma tupla válida e adicioná-lo ao seu cronograma preliminar.
  3. Se não tupla válida pode ser criado, rollback (e incremento) a última tupla acrescentou.
  4. Passar a programação parcial de uma função que os testes could_schedule_be_valid, isto é, poderia esta programação ser válido se os tuplos restantes foram preenchidas de uma forma possível
  5. Se !could_schedule_be_valid, simplesmente rollback (e incremento) da tupla adicionado (2).
  6. Se schedule_is_complete, return schedule
  7. Goto (2)

Você gradualmente construir uma mudança parcial desta forma. A vantagem é que alguns testes para a programação válida pode facilmente ser feito no Passo 2 (pré-testes), e outros devem permanecer no Passo 5 (pós-testes).

Boa sorte. Perdemos dias tentando os primeiros dois algoritmos, mas obteve o algoritmo recomendado gerando horários válidos instantaneamente em menos de 5 horas de desenvolvimento.

Além disso, apoiamos pré-fixação e pós-fixação de atribuições que o algoritmo iria respeitar. Você simplesmente não embaralhar essas ranhuras no Passo 1. Você verá que as soluções não tem que ser em qualquer lugar perto ideal. A nossa solução é O (N * M) a um mínimo, mas é executado no PHP (!) Em menos de meio segundo para uma instalação de fabricação de todo. A beleza está na exclusão de horários ruins rapidamente usando um teste bom could_schedule_be_valid.

As pessoas que são usados ??para fazê-lo manualmente não me importo se ele leva uma hora -. Eles só sei que eles não tem que fazê-lo manualmente mais

Mike,

Não sei se você já tem uma boa resposta para isso, mas eu tenho certeza que a programação restrição é o bilhete. Enquanto a GA pode dar-lhe uma resposta, CP é projetado para dar-lhe muitas respostas ou dizer-lhe se não há uma solução viável. Uma pesquisa de "programação por restrições" e agendamento deve trazer muita informação. É um relativamente novos métodos área e CP funcionam bem em muitos tipos de problemas onde métodos de otimização tradicionais atolar.

dinâmica programação a la Bell? Meio que parece que há um lugar para ele:. Subproblemas sobrepostas, subestruturas ótimas

Uma coisa que você pode fazer é tentar procurar simetrias do problema. Por exemplo. você pode tratar todos os enfermeiros como equivalentes para efeitos do problema? Se assim for, então você só precisa considerar enfermeiros em alguma ordem arbitrária - você pode deixar de considerar soluções de tal forma que qualquer enfermeira i está prevista antes de qualquer enfermeira j , onde i > j . (Você disse que os enfermeiros individuais têm tempos de troca preferenciais, o que contradiz este exemplo, embora talvez isso é um objetivo menos importante?)

Eu acho que você deve usar o algoritmo genético, porque:

  • É mais adequado para instâncias grandes problemas.
  • Ela produz reduzida complexidade de tempo sobre o preço de resposta inexata (não o melhor final)
  • Você pode especificar restrições e preferências facilmente ajustando punições aptidão para aqueles não atendidos.
  • Você pode especificar limite de tempo para a execução do programa.

  • A qualidade da solução depende de quanto tempo você pretende gastar resolver o programa ..

    Algoritmos Genéticos Definição

    Algoritmos Genéticos Tutorial

    projeto agendamento classe com GA

Também dê uma olhada em: uma pergunta semelhante e outro

Usando programação CSP Fiz programms para shitfs automáticas escalas de serviço. por exemplo:

  1. sistema de 2 turnos - testado para 100+ enfermeiros, 30 dias tempo horizonte, 10+ regras
    2. sistema
  2. 3 turnos - testado para mais de 80 enfermeiros, 30 dias horizonte de tempo, 10+ regras
  3. sistema de 3 turnos, 4-equipes - testado por 365 dias horizonte, 10+ regras,

e um par de sistemas de similiar. Todos eles foram testados em minha casa PC (1,8 GHz, dual-core). tempos de execução sempre foram isto é aceitável. para 3 / demorou cerca de 5 minutos e 300MB de RAM.

A maioria parte difícil desse problema foi a seleção estratégia de resolução adequada solver adequada e.

Metaheurísticas se saiu muito bem na Internacional enfermeira Rostering de Concorrência 2010 .

Para uma implementação, veja o vídeo desta com uma enfermeira contínua rostering (java) .

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top