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.

Programação da Produção

A programação da produção ou “scheduling” é a alocação de recursos escassos para a execução de tarefas em uma base de tempo (BAKER, 1974, p.2). Os recursos podem ser máquinas em uma fábrica, pistas em um aeroporto, trabalhadores em construções, unidades de processamento em ambiente computacional. As tarefas podem ser os pedidos de produção, as decolagens e aterrissagens de aviões, os estágios em um projeto de construção, as execuções de programas de computador, entre outros (PINEDO, 1995, p.1).

Uma operação é uma atividade elementar a ser executada. O tempo requerido pela operação é chamado tempo de processamento. Uma tarefa é um conjunto de operações inter-relacionadas por restrições de precedência derivadas de limitações tecnológicas. As restrições de precedência definem a rota das operações, ou seja, a ordem em que são processadas. Uma máquina é um equipamento, dispositivo ou instalação capaz de executar uma operação (HAX; CANDEA, 1984, p.258-9).

A atividade de “scheduling” envolve a alocação (associação das tarefas nas máquinas), o sequenciamento (ordenação das tarefas em cada máquina) e a posterior programação (obtenção dos tempos de início e término de cada operação). Segundo Pinedo (1995, p.1), “scheduling” é um processo de tomada de decisão presente tanto em sistemas de produção como em ambientes de processamento de informações, além das empresas de transporte e distribuição e outros tipos de serviços industriais.

Ruiz (2003, p.5) observou que a programação da produção supõe que o planejamento da produção já tenha sido realizado. Portanto, conhecem-se os produtos a fabricar e suas correspondentes quantidades, assim como a configuração, disposição e quantidade de recursos disponíveis. Um sequenciamento adequado da produção é vital para o funcionamento da empresa, garantindo os resultados almejados. Como afirmou Pinedo (1995, p.1), os objetivos do sequenciamento podem ser diversos como, por exemplo, a minimização da data de término da última tarefa ou do número de pedidos que se finalizam após a data de entrega prometida ao cliente.

Assim, a primeira característica que torna os problemas de programação difíceis de serem resolvidos é sua natureza combinatorial, o que significa que o número de soluções possíveis cresce exponencialmente em várias dimensões, de acordo com a quantidade de tarefas, operações ou máquinas.

Isto mostra o grande potencial de pesquisa desta área do conhecimento.