Problemas de Programação de Operações em Máquinas

Um problema de programação da produção é determinado pelo número de tarefas e operações a serem processadas, pelo número e tipo de máquinas disponíveis, pelo padrão de fluxo das operações nas máquinas e pelo critério de otimização com que se avalia uma solução (CONWAY et al., 1967, p.6). Normalmente, nos problemas de programação assume-se que o número de tarefas e de máquinas seja finito e determinado.

Os problemas tornam-se mais complexos com a presença de restrições, por exemplo, relacionando uma tarefa a outra, recursos a tarefas, um recurso ao outro e um recurso ou tarefa a eventos externos ao sistema. Pode haver também uma restrição de precedência entre tarefas ou pode não ser possível usar dois recursos simultaneamente durante certo período de tempo. Ou então um recurso pode não estar disponível durante um intervalo de tempo específico devido a manutenção. Como estes complexos inter-relacionamentos podem tornar muito difícil a busca da solução exata ou mesmo aproximada de um grande problema, é natural resolver primeiro versões mais simples. Então, a sensibilidade da solução pode ser testada quanto a sua complexidade e soluções aproximadas podem ser encontradas para problemas difíceis (MORTON; PENTICO, 1993, p.6).

Para classificar os principais modelos de programação, é necessário caracterizar a configuração dos recursos e o comportamento das tarefas (BAKER, 1974, p.6). Segundo MacCarthy e Liu (1993), as restrições tecnológicas são determinadas principalmente pelo padrão do fluxo das tarefas nas máquinas, levando à seguinte classificação dos problemas:

• Job shop: cada tarefa tem seu fluxo individual ou rota específica nas máquinas;

• Flow shop: todas as tarefas possuem o mesmo fluxo de processamento nas máquinas;

• Open shop: não há fluxo padrão estabelecido para as tarefas;

• Flow shop permutacional: flow shop em que a ordem de processamento das tarefas em cada máquina é estritamente a mesma;

• Máquina única: existe apenas uma única máquina disponível para o processamento das tarefas;

• Máquinas paralelas: em um único estágio de produção, há duas ou mais máquinas disponíveis que podem executar qualquer tarefa, sendo que cada tarefa só pode ser processada em uma única máquina.

Moccellin e Nagano (2003a) adaptaram esta classificação, acrescentando as seguintes classes:

• Job shop com máquinas múltiplas: job shop em que existem duas ou mais máquinas paralelas em cada estágio, sendo que cada tarefa é processada por somente uma máquina em cada um dos estágios; e

• Flow shop com máquinas múltiplas: as tarefas são processadas em múltiplos estágios na mesma ordem e em cada um deles há máquinas paralelas, podendo variar a quantidade por estágio. As tarefas são processadas por apenas uma máquina em cada estágio.