Programação da produção

Problemas de programação da produção são comuns na maioria das empresas. Dado um conjunto de tarefas, o problema consiste em determinar a sequência em que estas serão processadas em um conjunto de máquinas disponíveis de forma a otimizar algum indicador de desempenho.

Objetivo comuns são, por exemplo: minimização do makespan, o qual corresponde ao tempo total para executar todas as tarefas; e a minimização do tardiness total, o qual corresponde à soma dos atrasos das tarefas em relação às data de entrega (due date).

Programar tarefas em máquinas é um problema difícil de se resolver na prática, pois envolve a avaliação computacional de uma infinidade de sequenciamentos possíveis. Por exemplo, dadas 10 tarefas para execução em apenas uma máquina, existe um total de 3628800 sequenciamentos possíveis. A probabilidade de se encontrar o melhor sequenciamento simplesmente por tentativa e erro (como muitas vezes ocorre na prática) é muito pequena, equivalente a “ganhar na loteria”.

Adicionalmente, o número de sequenciamentos possíveis cresce exponencialmente com o número de tarefas, o que impede o uso de um computador para testar todos os sequenciamentos por “força bruta”. Por exemplo, para 100 tarefas, o número de sequenciamentos possíveis é da ordem de $10^{157}$ (1 seguido de 157 zeros), maior que o número estimado de partículas no universo, da ordem de $10^{80}$.

Por outro lado, é possível obter soluções ótimas utilizando algoritmos inteligentes. Neste projeto, são desenvolvidos algoritmos exatos e heurísticos para problemas de programação da produção. Atualmente, as pesquisas do OPL têm se concentrado em problemas do tipo flow shop híbrido e open shop. Estes são ambientes de produção com múltiplas máquinas, problemas mais difíceis ainda que o problema de máquina simples.

As principais tecnologias utilizadas nesse projeto são o solver IBM CPLEX, e a linguagens Python e Julia.

O projeto conta com a colaboração do Prof. Marcelo Seido Nagano, do Departamento de Engenharia de Produção da EESC-USP, e com a colaboração internacional do Prof. Jose M. Framinan, da Universidade de Sevilha.

Este projeto possui financiamento do Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq.


Integrantes do projeto

Bruno A. Prata (Coordenador)

Anselmo R. Pitombeira Neto (Pesquisador)

João V. Moccellin (Pesquisador)

Massimo P. Antonioli (Mestrando)