Pcp 1

XII SIMPEP - Bauru, SP, Brasil, 07 a 09 de novembro de 2005.

Programação da produção com recursos restritos e disjunções
José Francisco Ferreira Ribeiro (USP - Universidade de São Paulo, São Carlos, SP) [e-mail]

Resumo A programação da produção com recursos restritos e disjunções tem por objetivo determinar a seqüência e o calendário de fabricação em cada uma das máquinas disponíveis na fábrica, otimizando-se um critério. As peças são processadas de acordo com roteiros de fabricação previamente fixados e as durações das operações a executar são conhecidas. Neste artigo, o problema é estudado mediante duas abordagens: programação inteira e teoria dos grafos. O critério de otimização é o tempo total de fabricação. Um programa computacional baseado em teoria dos grafos foi escrito em linguagem C e testado. O programa permitiu a resolução eficiente de vários exemplos, apesar do caráter não-polinomial do problema estudado. Palavras-Chave: Programação da produção, Restrições disjuntivas, Otimização. 1. Introdução Em um problema de programação da produção com recursos restritos e disjunções, p peças devem ser fabricadas, e para tanto, dispõe-se de m máquinas. As máquinas executam diferentes tipos de operações e é fornecido um roteiro de fabricação para cada uma das peças. Uma peça, por exemplo, deverá passar sobre a máquina 2 antes da máquina 1, depois sobre a máquina 1 antes da máquina 3, etc. Um seqüenciamento w é uma m-upla (O1, O2, ..., Om), onde Oq designa a ordem de passagem das peças sobre a máquina q. Busca-se determinar o seqüenciamento de tempo total mínimo. 2. Formulação do Problema Entre os modelos de programação inteira desenvolvidos desde os anos 50, Muth e Thompson (1963) destacam: Wagner (1959), Bowman (1959) e Manne (1960), que usam o método dos planos de corte (Salkin, 1975) para resolução. Balas (1969) aplica o algoritmo de resolução implícita (Salkin, 1975) para resolver o modelo de Manne (1960). Nos anos 70, a resolução dos problemas