Gráfico de fluxo com limite inferior diferente de zero ou capacidade 0
Receio que o título da pergunta possa não ser suficientemente preciso, mas não consegui pensar em algo mais preciso
Aqui está o problema
Dadas 'n' máquinas
- Cada máquina tem um conjunto de recursos
- Cada máquina tem disponibilidade máxima (A (m))
Dadas as tarefas 'm'
- Cada tarefa requer um conjunto de recursos
- Cada tarefa leva um certo tempo (D (t))
- Uma tarefa deve ser realizada em apenas uma máquina
O problema é determinar se todas as tarefas podem ser concluídas.
Eu fico preso ao requisito de 'apenas uma máquina'. Os únicos gráficos de fluxo que posso criar não garantem que uma tarefa não esteja vinculada a mais de uma máquina.
É uma espécie de problema de correspondência bipartida, mas com capacidades> 1
Eu também encontrei um comportamento semelhante ao XOR em redes de fluxo, que é semelhante, mas tem o requisito 'xor' na extremidade 'origem' onde eu precisaria na extremidade destino.
Alguém teria alguma dica? É possível modelar isso como um gráfico de fluxo?
Tx!
Peter
PS Tentando esclarecer os requisitos com exemplos mais concretos
Assuma sistemas de impressão digital e trabalhos de impressão
- Cada impressora digital pode funcionar por várias horas
- Cada impressora tem algumas possibilidades de acabamento: por exemplo, 'cortador de folha', 'laminado', 'cortador a laser', 'dobragem de página', ....
- Cada trabalho de impressão requer várias horas
- Cada trabalho de impressão precisa de uma ou mais possibilidades de acabamento
Dado um conjunto de máquinas, a disponibilidade de cada uma e as possibilidades de acabamento e também um conjunto de trabalhos de impressão (duração, opções de acabamento necessárias) determinam se todos os trabalhos de impressão podem terminar
Então, por exemplo
- A impressora p1 está disponível por uma duração de 10 horas e tem os recursos f1 e f2
- A impressora p2 está disponível por uma duração de 10 horas e tem os recursos f2 e f3
- Job1, que requer os recursos f1 e f2, leva 8 horas para ser executado
- Job2, que requer os recursos f2 e f3, leva 8 horas para ser executado
- Job3, que exige o recurso f2, requer 4 horas para ser executado
Uma impressora que está disponível por, por exemplo, 10 horas pode executar trabalhos de 10 x 1 hora ou trabalhos de 5 x 2 horas, ou trabalho de 1 x 8 horas e 1 x trabalho de 2 horas, ... Os trabalhos sempre têm que ser executados em uma única impressora
Os diagramas de fluxo que eu poderia criar sempre resultam em casos em que
8 horas de p1 são atribuídas ao trabalho1 (deixando 2 horas para a impressora p1) 8 horas de p2 são atribuídas ao trabalho2 (deixando 2 horas para a impressora p2)
(até agora tudo bem)
mas então
As 2 horas de p1 e p2 restantes são usadas para fluir para o job3 e o fluxo máximo parece indicar que os três jobs podem ser executados (o que não está ok)
Respostas
Seu problema é NP-difícil. No caso especial em que nenhum trabalho requer recursos específicos e todas as impressoras têm a mesma disponibilidade, isso se torna apenas o problema de empacotamento do lixo , que é (fortemente) NP-completo.
Você pode tentar adaptar algoritmos padrão para embalagem de lixo à sua situação. Por exemplo, uma abordagem seria usar programação linear inteira e esperar que o solucionador ILP possa lidar com a instância do problema resultante.