Planejamento de tarefas com um problema de gargalo

11

Dado n trabalhos J1,J2,...,Jn , cada trabalho exige Ti>0,TiN tempo para completar.

Cada trabalho deve ser pré-processado e pós-processado por uma única máquina M que pode lidar com apenas 1 trabalho por vez e as duas fases requerem 1 unidade de tempo. Depois de ser pré-processados, trabalho Ji é enviado para uma máquina com poder ilimitado (que pode lidar em paralelo um número ilimitado de postos de trabalho) e ele vai estar pronto a tempo Ti , então ele deve ser enviado ( imediatamente ) a máquina M novamente para pós-processamento.

insira a descrição da imagem aqui

O problema de decisão associado é:

Entrada: O processamento tempos de N postos de trabalho, um inteiro K 2 N Pergunta: podemos processar todos os postos de trabalho em tempo KTi>0,TiNNK2N
K usando o modelo acima "gargalo"?

Esse problema tem um nome?
Qual é a sua complexidade? (está em ou está em N PPNP cheio de ?)

ATUALIZAÇÃO 29 de março:
Como percebido corretamente por M.Cafaro em sua resposta, o problema é semelhante ao Problema de tempo mínimo sem restrição (UMFT) (consulte o Capítulo 17 do Manual de programação de algoritmos ), que é duro (comprovado em W. Kern e W. Nawijn, "Planejando trabalhos de multi-operação com tempo atrasado em uma única máquina", University of Twente, 1993). Como posso ver, existem algumas diferenças, porque no meu modelo:NP

  • o tempo de pré / pós-processamento é constante (1 unidade de tempo)
  • assim que o trabalho for concluído, ele deverá ser imediatamente pós-processado (o modelo UMFT permite atrasos)

Não encontrei a prova de Kern & Nawijn on-line, então ainda não sei se as restrições acima alteram a dificuldade do problema.

Finalmente, você pode pensar em todo o processo como um único robô de cozinha com um grande forno; o robô pode preparar diferentes tipos de alimentos, um de cada vez (todos exigem o mesmo tempo de preparação), colocá-los no forno e, assim que estiverem cozidos, deve removê-los do forno e adicionar alguns ingredientes frios ... o " problema do robô de cozinha " :-)

Vor
fonte
Agradável. Tenho a sensação de que o gargalo deve simplificar as coisas.
Raphael
A restrição é sempre verificada, pois os custos de pré e pós-processamento são 1 unidade de tempo e você tem nk2nn empregos. Tem certeza de que a restrição está correta?
Massimo Cafaro 28/03
Desculpe, eu não entendi o que eu quis dizer no comentário anterior. é explicitamente dado na entrada como um "prazo" ou você está solicitando um algoritmo para minimizark ? k
Massimo Cafaro 28/03
@MassimoCafaro: é dado como entrada (para tornar o problema de otimização um problema de decisão). Como você notou, eu escrevi k 2 nkk2n porque se a resposta é trivialmente NÃO. Mas talvez seja confuso e eu deva excluí-lo. k<2n
Vor
1
Sua pergunta é comprovada como NP-completa em "Minimizar a produção em uma oficina de fluxo de duas máquinas com atrasos e operações de unidade de tempo é NP-Hard" por W. Yu, H. Hoogeveen e JK Lenstra (2004), que também afirmam que Kern e Nawijn não o resolveram. Cito: "O status de complexidade do caso especial com tarefas de tempo de processamento da unidade foi aberto para atrasos mínimos e exatos. O status de complexidade do caso com atrasos mínimos é colocado como uma questão em aberto por Kern e Nawijn (1991)".
Peter Shor

Respostas:

5

A questão é comprovada como NP-difícil em "Minimizar o tempo de fabricação em uma oficina de fluxo de duas máquinas com atrasos e operações de unidade de tempo é NP-difícil" por W. Yu, H. Hoogeveen e JK Lenstra (2004). Isso é comprovado na seção 9 do artigo:

Teorema 24. O problema de minimizar o makepan em uma única máquina com duas operações de tempo unitário por tarefa com atrasos intermediários arbitrários é muito difícil para NP.

O modelo exato estudado aqui é que o trabalho consiste em duas operações que levam tempo unitário separado por algum tempo de atraso T iEuTEu . O problema é fortemente NP-completos tanto quando o valor exato do atraso é especificado para cada trabalho, e quando algum tempo atraso mínimo é especificado para cada trabalho.TEu

Peter Shor
fonte
5

Parece o chamado modelo de programação mestre-escravo introduzido por Sahni . Em particular, seu problema se enquadra nos sistemas mestre-escravo de mestre único. Você pode distinguir vários casos:

1) Se você não adicionar nenhuma restrição adicional à ordem de execução da tarefa (como no seu caso), o problema será chamado de problema de tempo mínimo de término irrestrito (UMFT) e tem sido demonstrado ser NP-hard;

2) Mesmas ordens de pré e pós-processamento: é possível projetar um algoritmo para construir uma ordem, preservando o tempo mínimo de acabamentoO(nregistron) (OPMFT);

Portanto, no caso 1, seu problema é duro, enquanto estiver emNPP

Problemas relacionados adicionais são:

3) Pós-processamento de ordem inversa: para qualquer permutação de pré-processamento, , é possível construir um cronograma de ordem inversa, conhecido como cronograma canônico de ordem inversa (CROS). Dada uma permutação de pré-processamento σσσ , o CROS correspondente é único. É fácil estabelecer que todo cronograma mínimo de ordem inversa de término no tempo (ROMFT) é um CROS.

4) restrição no-wait-in-process:

a) [MFTNW] Minimize o tempo de conclusão, sujeito à restrição de não espera no processo; b) [OP-MFTNW] Esta é a versão de preservação de ordem do MFTNW. Ou seja, minimize o tempo de acabamento, sujeito às restrições de não espera no processo e de preservação da ordem; c) [RO-MFTNW] Minimize o tempo de término, sujeito às restrições de não espera no processo e ordem inversa.

umabc admite uma solução em tempo polinomial.

Detalhes adicionais no Manual de Agendamento , capítulo 17.

Massimo Cafaro
fonte
n
nnnn
2
Parece-me que a prova de dureza NP de Sahni usa criticamente o fato de que os tempos de pré-processamento e pós-processamento podem ser arbitrários. O problema do OP tem todos esses tempos iguais a 1. A prova funciona neste caso?
Peter Shor
Vor, o artigo a que você se refere é apenas um extrato com muitas partes ausentes do capítulo 17 do livro. No entanto, a parte que falta irá impedir que você entenda corretamente (notação ausente etc).
Massimo Cafaro 28/03
O(nregistron)