[ 1,5 ponto] Considere um problema de sequenciamento da produção com 5 tarefas em um ambiente produtivo com 3 máquinas em paralelo. Cada tarefa precisa ser processada por uma única máquina. Quantas programaçōes diferentes são possiveis?
Passo 1
O enunciado pede o número de sequenciamentos de
tarefas em
máquinas paralelas, sabendo que cada tarefa vai para exatamente uma máquina. O conteúdo aqui é contar maneiras de
(a) distribuir as tarefas entre as máquinas e
(b) ordenar as tarefas em cada máquina.
(a) distribuir as tarefas entre as máquinas e
(b) ordenar as tarefas em cada máquina.
Passo 2
Se numa distribuição a máquina
recebe
tarefas (com
), então há
maneiras de ordenar essas
tarefas na máquina
. Como as máquinas são independentes, para essa distribuição particular o número de ordenações é
Passo 3
O número de formas de escolher exatamente
tarefas para as máquinas, com
, vem do coeficiente multinomial
Portanto, somando sobre todas as tripletas
, o total de programações é
Passo 4
Dentro da soma cada termo simplifica-se para
O número de termos na soma é o número de soluções não-negativas de
, dado por
Passo 5
Logo o total de programações possíveis é