Qual (s) algoritmo pode resolver este problema de programação restrição?

Question

Eu preciso resolver um problema afetação trabalho e eu gostaria de encontrar algoritmos de preferência eficientes para resolver este problema.

Vamos dizer que existem alguns trabalhadores que podem fazer vários tipos de tarefas. Temos também um conjunto de tarefas que devem ser feitas a cada semana. Cada tarefa leva algum tempo. Cada tarefa deve ser tomada por alguém. Cada trabalhador deve trabalhar entre uma hora de N P uma semana.

Esta primeira parte do problema parece ser um bom candidato para um algoritmo de programação restrição.

Mas aqui é a complicação: porque um trabalhador pode fazer diferentes tarefas eles também podem ter preferências (ou desejos). Se alguém quer para satisfazer todos os desejos para todos que não há solução para o problema (demasiadas restrições).

Então, eu preciso de um algoritmo para resolver este problema. Eu não quero reinventar a roda se a roda perfeito já existe.

O algoritmo deve ser justo (se pode-se definir esta palavra), para, por exemplo, eu deveria ser capaz de adicionar uma restrição como "tentar satisfazer pelo menos um desejo por pessoas". Não tenho a certeza que este problema pode ser resolvido por métodos de restrição Hierarquias descrito aqui: restrição Herarchies . Na verdade eu não tenho certeza de que "justiça" e desejos podem ser expressos por restrições válidas para esta categoria de algoritmos.

Existe um especialista em programação restrição para me dar alguns conselhos? Eu preciso desenvolver uma nova roda com algumas heurísticas em vez de usar algoritmos CP eficientes?

Obrigado!

Answer 1

Seu problema é bastante complexo que uma solução geral provavelmente exigirá a formulação como um linear inteiro problema. Se, por outro lado, você é capaz de relaxar certos requisitos, você pode ser capaz de utilizar uma abordagem mais simples. Por exemplo, bipartite correspondência lhe permitiria agendar vários trabalhadores para vários trabalhos, e pode até mesmo punho preferências, mas não seria capaz de impor restrições gerais 'justiça'. Veja por exemplo este relacionado questão SO. Vertex coloração tem algoritmos eficientes para impor restrições de separação de trabalho.

Outros comentários mencionaram simplex e trabalho loja de agendamento . Simplex é um algoritmo de otimização - que atravessa um espaço solução buscando maximizar alguma função objetivo. Formular a função objetivo certamente pode ser feito, mas não é trivial. Classical loja de trabalho de agendamento, como correspondência bipartite, pode modelar alguns aspectos do seu problema, mas não todos. Não há restrições de precedência, por exemplo. Há versões estendidas que podem lidar com algumas restrições, por exemplo limites de tempo de colocação no tarefas.

Se você estiver interessado em implementações existentes, a NetworkX biblioteca Python tem uma implementação de essa correspondência algoritmo . Um exemplo de um programa de horários de código aberto que pode ser de interesse é Tablix .

Answer 2

Eu fiz horários, o que pode ser considerado uma forma de programação por restrições. Você tem restrições duras (invioláveis) e restrições soft (como preferências de intervalo).

Linear inteiro de programação geralmente torna-se inútil depois de mais de 30 variáveis, e isso também pode ser dito sobre simplex.

foi optimizações específicos do domínio calha de algoritmos heurísticos que uma solução Verificou-se.

Os algoritmos heurísticos utilizados foram simmulated recozimento , algoritmos genéticos , metaheurística algoritmos e similares, mas, no final, o melhor resultado foram fornecidos por um domínio "inteligente" personalizado gananciosos algoritmo de busca .

Basicamente, você pode obter alguns resultados decentes com uma das heurísticas aqui, mas o principal problema é ser capaz de discernir quando um problema é overconstrained.

A grande ferramenta de código aberto para a pesquisa é a HeuristicLab .

Answer 3

Concordo com o que foram propostos aqui. No entanto, MIP (problemas de programação inteira mista) de tamanho muito grande (muito além de 30 variáveis!) Estão praticamente resolvidos hoje em dia graças a códigos comerciais (Xpress, Cplex, Gurobi) ou open-source (Coin-Or / CBC). Além disso, linguagens de modelagem de fantasia, como OPL Studio, GAMS, AMPL, Flop ... permitir a escrever facilmente modelos matemáticos em vez de usar APIs.

Você pode tirar proveito do servidor NEOS ( http: //neos.mcs .anl.gov / neos / solucionadores / index.html ) para tentar muito esaily PMI diferentes disponíveis. Você envia o seu modelo em formato AMPL. Embora AMPL vem como uma versão gratuita limitada, NEOS pode lidar com casos ilimitadas.

existem

linguagens de modelagem também para CP (COMET / OPL Studio) e Local Search (COMET).

Sinta-se livre para entrar em contato comigo através do meu site www.rostudel.com ( 'contato' página)

David

Answer 4

Isso soa como trabalho loja de agendamento .