Problema de programação sustentable no ambiente jobshop flexível com flexibilidade de sequenciamento e efeitos de aprendizagem/deterioração

• Processo: 22/16743-1
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de junho de 2023
• Data de Término da vigência: 31 de março de 2024
• Área de conhecimento: Ciências Exatas e da Terra - Matemática - Matemática Aplicada
• Pesquisador responsável: Ernesto Julián Goldberg Birgin
• Beneficiário: José Angel Riveaux Merino
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 18/24293-0 - Métodos computacionais de otimização, AP.TEM
• Assunto(s): Pesquisa operacional Scheduling
• Palavra(s)-Chave do Pesquisador: Otimização discreta | pesquisa operacional | Scheduling | Otimização discreta

Resumo

O problema de programação de tarefas num ambiente jobshop clássico (JS) consiste em programar $n$ tarefas em um ambiente com $m$ máquinas. Cada tarefa é composta por várias operações com uma estrutura de precedência linear e tem uma rota pré-determinada através das máquinas. O problema de programação de tarefas num ambiente jobshop flexível (FJS) é uma generalização do problema anterior na qual pode haver várias máquinas, não necessariamente idênticas, capazes de processar cada operação. O tempo de processamento de cada operação em cada máquina é conhecido e não é permitido nenhum tipo de interrupção. O objetivo é decidir em que máquina cada operação será processada, e em que ordem as operações serão processadas em cada máquina, para que um determinado critério seja otimizado.O problema do FJS com flexibilidade de sequenciamento é uma variante do FJS em que a precedência entre as operações é dada por um digrafo acíclico ao invés de por uma ordenação linear. Este último caso ocorre quando há trabalhos, cada um composto de um conjunto de operações, e as operações do mesmo trabalho têm uma ordem linear na qual devem ser executadas. A flexibilidade de seqüenciamento aparece quando, dentro de um trabalho, não existe uma ordem linear entre as operações que o compõem. Por exemplo, se o trabalho for produzir um livro, ele pode consistir em operações independentes que consistem na impressão de diferentes partes do livro que posteriormente precisam ser coladas para formar o livro. As operações de impressão também podem ter uma operação comum que as precede, tal como uma etapa de diagramação. Este exemplo não é um exemplo aleatório, pois o problema da FJS com a flexibilidade de sequenciamento ganhou destaque recentemente dentro da indústria gráfica. Embora os problemas de programação tenham sido tradicionalmente definidos de acordo com métricas baseadas em questões econômicas ou de produtividade, estudos recentes na área começaram a incorporar as questões ambientais ao problema, dando origem aos chamados problemas de programação verde. Nesses problemas é comum considerar um compromisso entre produtividade e consumo de energia ou emissão de CO2.Nos problemas clássicos de programação, o tempo de processamento de uma operação em uma determinada máquina é um dado de entrada fixo. Em problemas com aprendizado ou efeito de deterioração, o tempo de processamento de uma operação em uma determinada máquina é uma função que pode depender da posição da operação na máquina (primeira a ser processada, segunda, etc.) ou da soma dos tempos de processamento das operações que já foram processadas pela máquina. A função pode ser exponencial e pode até ser descontínua se incluir algum tipo de truncamento. O efeito de aprendizagem pode estar relacionado à aquisição de experiência pelo operador da máquina, enquanto o efeito de deterioração pode estar relacionado à fadiga da máquina. Tal característica ajuda a aproximar o problema abordado dos problemas encontrados em aplicações reais.O problema do FJS com a flexibilidade de sequenciamento é NP-difícil, já que tem o problema JS (que é conhecido por NP-difícil) como caso particular. Devido a sua complexidade, o número de publicações preocupadas com a solução exata do problema FJS é pequeno. De acordo com a literatura recente, neste projeto pretendemos desenvolver métodos heurísticos para lidar com o FJS com flexibilidade de seqüenciamento. Em particular, estamos interessados em uma variante que inclui dois ingredientes: (i) efeitos de aprendizagem e deterioração no tempo de processamento das operações e (ii) uma função de custo de acordo com as preocupações atuais com sustentabilidade e meio ambiente.