Embed Size (px)
UNIVERSIDADE FEDERAL FLUMINENSE ESCOLA DE ENGENHARIA
MESTRADO EM ENGENHARIA DE PRODUCAO
FERNANDO PAES BARRETO MACHADO
FORMULAÇÕES DE PROGRAMAÇÃO INTEIRA PARA PROBLEMAS DE
ESCALONAMENTO DA PRODUÇÃO
NITERÓI
2018
FERNANDO PAES BARRETO MACHADO
FORMULAÇÕES DE PROGRAMAÇÃO INTEIRA PARA PROBLEMAS DE
ESCALONAMENTO DA PRODUÇÃO
Dissertação apresentada ao Curso de
Mestrado em Engenharia de Produção
da Universidade Federal Fluminense
como requisito parcial para obtenção
do Grau de Mestre em Engenharia de
Produção.
Professor Orientador:
Prof. D.Sc. EDUARDO UCHOA BARBOZA
NITERÓI
2018
Ficha catalográfica automática - SDC/BEE
Bibliotecária responsável: Fabiana Menezes Santos da Silva - CRB7/5274
M149f Machado, Fernando Paes BarretoFormulações de programação inteira para problemas de
escalonamento da produção / Fernando Paes Barreto Machado;Eduardo Uchoa Barboza, orientador. Niterói, 2018.145 f.
Dissertação (mestrado)-Universidade Federal Fluminense,Niterói, 2018.
1. Pesquisa operacional. 2. Programação inteira. 3.Otimização. 4. Tomada de decisão. 5. Produçãointelectual. I. Título II. Barboza,Eduardo Uchoa, orientador.III. Universidade Federal Fluminense. Escola de Engenharia.
CDD -
aaaa
a
a
a
a
AGRADECIMENTOS
Agradeço em primeiro lugar à minha família por todo apoio e compreensão
ao longo dessa difícil caminhada pelo saber que é a realização de um projeto de
pesquisa e escrita da dissertação. Pai e irmã foram ombros nos quais eu pude me
confortar e reforçar minha vontade em concluir este objetivo. Tenho gratidão
especial à minha mãe por me ensinar o verdadeiro significado das palavras
comprometimento, disciplina e perseverança. Seus ensinamentos foram
fundamentais para essa conquista.
Aos amigos também sou grato pelos momentos de companheirismo,
descontração e divertimento tão necessários ao longo do mestrado. Compartilhar as
dificuldades e potencializar as alegrias me ajudou a passar por este período de
muito estudo e algumas renúncias de maneira mais leve e suave.
Um agradecimento especial não poderia faltar ao Professor Uchoa por todo
profissionalismo, excelente didática, paciência e dedicação a este projeto. Registro
aqui, neste documento tão importante para minha vida pessoal e profissional, minha
profunda gratidão e admiração. Sem sua orientação a conclusão deste trabalho não
seria possível.
Direciono também meus agradecimentos aos professores que aceitaram
compor a banca examinadora de defesa desta dissertação. É uma grande honra ter
a oportunidade de apresentar minha pesquisa e receber os comentários de
profissionais com tamanho reconhecimento na academia e notória capacidade de
contribuição para o tema. Mais uma vez, muito obrigado pela disponibilidade.
Por fim, agradeço à Universidade Federal Fluminense e, mais
especificamente, a todos os professores e colaboradores dessa instituição que, com
muito empenho, trabalham no Programa de Mestrado e Doutorado em Engenharia
de Produção da UFF.
Our passion for learning…is our tool for survival.
Carl Sagan
RESUMO
Os modelos determinísticos para resolução de problemas de escalonamento
possuem grande aplicabilidade por permitirem o estudo de diversas situações em
diferentes áreas do conhecimento. Dois problemas deste tipo foram abordados neste
estudo: o problema de sequenciamento de job shop (PSJS) e o caso prático do
problema de alocação de bobinas (PAB) para fabricação de dutos flexíveis da
indústria de óleo e gás. O ambiente de produção job shop possibilita alta flexibilidade
na oferta de produtos e serviços, sendo estratégico para a satisfação dos clientes.
Devido à sua relevância, um dos objetivos dessa dissertação consiste em propor um
modelo de programação inteira (PI) para resolver o problema de sequenciamento de
job shop com função objetivo de minimizar o atraso total ponderado de forma
eficiente. O novo modelo é baseado na formulação proposta por Bowman e Kondili,
Pantelides e Sargent com variáveis indexadas no tempo e introdução de restrições
como fluxos em rede. Os resultados demonstraram que a nova formulação é
competitiva em condições em que os tempos de processamento das tarefas pelas
máquinas é reduzido e apresenta resultados iniciais, isto é, soluções ótimas com
relaxação linear mais próximas da solução ótima inteira do que as formulações
presentes na literatura. As bobinas tratadas no segundo problema deste trabalho
são utilizadas para armazenagem e transporte de dutos flexíveis em cada etapa da
sua produção até a entrega final ao cliente. Outro objetivo desta dissertação é a
proposição de um modelo de PI para resolução do problema de alocação de bobinas
a fim de minimizar o número de bobinas necessárias e/ou reduzir a sua
movimentação dentro da fábrica. A contribuição deste modelo é a capacidade de
fornecer respostas ágeis e precisas em um cenário de escassez de bobinas e
esforço crescente para redução de custos na indústria do petróleo. O modelo foi
aplicado em uma fábrica de dutos localizada no Estado do Rio de Janeiro. O teste foi
realizado para um horizonte de planejamento de seis meses, correspondendo a uma
produção de dutos 10% maior do que a do semestre anterior. O modelo mostrou que
era possível realizar esse aumento de produção sem a aquisição de bobinas
adicionais, gerando consideráveis ganhos financeiros.
Palavras-chave: escalonamento, programação inteira, job shop, atraso total
ponderado, dutos flexíveis, bobinas
ABSTRACT
The deterministic models for solving scheduling problems have high
applicability due to the fact they permit the study of several situations in different
areas of knowledge. Two problems of this type were addressed in this study: the job
shop scheduling problem (JSSP) and the practical case of the reel allocation problem
(RAP) for the production of flexible pipes in the oil and gas industry. The job shop
machine environment enables high flexibility to offer products and services and
therefore it is strategic for customer satisfaction. Due to its relevance, one of the
objectives of this master thesis consists in proposing an integer programming (IP)
model to solve the job shop scheduling problem with the objective function of
minimizing the total weighted tardiness. The new model for solving the job shop
scheduling problem is based on the formulation proposed by Bowman and Kondili,
Pantelides and Sargent with time-indexed variables and introduction of constraints as
network flows. Results have shown that the new formulation is competitive under
conditions in which processing times of the jobs in the machines are reduced and
presents initial results, i.e. optimal solutions with linear relaxation closer to the integer
optimal solution than the existing formulations in the literature. The reels treated in
the second problem of this work are used for storage and transportation of flexible
pipes at each stage of their production, until final delivery to the customer. Another
objective of this master thesis is proposing an IP model for solving the reel allocation
problem in order to minimize the number of reels required and/or reduce its
movement inside the factory. The contribution of the proposed model for the
definition of reel allocation is the ability to provide agile and accurate responses in
scenarios of reel shortages and increasing effort to reduce costs in the oil industry.
The model was applied to a pipe plant located in the State of Rio de Janeiro. The test
was performed for a planning horizon of six months, corresponding to a production of
pipes 10% higher than that of the previous semester. The model showed that it was
possible to achieve this increase of production without purchasing additional reels,
generating considerable financial gains.
Keywords: scheduling, integer programming, job shop, total weighted tardiness,
flexible pipes, reels
SUMÁRIO
1 INTRODUÇÃO .................................................................................................... 13
1.1 MOTIVAÇÃO DO TRABALHO ..................................................................... 14
1.2 DESCRIÇÃO DO PROBLEMA ..................................................................... 16
1.3 JUSTIFICATIVA E RELEVÂNCIA DO ESTUDO .......................................... 17
1.4 OBJETIVO GERAL ...................................................................................... 18
1.5 OBJETIVOS ESPECÍFICOS ........................................................................ 18
1.6 DELIMITAÇÕES DO ESTUDO .................................................................... 19
1.7 METODOLOGIA E TRABALHO REALIZADO .............................................. 20
1.8 ORGANIZAÇÃO DO TRABALHO ................................................................ 21
2 FUNDAMENTAÇÃO TEÓRICA .......................................................................... 24
2.1 ESTRUTURA E NOTAÇÕES PARA MODELOS DETERMINÍSTICOS DE
ESCALONAMENTO ............................................................................................... 24
2.1.1 Campo 𝛂 – Ambientes de máquina ....................................................... 25
2.1.2 Campo 𝛃 – Detalhes das características e restrições de processamento
27
2.1.3 Campo 𝛄 – Objetivos de minimização ................................................... 30
2.2 JOB SHOP ................................................................................................... 32
2.3 PROBLEMA DE FLUXO EM REDE ............................................................. 38
2.3.1 Problema do fluxo de custo mínimo ....................................................... 40
3 FORMULAÇÃO DE PI PARA O PROBLEMA DE SEQUENCIAMENTO DE JOB
SHOP ........................................................................................................................ 42
3.1 INTRODUÇÃO ............................................................................................. 42
3.2 METODOLOGIA DA PESQUISA ................................................................. 43
3.2.1 Levantamento e análise das melhores formulações .............................. 44
3.2.2 Identificação e implementação de oportunidades de melhoria .............. 44
3.2.3 Realização de testes com a nova formulação e as de referência .......... 44
3.2.4 Comparação dos resultados obtidos ..................................................... 46
3.3 MODELO MATEMÁTICO ............................................................................. 47
3.4 EXEMPLO ILUSTRATIVO ........................................................................... 49
3.5 FORMULAÇÕES DE REFERÊNCIA PARA OS TESTES ............................ 54
3.6 DISCUSSÃO DOS RESULTADOS .............................................................. 57
4 FORMULAÇÃO DE PI PARA O PROBLEMA DE ALOCAÇÃO DE BOBINAS NA
PRODUÇÃO DE DUTOS FLEXÍVEIS ....................................................................... 70
4.1 INTRODUÇÃO ............................................................................................. 70
4.2 METODOLOGIA DA PESQUISA ................................................................. 74
4.2.1 Reconhecimento e levantamento de dados do processo fabril ............. 74
4.2.2 Elaboração e programação do modelo matemático .............................. 75
4.2.3 Aplicação no estudo de caso ................................................................. 75
4.2.4 Discussão dos resultados e comparação com a situação anterior ........ 76
4.3 PRODUTO E PROCESSO DE PRODUÇÃO ............................................... 76
4.4 EXEMPLO ILUSTRATIVO ........................................................................... 78
4.5 MODELO MATEMÁTICO ............................................................................. 83
4.6 IMPLEMENTAÇÃO E ESTUDO DE CASO .................................................. 88
5 CONCLUSÃO E TRABALHOS FUTUROS ......................................................... 92
6 REFERÊNCIAS BIBLIOGRÁFICAS ................................................................... 95
7 APÊNDICES ....................................................................................................... 98
LISTA DE ILUSTRAÇÕES
Figura 1 – Produção científica relacionada ao tema "job shop" ................................ 14
Figura 2 – Produção científica relacionada ao tema "scheduling" ............................. 15
Figura 3 – Produção científica relacionada ao tema "integer programming" ............. 16
Figura 4 – Etapas da metodologia da pesquisa para o problema de sequenciamento
de job shop ................................................................................................................ 43
Figura 5 – Representação esquemática das Restrições (28) e (29) relativas à
capacidade das máquinas ......................................................................................... 49
Figura 6 – Representação esquemática das Restrições (30) a (32) relativas à ordem
de precedência das tarefas ....................................................................................... 49
Figura 7 – Diagrama de Gantt da solução ótima do exemplo ................................... 51
Figura 8 – Esquema representativo dos fluxos em rede das restrições de capacidade
de máquina do exemplo ............................................................................................ 52
Figura 9 – Esquema representativo do fluxo em rede da restrição de precedência da
tarefa 1 do exemplo ................................................................................................... 52
Figura 10 – Esquema representativo do fluxo em rede da restrição de precedência
da tarefa 2 do exemplo .............................................................................................. 53
Figura 11 – Esquema representativo do fluxo em rede da restrição de precedência
da tarefa 3 do exemplo .............................................................................................. 53
Figura 12 – Análise comparativa dos gaps de integralidade das formulações para
uma instância 8 x 8 com tempos de processamento entre 1 e 5 UT, semente 3 e
solução ótima igual 266 ............................................................................................. 67
Figura 13 – Análise comparativa dos gaps de integralidade das formulações para
uma instância 8 x 8 com tempos de processamento entre 1 e 10 UT, semente 6 e
solução ótima igual 468 ............................................................................................. 68
Figura 14 – Exemplo de arranjo submarino com aplicações de dutos flexíveis ........ 71
Figura 15 – Duto flexível ........................................................................................... 72
Figura 16 – Bobinas .................................................................................................. 73
Figura 17 – Etapas da metodologia da pesquisa para o problema de alocação de
bobinas ...................................................................................................................... 74
Figura 18 – Partes de uma bobina ............................................................................ 77
Figura 19 – Diagramas de Gantt do plano de produção e dos seus usos ................. 81
Figura 20 – Grafos de usos e a solução para o exemplo dado ................................. 86
Figura 21 – Diagrama de Gantt dos usos alocados com bobinas de 14 ft ................ 90
Figura 22 – Diagrama de Gantt dos usos alocados com bobinas de 16 ft, 17 ft, 19 ft e
22 ft ........................................................................................................................... 91
LISTA DE TABELAS
Tabela 1 – Tamanho das instâncias adotadas na metodologia de pesquisa ............ 45
Tabela 2 – Tempos de processamento das tarefas nas máquinas do exemplo ........ 50
Tabela 3 – Sequência das máquinas de cada tarefa do exemplo ............................. 50
Tabela 4 – Valores das variáveis de decisão da solução ótima do exemplo ............. 50
Tabela 5 – Resultados do novo modelo .................................................................... 58
Tabela 6 – Resultados do modelo disjuntivo adaptado ............................................. 59
Tabela 7 – Resultados do modelo de Kondili adaptado ............................................ 60
Tabela 8 – Resultados do modelo de kondili adaptado e revisado ........................... 61
Tabela 9 – Resumo das formulações mais eficientes por instância .......................... 62
Tabela 10 – Redução do tempo de resolução dos modelos com variáveis indexadas
no tempo com alguma restrição como fluxo em rede em comparação ao modelo de
kondili adaptado ........................................................................................................ 64
Tabela 11 – Resultados das formulações para uma instância 8 x 8 com tempos de
processamento entre 1 e 5 UT, semente 3 e solução ótima igual 266 ...................... 66
Tabela 12 – Resultados das formulações para uma instância 8 x 8 com tempos de
processamento entre 1 e 10 UT, semente 6 e solução ótima igual 468 .................... 68
Tabela 13 – Descrição das camadas de um típico duto ............................................ 76
Tabela 14 – Exemplo de plano de produção ............................................................. 78
Tabela 15 – Distâncias (metros) entre locais do exemplo ......................................... 79
Tabela 16 – Instantes e locais de liberação das bobinas do exemplo ....................... 79
Tabela 17 – Usos definidos pelo plano de produção do exemplo ............................. 80
Tabela 18 – Alocação das bobinas na solução do exemplo ...................................... 82
Tabela 19 – Movimentação das bobinas vazias na solução do exemplo .................. 82
Tabela 20 – Quantidade de bobinas e total de instantes de liberação por diâmetro . 88
Tabela 21 – Dados dos usos considerados no trabalho ............................................ 98
Tabela 22 – Matriz distância entre máquinas .......................................................... 119
Tabela 23 – Solução ótima da alocação de bobinas aos usos ................................ 120
LISTA DE ABREVIATURAS, SIGLAS E SÍMBOLOS
𝛼 tempo mínimo entre duas alocações consecutivas de uma
bobina a usos
𝛿𝑘−(𝑢) conjunto de arcos de 𝐺𝑘 entrando no vértice 𝑢 ∈ 𝑉𝑘
𝛿𝑘+(𝑢) conjunto de arcos de 𝐺𝑘 deixando o vértice 𝑢 ∈ 𝑉𝑘
∑ 𝑤𝑗(1 − 𝑒−𝑟𝐶𝑗) tempo total de conclusão ponderado descontado
∑ 𝑤𝑗𝐶𝑗 tempo total de conclusão ponderado
∑ 𝑤𝑗𝑇𝑗 atraso total ponderado
∑ 𝑤𝑗𝑈𝑗 número ponderado de tarefas atrasadas
𝜎ℎ𝑗 h-ésima operação da tarefa j
𝑎𝑖𝑗 limite de fluxo de (i,j)
𝐴𝑘 conjunto de arcos do grafo direcionado das bobinas de tamanho
k
𝑏𝑖𝑗 limite de fluxo de (i,j)
𝑏𝑘(𝑟) número de bobinas liberadas de tamanho k
batch(b) processamento em lotes
block bloqueio
brkdwn paradas
𝑐𝑖𝑗 coeficiente de custo de (i,j)
𝐶𝑚𝑎𝑥 makespan
𝑐𝑢𝑣𝑘 custo de movimentação de uma bobina de tamanho k de 𝑒𝑙(𝑢)
até 𝑠𝑙(𝑣)
𝑑𝑖𝑗 distância entre um par de locais 𝑖, 𝑗 ∈ 𝐿
𝑑𝑗 prazo em que a tarefa j deve estar finalizada
DLL Dynamic Link Library
𝑒𝑖𝑗𝑡 variável binária que é igual a 1 se a tarefa j não começar na
máquina i no momento t
𝑒(𝑟) instante de liberação de bobinas
𝑒(𝑢) instante final de um uso
𝑒𝑙(𝑢) local final de um uso
𝑒𝑙(𝑟) local de liberação de bobinas
𝑓𝑖𝑡 variável binária que se iguala a 1 quando a máquina i permanece
ociosa no período t
FIFO First In First Out
ℎ𝑖𝑘 variável que representa o tempo de início do processamento da
tarefa na k-ésima posição da máquina i
𝐽𝑚 job shop
JSSP job shop scheduling problem
𝐾 conjunto de tamanhos do diâmetro do tambor das bobinas
𝐹𝑚 flow shop
𝐹𝐹𝑐 flow shop flexível
𝐹𝐽𝑐 job shop flexível
fmls famílias de tarefa
𝐺𝑘 grafo direcionado das bobinas de tamanho k
𝐿 conjunto de locais na fábrica de dutos flexíveis
𝑀𝑗 restrições de elegibilidade de máquina
nwt sem espera
𝑂𝑚 open shop
𝑝𝑖𝑗 tempo de processamento da tarefa j na máquina i
𝑃𝑚 máquinas idênticas em paralelo
PAB problema de alocação de bobinas
PSJS problema de sequenciamento de job shop
PI programação inteira
PIM programação inteira mista
prec restrições de precedência
prmp preempção
prmu permutação
𝑞𝑖𝑗𝑘 variável de excesso relacionada à máquina i e às tarefas j e k
𝑄𝑚 máquinas em paralelo com diferentes velocidades
rijk variável binária igual a 1 se a k-ésima operação da tarefa j for
processada na máquina i e 0
𝑅𝑘 conjunto de liberações de bobinas de tamanho k
RAP reel allocation problem
𝑟𝑗 data de liberação da tarefa j
𝑅𝑚 diferentes máquinas em paralelo
rcrc recirculação
𝑠𝑖 suprimento do nó i
𝑠𝑖𝑗 variável contínua que representa o tempo de início da tarefa j na
máquina i
𝑠𝑗𝑘 tempo de configuração que depende da sequência de
processamento entre as tarefas j e k
𝑠(𝑢) instante de início de um uso
𝑠𝑙(𝑢) local de início de um uso
𝑡𝑗 atraso da tarefa j, calculado como 𝑡𝑗 = 𝑚𝑎𝑥{0, 𝐶𝑗 − 𝑑𝑗}, onde 𝐶𝑗 é
o tempo de conclusão da tarefa j
U conjunto definido como {1, … , 𝐻} no problema de
sequenciamento de job shop ou conjunto de usos de bobina no
problema de alocação de bobinas
𝑈𝑖𝑗 conjunto dos tempos em que a tarefa j pode efetivamente
começar sua operação na máquina i sem exceder o tempo H
definido, uma vez que a tarefa j também precisa ser executada
em máquinas antes e/ou depois de i
𝑈𝑘 conjunto de usos que são compatíveis com bobinas de tamanho
k ou maiores
UT unidade de tempo
𝑤𝑗 peso atribuído à tarefa j
𝑉 número com valor grande
𝑉𝑘 conjunto de vértices
VBA Visual Basic for Applications
𝑥𝑖𝑗𝑡 variável binária que assume o valor igual a 1 caso a tarefa j
comece na máquina i no instante t
𝑥𝑢𝑣𝑘 variável binária que indica se uma bobina de tamanho k é
alocada a 𝑢 e em seguida é alocada para 𝑣
𝑧𝑖𝑗𝑘 variável binária que assume o valor 1 quando a tarefa j precede
a tarefa k na máquina i
𝑍𝑂𝑝𝑡 valor da solução ótima
𝑍𝑅𝐿 valor da solução ótima com relaxação linear
13
1 INTRODUÇÃO
Escalonamento ou sequenciamento consiste na função de alocar um
conjunto de tarefas a um conjunto de meios de produção ao longo de um
determinado intervalo de tempo com o objetivo de otimizar um ou mais indicadores
de desempenho. Assim, encontrar uma solução ótima para um problema de
escalonamento significa determinar a sequência de processamento das tarefas
capaz de maximizar ou minimizar uma ou mais funções objetivo. A principal
contribuição deste processo é a capacidade de planejamento e controle da produção
de bens e da prestação de serviços.
Este trabalho apresenta formulações de programação inteira para dois
problemas de escalonamento da produção. O primeiro se trata de um problema
teórico, clássico e de difícil resolução: o problema de sequenciamento de job shop.
Amplamente encontrado em várias indústrias, segundo Pinedo (2016), este
problema é classificado como NP-difícil e vem sendo estudado há aproximadamente
70 anos. O segundo é um problema real encontrado em uma fábrica e consiste em
definir a alocação ótima de bobinas utilizadas no armazenamento e transporte ao
longo da fabricação de dutos flexíveis para produção e exploração de petróleo e gás.
O autor não encontrou registros de trabalhos publicados na literatura que abordem
este problema.
Essa dissertação está estruturada em seis capítulos. O presente capítulo
apresenta uma breve contextualização e introduz os problemas estudados. O
Capítulo 2 se refere à fundamentação teórica, onde os principais elementos
conceituais do estudo são abordados. O Capítulo 3 aborda especificamente a
formulação proposta para o problema de sequenciamento de job shop. Neste
capítulo, há introdução, metodologia da pesquisa, proposição do novo modelo
matemático, exemplo ilustrativo, apresentação das formulações de referência para
os testes e discussão dos resultados. O Capítulo 4 trata do modelo de programação
inteira proposto para resolver o problema de alocação de bobinas na produção de
dutos flexíveis. Neste capítulo, há introdução, contextualização do produto e seu
processo de fabricação, exemplo ilustrativo, apresentação da formulação
matemática proposta, implementação e realização do estudo de caso. O Capítulo 5
expõe a conclusão do trabalho e as sugestões para trabalhos futuros. O Capítulo 6
14
organiza as referências bibliográficas utilizadas na elaboração desta pesquisa e, por
fim, o Capítulo 7 apresenta os apêndices.
1.1 MOTIVAÇÃO DO TRABALHO
Os problemas de escalonamento permitem a modelagem de um vasto
conjunto de situações reais e permeiam diversas áreas do conhecimento. Pinedo
(2016) cita alguns exemplos de problemas deste tipo encontrados em uma fábrica
de sacola de papel, em uma instalação de manufatura de semicondutores, em um
aeroporto no processo de alocação de portões de embarque e em uma unidade de
processamento central de um computador para sequenciamento de tarefas. Nesta
dissertação, são tratados especificamente dois problemas desta classe: o
sequenciamento de job shop e a alocação de bobinas para fabricação de dutos
flexíveis.
O problema de sequenciamento de job shop é relacionado à indústria de
manufatura e apresenta muitas aplicações práticas para a programação de
operações em ambientes de produção (JAMILI, 2016). Outro fator que torna o
problema interessante para se tratar em um estudo é o seu nível de complexidade.
O sequenciamento das tarefas de um job shop, como explicado por Akram, Kamal e
Zeb (2016), é um problema NP-difícil bem conhecido de otimização combinatória.
O interesse pela investigação deste tipo de problema vem aumentando na
literatura ao longo dos últimos anos, o que pode ser percebido a partir da análise da
produção científica de 2006 a 2017 sobre este tema.
Figura 1 – Produção científica relacionada ao tema "job shop"
Fonte: Scopus – Acesso em janeiro de 2018
15
Os números apresentados na Figura 1 resultam da consulta realizada na
base de periódicos Scopus a partir da expressão “job shop” nos títulos dos
documentos, resumos e palavras chaves.
O problema de alocação de bobinas é um problema bem específico da
fabricação de dutos flexíveis, que pertence à indústria de óleo e gás. Resolver este
problema exige sequenciar a utilização de bobinas para transporte e
armazenamento de dutos ao longo de sua fabricação e em função de uma de suas
dimensões. Problemas como este vêm recebendo bastante atenção da comunidade
científica, mais que triplicando o número de publicações sobre o tema
“sequenciamento” de 2000 até 2017. A Figura 2 evidencia essa tendência.
Figura 2 – Produção científica relacionada ao tema "scheduling"
Fonte: Scopus – Acesso em janeiro de 2018
Esse gráfico apresenta números resultantes da consulta realizada na base
de periódicos Scopus a partir da expressão “scheduling” nos títulos dos documentos,
resumos e palavras chaves e limitando a pesquisa a quatro áreas do conhecimento:
ciência da computação, engenharia, matemática e ciência da decisão.
A pesquisa relacionada à programação inteira também se mostrou
promissora ao demonstrar um aumento das publicações sobre o tema nos últimos
anos. A Figura 3 esboça essa inclinação.
16
Figura 3 – Produção científica relacionada ao tema "integer programming"
Fonte: Scopus – Acesso em janeiro de 2018
Os dados para elaboração do gráfico anterior foram extraídos de uma
consulta na base de periódicos Scopus a partir da expressão “integer programming”
nos títulos dos documentos, resumos e palavras chaves.
1.2 DESCRIÇÃO DO PROBLEMA
Lakatos e Marconi (2003) definem o problema de uma pesquisa como uma
dificuldade, que pode ser teórica ou prática, relativa ao conhecimento de algo de real
importância, para a qual uma solução deve ser encontrada. Gil (2009) complementa
esta visão e defende que um problema é de natureza científica quando envolve
variáveis que podem ser classificadas como testáveis, isto é, são passíveis de
observação ou de manipulação.
Lakatos e Marconi (2003) citam cinco aspectos a serem analisados para que
um problema seja considerado apropriado:
1) Viabilidade: possibilidade de ser resolvido de forma eficaz por meio da
pesquisa;
2) Relevância: capacidade de trazer novos conhecimentos;
3) Novidade: adequação ao nível atual de evolução científica e
capacidade de trazer novo enfoque e/ou soluções;
4) Exequibilidade: possibilidade de chegar a uma conclusão válida;
5) Oportunidade: atendimento a interesses particulares e gerais.
17
Os dois problemas que norteiam esta pesquisa são:
1) Resolver de maneira eficiente o problema de sequenciamento de job
shop e minimizar o atraso total ponderado das tarefas;
2) Alocar eficientemente o menor número possível e/ou com o menor
deslocamento possível as bobinas utilizadas para armazenamento e
transporte de dutos flexíveis ao longo do seu processo de fabricação.
Entende-se como eficiência, neste estudo, a capacidade de resolver uma
determinada instância em um tempo computacional inferior aos demais métodos
atualmente propostos ou em tempo razoável e a propriedade de ser aplicável nas
atividades de planejamento de curto prazo.
1.3 JUSTIFICATIVA E RELEVÂNCIA DO ESTUDO
As justificativas do estudo dos dois problemas apresentados nesta
dissertação estão listadas abaixo:
1) Para o sequenciamento de job shop é o avanço na compressão da
abordagem de programação inteira em função de sua complexidade e
pelas oportunidades que a otimização pode possibilitar;
2) Para a alocação das bobinas é a possibilidade de melhorar o
processo de planejamento encontrado na operação de uma fábrica de
dutos flexíveis.
A relevância do estudo foi identificada conforme exposto a seguir:
1) Alto potencial de aplicabilidade dos métodos desenvolvidos uma vez
que o job shop é um ambiente de produção comum na indústria
brasileira e mundial. Além disso, as técnicas utilizadas neste trabalho
acadêmico podem servir de referência para resolução e tratamento de
outros problemas NP-difíceis;
2) O modelo proposto para a alocação ótima de bobinas pode aumentar
a eficiência de utilização dos recursos da fábrica analisada e
contribuir para a redução de custos do produto vendido. Em última
escala, esse ganho pode ser revertido para os operadores dos
18
campos de petróleo e gás e até para os consumidores finais de seus
derivados.
1.4 OBJETIVO GERAL
Para Lakatos e Marconi (2003) toda pesquisa deve apresentar um objetivo
determinado com a finalidade de definir o que será procurado e o que se pretende
atingir. Os mesmos autores complementam que o objetivo torna o problema
explícito, o que contribui para o aumento de conhecimento acerca do assunto
tratado.
Os objetivos gerais desta dissertação consistem em:
1) Propor uma formulação para resolver o problema de sequenciamento
de job shop com função objetivo de minimizar o atraso total
ponderado de forma eficiente;
2) Elaborar um modelo capaz de resolver o problema de alocação das
bobinas para transporte e armazenamento de dutos flexíveis ao longo
de sua fabricação de maneira ótima e em tempo razoável para o
processo de planejamento.
1.5 OBJETIVOS ESPECÍFICOS
O desdobramento do objetivo geral relativo ao problema de sequenciamento
de job shop resulta nos seguintes objetivos específicos:
Identificar e analisar as melhores formulações de PI utilizadas para resolver o
problema de sequenciamento de job shop;
Adaptar as melhores formulações encontradas para o caso em que a função
objetivo consiste em minimizar o atraso total ponderado;
Implementar melhorias em uma formulação de maneira a diminuir o tempo e
esforço computacional na resolução das diferentes instâncias;
Realizar testes com a formulação proposta e as de referência;
Mensurar os resultados obtidos com os testes computacionais e comparar o
desempenho dos diferentes modelos;
19
Definir as limitações do estudo de modo a delinear as condições nas quais as
vantagens da aplicação do método proposto podem ser reproduzidas.
O objetivo geral referente ao problema de alocação de bobinas leva aos
seguintes objetivos específicos:
Resolver o problema de alocação de bobinas e encontrar soluções ótimas;
Reduzir o tempo do processo de planejamento da utilização das bobinas;
Diminuir a movimentação das bobinas na planta fabril ao longo da fabricação
de dutos flexíveis;
Aumentar a taxa de uso das bobinas, o que implica na redução do tempo
ocioso desse tipo de equipamento;
Reduzir investimentos na aquisição de novas bobinas;
Reduzir o capital imobilizado em bobinas que não precisariam estar
participando do processo de fabricação dos dutos flexíveis.
1.6 DELIMITAÇÕES DO ESTUDO
A pesquisa foi delimitada conforme os pontos a seguir:
1) O problema de sequenciamento de job shop se refere à versão
clássica do problema, isto é, aquele em que não há recirculação e
não é composto por centros de trabalho. O foco desta dissertação é a
análise e aplicação de métodos exatos para otimização, portanto o
desenvolvimento de técnicas heurísticas não faz parte do escopo
deste trabalho;
2) Para o modelo de alocação de bobinas somente foram consideradas
aquelas destinadas ao transporte e armazenamento dos dutos
flexíveis enquanto estes estão sendo fabricados. Isso exclui do estudo
as bobinas enviadas para o cliente ou utilizadas para transporte e
armazenamento dos dutos flexíveis já acabados. Somente o diâmetro
do tambor das bobinas foi considerado, neste trabalho, como uma
restrição. A dimensão dos flanges foi desconsiderada por não
impactar na operação fabril nem oferecer riscos às propriedades dos
dutos flexíveis. Essa pesquisa também não visa realizar a otimização
20
da fabricação de dutos flexíveis. O plano de produção é considerado
uma entrada já definida para o modelo de alocação de bobinas.
1.7 METODOLOGIA E TRABALHO REALIZADO
Segundo Lakatos e Marconi (2003), pesquisa é um procedimento formal
realizado com um método de pensamento reflexivo, que demanda um tratamento
científico e compõe o meio pelo qual a realidade será conhecida ou verdades
parciais serão descobertas.
Gil (2009) complementa esta visão ao definir pesquisa como o procedimento
racional e sistemático cuja finalidade é encontrar respostas aos problemas que se
apresentam. A pesquisa tem sua função requisitada quando não há informações
disponíveis para obter respostas a um determinado problema ou no caso em que as
informações disponíveis não estão suficientemente organizadas, o que impossibilita
a correlação adequada ao problema.
Lakatos e Marconi (2003) propõem que o desenvolvimento de um projeto de
pesquisa seja estruturado em seis etapas:
1) Seleção do tópico ou problema para a investigação;
2) Definição e diferenciação do problema;
3) Levantamento de hipóteses de trabalho;
4) Coleta, sistematização e classificação dos dados;
5) Análise e interpretação dos dados;
6) Relatório do resultado da pesquisa.
Desse modo, a base metodológica desta pesquisa para abordar o problema
de sequenciamento de job shop é composta de quatro fases:
1) Levantamento e análise das melhores formulações;
2) Identificação e implementação de oportunidades de melhoria;
3) Realização de testes com a nova formulação e as de referência;
4) Comparação dos resultados obtidos.
21
A primeira etapa consiste em identificar e analisar as melhores formulações
utilizadas para resolução do problema de sequenciamento de job shop. A próxima
fase tem como objetivo buscar e implementar oportunidades de melhoria que sejam
capazes de trazer aumento de velocidade na resolução das diferentes instâncias.
Em seguida, é necessário realizar testes para medir o desempenho da nova
formulação proposta e das demais que são referência para a comparação. Por fim,
as diferentes abordagens do problema são comparadas como forma de medir quais
resultados apresentam mais vantagens em termos de eficiência.
Para elaboração e aplicação do modelo de alocação de bobinas foi utilizada
a seguinte metodologia:
1) Reconhecimento e levantamento de dados do processo fabril;
2) Elaboração e programação do modelo;
3) Aplicação do estudo de caso;
4) Discussão dos resultados e comparação com a situação anterior.
A fase inicial consistiu em mapear o processo fabril e coletar os dados
referentes ao plano de produção dos dutos flexíveis. Isso permitiu o agrupamento de
atividades consecutivas realizadas em um mesmo duto por máquinas diferentes.
Após o reconhecimento e estudo da operação da fábrica, foi possível elaborar o
modelo matemático e implementar sua programação com a utilização do UFFLP. A
terceira etapa foi a aplicação do modelo para o caso real descrito no plano de
produção. Com a solução do problema, houve a análise dos resultados e a
realização de um comparativo com a situação anterior, tanto em termos de eficiência
do processo de planejamento quanto em ganhos de utilização das bobinas.
1.8 ORGANIZAÇÃO DO TRABALHO
Essa dissertação está dividida em cinco capítulos mais a seção destinada
aos apêndices. Assim, no Capítulo 1 referente à introdução, buscou-se
contextualizar o tema da pesquisa, descrever os problemas em torno do qual a
dissertação foi escrita, apresentar as motivações e os objetivos e delimitar o escopo
do trabalho.
22
O Capítulo 2 aborda a fundamentação teórica dos assuntos centrais
discutidos neste estudo. Assim, foram feitas consultas aos mais importantes livros
que compõem a literatura de cada tópico tratado. Em paralelo, houve um
levantamento junto às bases de periódicos mais consistentes e reconhecidas pela
comunidade científica internacional a fim de coletar o que há de estado da arte em
matéria de conhecimento.
O Capítulo 3 é destinado ao problema de sequenciamento de job shop. Nele,
é encontrada a Seção 3.1 que trata de sua introdução e a Seção 3.2, que apresenta
a metodologia empregada para estudo deste problema. Em termos gerais, a partir
da fundamentação teórica foi possível levantar as principais técnicas utilizadas
recentemente na resolução do problema de sequenciamento de job shop e propor
melhorias que tragam ganhos em termos de eficiência. Após a realização de uma
comparação detalhada das abordagens foi possível identificar as vantagens da nova
proposição.
A Seção 3.3 apresenta a formulação proposta para resolver o problema de
sequenciamento de job shop com função objetivo de minimizar o atraso total
ponderado e detalha as características da nova abordagem. Nesta seção, as
variáveis de decisão, bem como as restrições que foram propostas são
especificadas e explicadas detalhadamente.
A Seção 3.4 propõe um exemplo ilustrativo de resolução do problema para
aprofundar o entendimento do leitor. A Seção 3.5 introduz as formulações de
referência utilizadas para os testes comparativos. A Seção 3.6 se refere aos
resultados obtidos com as formulações adaptadas e com a nova proposição. A partir
de uma comparação foi possível mapear em que condições as diferentes
abordagens possuem vantagens e desvantagens.
O Capítulo 4 aborda o problema de alocação de bobinas. Assim, na Seção
4.1, é feita sua introdução e na Seção 4.2, a metodologia utilizada para abordar este
problema é definida. Em linhas gerais, foi realizado o mapeamento do processo
fabril de dutos flexíveis e o levantamento de dados do plano de produção. Essa
etapa inicial viabilizou a elaboração e programação do modelo matemático. Após a
conclusão do modelo houve sua aplicação no estudo de caso representativo de uma
situação real. A resolução do problema de alocação de bobinas gerou resultados
23
que foram comparados à situação antes da implementação do novo método
proposto.
Na Seção 4.3, é apresentado o que é um duto flexível e como ocorre seu
processo de fabricação. Nesta seção, as principais camadas de um duto e suas
funções são detalhadas, as máquinas onde cada camada é fabricada são definidas
e as partes de uma bobina convencional são apresentadas.
Na Seção 4.4, é proposto um exemplo ilustrativo completo. Neste exemplo, é
resolvida uma instância pequena e simples do problema para aprofundar o
entendimento do leitor e tornar a abordagem do problema mais clara. Na Seção 4.5,
o modelo matemático é formulado e na Seção 4.6, ocorre o detalhamento de sua
implementação em um caso real.
O Capítulo 5 retoma os principais objetivos e resultados do trabalho, expõe
as conclusões e identifica oportunidades para novas pesquisas. Os Capítulos 6 e 7
estão relacionados, respectivamente, às referências bibliográficas que suportaram
este estudo e aos apêndices, onde mais detalhes sobre a pesquisa podem ser
consultados.
24
2 FUNDAMENTAÇÃO TEÓRICA
2.1 ESTRUTURA E NOTAÇÕES PARA MODELOS DETERMINÍSTICOS DE
ESCALONAMENTO
De acordo com Pinedo (2016) em todos os problemas de escalonamento
(scheduling problems) considerados, tanto o número de tarefas (jobs) quanto o de
máquinas são finitos. Atribui-se ao número de tarefas a letra n, enquanto a letra m é
utilizada para denominar o número de máquinas do problema. É usual que a letra j,
subscrita a uma variável, represente uma tarefa específica e que a letra i, da mesma
maneira, se refira a uma determinada máquina. Para representar uma etapa de
processamento ou operação da tarefa j na máquina i utiliza-se o par (i, j).
Algumas características, apresentadas a seguir, podem estar associadas a
uma tarefa j:
Tempo de processamento (𝑝𝑖𝑗): Refere-se ao tempo de processamento
da tarefa j na máquina i. Se o tempo de processamento da tarefa j for
independente da máquina em que a operação está sendo realizada ou só
existir uma máquina pela qual a tarefa é processada, a letra subscrita i é
omitida;
Data de liberação (𝑟𝑗): É o tempo no qual a tarefa j chega ao sistema
produtivo. Em outras palavras, é o tempo mais cedo no qual a tarefa j
pode começar a ser processada em uma máquina. Outra nomenclatura,
citada por Pinedo (2016) em sua obra, para essa mesma característica é
a data de prontidão da tarefa j;
Prazo de finalização (𝑑𝑗): Representa a data esperada de finalização da
tarefa j no processo produtivo. Caso o prazo de finalização não seja
cumprido, o sistema é penalizado com um atraso. Nos casos em que o
prazo deve obrigatoriamente ser atendido, muda-se a representação para
(�̅�𝑗) e denomina-se prazo limite (deadline);
Peso (𝑤𝑗): Denota a importância de uma tarefa em relação às demais do
sistema e constitui um fator de prioridade. Pode estar atrelado ao custo do
não cumprimento do prazo de finalização de uma tarefa e sua
consequente permanência no processo de produção.
25
Um problema de sequenciamento geralmente é descrito em função de uma
tríplice 𝛼|𝛽|𝛾. O campo 𝛼 descreve o ambiente de máquinas do processo e
apresenta uma única entrada. O campo 𝛽, por sua vez, fornece detalhes das
características e restrições de processamento, podendo conter uma única entrada,
múltiplas entradas ou mesmo nenhuma. Finalmente, o campo 𝛾 explicita o objetivo a
ser minimizado e, embora possa apresentar mais de uma entrada, frequentemente
apresenta uma única.
As próximas três subseções tratam dos campos citados anteriormente e
mostram as principais possibilidades de entrada e suas representações:
2.1.1 Campo 𝛂 – Ambientes de máquina
As possibilidades de ambientes de máquina a serem preenchidas no campo
α são as listadas a seguir:
Máquina única (1): A situação onde há somente uma máquina é o caso
mais simples de todos os ambientes de máquina e também um caso
especial de todos os outros casos mais complicados;
Máquinas idênticas em paralelo (𝑃𝑚): Neste ambiente há m máquinas
dispostas paralelamente. Assim, uma tarefa j precisa passar por somente
uma operação e pode ser processada em qualquer uma das m máquinas
ou qualquer uma que pertença a um determinado subconjunto. No caso
em que a tarefa j não puder ser processada em qualquer uma das m
máquinas do sistema, mas somente em qualquer uma do subconjunto 𝑀𝑗,
então o atributo 𝑀𝑗 é acrescentado ao campo 𝛽;
Máquinas em paralelo com diferentes velocidades (𝑄𝑚): Neste arranjo,
também chamado de máquinas uniformes, há m máquinas em paralelo
com diferentes velocidades, onde denota-se por 𝑣𝑖 a velocidade da
máquina i. Assumindo que a tarefa j é integralmente processada pela
máquina i, o tempo de processamento 𝑝𝑖𝑗 que a tarefa j gasta na máquina
i pode ser calculado como 𝑝𝑗 / 𝑣𝑖. Se todas as máquinas apresentarem a
mesma velocidade de processamento, então este ambiente se torna
idêntico ao mencionado anteriormente;
26
Diferentes máquinas em paralelo (𝑅𝑚): Neste layout há m diferentes
máquinas em paralelo, sendo assim uma generalização do ambiente
anterior. Tomando-se como premissa que a tarefa j é processada somente
pela máquina i, o tempo de processamento 𝑝𝑖𝑗 gasto pela tarefa j na
máquina i pode ser obtido dividindo-se 𝑝𝑗 por 𝑣𝑖𝑗, ou seja, a velocidade na
qual a máquina i pode processar a tarefa j;
Flow shop (𝐹𝑚): Há m máquinas em série nas quais cada tarefa precisa
ser processada. Todas as tarefas apresentam a mesma rota de
processamento, isto é, precisam passar pela máquina 1, depois pela
máquina 2 até a máquina m. Uma vez concluída a etapa em uma
máquina, a tarefa se junta à fila para a próxima máquina. Geralmente, as
filas são organizadas pela lógica First In First Out (FIFO), ou seja, a tarefa
que entrou na fila primeiro tem prioridade na saída. Quando esta lógica é
adotada, o flow shop é chamado de flow shop de permutação e incluem-
se no campo 𝛽 as letras prmu;
Flow shop flexível (𝐹𝐹𝑐): É uma generalização do flow shop e do
ambiente de máquinas em paralelo. Em vez de m máquinas em série, há c
estágios em série compostos por um número de máquinas idênticas em
paralelo. Cada tarefa apresenta a mesma sequência pelos diferentes
estágios, isto é, cada tarefa precisa passar pelo estágio 1, pelo estágio 2
até chegar ao estágio c. Cada tarefa precisa passar por apenas uma
máquina de cada estágio, sendo que qualquer uma pode realizar o
processamento;
Job shop (𝐽𝑚): Em um job shop há m máquinas e n tarefas que
apresentam rotas de processamento diferentes. É feita uma distinção
entre os casos em que uma tarefa visita uma única vez cada máquina e
os casos em que uma tarefa é processada mais de uma vez na mesma
máquina. No último caso, é dito que o job shop apresenta recirculação e
as letras rcrc devem ser acrescentadas no campo 𝛽;
Job shop flexível (𝐹𝐽𝑐): É a generalização do job shop e do ambiente de
máquinas em paralelo. Em vez de m máquinas em série, há c centros de
trabalho compostos por um número de máquinas idênticas. Cada tarefa
apresenta sua própria rota de processamento pelos diferentes centros de
27
trabalho. Uma tarefa precisa ser processada em uma máquina do centro
uma única vez e qualquer máquina é capaz de realizar a operação. Caso
uma tarefa precise visitar um centro de trabalho mais de uma vez, então
as letras rcrc devem ser acrescentadas no campo 𝛽, indicando que o job
shop flexível tem a característica de recirculação;
Open shop (𝑂𝑚): Neste ambiente, há m máquinas nas quais cada tarefa
precisa passar uma vez. Entretanto, o tempo de processamento de uma
tarefa j em uma máquina i pode ser igual a zero. Não existem restrições
para as rotas de processamento das tarefas, ou seja, as tarefas não
possuem sequências predeterminadas de visita às máquinas.
2.1.2 Campo 𝛃 – Detalhes das características e restrições de processamento
As características e restrições de processamento no campo β podem incluir
múltiplas entradas. Algumas dessas possibilidades podem ser observadas a seguir:
Datas de liberação (𝑟𝑗): Quando este símbolo aparece no campo β, então
a tarefa j não pode iniciar seu processamento antes da data de liberação.
Caso não seja especificado, não há restrições a respeito do início de
processamento;
Preempção (prmp): Preempções implicam que não é necessário manter
uma tarefa em uma máquina do início até a sua conclusão. É possível
programar a produção de modo que o processamento de uma tarefa seja
interrompido para que outra tarefa seja processada na máquina. Essa
movimentação não faz com que a quantidade processada da tarefa
interrompida seja perdida, sendo necessário, posteriormente, somente
completar o processamento na mesma máquina ou em uma máquina
idêntica em paralelo. Quando essa característica está presente em um
ambiente de produção, as letras prmp são acrescentadas no campo β.
Caso não haja nenhuma especificação nesse sentido, a preempção não é
permitida;
Restrições de precedência (prec): Restrições de precedência podem
acontecer em um ambiente com uma única máquina ou com máquinas
em paralelo, garantindo que uma tarefa inicie seu processamento
28
somente após a conclusão de outra. Há algumas formas especiais de
restrições de precedência, como as cadeias, em que cada tarefa tem no
máximo uma predecessora e uma sucessora. Se cada tarefa tem no
máximo uma sucessora, então as restrições são chamadas de árvores
internas. Por outro lado, são chamadas de árvores externas, caso cada
tarefa apresente no máximo uma predecessora. Se as letras prec não
estiverem presentes no campo β, então as tarefas não estão sujeitas às
restrições de precedência;
Tempo de configuração dependente da sequência (𝑠𝑗𝑘): 𝑠𝑗𝑘 representa
o tempo de configuração que depende da sequência de processamento
entre as tarefas j e k. 𝑠0𝑘 e 𝑠𝑗0 são, respectivamente, o tempo de
configuração se a tarefa k for a primeira da sequência e o tempo de
limpeza caso a tarefa j seja a última da sequência. Caso o tempo de
configuração entre as tarefas j e k também dependam da máquina em que
o processamento será realizado, então a letra subscrita i é adicionada à
variável, tornando-se 𝑠𝑖𝑗𝑘. Caso 𝑠𝑗𝑘 não apareça no campo β, os tempos
de configuração são tidos como zero ou independentes da sequência,
neste caso já estão considerados no tempo de processamento;
Famílias de tarefa (fmls): Neste caso, as n tarefas pertencem a F
famílias. As tarefas pertencentes à mesma família podem ter diferentes
tempos de processamento, no entanto não requerem tempo de
configuração em uma máquina quando uma tarefa é processada depois
de outra da mesma família. Por outro lado, quando uma máquina
processa uma tarefa de uma família g e depois processa outra de uma
família h, então se incorre em um tempo de configuração. Se este tempo
depende das famílias g e h, a variável é tida como 𝑠𝑔ℎ, se depende
somente de uma das famílias, por exemplo a família h, então a variável
torna-se 𝑠ℎ. Caso não dependa de nenhuma família, a variável é escrita
simplesmente como s;
Processamento em lotes (batch(b)): Uma máquina pode ser capaz de
processar um número de tarefas, assume-se b, simultaneamente. O
tempo de processamento das tarefas em um lote pode não
necessariamente ser o mesmo e um lote completo só é concluído quando
29
a última tarefa do lote é finalizada. Isso implica que o tempo de conclusão
do lote é determinado pelo tempo de processamento mais longo dentre as
tarefas. Se 𝑏 = 1, então o problema é convertido em um ambiente
convencial de sequenciamento. Há casos em que se assume que não há
limite do número de tarefas que uma máquina pode processar, adotando,
assim, 𝑏 = ∞;
Paradas (brkdwn): Paradas de máquinas implicam que uma máquina
pode não estar continuamente disponível. Os períodos nos quais uma
máquina não está disponível são assumidos como fixos, como nos casos
onde há trocas ou manutenções programadas. Se há um número de
máquinas idênticas em paralelo, o número de máquinas disponíveis em
um dado momento é uma função do tempo, isto é, m(t). Paradas de
máquina são conhecidas também como restrições de disponibilidade de
máquina;
Restrições de elegibilidade de máquina (𝑀𝑗): Esta condição está
relacionada aos ambientes com m máquinas em paralelo. Quando 𝑀𝑗 está
presente, nem todas m máquinas são capazes de processar a tarefa j.
Assim, o conjunto 𝑀𝑗 denota o conjunto de máquinas que pode processar
a tarefa j. Se o campo 𝛽 não contém 𝑀𝑗, então a tarefa j pode ser
processada em qualquer uma das m máquinas;
Permutação (prmu): Esta condição é relativa aos ambientes flow shop e
se refere a uma restrição que impõe que as filas em frente a cada
máquina operem de acordo com a lógica FIFO, que prioriza o
processamento das tarefas que chegaram primeiro. Isso implica que a
ordem ou a permutação que as tarefas passaram pela primeira máquina é
mantida ao longo de todo sistema;
Bloqueio (block): Bloqueio é um fenômeno que pode ocorrer em flow
shops e está relacionado à limitação de estoque entre duas máquinas
sucessivas. Quando o estoque está cheio, a máquina anterior no fluxo de
produção não pode liberar uma tarefa completa, bloqueando a próxima
tarefa da sequência de processamento. Nos casos em que se assume
que não há estoque entre duas máquinas consecutivas, uma tarefa não
30
pode deixar uma máquina enquanto a tarefa precedente não tiver sido
concluída na próxima máquina;
Sem Espera (nwt): Este requisito está relacionado aos ambientes flow
shop e se refere à condição de que as tarefas não podem esperar entre
máquinas consecutivas. Isso obriga que uma tarefa tenha o início de seu
processamento na primeira máquina atrasada para garantir que não
haverá tempo de espera para nenhuma máquina ao longo do sistema;
Recirculação (rcrc): Recirculação pode ocorrer em um job shop ou flow
shop quando uma tarefa pode visitar uma máquina ou um centro de
trabalho mais de uma vez.
2.1.3 Campo 𝛄 – Objetivos de minimização
Embora diferentes objetivos possam ser escolhidos para serem minimizados
em um sequenciamento, todos eles dependem de uma variável em comum: o tempo
de conclusão das tarefas, referenciado como 𝐶𝑗. O tempo de conclusão da operação
da tarefa j em uma máquina i é 𝐶𝑖𝑗. O objetivo também pode estar relacionado ao
prazo de finalização de uma tarefa. Nesses casos, há três principais funções de
penalidade consideradas:
a) O descumprimento de uma tarefa pode ser calculado por: 𝐿𝑗 = 𝐶𝑗 − 𝑑𝑗, que
é positivo quando a conclusão ocorre após o prazo de finalização e negativo
em caso de antecedência;
b) 𝑡𝑗, o atraso de uma tarefa, é obtido pela fórmula: max(𝐿𝑗,0), sempre sendo
positivo por ser o máximo entre duas medidas, descumprimento e zero;
c) A unidade de penalidade de uma tarefa é definida como:
𝑈𝑗 = {1, 𝑠𝑒 𝐶𝑗 > 𝑑𝑗;
0, 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜
Alguns exemplos de objetivos a serem incluídos no campo γ podem ser
listados abaixo:
Makespan (𝐶𝑚𝑎𝑥): O makespan é definido como max(𝐶1, … , 𝐶𝑛), isto é, é o
tempo de conclusão da última tarefa a deixar o sistema;
31
Máximo descumprimento (𝐿𝑚𝑎𝑥): Esta medida é definida como
max(𝐿1, … , 𝐿𝑛), e mensura a máxima diferença entre o prazo de
finalização e o tempo de conclusão de uma tarefa;
Tempo total de conclusão ponderado (∑ 𝑤𝑗𝐶𝑗): Também chamado de
tempo de fluxo ponderado, este indicador calcula a soma de todos os
tempos de conclusão das tarefas, ponderando os a partir de um peso
previamente escolhido;
Tempo total de conclusão ponderado descontado (∑ 𝑤𝑗(1 − 𝑒−𝑟𝐶𝑗):
Nesta medida, se uma tarefa não for concluída no tempo t, incorre-se em
um custo adicional 𝑤𝑗𝑟𝑒−𝑟𝑡𝑑𝑡 ao longo do período [t, t + dt]. Por outro lado,
caso a tarefa seja concluída no tempo t, o custo entre 0 e t será igual a
𝑤𝑗(1 − 𝑒−𝑟𝑡). O valor estimado para r deve estar entre 0 e 1;
Atraso total ponderado (∑ 𝑤𝑗𝑇𝑗): Neste objetivo, busca-se minimizar o
somatório ponderado dos atrasos das tarefas;
Número ponderado de tarefas atrasadas (∑ 𝑤𝑗𝑈𝑗): Essa medida procura
indicar o número de tarefas atrasadas, ponderando as por um peso pré-
estabelecido.
Muito esforço tem sido aplicado em pesquisas para planejamento e
sequenciamento da produção com utilização de programação inteira e programação
inteira mista (PIM) (PINEDO, 2005). Um modelo linear inteiro misto consiste em um
programa que envolve variáveis contínuas e inteiras e restrições lineares (POCHET
e WOLSEY, 2006). A seguir são exemplificados alguns trabalhos relevantes
publicados recentemente sobre o tema.
No estudo de Ham (2017), uma formulação de programação inteira mista foi
utilizada em uma fábrica de semicondutores para sequenciamento de um job shop
flexível com máquinas de processamento em lotes dispostas paralelamente. O
trabalho de Samarghandi e Behroozi (2017) propôs modelos de PIM e de
programação de restrições para minimizar o makespan de um flow shop sem espera
entre atividades sucessivas e cujas tarefas devem ser concluídas antes do prazo de
finalização. Na pesquisa de Nguyen et al. (2018), um modelo linear inteiro misto e
uma heurística são propostos para minimizar o tempo total de conclusão de um
problema específico de sequenciamento de máquinas paralelas com um único
32
recurso adicional. As tarefas consideradas neste problema possuem função linear de
consumo de recursos semelhante.
Os resultados do estudo de Zhang et al. (2017) mostram avanço na
resolução de problemas de job shop flexível com eficiência energética utilizando PIM
e heurística de geração evolutiva. A pesquisa de Yazdani et al. (2017) introduz um
novo critério de otimização baseado na soma do máximo adiantamento e atraso
para o problema de sequenciamento de job shop com uso de PIM. No trabalho de
Jaramillo e Erkoc (2017), foi proposta uma formulação de PIM para minimizar o
atraso total ponderado e custo de horas extras no sequenciamento de uma máquina
única com tarefas que podem ser preemptivas.
O estudo de Tan, Mönch e Fowler (2017) se concentrou na proposta de uma
abordagem híbrida a partir de um modelo de PIM e de heurística de busca em
vizinhança para minimizar o atraso total ponderado de um problema de
sequenciamento de flow shop flexível com máquinas de processamento em lote. O
trabalho de Kongchuenjai e Prombanpong (2017) demonstra a aplicação de um
modelo de PIM com o objetivo de minimizar o tempo total de produção de peças de
modelos mistos em centros de trabalho com controle numérico computadorizado. PI
e fluxo em rede foram empregados no estudo de Fukasawa et al. (2002) para
otimizar o problema do fluxo de vagões de carga com a obtenção de resultados
efetivos para todas as instâncias até então utilizadas pelo maior operador de
ferrovias da América Latina. Torjai e Kruzslicz (2016) propuseram três formulações
de PIM para o problema de sequenciamento de caminhões que realizam o
transporte de biomassa e bons resultados foram obtidos na minimização de custos
de disponibilização de recursos e de tempo ocioso total dos caminhões.
2.2 JOB SHOP
Segundo Beemsterboer et al. (2017) a oferta de produtos diferenciados é
fundamental para a sobrevivência de muitas empresas. Neste sentido, o job shop
apresenta grande relevância por ser um ambiente de manufatura que possibilita
grande variedade de produção, com os pedidos passando por diferentes rotas e em
máquinas com propósitos diferentes. Muitos produtos manufaturados neste
ambiente são únicos em função da política de tratamento da demanda make-to-
33
order, isto é, o processo produtivo de um item se inicia somente após a efetivação
do pedido pelo cliente.
De acordo com Pinedo (2016) o job shop é um ambiente de produção onde
há um conjunto finito M de m máquinas e que cada tarefa, de um conjunto J, possui
uma rota predeterminada a seguir. Para cada tarefa j ∈ J é dada uma lista
(𝜎1𝑗,...,𝜎ℎ
𝑗, … , 𝜎𝑚
𝑗) de máquinas que representa a sequência de processamento da
tarefa j. Dessa forma, tem-se que 𝜎ℎ𝑗 é a h-ésima operação da tarefa j, enquanto 𝜎𝑚
𝑗é
a última operação da tarefa j, isto é, a última máquina em que a tarefa j é
processada. Nos casos em que uma tarefa precisa visitar uma máquina mais de uma
vez, atribui-se ao job shop a característica de recirculação. Além disso, para cada
tarefa j e cada máquina i é dado um tempo de processamento 𝑝𝑖𝑗que assume valores
inteiros não negativos.
O problema de sequenciamento de job shop apresenta diferentes
formulações na literatura. Manne (1960) propôs um modelo com restrições
disjuntivas e uma constante com valor relativo alto. Liao e You (1992) adicionaram
variáveis contínuas de excesso ao modelo disjuntivo de Manne com o objetivo de
aumentar o desempenho da resolução do problema. Bowman (1959) e Kondili,
Pantelides e Sargent (1993) desenvolveram um modelo com variáveis indexadas no
tempo, enquanto Wagner (1959) elaborou um modelo baseado nas posições das
máquinas.
Ku e Beck (2016) realizaram extensivos testes e análises computacionais
para definir qual modelo apresentava o melhor desempenho na resolução de
problemas para minimização do makespan. Neste estudo, cada máquina era capaz
de processar somente uma tarefa por vez e, uma vez iniciado o processamento de
uma tarefa em uma máquina, não poderia haver interrupções. Os pesquisadores
concluíram que o modelo disjuntivo proposto por Manne em 1960 é amplamente
mais eficiente que os demais. Problemas com instâncias de tamanho moderado, isto
é, com 15 tarefas e 15 máquinas podem ser resolvidos, se formulados com as
restrições disjuntivas de Manne, na média, em pouco mais de 15 minutos.
Problemas com instâncias menores, abaixo de 12 tarefas e 12 máquinas, podem ser
resolvidos praticamente de forma instantânea.
34
O modelo disjuntivo de Manne será chamado de modelo disjuntivo original
neste trabalho. Essa formulação possui as seguintes variáveis de decisão:
𝑠𝑖𝑗: variável contínua que representa o tempo de início da tarefa j na
máquina i;
𝑧𝑖𝑗𝑘: variável binária que assume o valor 1 quando a tarefa j precede a
tarefa k na máquina i.
A seguir, a formulação do modelo pode ser observada:
Min 𝐶𝑚𝑎𝑥 (1)
Sujeito a
𝑠𝜎ℎ
𝑗,𝑗
≥ 𝑠𝜎ℎ−1
𝑗,𝑗
+ 𝑝𝜎ℎ−1
𝑗,𝑗, ∀𝑗 ∈ 𝐽, ℎ = 2, … , 𝑚 (2)
𝑠𝑖𝑗 ≥ 𝑠𝑖𝑘 + 𝑝𝑖𝑘 − 𝑉. 𝑧𝑖𝑗𝑘, ∀𝑗, 𝑘 ∈ 𝐽, 𝑗 < 𝑘, ∀𝑖 ∈ 𝑀 (3)
𝑠𝑖𝑘 ≥ 𝑠𝑖𝑗 + 𝑝𝑖𝑗 − 𝑉. (1 − 𝑧𝑖𝑗𝑘), ∀𝑗, 𝑘 ∈ 𝐽, 𝑗 < 𝑘, ∀𝑖 ∈ 𝑀 (4)
𝐶𝑚𝑎𝑥 ≥ 𝑠𝜎𝑚
𝑗,𝑗
+ 𝑝𝜎𝑚
𝑗,𝑗, ∀𝑗 ∈ 𝐽 (5)
𝑠𝑖𝑗 ≥ 0, ∀𝑗 ∈ 𝐽, ∀𝑖 ∈ 𝑀 (6)
𝑧𝑖𝑗𝑘 ∈ {0,1), ∀𝑗, 𝑘 ∈ 𝐽, ∀𝑖 ∈ 𝑀 (7)
A função objetivo do modelo, que consiste em minimizar o makespan do
problema, está definida em (1). As Equações (2) são as restrições de precedência e
têm a função de assegurar que as operações das tarefas sejam executadas na
35
ordem preestabelecida. As Equações (3) e (4) são as restrições disjuntivas e são
responsáveis por garantir que somente uma tarefa é alocada em uma máquina de
cada vez. Para que as Restrições (3) e (4) estejam corretas e funcionem
adequadamente, é necessário que V seja um valor grande o suficiente. Na versão de
Ku e Beck (2016), definiu-se que 𝑉 = ∑ ∑ 𝑝𝑖𝑗𝑖∈𝑀𝑗∈𝐽 , pois o tempo de conclusão de
qualquer operação não pode ser maior que o somatório do tempo de processamento
de todas as operações. As Restrições (5) expressam que o makespan deve ser no
mínimo igual ao maior tempo de conclusão das últimas operações de todos as
tarefas. As Restrições (6) definem que os tempos de início de cada tarefa são
maiores ou iguais a zero. As Restrições (7) garantem a característica binária das
variáveis utilizadas nas restrições disjuntivas. Pan (1997) complementa que essas
variáveis estabelecem uma relação “um ou outro” para as restrições de não
interferência em máquinas individuais.
Liao e You (1992) propuseram uma nova versão do modelo disjuntivo ao
adicionar variáveis contínuas de excesso às Restrições (3). Dessa forma, as
Restrições (3) e (4) passam a ser escritas como:
𝑉. 𝑧𝑖𝑗𝑘 + (𝑠𝑖𝑗 − 𝑠𝑖𝑘) − 𝑝𝑖𝑘 = 𝑞𝑖𝑗𝑘, ∀𝑗, 𝑘 ∈ 𝐽, 𝑗 < 𝑘, ∀𝑖 ∈ 𝑀 (8)
𝑞𝑖𝑗𝑘 ≤ 𝑉 − 𝑝𝑖𝑗 − 𝑝𝑖𝑘, ∀𝑗, 𝑘 ∈ 𝐽, 𝑗 < 𝑘, ∀𝑖 ∈ 𝑀 (9)
Outra formulação analisada no estudo de Ku e Beck (2016) foi a com
variáveis indexadas no tempo proposta inicialmente por Kondili, Pantelides e
Sargent em um simpósio em Sydney, Austrália no ano de 1988, após
desenvolvimentos da formulação original introduzida por Bowman em 1959. Neste
trabalho, a formulação desenvolvida pelo trio será chamada de modelo de Kondili
original. A variável de decisão deste modelo é 𝑥𝑖𝑗𝑡, que é binária e tem valor igual a
1, se a tarefa j começa seu processamento na máquina i no tempo t. O conjunto 𝑈 é
definido como {1, … , 𝐻}, onde H indica o horizonte de tempo, ou seja, o maior tempo
em que uma tarefa pode começar seu processamento, sem o risco de perder a
solução ótima. O modelo matemático pode ser observado a seguir:
36
Min 𝐶𝑚𝑎𝑥 (10)
Sujeito a
∑ 𝑥𝑖𝑗𝑡 = 1
𝑡∈𝑈
, ∀𝑗 ∈ 𝐽, ∀𝑖 ∈ 𝑀 (11)
∑(𝑡 + 𝑝𝑖𝑗). 𝑥𝑖𝑗𝑡 ≤ 𝐶𝑚𝑎𝑥,
𝑡∈𝑈
∀𝑗 ∈ 𝐽, ∀𝑖 ∈ 𝑀 (12)
∑ ∑ 𝑥𝑖𝑗𝑡 ≤ 1
𝑡∈𝑇𝑖𝑗𝑡𝑗∈𝐽
,
∀𝑖 ∈ 𝑀, 𝑡 ∈
𝑈, 𝑜𝑛𝑑𝑒 𝑇𝑖𝑗𝑡 = {𝑡 −
𝑝𝑖𝑗 + 1, … , 𝑡}
(13)
∑ (𝑡 + 𝑝𝜎ℎ−1
𝑗,𝑗
) . 𝑥𝜎ℎ−1
𝑗,𝑗𝑡
≤ ∑ 𝑡. 𝑥𝜎ℎ
𝑗,𝑗𝑡
𝑡∈𝑈𝑡∈𝑈
, ∀𝑗 ∈ 𝐽, ℎ = 2, … , 𝑚 (14)
𝑥𝑖𝑗𝑡 ∈ {0,1} ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑈 (15)
A função objetivo está declarada em (10). As Restrições (11) garantem que
cada tarefa comece exatamente uma única vez em cada máquina. As Equações (12)
asseguram que o makespan é no mínimo equivalente ao tempo de conclusão mais
longo da última operação de todas as tarefas. As Restrições (13) fazem com que as
capacidades das máquinas sejam respeitadas ao longo de todo o período. As
Restrições (14) são responsáveis por manter a ordem das operações de cada tarefa
conforme definição prévia. As Restrições (15) impõem que a variável de decisão
seja binária.
O modelo de Wagner (1959) também foi analisado nos estudos de Ku e
Beck (2016) e baseia-se na alocação das tarefas em posições das máquinas. As
variáveis de decisão dessa formulação podem ser observadas a seguir:
37
𝑥𝑖𝑗𝑘: variável binária que tem valor 1, se a tarefa j é sequenciada na k-
ésima posição da máquina i;
ℎ𝑖𝑘: representa o tempo de início do processamento da tarefa na k-
ésima posição da máquina i.
O modelo matemático define-se da seguinte forma:
Min 𝐶𝑚𝑎𝑥 (16)
Sujeito a
∑ 𝑥𝑖𝑗𝑘 = 1
𝑗∈𝐽
, ∀𝑖 ∈ 𝑀, ℎ = 1, … 𝑛 (17)
∑ 𝑥𝑖𝑗𝑘 = 1
𝑛
𝑘=1
, ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐽 (18)
ℎ𝑖𝑘 + ∑ 𝑝𝑖𝑗𝑥𝑖𝑗𝑘 ≤ ℎ𝑖,𝑘+1,
𝑗∈𝐽
∀𝑗 ∈ 𝐽, ∀𝑖 ∈ 𝑀 (19)
∑ 𝑟𝑖𝑗𝑙ℎ𝑖𝑘 + ∑ 𝑟𝑖𝑗𝑙𝑝𝑖𝑗 ≤𝑖∈𝑀𝑖∈𝑀 𝑉. (1 −
∑ 𝑟𝑖𝑗𝑙𝑥𝑖𝑗𝑘)𝑖∈𝑀 + 𝑉. (1 − ∑ 𝑟𝑖𝑗,𝑙+1𝑥𝑖𝑗𝑘′) +𝑖∈𝑀
∑ 𝑟𝑖𝑗,𝑙+1ℎ𝑖𝑘′𝑖∈𝑀 ,
∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐽
𝑘, 𝑘′ = 1, … , 𝑛
𝑙 = 1, … , 𝑚 − 1
(20)
ℎ𝑖𝑛 + ∑ 𝑝𝑖𝑗𝑥𝑖𝑗𝑛 ≤ 𝐶𝑚𝑎𝑥,
𝑗∈𝐽
∀𝑖 ∈ 𝑀 (21)
ℎ𝑖𝑘 ≥ 0, ∀𝑖 ∈ 𝑀, 𝑘 = 1, … , 𝑛 (22)
𝑥𝑖𝑗𝑘 ∈ {0,1}, ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐽, 𝑘 = 1, … , 𝑛 (23)
38
O parâmetro 𝑟𝑖𝑗𝑘 é igual a 1, se a k-ésima operação da tarefa j for
processada na máquina i e 0, caso contrário. A função objetivo é declarada em (16).
As Restrições (17) garantem que cada posição em cada máquina é reservada
somente para uma tarefa. As Restrições (18) impõem que cada tarefa ocupe
somente uma posição em uma máquina. As Restrições (19) declaram que o tempo
de início de uma tarefa em uma máquina deve ser maior que o tempo de finalização
da tarefa alocada na posição anterior. As Restrições (20) são responsáveis por
manter a ordem de precedência conforme estabelecido. As Restrições (21) fazem
com que o makespan seja, no mínimo, igual ao maior tempo de finalização da última
tarefa de todas as máquinas. As Equações (22) definem que os tempos de início de
todas as tarefas em todas as posições das máquinas são maiores ou iguais a zero.
As Restrições (23) conferem a característica binária à variável que indica se a tarefa
j é sequenciada na k-ésima posição da máquina i.
2.3 PROBLEMA DE FLUXO EM REDE
Problemas de fluxos em rede são uma das mais importantes e mais
recorrentes classes de problemas de otimização. Eles surgem em decorrência da
análise e do projeto de grandes sistemas como de comunicação, transporte e redes
de manufatura. Ahuja, Magnanti e Orlin (1993) complementam essa visão ao
afirmarem que modelos baseados em fluxos em rede aparecem em quase todas as
indústrias, como agricultura, comunicação, defesa, educação, energia, saúde,
manufatura, medicina, varejo e transporte. Também possuem grande relevância por
serem utilizados para modelagem de classes importantes de problemas
combinatórios como de atribuição, caminho mais curto e caixeiro viajante
(BERTSEKAS, 1998).
Mazraeh Farahani et al. (2018) desenvolveram um modelo de programação
linear inteira mista para resolução do problema de evacuação-localização, aplicável
em ocasiões de logística emergencial. O modelo combina decisões de localização
com o problema do fluxo máximo com o objetivo de selecionar destinos seguros que
sejam capaz de maximizar o número de pessoas deslocadas em um desastre ou
evento de calamidade.
39
Em um cenário de escassez de investimentos em plantas de biogás na
Dinamarca, Jensen, Münster e Pisinger (2017) elaboraram um modelo de
programação linear inteira mista para determinar a produção ótima e o plano de
investimentos em uma cadeia de suprimentos de biogás de modo a garantir o
melhor retorno para toda a cadeia. O problema é resolvido utilizando um modelo de
fluxo em rede cujo lado de entrada apresenta um espaço de tempo, processo e
conteúdo energético e o lado de saída apresenta um espaço de tempo e processo.
Isto é, no lado da entrada, o modelo deve ter mapeado a massa e o conteúdo
energético ao longo do tempo. A massa é necessária para o dimensionamento dos
processos e da quantidade de digestato, enquanto o conteúdo de energia deve ser
usado para calcular o rendimento do biogás para a saída. No lado da saída, é
necessário apenas ter mapeado a quantidade de metros cúbicos de biogás
disponível ao longo do tempo.
Venkatadri, Elaskari, Kurdi (2017) desenvolveram uma formulação baseada
em fluxo em rede multi-commodity para o problema de formação de células
multiperíodo, bastante relevante para área de projetos e planejamento de
instalações. O modelo proposto pelos pesquisadores visa minimizar o custo total de
aquisição, disposição e realocação de máquinas, fabricação e manuseio de
materiais entre células e dentro da célula.
Scheffler e Strehler (2016) apresentam em seu estudo uma formulação de
programação linear inteira mista que visa otimizar simultaneamente a sincronização
de sinais de trânsito e a alocação de tráfego em megaeventos programados, como
jogos de futebol e shows. Os pesquisadores utilizaram uma extensão de um modelo
de fluxo em rede de tempo expandido ciclicamente.
Problemas de fluxos em rede podem ser entendidos como uma composição
de pontos de suprimento e demanda, conectados por um número de rotas
responsáveis pela transferência do que está sendo fornecido para onde será
consumido ou recebido. Os pontos de fornecimento e demanda podem ser
modelados como nós ou vértices de um grafo, enquanto as rotas podem ser
definidas como arestas ou arcos de um grafo.
Segundo Bertsimas e Tsitsiklis (1997) um grafo orientado, 𝐺 = (𝑁, 𝐴),
consiste em um conjunto N de nós e um conjunto A de pares de nós diferentes de N
40
chamados arcos. Denota-se como N o número de nós e A o número de arcos e
assume-se que 1 ≤ 𝑁 ≤ ∞ e 0 ≤ 𝐴 ≤ ∞. Um arco (𝑖, 𝑗) é tido como um par
ordenado, assim se diferenciando do arco (𝑗, 𝑖). No caso do par (𝑖, 𝑗) é dito que o
arco sai de i e entra em j . O grau de um nó i é o número de arcos incidentes em i.
O caminho P em um grafo orientado é a sequência de nós (𝑛1, 𝑛2, … , 𝑛𝑘) com
𝑘 ≥ 2 e uma sequência correspondente de k-1 arcos. O i-ésimo arco na sequência é
(𝑛𝑖, 𝑛𝑖+1), neste caso chamado de arco progressivo, ou (𝑛𝑖+1, 𝑛𝑖), conhecido como
arco regressivo (BERTSEKAS, 1998).
Bertsekas (1998) menciona que em muitas aplicações envolvendo grafos é
útil introduzir uma variável que meça a quantidade que flui através de cada arco. O
pesquisador cita exemplos de fluxos como corrente elétrica em um circuito elétrico
ou o fluxo de água em uma rede hidráulica. Refere-se a essa variável como fluxo de
um arco e denota-se como 𝑥𝑖𝑗, sendo um escalar e número real.
2.3.1 Problema do fluxo de custo mínimo
O problema do fluxo de custo mínimo tem como objetivo achar um conjunto
de fluxos de arco que minimize uma função de custo linear sujeita às restrições que
produzem um determinado vetor de divergência e que permaneçam dentro de
alguns limites. A formulação do problema pode ser observada a seguir:
Min ∑ 𝑐𝑖𝑗𝑥𝑖𝑗(𝑖,𝑗)∈𝐴 (24)
Sujeito a
∑ 𝑥𝑖𝑗 − ∑ 𝑥𝑗𝑖 = 𝑠𝑖{𝑗|(𝑗,𝑖)∈𝐴}{𝑗|(𝑖,𝑗)𝜖𝐴} , ∀𝑖 ∈ 𝑁 (25)
𝑎𝑖𝑗 ≤ 𝑥𝑖𝑗 ≤ 𝑏𝑖𝑗, ∀(𝑖, 𝑗) ∈ 𝐴 (26)
Onde 𝑎𝑖𝑗, 𝑏𝑖𝑗, 𝑐𝑖𝑗 e 𝑠𝑖são escalares. A seguir a descrição das constantes
utilizadas:
41
𝑐𝑖𝑗: coeficiente de custo de (i,j);
𝑎𝑖𝑗 e 𝑏𝑖𝑗: os limites de fluxo de (i,j);
[𝑎𝑖𝑗, 𝑏𝑖𝑗]: intervalo viável de fluxo de (i,j);
𝑠𝑖: o suprimento do nó i. Quando 𝑠𝑖 é negativo, o escalar -𝑠𝑖 é
chamado de demanda de i;
A função objetivo está declarada em (24). As Restrições (25) são chamadas
de restrições de conservação de fluxo, enquanto as Restrições (26) são conhecidas
como restrições de capacidade.
42
3 FORMULAÇÃO DE PI PARA O PROBLEMA DE
SEQUENCIAMENTO DE JOB SHOP
3.1 INTRODUÇÃO
Resolver o problema de sequenciamento de job shop consiste em programar
o processamento de um conjunto de tarefas em um conjunto de máquinas. Nesse
ambiente, cada tarefa possui uma rota predeterminada de operações nas máquinas
que precisa ser cumprida. Esse tipo de problema tornou-se amplamente estudado
devido à sua grande aplicação em diversas áreas do conhecimento. Além disso,
ficou ainda mais conhecido em função de sua complexidade, uma vez que é
classificado como NP-difícil. Isso significa que os algoritmos desenvolvidos para
resolver este problema podem levar um tempo exponencial para encontrar uma
solução.
A relevância do job shop para a engenharia, ciência da computação, ciência
da decisão, matemática, gerenciamento de operações, entre outras áreas, pode ser
constatada por pesquisas recentes. Gran et al. (2015) demonstraram que o modelo
proposto para resolução do problema de sequenciamento de job shop flexível
baseado em programação por meta inteira mista multiobjetivo é competitivo em
comparação com métodos metaheurísticos largamente utilizados.
Kusuma e Maruf (2016) elaboraram um modelo de programação linear
inteira para resolver o problema de sequenciamento de job shop com máquinas de
prensa não idênticas e minimizar o atraso total. A principal restrição do modelo é que
as tarefas apresentam datas de entrega fixas. Os resultados da pesquisa apontam
que, no melhor cenário, foram necessárias 14 máquinas das 59 existentes para
escalonar 70 tarefas com quatro datas de entrega. Esse cenário foi resolvido em 13
segundos, não apresentou nenhum atraso e aumentou a taxa de utilização das
máquinas para 89% em comparação com os 71% de utilização da operação
convencional com as 59 máquinas iniciais.
Lange e Werner (2017) modelaram um problema de programação de trens
como um problema de sequenciamento de job shop com restrições de bloqueio.
Restrições como essa se referem às situações em que um trem precisa ocupar um
trecho mais tempo do que o necessário até que o próximo trecho a ser seguido
43
esteja liberado para passagem. Quatro formulações de programação inteira mista
foram desenvolvidas e comparadas em um estudo computacional que levou em
consideração instâncias difíceis de até 20 tarefas e 11 máquinas. Os modelos
propostos apresentam boa eficiência para a resolução de instâncias não tão
extensas.
O restante do capítulo é organizado como exposto a seguir. A Seção 3.2
apresenta a metodologia da pesquisa e a Seção 3.3 traz a formulação proposta para
resolver o problema de sequenciamento de job shop. A Seção 3.4 fornece um
exemplo ilustrativo de resolução de uma instância simples e a Seção 3.5 introduz as
formulações de referência para os testes de comparação. Por fim, a Seção 3.6
destina-se à discussão de resultados.
3.2 METODOLOGIA DA PESQUISA
A base metodológica deste capítulo pode ser esquematizada conforme a
Figura 4:
Figura 4 – Etapas da metodologia da pesquisa para o problema de sequenciamento de job shop
44
As diferentes fases podem ser detalhadas conforme as próximas
subseções.
3.2.1 Levantamento e análise das melhores formulações
O levantamento e análise das melhores formulações consistiu na busca de
artigos recentes que tratassem da resolução do problema de sequenciamento de job
shop. Foi possível observar que a maioria das técnicas empregadas atualmente tem
como fim o sequenciamento das tarefas para minimizar o makespan. Em função
disso, foi preciso adaptar as formulações para o caso em que se procura minimizar o
atraso total ponderado antes de estudá-las.
3.2.2 Identificação e implementação de oportunidades de melhoria
Após análise das formulações, algumas estratégias para resolução de
problemas com programação inteira foram estudadas e a aplicabilidade nos modelos
já existentes foi avaliada. O foco das melhorias foi a formulação com variáveis
indexadas no tempo e a estratégica adotada para aumentar o desempenho deste
modelo foi a introdução do fluxo em rede nas restrições responsáveis por garantir
que uma determinada máquina não fique sobrecarregada em nenhum momento e
por assegurar que as operações de uma dada tarefa sejam executadas na ordem
definida.
3.2.3 Realização de testes com a nova formulação e as de referência
Os testes realizados têm como objetivo mensurar o desempenho de quatro
formulações aplicadas para resolução do problema de sequenciamento de job shop
para o caso em que o objetivo é minimizar o atraso total ponderado. Os modelos
avaliados são: o modelo disjuntivo adaptado, o modelo de Kondili adaptado, o
modelo de kondili adaptado e revisado e o novo modelo.
Para medição do desempenho dessas formulações foram propostas
instâncias com sequências de máquinas pseudoaleatórias e com tempos de
processamento também pseudoaleatórios variando entre 1 e 5 e 1 e 10 unidades de
tempo (UT). Para isso, foi utilizado um algoritmo gerador de números
pseudoaleatórios inicializado por diferentes valores inteiros maiores ou iguais a 1,
45
chamados de sementes (seeds). As sementes permitem que as sequências de
números pseudoaleatórios geradas sejam recuperadas e reutilizadas em outros
testes.
O tempo limite adotado para resolução do problema foi de 3.600 segundos.
O prazo de finalização adotado foi igual a zero e o peso igual a um para todas as
tarefas. Os tamanhos das instâncias, ou seja, o número de máquinas e tarefas do
problema foram os mesmos usados no estudo conduzido por Ku e Beck (2016). A
Tabela 1 apresenta o tamanho das instâncias utilizadas:
Tabela 1 – Tamanho das instâncias adotadas na metodologia de pesquisa
Número de tarefas
Número de máquinas
3 3
4 3
5 3
3 6
3 8
3 10
5 5
8 8
10 10
12 12
15 15
20 15
A definição do horizonte de tempo para resolução das instâncias pelas
formulações com variáveis indexadas no tempo foi realizada com base nas soluções
ótimas apresentadas pelo modelo disjuntivo adaptado. Assim, o instante mais tarde
em que uma tarefa dos modelos de Kondili adaptado, de Kondili adaptado e revisado
e do novo modele pode começar seu processamento, sem o risco de perder a
solução ótima, é calculado a partir do tempo de conclusão da última tarefa do
modelo disjuntivo adaptado. Isso implica que os testes para esses três modelos só
46
foram realizados para as instâncias cujo modelo disjuntivo adaptado foi capaz de
encontrar uma solução ótima em até 3.600 segundos.
Os modelos testados foram implementados usando o UFFLP, que consiste
em uma biblioteca de funções para interface entre linguagens de programação e
resolvedores de programação inteira mista. Pessoa e Uchoa (2011) complementam
que o UFFLP é uma Dynamic Link Library (DLL) que pode ser chamada de
programas escritos em Visual Basic for Applications (VBA) ou de programas em
C/C++ a partir do Windows ou do Linux. Ainda segundo os autores, algumas
funcionalidades do UFFLP são:
Referência a variáveis e restrições do modelo pelos seus nomes (strings);
Integração com heurísticas e rotinas de geração de cortes chamadas por
meio de callbacks em VBA ou em C/C++;
Opção de utilização dos resolvedores Coin-CBC e CPLEX. O primeiro é
aberto e gratuito, enquanto o segundo é fechado e gratuito somente para
aplicações acadêmicas;
Gratuidade e abertura do código fonte;
A linguagem de programação escolhida foi o VBA. O resolvedor adotado na
pesquisa foi o CPLEX Optimization versão 12.7.0 e todos os oitos processadores
lógicos disponíveis foram utilizados. A decisão em utilizar o CPLEX foi tomada em
função dos bons resultados encontrados por Ku e Beck (2016) em comparação com
os resolvedores GUROBI e SCIP, além da facilidade de integração com o UFFLP.
Os experimentos foram realizados em um computador com as seguintes
configurações:
Processador: Intel® Core ™ i7-4970 CPU @ 3.60 GHz;
Memória instalada (RAM): 16 GB;
Tipo de sistema: Sistema Operacional Windows 10 de 64 bits.
3.2.4 Comparação dos resultados obtidos
A garantia de que as condições de teste para todos os modelos estudados
nesta pesquisa foram respeitadas é fundamental para que a comparação de
47
resultados seja bem sucedida. Dessa forma, todas as saídas geradas pelos testes
com as quatro formulações estudadas (modelo disjuntivo adaptado, modelo de
Kondili adaptado, modelo de kondili adaptado e revisado e novo modelo) puderam
ser analisadas, permitindo a definição do melhor modelo de resolução do problema
de job shop para minimizar o atraso total ponderado em função dos diferentes
cenários.
3.3 MODELO MATEMÁTICO
O novo método exato proposto neste estudo para resolver o problema de
sequenciamento de job shop com o objetivo de minimizar o atraso total ponderado é
baseado no modelo de Kondili com variáveis indexadas no tempo e na estratégia de
fluxo em rede. A nova formulação proposta será chamada, neste trabalho, de o
novo modelo e apresenta três variáveis de decisão, conforme a seguir:
𝑥𝑖𝑗𝑡: variável binária que assume o valor igual a 1, caso a tarefa j
comece na máquina i no instante t;
𝑓𝑖𝑡: variável binária que se iguala a 1, quando a máquina i permanece
ociosa no período t.
𝑒𝑖𝑗𝑡: variável binária que é igual a 1, se a tarefa j já terminou na
máquina anterior, mas ainda não começou na máquina i no momento
t.
Min ∑ ∑ 𝑤𝑗. max {𝑡 + 𝑝𝜎𝑚
𝑗,𝑗
− 𝑑𝑗 , 0} . 𝑥𝜎𝑚
𝑗,𝑗𝑡𝑡∈𝑈
𝜎𝑚𝑗
,𝑗𝑗∈𝐽 (27)
Sujeito a
∑ 𝑥𝑖𝑗,𝑡−𝑝𝑖𝑗+
𝑗∈𝐽
𝑓𝑖,𝑡−1 − ∑ 𝑥𝑖𝑗𝑡 −
𝑗∈𝐽
𝑓𝑖𝑡 = −1, ∀𝑖 ∈ 𝑀, 𝑡 = 1 (28)
∑ 𝑥𝑖𝑗,𝑡−𝑝𝑖𝑗+
𝑗∈𝐽
𝑓𝑖,𝑡−1 − ∑ 𝑥𝑖𝑗𝑡 −
𝑗∈𝐽
𝑓𝑖𝑡 = 0, ∀𝑖 ∈ 𝑀, 𝑡 ∈ 𝑈 − {1} (29)
48
𝑥𝜎ℎ−1
𝑗,𝑗,𝑡−𝑝
𝜎ℎ−1𝑗
,𝑗
+ 𝑒𝜎ℎ
𝑗,𝑗,𝑡−1
− 𝑥𝜎ℎ
𝑗,𝑗𝑡
− 𝑒𝜎ℎ
𝑗,𝑗𝑡
= −1, ∀𝑗 ∈ 𝐽, 𝑡 = 1, ℎ = 1 (30)
𝑥𝜎ℎ−1
𝑗,𝑗,𝑡−𝑝
𝜎ℎ−1𝑗
,𝑗
+ 𝑒𝜎ℎ
𝑗,𝑗,𝑡−1
− 𝑥𝜎ℎ
𝑗,𝑗𝑡
− 𝑒𝜎ℎ
𝑗,𝑗𝑡
= 0, ∀𝑗 ∈ 𝐽, 𝑡 ∈ 𝑈 − {1}, ℎ
= 1, … , 𝑚 (31)
𝑥𝜎ℎ−1
𝑗,𝑗,𝑡−𝑝
𝜎ℎ−1𝑗
,𝑗
+ 𝑒𝜎ℎ
𝑗,𝑗,𝑡−1
− 𝑥𝜎ℎ
𝑗,𝑗𝑡
− 𝑒𝜎ℎ
𝑗,𝑗𝑡
= 0, ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑈, ℎ = 2, … , 𝑚 (32)
𝑥𝑖𝑗𝑡 ∈ {0,1}, ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑈 (33)
𝑓𝑖𝑡 ∈ {0,1}, ∀𝑖 ∈ 𝑀, ∀𝑡 ∈ 𝑈 (34)
𝑒𝑖𝑗𝑡 ∈ {0,1}, ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑈 (35)
O conjunto 𝑈 é definido como {1, … , 𝐻} e 𝑈𝑖𝑗 ⊂ 𝑈 contém os tempos em que
a tarefa j pode efetivamente começar sua operação na máquina i sem exceder o
tempo H definido, uma vez que a tarefa j também precisa ser executada em
máquinas antes e/ou depois de i.
A função objetivo, neste caso a de minimizar o atraso total ponderado, está
declarada em (27). A Restrições (28) e (29) são os fluxos em rede que asseguram
que a máquina i não fica sobrecarregada em nenhum instante. As Restrições (30) a
(32) garantem que as precedências sejam respeitadas, isto é, garantem que as
operações de uma tarefa j sejam executadas na sequência determinada. As
Restrições (33) a (35) definem as variáveis de decisão como binárias.
Os esquemas a seguir são representações das duas restrições, capacidade
de máquina e precedência, modeladas como fluxos em rede e propostas no novo
modelo:
49
Figura 5 – Representação esquemática das Restrições (28) e (29) relativas à capacidade das máquinas
Figura 6 – Representação esquemática das Restrições (30) a (32) relativas à ordem de precedência das tarefas
3.4 EXEMPLO ILUSTRATIVO
Para melhor compreensão do novo modelo é apresentada a resolução de
uma instância e o esboço dos fluxos em rede das restrições. O problema escolhido
tem tamanho 3 x 3, isto é, 3 tarefas e 3 máquinas, horizonte de tempo (H) igual a 9 e
possui os seguintes tempos de processamento e ordens de precedência:
50
Tabela 2 – Tempos de processamento das tarefas nas máquinas do exemplo
Tarefas | Máquinas 1 2 3
1 1 2 2
2 1 2 2
3 2 1 4
Tabela 3 – Sequência das máquinas de cada tarefa do exemplo
Tarefas | Sequência 1ª Máquina 2ª Máquina 3ª Máquina
1 1 2 3
2 1 3 2
3 2 1 3
O valor da solução ótima encontrada é igual a 21. Os valores das variáveis
de decisão e o diagrama de Gantt com o sequenciamento referente à solução ótima
podem ser observados na Tabela 4 e na Figura 7, respectivamente:
Tabela 4 – Valores das variáveis de decisão da solução ótima do exemplo
Variável de decisão
Resultado
f_1_4 1
f_1_6 1
f_1_7 1
f_1_8 1
f_1_9 1
f_2_2 1
f_2_3 1
f_2_8 1
f_2_9 1
f_3_1 1
e_1_1_1 1
e_1_1_2 1
51
e_1_1_3 1
e_1_1_4 1
x_1_1_5 1
x_1_2_1 1
x_1_3_2 1
x_2_1_6 1
x_2_2_4 1
x_2_3_1 1
x_3_1_8 1
x_3_2_2 1
x_3_3_4 1
Figura 7 – Diagrama de Gantt da solução ótima do exemplo
Os esquemas dos fluxos em rede das restrições de capacidade de máquina
e precedência para as três tarefas podem ser observados a seguir:
Máquina 1 2 3 4 5 6 7 8 9 10
1
2
3
Legenda
Tarefa 1
Tarefa 2
Tarefa 3
Tempo
52
Figura 8 – Esquema representativo dos fluxos em rede das restrições de capacidade de máquina do exemplo
Figura 9 – Esquema representativo do fluxo em rede da restrição de precedência da tarefa 1 do exemplo
53
Figura 10 – Esquema representativo do fluxo em rede da restrição de precedência da tarefa 2 do exemplo
Figura 11 – Esquema representativo do fluxo em rede da restrição de precedência da tarefa 3 do exemplo
54
3.5 FORMULAÇÕES DE REFERÊNCIA PARA OS TESTES
O desempenho do novo modelo foi testado a partir de uma análise
comparativa com outras três formulações com função objetivo de minimizar o atraso
total ponderado:
O modelo disjuntivo adaptado;
O modelo de Kondili adaptado;
O modelo de kondili adaptado e revisado.
O modelo disjuntivo adaptado consiste no modelo disjuntivo de Manne
adaptado ao caso em que a função objetivo é minimizar o atraso total ponderado.
Este modelo apresenta as mesmas variáveis de decisão que a formulação disjuntiva
original, mas introduz novos parâmetros:
𝑑𝑗: prazo em que a tarefa j deve estar finalizada;
𝑤𝑗: peso atribuído à tarefa j;
𝑡𝑗: atraso da tarefa j, calculado como 𝑡𝑗 = max {0, 𝐶𝑗 − 𝑑𝑗}, onde 𝐶𝑗 é o
tempo de conclusão da tarefa j.
Min ∑ 𝑤𝑗𝑡𝑗𝑗∈𝐽 (36)
Sujeito a
𝑠𝜎ℎ
𝑗,𝑗
≥ 𝑠𝜎ℎ−1
𝑗,𝑗
+ 𝑝𝜎ℎ−1
𝑗,𝑗, ∀𝑗 ∈ 𝐽, ℎ = 2, … , 𝑚 (37)
𝑠𝑖𝑗 ≥ 𝑠𝑖𝑘 + 𝑝𝑖𝑘 − 𝑉. 𝑧𝑖𝑗𝑘, ∀𝑗, 𝑘 ∈ 𝐽, 𝑗 < 𝑘, ∀𝑖 ∈ 𝑀 (38)
𝑠𝑖𝑘 ≥ 𝑠𝑖𝑗 + 𝑝𝑖𝑗 − 𝑉. (1 − 𝑧𝑖𝑗𝑘), ∀𝑗, 𝑘 ∈ 𝐽, 𝑗 < 𝑘, ∀𝑖 ∈ 𝑀 (39)
55
𝑡𝑗 ≥ 𝑠𝜎𝑚
𝑗,𝑗
+ 𝑝𝜎𝑚
𝑗,𝑗
− 𝑑𝑗, ∀𝑗 ∈ 𝐽 (40)
𝑠𝑖𝑗 ≥ 0, ∀𝑗 ∈ 𝐽, ∀𝑖 ∈ 𝑀 (41)
𝑧𝑖𝑗𝑘 ∈ {0,1), ∀𝑗, 𝑘 ∈ 𝐽, ∀𝑖 ∈ 𝑀 (42)
𝑡𝑗 ≥ 0, ∀𝑗 ∈ 𝐽 (43)
A função objetivo está definida em (36). Em relação ao modelo original,
acrescentam-se as Restrições (40) em substituição às Restrições (5). Essas
restrições garantem que o atraso de uma tarefa j seja maior ou igual ao seu tempo
de conclusão menos o seu prazo de finalização. Outra diferença em relação à
versão original com função objetivo para minimizar o makespan é a inclusão das
Restrições (43) que impõem que o atraso de uma tarefa j seja maior ou igual a zero.
O modelo de Kondili adaptado se refere ao modelo com variáveis
indexadas no tempo de Kondili adaptado para minimizar o atraso total ponderado.
Essa formulação apresenta a mesma variável de decisão do modelo de Kondili
original e os parâmetros 𝑑𝑗 e 𝑤𝑗 já introduzidos no modelo disjuntivo adaptado. A
formulação matemática pode ser observada a seguir:
Min ∑ ∑ 𝑤𝑗. max {𝑡 + 𝑝𝜎𝑚
𝑗,𝑗
− 𝑑𝑗 , 0} . 𝑥𝜎𝑚
𝑗,𝑗𝑡𝑡∈𝑈
𝜎𝑚𝑗
,𝑗𝑗∈𝐽 (44)
Sujeito a
∑ 𝑥𝑖𝑗𝑡 = 1
𝑡∈𝑈
, ∀𝑗 ∈ 𝐽, ∀𝑖 ∈ 𝑀 (45)
56
∑ ∑ 𝑥𝑖𝑗𝑡 ≤ 1
𝑡∈𝑇𝑖𝑗𝑡𝑗∈𝐽
, ∀𝑖 ∈ 𝑀, 𝑡 ∈ 𝑈, 𝑜𝑛𝑑𝑒 𝑇𝑖𝑗𝑡 =
{𝑡 − 𝑝𝑖𝑗 + 1, … , 𝑡} (46)
∑ (𝑡 + 𝑝𝜎ℎ−1
𝑗,𝑗
) . 𝑥𝜎ℎ−1
𝑗,𝑗𝑡
≤ ∑ 𝑡 . 𝑥𝜎ℎ
𝑗,𝑗𝑡
𝑡∈𝑈𝑡∈𝑈
, ∀𝑗 ∈ 𝐽, ℎ = 2, … , 𝑚 (47)
𝑥𝑖𝑗𝑡 ∈ {0,1}, ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑈 (48)
A função objetivo está declarada em (44) e calcula o somatório dos
resultados não negativos da diferença entre os tempos de conclusão e os prazos
predeterminados. Assim, se o prazo de finalização for maior que o tempo de
conclusão da tarefa, multiplica-se por zero à variável de decisão de forma que o
atraso total ponderado jamais resulte em um valor negativo. As demais restrições
permanecem as mesmas da formulação original.
O modelo de Kondili adaptado e revisado é o modelo com variáveis
indexadas no tempo de Kondili adaptado para minimizar o atraso total ponderado e
modelado com a restrição de precedência na lógica de fluxo em rede. Essa
formulação pode ser observada a seguir:
Min ∑ ∑ 𝑤𝑗. max {𝑡 + 𝑝𝜎𝑚
𝑗,𝑗
− 𝑑𝑗 , 0} . 𝑥𝜎𝑚
𝑗,𝑗𝑡𝑡∈𝑈
𝜎𝑚𝑗
,𝑗𝑗∈𝐽 (49)
Sujeito a
∑ ∑ 𝑥𝑖𝑗𝑡 ≤ 1
𝑡∈𝑇𝑖𝑗𝑡𝑗∈𝐽
, ∀𝑖 ∈ 𝑀, 𝑡 ∈ 𝑈, 𝑜𝑛𝑑𝑒 𝑇𝑖𝑗𝑡 =
{𝑡 − 𝑝𝑖𝑗 + 1, … , 𝑡} (50)
𝑥𝜎ℎ−1
𝑗,𝑗,𝑡−𝑝
𝜎ℎ−1𝑗
,𝑗
+ 𝑒𝜎ℎ
𝑗,𝑗,𝑡−1
− 𝑥𝜎ℎ
𝑗,𝑗𝑡
− 𝑒𝜎ℎ
𝑗,𝑗𝑡
= −1, ∀𝑗 ∈ 𝐽, 𝑡 = 1, ℎ = 1 (51)
57
𝑥𝜎ℎ−1
𝑗,𝑗,𝑡−𝑝
𝜎ℎ−1𝑗
,𝑗
+ 𝑒𝜎ℎ
𝑗,𝑗,𝑡−1
− 𝑥𝜎ℎ
𝑗,𝑗𝑡
− 𝑒𝜎ℎ
𝑗,𝑗𝑡
= 0, ∀𝑗 ∈ 𝐽, 𝑡 ∈ 𝑈 − {1}, ℎ
= 1, … , 𝑚 (52)
𝑥𝜎ℎ−1
𝑗,𝑗,𝑡−𝑝
𝜎ℎ−1𝑗
,𝑗
+ 𝑒𝜎ℎ
𝑗,𝑗,𝑡−1
− 𝑥𝜎ℎ
𝑗,𝑗𝑡
− 𝑒𝜎ℎ
𝑗,𝑗𝑡
= 0, ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑈, ℎ = 2, … , 𝑚 (53)
𝑥𝑖𝑗𝑡 ∈ {0,1}, ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑈 (54)
𝑒𝑖𝑗𝑡 ∈ {0,1}, ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑈 (55)
A função objetivo está definida em (49). Em relação à formulação anterior,
houve substituição das Restrições (46) pelas Restrições (30) a (32).
A análise comparativa não envolveu o modelo de Wagner adaptado para o
caso em que a função objetivo é minimizar o atraso total ponderado, pois essa
formulação não conta com uma variável de decisão que relacione quando uma
tarefa específica começou a ser processada em uma determinada máquina. A
variável ℎ𝑖𝑘 representa o início do processamento de uma tarefa na posição k da
máquina i, porém não define qual tarefa. Isso impossibilita o cálculo do atraso das
tarefas e, consequentemente, do atraso total ponderado.
3.6 DISCUSSÃO DOS RESULTADOS
Nesta seção é apresentada a análise comparativa entre o novo modelo e as
outras três formulações anteriormente descritas:
O modelo disjuntivo adaptado;
O modelo de Kondili adaptado;
O modelo de kondili adaptado e revisado.
Os resultados foram comparados em função dos intervalos de tempo de
processamento definidos de maneira pseudoaleatória para cada tarefa e máquina e
em função do tamanho das instâncias. O desempenho das formulações foi medido
58
por dois indicadores: média aritmética e média geométrica deslocada. Esta última
medida foi proposta por Ku e Beck (2016) e apresenta menor sensibilidade à
variação dos números do que a média aritmética, o que reduz a influência de outliers
na análise dos dados. Sua fórmula exibida a seguir:
∏(𝑡𝑖 + 𝑠)1/𝑛 − 𝑠 (56)
Onde 𝑡𝑖 é o tempo de resolução, isto é, o tempo no qual o modelo levou até
chegar à solução ótima, n é o número de instâncias resolvidas e s é igual a 10. A
estratégia de somar uma constante aos tempos de resolução é permitir o cálculo das
médias geométricas relativas às instâncias menores, que, na maioria dos casos,
chegam a um resultado ótimo em intervalos de tempo muito curtos.
A seguir podem ser observadas as Tabelas 5, 6, 7 e 8 com os resultados
das quatro formulações que estão sendo comparadas.
Tabela 5 – Resultados do novo modelo
Intervalos dos tempos de
processamento (UT)
Instância (n x m)
Número de rodadas com otimalidade
Média aritmética do
tempo de resolução (s)
Média geométrica
deslocada do tempo de
resolução (s)
[1,5] 3 x 3 10 0,01025 0,01025
[1,5] 3 x 6 10 0,02495 0,02494
[1,5] 3 x 8 10 0,03110 0,03108
[1,5] 3 x 10 10 0,03599 0,03593
[1,5] 4 x 3 10 0,02354 0,02353
[1,5] 5 x 3 10 0,04463 0,04460
[1,5] 5 x 5 10 0,10718 0,10710
[1,5] 8 x 8 10 21,24204 16,66033
[1,5] 10 x 10 5 225,19688 184,13887
[1,5] 12 x 12 0 - -
[1,5] 15 x 15 0 - -
[1,5] 20 x 15 0 - -
[1,10] 3 x 3 10 0,00459 0,00459
59
[1,10] 3 x 6 10 0,03579 0,03572
[1,10] 3 x 8 10 0,04692 0,04683
[1,10] 3 x 10 10 0,05454 0,05443
[1,10] 4 x 3 10 0,05010 0,04999
[1,10] 5 x 3 10 0,06123 0,06118
[1,10] 5 x 5 10 0,18447 0,18379
[1,10] 8 x 8 10 366,05396 204,72822
[1,10] 10 x 10 2 1.869,06738 1.453,68224
[1,10] 12 x 12 0 - -
[1,10] 15 x 15 0 - -
[1,10] 20 x 15 0 - -
Tabela 6 – Resultados do modelo disjuntivo adaptado
Intervalos dos tempos de
processamento (UT)
Instância (n x m)
Número de rodadas com otimalidade
Média aritmética do
tempo de resolução (s)
Média geométrica
deslocada do tempo de
resolução (s)
[1,5] 3 x 3 10 0,01471 0,01471
[1,5] 3 x 6 10 0,01442 0,01442
[1,5] 3 x 8 10 0,01279 0,01279
[1,5] 3 x 10 10 0,01548 0,01548
[1,5] 4 x 3 10 0,01390 0,01390
[1,5] 5 x 3 10 0,02920 0,02919
[1,5] 5 x 5 10 0,03893 0,03893
[1,5] 8 x 8 10 18,56375 15,75674
[1,5] 10 x 10 5 995,67539 874,00137
[1,5] 12 x 12 0 - -
[1,5] 15 x 15 0 - -
[1,5] 20 x 15 0 - -
[1,10] 3 x 3 10 0,01615 0,01613
[1,10] 3 x 6 10 0,00837 0,00836
60
[1,10] 3 x 8 10 0,01149 0,01149
[1,10] 3 x 10 10 0,01300 0,01300
[1,10] 4 x 3 10 0,01566 0,01563
[1,10] 5 x 3 10 0,02882 0,02881
[1,10] 5 x 5 10 0,04259 0,04258
[1,10] 8 x 8 10 14,16336 11,71054
[1,10] 10 x 10 5 966,80355 822,76860
[1,10] 12 x 12 0 - -
[1,10] 15 x 15 0 - -
[1,10] 20 x 15 0 - -
Tabela 7 – Resultados do modelo de Kondili adaptado
Intervalos dos tempos de
processamento (UT)
Instância (n x m)
Número de rodadas com otimalidade
Média aritmética do
tempo de resolução (s)
Média geométrica
deslocada do tempo de
resolução (s)
[1,5] 3 x 3 10 0,02695 0,02693
[1,5] 3 x 6 10 0,08652 0,08644
[1,5] 3 x 8 10 0,07402 0,07390
[1,5] 3 x 10 10 0,08496 0,08484
[1,5] 4 x 3 10 0,11016 0,11014
[1,5] 5 x 3 10 0,37656 0,36862
[1,5] 5 x 5 10 0,86758 0,85112
[1,5] 8 x 8 10 104,91191 69,52654
[1,5] 10 x 10 2 1.736,86914 1.661,81459
[1,5] 12 x 12 0 - -
[1,5] 15 x 15 0 - -
[1,5] 20 x 15 0 - -
[1,10] 3 x 3 10 0,04219 0,04216
[1,10] 3 x 6 10 0,16250 0,16138
[1,10] 3 x 8 10 0,22734 0,22478
61
[1,10] 3 x 10 10 0,23516 0,23329
[1,10] 4 x 3 10 0,21563 0,21382
[1,10] 5 x 3 10 1,18281 1,15637
[1,10] 5 x 5 10 2,02266 1,97336
[1,10] 8 x 8 9 986,55642 739,18695
[1,10] 10 x 10 0 - -
[1,10] 12 x 12 0 - -
[1,10] 15 x 15 0 - -
[1,10] 20 x 15 0 - -
Tabela 8 – Resultados do modelo de kondili adaptado e revisado
Intervalos dos tempos de
processamento (UT)
Instância (n x m)
Número de rodadas com otimalidade
Média aritmética do
tempo de resolução (s)
Média geométrica
deslocada do tempo de
resolução (s)
[1,5] 3 x 3 10 0,00898 0,00898
[1,5] 3 x 6 10 0,01797 0,01797
[1,5] 3 x 8 10 0,02227 0,02226
[1,5] 3 x 10 10 0,02383 0,02382
[1,5] 4 x 3 10 0,02031 0,02031
[1,5] 5 x 3 10 0,04102 0,04097
[1,5] 5 x 5 10 0,06992 0,06984
[1,5] 8 x 8 10 19,65859 15,11455
[1,5] 10 x 10 5 229,98906 203,47480
[1,5] 12 x 12 0 - -
[1,5] 15 x 15 0 - -
[1,5] 20 x 15 0 - -
[1,10] 3 x 3 10 0,01250 0,01250
[1,10] 3 x 6 10 0,03594 0,03588
[1,10] 3 x 8 10 0,04375 0,04367
[1,10] 3 x 10 10 0,04375 0,04370
62
[1,10] 4 x 3 10 0,02813 0,02811
[1,10] 5 x 3 10 0,06875 0,06859
[1,10] 5 x 5 10 0,19844 0,19688
[1,10] 8 x 8 10 319,25156 163,56415
[1,10] 10 x 10 3 1.119,55339 1.105,03498
[1,10] 12 x 12 0 - -
[1,10] 15 x 15 0 - -
[1,10] 20 x 15 0 - -
A Tabela 9 sumariza quais modelos foram mais eficientes, isto é, quais
formulações conseguiram resolver cada instância no menor tempo de resolução.
Tabela 9 – Resumo das formulações mais eficientes por instância
Intervalos dos tempos de
processamento (UT)
Instância (n x m)
Modelo mais eficiente
1 – 5 3 x 3 Modelo de Kondili adaptado e revisado
1 – 5 3 x 6 Modelo disjuntivo adaptado
1 – 5 3 x 8 Modelo disjuntivo adaptado
1 – 5 3 x 10 Modelo disjuntivo adaptado
1 – 5 4 x 3 Modelo disjuntivo adaptado
1 – 5 5 x 3 Modelo disjuntivo adaptado
1 – 5 5 x 5 Modelo disjuntivo adaptado
1 – 5 8 x 8 Modelo disjuntivo adaptado
1 – 5 10 x 10 Novo modelo
1 – 5 12 x 12 -
1 – 5 15 x 15 -
1 – 5 20 x 15 -
1 – 10 3 x 3 Novo modelo
1 – 10 3 x 6 Modelo disjuntivo adaptado
1 – 10 3 x 8 Modelo disjuntivo adaptado
63
1 – 10 3 x 10 Modelo disjuntivo adaptado
1 – 10 4 x 3 Modelo disjuntivo adaptado
1 – 10 5 x 3 Modelo disjuntivo adaptado
1 – 10 5 x 5 Modelo disjuntivo adaptado
1 – 10 8 x 8 Modelo disjuntivo adaptado
1 – 10 10 x 10 Modelo disjuntivo adaptado
1 – 10 12 x 12 -
1 – 10 15 x 15 -
1 – 10 20 x 15 -
A análise das tabelas com os resultados das quatro formulações
comparadas evidenciou que as médias aritmética e geométrica deslocada dos
tempos de resolução são bem próximas, o que revela pouca dispersão na solução
de diferentes instâncias de mesmo tamanho. Para instâncias maiores, a
variabilidade dos tempos de resolução foi mais alta em comparação com instâncias
menores, pois houve menos soluções ótimas encontradas.
Observa-se pela tabela anterior que à medida que os intervalos de tempo
aumentam, passando de 1 a 5 para 1 a 10 UT, o modelo disjuntivo adaptado se
torna ainda mais competitivo, sendo capaz de resolver o problema de
sequenciamento de job shop mais rapidamente em quase todos os testes com
tempos de processamento entre 1 e 10 UT. Quando as instâncias apresentam
tempo de processamento das tarefas entre o intervalo de 1 a 5 UT e tamanho médio,
isto é, até 5 tarefas e 5 máquinas, o novo modelo, o modelo de kondili adaptado e
revisado e o modelo disjuntivo adaptado são capazes de encontrar uma solução
ótima em até 0,1 segundo. Também nessas condições o modelo disjuntivo adaptado
apresentou uma leve vantagem.
Das 10 rodadas realizadas para resolver instâncias 10 x 10 e com tempos de
processamento entre 1 e 5 UT, o modelo disjuntivo adaptado conseguiu encontrar
uma solução ótima em 50% dos casos. Nessas condições, as formulações com
variáveis indexadas no tempo e com ao menos uma restrição modelada como fluxo
em rede foram quase quatro vezes mais ágeis para encontrar a solução ótima do
que o modelo disjuntivo adaptado.
64
Quando o intervalo dos tempos de processamento aumenta para entre 1 e
10 UT, as formulações com variáveis indexadas no tempo perdem muita
competitividade. Uma explicação para isso é que neste tipo de modelo o número de
variáveis de decisão aumenta à medida que o tempo total H definido aumenta,
precisando, assim, de um esforço computacional maior.
Um resultado a ser notado é o ganho de desempenho das formulações com
variáveis indexadas no tempo em função da introdução das restrições modeladas
como fluxos em rede. Para quantificar essa melhoria foi comparada a diminuição do
tempo de resolução das instâncias pelo novo modelo e pelo modelo de Kondili
adaptado e revisado em relação ao modelo de Kondili adaptado. A base de
comparação para os resultados apresentados na Tabela 10 foi a média do tempo
gasto por cada formulação para encontrar a solução ótima das instâncias testadas.
Tabela 10 – Redução do tempo de resolução dos modelos com variáveis indexadas no tempo com alguma restrição como fluxo em rede em comparação ao modelo de kondili
adaptado
Intervalos dos tempos de
processamento (UT)
Instância (n x m)
Modelo de kondili adaptado e revisado
Novo modelo
[1,5] 3 x 3 66,67% 61,96%
[1,5] 3 x 6 79,23% 71,16%
[1,5] 3 x 8 69,92% 57,98%
[1,5] 3 x 10 71,95% 57,64%
[1,5] 4 x 3 81,56% 78,63%
[1,5] 5 x 3 89,11% 88,15%
[1,5] 5 x 5 91,94% 87,65%
[1,5] 8 x 8 81,26% 79,75%
[1,5] 10 x 10 86,76% 87,03%
[1,5] 12 x 12 - -
[1,5] 15 x 15 - -
[1,5] 20 x 15 - -
[1,10] 3 x 3 70,37% 89,12%
[1,10] 3 x 6 77,88% 77,97%
[1,10] 3 x 8 80,76% 79,36%
65
[1,10] 3 x 10 81,40% 76,81%
[1,10] 4 x 3 86,96% 76,77%
[1,10] 5 x 3 94,19% 94,82%
[1,10] 5 x 5 90,19% 90,88%
[1,10] 8 x 8 67,64% 62,90%
[1,10] 10 x 10 - -
[1,10] 12 x 12 - -
[1,10] 15 x 15 - -
[1,10] 20 x 15 - -
Além do tempo de resolução, outro indicador utilizado para medir a eficiência
de uma formulação é o gap de integralidade ou a diferença entre o valor da solução
ótima inteira e o valor da solução ótima com relaxação linear antes e depois dos
cortes. Assim, quanto menor o gap de integralidade de um modelo, menor o
tamanho da árvore de branch-and-bound e o esforço computacional de busca por
uma solução ótima. A fórmula para obter esta medida por ser observada abaixo:
𝐺𝑎𝑝 𝑑𝑒 𝐼𝑛𝑡𝑒𝑔𝑟𝑎𝑙𝑖𝑑𝑎𝑑𝑒 =(𝑍𝑂𝑝𝑡 − 𝑍𝑅𝐿)
𝑍𝑂𝑝𝑡 (57)
Onde 𝑍𝑂𝑝𝑡 é o valor da solução ótima e 𝑍𝑅𝐿 é o valor da solução ótima com
relaxação linear, que pode ser antes dos cortes ou depois dos cortes.
A seguir são analisados os valores das soluções ótimas com relaxação
linear antes e depois dos cortes, o número de nós até a solução ótima e o tempo de
resolução de duas instâncias 8 x 8 para os casos em que os tempos de
processamento estão entre 1 e 5 e 1 e 10 UT para as quatro formulações
comparadas. As instâncias utilizadas para a comparação foram escolhidas por
apresentarem tamanho moderado, terem suas soluções ótimas encontradas para as
quatro formulações avaliadas e devido aos seus tempos de resolução razoáveis. Os
correspondentes gráficos comparativos dos gaps de integralidade podem ser
66
observados e revelam a diferença entre as soluções iniciais dos quatro modelos
analisados.
Tabela 11 – Resultados das formulações para uma instância 8 x 8 com tempos de processamento entre 1 e 5 UT, semente 3 e solução ótima igual 266
Modelo
Resultado da relaxação
linear antes dos cortes
Resultado da relaxação
linear depois dos cortes
Número de nós
Tempo de resolução
(s)
Modelo disjuntivo adaptado 205,00 220,16 128.443 19,02
Modelo de Kondili adaptado 205,00 206,87 60.588 129,17
Modelo de kondili adaptado e revisado
246,28 248,06 8.318 27,45
Novo modelo 245,71 246,36 4.795 26,78
A Tabela 11 demonstra que o modelo disjuntivo adaptado é capaz de
resolver uma quantidade de nós muito mais rapidamente que as formulações com
variáveis indexadas no tempo. A mesma tabela evidencia o ganho na introdução das
restrições como fluxos em rede. Nota-se há uma grande redução do número de nós
analisados pelo novo modelo e pelo modelo de Kondili adaptado e revisado em
comparação com o modelo de Kondili adaptado.
A Figura 12 compara os gaps de integralidade antes e depois dos cortes
com base nos resultados apresentados na Tabela 11 para as quatro formulações.
67
Figura 12 – Análise comparativa dos gaps de integralidade das formulações para uma instância 8 x 8 com tempos de processamento entre 1 e 5 UT, semente 3 e solução ótima
igual 266
A Figura 12 mostra uma queda dos gaps de integralidade antes e depois do
corte com a introdução das restrições como fluxos em rede. Além de terem os
menores gaps de integralidade entre as quatro formulações analisadas, o novo
modelo e o modelo de Kondili adaptado e revisado apresentam uma variação
relativamente pequena entre o resultado da relaxação antes e o resultado da
relaxação depois dos cortes em comparação ao modelo disjuntivo adaptado.
A Tabela 12 confirma os resultados encontrados na Tabela 11 e indica a
maior velocidade do modelo disjuntivo adaptado na análise de nós. Além disso, o
novo modelo e o modelo de Kondili adaptado, também nessas condições, reduziram
consideravelmente a quantidade de nós analisados até encontrem a solução ótima.
68
Tabela 12 – Resultados das formulações para uma instância 8 x 8 com tempos de processamento entre 1 e 10 UT, semente 6 e solução ótima igual 468
Modelo
Resultado da relaxação
linear antes dos cortes
Resultado da relaxação
linear depois dos cortes
Número de nós
Tempo de resolução
(s)
Modelo disjuntivo adaptado 367,10 370,61 31.512 4,63
Modelo de Kondili adaptado 301,00 338,37 66.038 289,58
Modelo de kondili adaptado e revisado
434,82 436,05 5.520 74,98
Novo modelo 434,82 435,29 5.710 132,03
De forma análoga, a Figura 13 ratifica a comparação demonstrada na Figura
12 e evidencia a diminuição dos gaps de integralidade a partir da modelagem de
restrições como fluxos em rede nas formulações com variáveis indexadas no tempo.
Figura 13 – Análise comparativa dos gaps de integralidade das formulações para uma instância 8 x 8 com tempos de processamento entre 1 e 10 UT, semente 6 e solução ótima
igual 468
69
Nas duas instâncias escolhidas para serem analisadas, embora os tempos
de resolução do modelo disjuntivo adaptado tenham sido inferiores aos do novo
modelo e do modelo de Kondili adaptado e revisado, os gaps de integralidade para
estas formulações foram bem menores. A introdução das restrições como fluxos em
rede também foi determinante para diminuir a diferença entre os valores ótimos com
relaxação linear e a solução ótima inteira.
70
4 FORMULAÇÃO DE PI PARA O PROBLEMA DE ALOCAÇÃO DE
BOBINAS NA PRODUÇÃO DE DUTOS FLEXÍVEIS
4.1 INTRODUÇÃO
Em 2016, a produção nacional de petróleo alcançou a média de 2,52
milhões de barris diários, dos quais 94,0% são de origem marítima (EPE, 2017).
Para atingir este marco, a produção offshore de óleo e gás exige um conjunto de
soluções elaboradas a fim de viabilizar as diversas operações complexas que
compõem a exploração no oceano. Dentre o universo de ferramentas, máquinas e
equipamentos desenvolvidos para atender essa indústria, está o duto flexível que é
aplicado no transporte de petróleo bruto, gás, condensados, água e produtos
químicos. A direção do fluxo que passa por um duto flexível pode ser da unidade de
produção para o poço, do poço para a unidade de produção e entre unidades de
produção.
Os dutos flexíveis podem ser aplicados de três maneiras distintas: como
risers, flowlines e jumpers. Os risers são empregados para interligar pontos entre
unidades de produção e equipamentos submarinos. Os dutos aplicados para cumprir
essa função estão sujeitos a cargas dinâmicas devido aos movimentos gerados
pelas forças resultantes de carregamentos causados por condições ambientais
como vento, estado de mar e irregularidades do leito marinho. Os flowlines são
utilizados para escoamento e ligam os equipamentos submarinos aos risers. Após
sua instalação, permanecem apoiados no fundo do mar. Os jumpers, por sua vez,
são dutos flexíveis de menor comprimento responsáveis pela interligação entre
equipamentos submarinos como a árvore de natal ao manifold. A árvore de natal é
um equipamento instalado na cabeça do poço e permite a abertura, fechamento e
controle de sua produção ou injeção, enquanto o manifold possibilita o controle e
intervenção da produção de um grupo de poços. A Figura 14 apresenta um exemplo
de arranjo submarino com as aplicações descritas para um duto flexível.
71
Figura 14 – Exemplo de arranjo submarino com aplicações de dutos flexíveis
A busca pela redução de custos na fabricação de equipamentos para
exploração no oceano, caso dos dutos flexíveis, se intensificou a partir da recente
queda do preço do barril de petróleo. Um dos motivos dessa queda foi o aumento da
oferta do petróleo de xisto, uma fonte de energia fóssil com enormes reservas
conhecidas. O óleo e gás de xisto, nome popular da rocha denominada folhelho, são
extraídos a partir de técnicas ainda caras, como a dissolução térmica e o fracking ou
fraturamento hidráulico. Quando o preço do barril de petróleo ultrapassa um
determinado patamar, a exploração de muitas dessas reservas passa a ser viável.
Na prática, isso acaba impondo um teto ao preço do petróleo. Com uma receita
prevista para o futuro praticamente constante, as únicas formas de aumento das
margens de lucro são o aumento da eficiência e redução dos custos operacionais.
Um duto flexível é composto por várias camadas independentes cujos
principais componentes são materiais termoplásticos e fios de aço espiralados em
hélices, conforme Figura 15. As camadas termoplásticas têm como objetivos conferir
estanqueidade ao escoamento do fluido interno e proteger contra o processo
corrosivo as camadas de aço. Estas, por sua vez, têm a função de resistir às
pressões externas, internas e às cargas axiais, além de contribuir para a flexibilidade
72
do duto. A sequência exata de camadas, o comprimento e o diâmetro de um duto
são calculados de acordo com seu projeto de utilização, que é influenciado pela sua
aplicação, fluido transportado, poço produtor e tipo de plataforma. Devido à estrutura
multicamadas do duto flexível, sua produção, armazenamento, manuseio e
instalação requerem alguns cuidados de modo que o produto não perca as
propriedades para as quais foi projetado. Um desses cuidados é evitar que o duto
seja submetido a uma curvatura acima da especificada.
Figura 15 – Duto flexível
A fabricação dos dutos flexíveis é realizada de forma modular, da camada
mais interna para a mais externa. Cada camada é fabricada em uma máquina, que
pertence a um workcenter composto de várias máquinas similares. Os dutos flexíveis
em produção são temporariamente armazenados e transportados de uma máquina a
outra em bobinas. Exemplos de bobinas podem ser observados na Figura 16. A
principal contribuição deste capítulo é propor um modelo de PI para alocação ótima
das bobinas usadas na produção de dutos flexíveis. Esse modelo já utiliza como
entrada um plano de produção, um sequenciamento no tempo das atividades de
produção nas máquinas. A resolução desse problema de sequenciamento, que
costuma corresponder a um problema de job shop flexível, devido à existência de
workcenters, segundo Pinedo (2005), não é o escopo deste estudo. Existem várias
metodologias propostas na literatura e que são utilizadas na prática para a resolução
do clássico e difícil problema de sequenciamento de job shop, um problema que
73
pode ocorrer em muitos tipos de indústria. Entretanto, não é de conhecimento do
autor nenhum outro trabalho que proponha uma metodologia para resolver o
problema da alocação de bobinas, que é um problema específico à indústria da
fabricação de dutos.
Figura 16 – Bobinas
É natural que ao longo da execução de um planejamento ocorram eventos
inesperados, que forcem alterações no planejamento inicial. O modelo proposto
neste capítulo foi criado pensando nessa necessidade, permitindo que bobinas já
comprometidas com certas atividades, fiquem fora de um replanejamento, só sendo
consideradas pelo modelo a partir de um dado instante de liberação no futuro,
quando aquelas atividades terminarem. A função objetivo do modelo visa minimizar
o custo de movimentação das bobinas vazias na fábrica. No entanto, o modelo
também pode ser usado para reduzir o número de bobinas necessárias para realizar
certo número de atividades. O modelo de PI para a alocação ótima de bobinas foi
testado em um caso real de grande porte, com dados que correspondem a um
período de planejamento de seis meses de uma empresa fabricante de dutos.
74
O restante do capítulo é organizado nas seguintes seções. Na Seção 4.2, a
metodologia do capítulo é explicada. Na Seção 4.3, são fornecidos detalhes do
produto considerado no trabalho, isto é, o duto flexível, e das principais
características de seu processo produtivo. A Seção 4.4 introduz um exemplo
ilustrativo para aprofundar o entendimento do leitor sobre o objeto deste estudo. A
Seção 4.5 descreve o modelo matemático utilizado para calcular a alocação de
bobinas vazias no processo produtivo do duto flexível. A Seção 4.6 demonstra a
implementação do método proposto e analisa seus resultados.
4.2 METODOLOGIA DA PESQUISA
A estrutura metodológica para abordar o problema de alocação de bobinas
foi esquematizada conforme a Figura 17:
Figura 17 – Etapas da metodologia da pesquisa para o problema de alocação de bobinas
4.2.1 Reconhecimento e levantamento de dados do processo fabril
O problema de alocação de bobinas foi identificado em uma fábrica de dutos
flexíveis localizada no Estado do Rio de Janeiro. Após finalização do planejamento
de curto prazo da fabricação dos produtos, o processo de alocação de bobinas
75
acontecia de maneira não sistemática e demandava tempo considerável. Assim,
para iniciar o estudo do problema foi necessário, em primeiro lugar, levantar os
dados referentes ao plano de produção de um semestre. Este levantamento foi
realizado por Dos Santos (2017) em seu trabalho de conclusão de curso. Em posse
desse material, foi possível compreender a operação da fábrica e mapear as
máquinas e atividades envolvidas no processo fabril. A partir do plano de produção
foi possível agrupar atividades consecutivas realizadas em um mesmo duto por
máquinas diferentes.
4.2.2 Elaboração e programação do modelo matemático
Após a etapa de levantamento de dados de fabricação e mapeamento das
operações da fábrica, o modelo matemático foi elaborado. O problema da alocação
de bobinas foi modelado como um problema de escalonamento com variáveis
inteiras.
A programação foi realizada com o UFFLP e o VBA. O resolvedor escolhido
foi o CPLEX Optimization versão 12.7.0 e sua utilização envolveu os 8
processadores lógicos disponíveis. Os testes foram rodados em um computador com
as configurações listadas a seguir:
Processador: Intel® Core ™ i7-4970 CPU @ 3.60 GHz;
Memória instalada (RAM): 16 GB;
Sistema Operacional: Windows 10 de 64 bits.
4.2.3 Aplicação no estudo de caso
Neste estudo, foi utilizada a modalidade de pesquisa chamada estudo de
caso. Segundo Gil (2009), essa modalidade consiste no estudo profundo e exaustivo
de uma ou poucas situações ou objetos de modo a possibilitar seu conhecimento
amplo e detalhado. Assim, utilizando os dados levantados na primeira etapa, o
modelo foi utilizado para resolver o caso real do problema de alocação de bobinas
para fabricação de dutos flexíveis.
76
4.2.4 Discussão dos resultados e comparação com a situação anterior
Os resultados gerados com a solução do problema foram analisados e
comparados com o método anterior que definia como as bobinas seriam alocadas
aos dutos flexíveis. Dessa forma, foi possível mensurar as melhorias em termos de
eficiência do processo de planejamento e os ganhos de utilização das bobinas.
4.3 PRODUTO E PROCESSO DE PRODUÇÃO
Cada duto flexível é composto por diferentes camadas e materiais com o
objetivo de realizar funções específicas e este conjunto é denominado de estrutura.
Cada camada possui uma função de aplicação, conforme exemplificado na Tabela
13. Cada camada deve ser produzida em uma das máquinas de um determinado
workcenter. Tipicamente, existem quatro workcenters para produção dos dutos:
carcaça, extrusora, espiraladora e armadora.
Tabela 13 – Descrição das camadas de um típico duto
Camada Principal função Workcenter
Carcaça Resistência aos carregamentos radiais e ao
colapso Carcaça
Barreira de pressão Estanqueidade de fluido interno Extrusora
Armadura de pressão Resistência à pressão interna e ao esforço radial Espiraladora
Camada anti-colapso Vedação para as armaduras de pressão e
resistência à pressão hidrostática Extrusora
Armadura de tração Resistência ao esforço axial e radial Armadora
Camada anti-atrito Restrição do atrito entre armadura de tração e
armadura de pressão Extrusora
Camada de
isolamento térmico Diminuição da perda de calor interno do duto Espiraladora
Barreira externa Vedação de fluido externo Extrusora
A fabricação de cada camada de um duto específico define uma atividade.
Cada atividade deve estar alocada a uma bobina de entrada, que armazena o duto
77
em produção vindo da atividade anterior. A única exceção é a primeira atividade de
um duto, que não precisa de bobina de entrada, pois é responsável por fabricar a
sua camada mais interna. De modo similar, cada atividade deve também estar
alocada a uma bobina de saída, que armazena o duto com a camada adicional
produzida. A bobina de saída de uma atividade é a mesma bobina de entrada da
atividade seguinte e o transporte dos dutos em produção de uma máquina para a
seguinte é feito nessa bobina. Após a conclusão de todas as camadas de um duto, a
última atividade, chamada de respool, é executada e consiste em transferir o duto da
bobina de saída da última camada para uma bobina externa, que será enviada ao
cliente. Este trabalho trata apenas da alocação das bobinas internas à produção,
assim as bobinas externas enviadas ao cliente não foram consideradas. Dessa
forma, no modelo proposto, a última atividade de um duto, o respool, apenas precisa
de uma bobina de entrada. O duto em produção deve ser alocado a uma bobina com
um raio de curvatura que não faça com que este seja danificado.
A bobina, que é responsável pelo armazenamento e locomoção dos dutos, é
dividida em duas partes, o tambor e o flange. O tambor é a parte central da bobina,
onde os dutos ficam armazenados, e pode apresentar variação de diâmetro e do
tamanho do transverso. Já o flange são as duas abas localizadas nas extremidades
da bobina, que são responsáveis pela sustentação de toda estrutura e suporte para
movimentação. A Figura 18 esquematiza as partes de uma bobina.
Figura 18 – Partes de uma bobina
78
Neste estudo, somente o diâmetro do tambor foi considerado crítico para a
alocação das bobinas, pois está diretamente relacionado à restrição do raio de
curvatura mínimo do duto. O diâmetro do flange e a largura do transverso, por suas
vezes, estão associados ao comprimento do duto e não apresentam nenhuma
restrição para a extensa maioria dos casos.
4.4 EXEMPLO ILUSTRATIVO
Para ilustrar o problema tratado neste trabalho foi proposto um exemplo
completo do processo de alocação de bobinas. Neste exemplo, o objetivo é alocar
de forma ótima, isto é, com a movimentação mínima, quatro bobinas, sendo duas
com tambor de 14 ft e duas com tambor de 20 ft, para produção de três dutos
fictícios compostos, cada um, por três camadas. As atividades para a fabricação de
cada camada dos dutos e o seu escalonamento em máquinas já foram
estabelecidas conforme o plano de produção mostrado na Tabela 14.
Tabela 14 – Exemplo de plano de produção
Duto Atividade Diâmetro
mínimo (ft) Início (UT)
Fim (UT)
Workcenter Máquina Local
Duto 1 AT1 14 1 3 Carcaça Carcaça 1 1
Duto 1 AT2 20 4 6 Armadora Armadora1 3
Duto 1 AT3 14 7 9 Extrusora Extrusora 1 4
Duto 1 R - 11 14 Respool Respool I 5
Duto 2 AT1 14 8 10 Carcaça Carcaça 1 1
Duto 2 AT2 20 11 13 Armadora Armadora1 2
Duto 2 AT3 20 15 17 Extrusora Extrusora 1 4
Duto 2 R - 18 20 Respool Respool I 5
Duto 3 AT1 14 2 4 Carcaça Carcaça 2 1
Duto 3 AT2 14 5 7 Espiraladora Espiraladora 1 3
Duto 3 AT3 14 15 17 Extrusora Extrusora 2 4
Duto 3 R - 18 20 Respool Respool 2 5
A Tabela 15 apresenta a matriz de distância entre os cinco locais
considerados neste exemplo, que correspondem aos quatro workcenters de
79
produção e ao respool. A distância é obtida considerando o percurso de
movimentação de uma bobina vazia da entrada de um workcenter à saída de outro
workcenter. A distância de um workcenter para ele mesmo não é nula, pois o
deslocamento entre sua entrada e a saída não pode ser desconsiderado.
Tabela 15 – Distâncias (metros) entre locais do exemplo
Entrada|Saída 1 2 3 4 5
1 85 20 70 90 80
2 130 85 115 20 55
3 120 75 80 75 25
4 165 130 150 90 105
5 115 80 100 75 0
A Tabela 16 mostra os instantes e locais de liberação de cada bobina.
Tabela 16 – Instantes e locais de liberação das bobinas do exemplo
Bobina Diâmetro
(ft) Instante de
liberação (UT) Local de liberação
Bobina 1 14 0 5
Bobina 2 14 0 5
Bobina 3 20 1 5
Bobina 4 20 1 5
Neste trabalho é proposto o conceito de uso de uma bobina. Um uso
corresponde a um par de atividades consecutivas do mesmo duto. Um uso possui
um instante e um local de início, que são, respectivamente, o instante e o local da
sua primeira atividade. De forma análoga, um uso apresenta um instante e local de
fim, que são, respectivamente, o local e o fim de sua segunda atividade. O uso
também possui um diâmetro mínimo, que é o diâmetro mínimo de sua primeira
atividade. A Tabela 17 apresenta os dados dos 9 usos definidos pelas 12 atividades
do exemplo.
80
Tabela 17 – Usos definidos pelo plano de produção do exemplo
Uso Duto Primeira atividade
Segunda atividade
Diâmetro mínimo (ft)
Início do uso
(UT)
Fim do uso (UT)
Local de início
Local de fim
Uso 1 Duto 1 AT1 AT2 14 1 6 1 3
Uso 2 Duto 1 AT2 AT3 20 4 9 3 4
Uso 3 Duto 3 AT1 AT2 14 2 7 1 3
Uso 4 Duto 3 AT2 AT3 14 5 17 3 4
Uso 5 Duto 1 AT3 R 14 7 14 4 5
Uso 6 Duto 2 AT1 AT2 14 8 13 1 2
Uso 7 Duto 2 AT2 AT3 20 11 17 2 4
Uso 8 Duto 2 AT3 R 20 15 20 4 5
Uso 9 Duto 3 AT3 R 14 15 20 4 5
No alto da Figura 19 é possível observar um diagrama de Gantt do plano de
produção definido na Tabela 17. Na parte de baixo da mesma figura, há um
diagrama de Gantt para os usos correspondentes. Os usos são identificados por
números diferentes e estão relacionados a um duto e a duas atividades. Assim, por
exemplo, o Uso 4 refere-se ao Duto 3 e às suas Atividades 2 e 3, que correspondem
à execução das máquinas Espiraladora 1 e Extrusora 2.
As bobinas devem ser alocadas aos usos. Essa alocação significa que a
bobina alocada será colocada vazia na saída da máquina que executa a primeira
atividade, depois essa bobina cheia, isto é, com o duto em produção, será
movimentada para a entrada da máquina que executa a segunda atividade. Ao final
da segunda atividade a bobina estará novamente vazia e pronta para ser
movimentada para o seu próximo uso. A movimentação das bobinas cheias já é
fixada pelo plano de produção, e, portanto, não tem como ser otimizada nessa etapa
do planejamento. Entretanto, a alocação afeta diretamente a movimentação de
bobinas vazias.
81
Figura 19 – Diagramas de Gantt do plano de produção e dos seus usos
Duto 1
Duto 2
Duto 3
Uso 3-D3 AT1/AT2 (14) Uso 9-D3 AT3/R (14)
Uso 4-D3 AT2/AT3 (14)
Diagrama de Usos
Plano de Produção
Uso 1-D1 AT1/AT2 (14) Uso 5-D1 AT3/R (14)
Uso 2-D1 AT2/AT3 (20)
Uso 6-D2 AT1/AT2 (14) Uso 8-D2 AT3/R (20)
Tempo 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
D1-AT1 (14) D1-AT2 (20) D1-AT3 (14) D1-R
D2-AT1 (14) D2-AT2 (20)
Uso 7-D2 AT2/AT3 (20)
D2-AT3 (20) D2-R
D3-AT1 (14) D3-AT2 (14) D3-AT3 (14) D3-R
82
As Tabelas 18 e 19 mostram a solução do problema, uma alocação das
bobinas de 14 ft e 20 ft aos usos e a correspondente movimentação de bobinas
vazias. Essa solução assume que deve ser respeitado um intervalo mínimo de um
período entre duas alocações consecutivas de uma bobina, tempo para que sua
movimentação possa ser realizada.
Tabela 18 – Alocação das bobinas na solução do exemplo
Uso Bobina
Uso 1 Bobina 1
Uso 2 Bobina 3
Uso 3 Bobina 4
Uso 4 Bobina 2
Uso 5 Bobina 1
Uso 6 Bobina 4
Uso 7 Bobina 3
Uso 8 Bobina 4
Uso 9 Bobina 1
Tabela 19 – Movimentação das bobinas vazias na solução do exemplo
Bobina Diâmetro
(ft) Uso inicial Uso final
Local de entrada
Local de saída
Distância (m)
Bobina 1 14 Local de
Liberação Uso 1 5 1 115
Bobina 1 14 Uso 1 Uso 5 3 4 75
Bobina 1 14 Uso 5 Uso 9 5 4 75
Bobina 2 14 Local de
Liberação Uso 4 5 3 100
Bobina 3 20 Local de
Liberação Uso 2 5 3 100
Bobina 3 20 Uso 2 Uso 7 4 2 130
Bobina 4 20 Local de
Liberação Uso 3 5 1 115
Bobina 4 20 Uso 3 Uso 6 3 1 120
Bobina 4 20 Uso 6 Uso 8 2 4 20
Total 850 (m)
83
Considere, por exemplo, a Bobina 1. Essa bobina é liberada no respool
(Local 5) no instante 0. Ela é transportada vazia até a saída do workcenter Carcaça
(Local 1), percorrendo uma distância de 115 metros. Entre os instantes 1 e 3, a
bobina recebe a camada mais interna do Duto 1. A bobina, contendo essa camada
totalmente fabricada, será transportada para a entrada do workcenter Armadora
(Local 3). No instante 4 a bobina começa a alimentar a máquina que fabrica a
camada intermediária do Duto 1, ficando totalmente esvaziada no instante 6. A
bobina é transportada, percorrendo 75 metros, para a saída do workcenter Extrusora
(Local 4), onde, entre os instantes 7 e 9, receberá o Duto 1 já completo, com todas
as suas três camadas. A bobina será levada para o respool, onde, entre os instantes
11 e 14, o Duto 1 será transferido para uma bobina externa, que será enviada ao
cliente. A Bobina 1 em seguida será levada para a Extrusora, percorrendo 75
metros e receberá o Duto 3 da máquina que fabrica sua última camada. A bobina em
seguida retorna para o respool, onde estará disponível ao final do horizonte de
planejamento.
4.5 MODELO MATEMÁTICO
Seja 𝐿 o conjunto de locais na fábrica. Dado um par de locais 𝑖, 𝑗 ∈ 𝐿, 𝑑𝑖𝑗
denota a distância entre eles. Seja U o conjunto de usos de bobina, defina 𝑛 = |𝑈|.
Para cada uso 𝑢 ∈ 𝑈, 𝑠(𝑢), 𝑠𝑙(𝑢), 𝑒(𝑢) e 𝑒𝑙(𝑢) denotam seu instante de início, local
de início, instante final e local final, respectivamente. Seja 𝐾 o conjunto de tamanhos
do diâmetro do tambor das bobinas, defina 𝑚 = |𝐾|. Para cada tamanho 𝑘 ∈ 𝐾,
𝑈𝑘 ⊆ 𝑈 denota o conjunto de usos que são compatíveis com bobinas de tamanho k
ou maiores. Para cada tamanho 𝑘 ∈ 𝐾, seja 𝑅𝑘 o conjunto de liberações de bobinas
de tamanho k. Para cada 𝑟 ∈ 𝑅𝑘, seja 𝑒(𝑟) o instante de liberação, 𝑒𝑙(𝑟) o local de
liberação e 𝑏𝑘(𝑟) o número de bobinas liberadas. Ressalta-se que é possível ter
duas ou mais liberações simultâneas de bobinas de mesmo tamanho, se elas
acontecerem em diferentes locais. Os instantes de liberação podem ser
compreendidos como usos especiais, em que somente o instante final e o local final
são definidos e que 𝑏𝑘(𝑟) bobinas são pré-alocadas. Por fim, o parâmetro 𝛼
representa o tempo mínimo entre duas alocações consecutivas de uma bobina para
usos.
84
Para cada tamanho 𝑘 ∈ 𝐾, define-se um grafo direcionado 𝐺𝑘 = (𝑉𝑘, 𝐴𝑘) com
o conjunto de vértices 𝑉𝑘 = 𝑈𝑘⋃𝑅𝑘⋃{𝑡}, onde t é um uso artificial que representa o
final da sequência de alocações de todas as bobinas. O conjunto de arcos 𝐴𝑘 é dado
por 𝐴𝑘1 ⋃𝐴𝑘
2⋃𝐴𝑘3 , onde 𝐴𝑘
1 = {(𝑟, 𝑢)|𝑟 ∈ 𝑅𝑘, 𝑢 ∈ 𝑈𝑘, 𝑠(𝑢) ≥ 𝑒(𝑟) + 𝛼}, 𝐴𝑘2 = {(𝑢, 𝑣)|𝑢 ∈
𝑈𝑘, 𝑣 ∈ 𝑈𝑘, 𝑠(𝑣) ≥ 𝑒(𝑢) + 𝛼} e 𝐴𝑘3 = {(𝑢, 𝑡)|𝑢 ∈ 𝑈𝑘⋃ 𝑅𝑘}. Para cada 𝑘 ∈ 𝐾, defina
𝛿𝑘−(𝑢) ⊆ 𝐴𝑘 como o conjunto de arcos de 𝐺𝑘 entrando no vértice 𝑢 ∈ 𝑉𝑘.
Analogamente, 𝛿𝑘+(𝑢) denota o conjunto de arcos que deixa 𝑢. Para cada 𝑘 ∈ 𝐾 e
todo (𝑢, 𝑣) ∈ 𝐴𝑘, defina uma variável binária 𝑥𝑢𝑣𝑘 que indica se uma bobina de
tamanho k é alocada a 𝑢 e em seguida é alocada para 𝑣.
O custo 𝑐𝑢𝑣𝑘 de uma variável 𝑥𝑢𝑣𝑘 corresponde ao custo de movimentação
de uma bobina vazia de tamanho 𝑘 de 𝑒𝑙(𝑢) até 𝑠𝑙(𝑣). Se 𝑣 = 𝑡, o custo é definido
como zero, uma vez que as bobinas não são de fato transferidas para o uso final
artificial; caso contrário, o custo pode ser proporcional a 𝑑𝑒𝑙(𝑢),𝑠𝑙(𝑣). No entanto, caso
o usuário do modelo também esteja interessado em minimizar o número de bobinas
utilizadas, custos fixos 𝑀𝑘 devem ser adicionados aos custos das variáveis
referentes aos arcos em 𝐴𝑘1 . Se os custos fixos forem relativamente altos em
comparação aos custos de movimentação, o modelo é capaz de encontrar soluções
com a quantidade mínima possível de bobinas.
A formulação pode ser observada a seguir:
𝑀𝑖𝑛 ∑ ∑ 𝑐𝑢𝑣𝑘𝑥𝑢𝑣𝑘
(𝑢,𝑣)∈𝐴𝑘𝑘∈𝐾
(58)
sujeito a
∑ 𝑥𝑣𝑢𝑘
(𝑣,𝑢)∈𝛿𝑘−(𝑢)
− ∑ 𝑥𝑢𝑣𝑘
(𝑢,𝑣)∈𝛿𝑘+(𝑢)
= 0 ∀𝑘 ∈ 𝐾, ∀𝑢 ∈ 𝑈𝑘 (59)
− ∑ 𝑥𝑟𝑢𝑘
(𝑟,𝑢)∈𝛿𝑘+(𝑟)
= −𝑏𝑘(𝑟) ∀𝑘 ∈ 𝐾, ∀𝑟 ∈ 𝑅𝑘 (60)
85
∑ ∑ 𝑥𝑣𝑢𝑘
(𝑣,𝑢)∈𝛿𝑘−(𝑢)
= 1
𝑘∈𝐾
∀𝑢 ∈ 𝑈 (61)
𝑥𝑢𝑣𝑘 ≥ 0 𝑒 é 𝑖𝑛𝑡𝑒𝑖𝑟𝑎 ∀𝑘 ∈ 𝐾, ∀(𝑢, 𝑣) ∈ 𝐴𝑘 (62)
A função objetivo está definida em (58) e consiste em minimizar o custo
associado à movimentação de bobinas vazias devido às sequências de alocação
para cada uma delas. As Equações (59) são restrições de conservação de fluxo, que
garantem que, para cada diâmetro de bobina e para cada uso, deve haver o mesmo
número de usos antecessores, que pode ser uma liberação, e de usos sucessores,
que pode ser t. As Equações (60) garantem que as alocações sejam compatíveis
com o número de bobinas de diâmetro k liberadas em cada instante. As Equações
(61) garantem que exatamente uma bobina compatível deve ser alocada para cada
uso. As Restrições (62) definem que todas as variáveis 𝑥𝑢𝑣𝑘 são não negativas e
inteiras. Em função das Equações (61), as únicas variáveis que possivelmente
podem assumir valores superiores a 1 são aquelas em que 𝑢 ∈ 𝑅𝑘 e 𝑣 = 𝑡, isto é, as
variáveis que indicam quantas bobinas de cada liberação não serão usadas na
solução. A seguinte equação:
∑ ∑ 𝑥𝑢𝑡𝑘
(𝑢,𝑡)∈𝛿𝑘−(𝑡)
= ∑ ∑ 𝑏𝑘
𝑟∈𝑅𝑘𝑘∈𝐾
(𝑟),
𝑘∈𝐾
(63)
decorre de (59-60) e, portanto, não precisa ser incluída no modelo. De
qualquer forma, ela significa que o fluxo de todas as bobinas termina no vértice t.
A Figura 20 apresenta os grafos dos usos das bobinas de 14 ft e 20 ft para o
exemplo ilustrativo da Seção 4.4. No grafo de usos de bobinas de 14 ft, a bobina que
sai do Uso 1 no instante 6, tem a possibilidade de ser realocada a seguir para os
Usos 5, 6 e 9 ou seguir direto para t (o que significa que ela não vai mais ser usada).
Já no grafo de usos de bobinas de 20 ft, a mesma bobina que sai do Uso 1 tem a
possibilidade de ser realocada, além dos outros usos mencionados no caso anterior,
para os Usos 7 ou 8. Na parte de baixo da mesma figura, mostra-se um grafo com
os arcos que possuem valor 1 na solução do modelo. Esses arcos correspondem à
solução ótima mostrada nas Tabelas 18 e 19.
86
Figura 20 – Grafos de usos e a solução para o exemplo dado
Uso 3-D3 AT1/AT2 (14) Uso 9-D3 AT3/R (14)
Uso 4-D3 AT2/AT3 (14)
Grafo da Solução
Uso 2-D1 AT2/AT3 (20)
Uso 6-D2 AT1/AT2 (14) Uso 8-D2 AT3/R (20)
Uso 7-D2 AT2/AT3 (20)
Uso 3-D3 AT1/AT2 (14) Uso 9-D3 AT3/R (14)
Uso 4-D3 AT2/AT3 (14)
Grafo de Usos de Bobinas de 20 ft
Uso 1-D1 AT1/AT2 (14) Uso 5-D1 AT3/R (14)
Uso 2-D1 AT2/AT3 (20)
Uso 6-D2 AT1/AT2 (14) Uso 8-D2 AT3/R (20)
Uso 7-D2 AT2/AT3 (20)
Uso 9-D3 AT3/R (14)
Uso 4-D3 AT2/AT3 (14)
Grafo de Usos de Bobinas de 14 ft
Uso 1-D1 AT1/AT2 (14) Uso 5-D1 AT3/R (14)
Uso 6-D2 AT1/AT2 (14)
Uso 1-D1 AT1/AT2 (14) Uso 5-D1 AT3/R (14)
Tempo 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Liberação 1 t
Liberação 2 t
t
Liberação 1
Liberação 2
Uso 1-D1 AT1/AT2 (14) Uso 5-D1 AT3/R (14)
Uso 4-D3 AT2/AT3 (14)
Uso 3-D3 AT1/AT2 (14) Uso 9-D3 AT3/R (14)
Uso 6-D2 AT1/AT2 (14)
Uso 1-D1 AT1/AT2 (14)
Uso 2-D1 AT2/AT3 (20)
Uso 5-D1 AT3/R (14)
Uso 7-D2 AT2/AT3 (20)
Uso 4-D3 AT2/AT3 (14)
Uso 3-D3 AT1/AT2 (14) Uso 9-D3 AT3/R (14)
Uso 8-D2 AT3/R (20)Uso 6-D2 AT1/AT2 (14)
Uso 1-D1 AT1/AT2 (14)
Uso 2-D1 AT2/AT3 (20)
Uso 5-D1 AT3/R (14)
Uso 7-D2 AT2/AT3 (20)
Uso 4-D3 AT2/AT3 (14)
Uso 3-D3 AT1/AT2 (14) Uso 9-D3 AT3/R (14)
Uso 8-D2 AT3/R (20)Uso 6-D2 AT1/AT2 (14)
87
Teorema 1. Para o caso de um único tamanho, ou seja, |𝐾|=1, a relaxação
linear de (58-62) corresponde a um problema de fluxo em rede de custo mínimo e,
portanto, pode ser resolvido em tempo polinomial e sempre tem solução ótima
inteira.
Prova. Para o caso de um único tamanho, as Equações (59-61) e (63)
podem ser simplificadas para:
∑ 𝑥𝑣𝑢
(𝑣,𝑢)∈𝛿−(𝑢)
− ∑ 𝑥𝑢𝑣
(𝑢,𝑣)∈𝛿+(𝑢)
= 0 ∀𝑢 ∈ 𝑈 (64)
− ∑ 𝑥𝑟𝑢
(𝑟,𝑢)∈𝛿+(𝑟)
= −𝑏(𝑟) ∀𝑟 ∈ 𝑅 (65)
∑ 𝑥𝑣𝑢
(𝑣,𝑢)∈𝛿−(𝑢)
= 1 ∀𝑢 ∈ 𝑈 (66)
∑ 𝑥𝑢𝑡
(𝑢,𝑡)∈𝛿𝑘−(𝑡)
= ∑ 𝑏(𝑟)
𝑟∈𝑅
(67)
Subtraindo as Equações (66) das correspondentes Equações (64), obtém-se:
− ∑ 𝑥𝑢𝑣
(𝑢,𝑣)∈𝛿+(𝑢)
= −1 ∀𝑢 ∈ 𝑈 (68)
As Equações (65-68) definem um fluxo em rede em um grafo com
2|𝑈|+|𝑅|+1 nós, onde cada vértice 𝑢 ∈ 𝑈 é dividido em um nó de entrada com
demanda de 1 unidade (Equações (66)) e um nó de saída com oferta de 1 unidade
(Equações (68)). Logo, pela propriedade da integralidade de fluxo, conforme
apresentado por Ahuja, Magnanti e Orlin (1993), sempre existe uma solução ótima
em que todas as variáveis são inteiras. ∎
Para o caso em que existem vários tamanhos (|𝐾|>1), o modelo proposto
corresponde a um fluxo em rede multi-commodity inteiro. Apesar desse problema em
geral ser NP-difícil, em muitos casos práticos o valor de relaxação costuma ser muito
forte, muito próximo ou até mesmo igual ao valor da solução ótima inteira. Isso
permite que problemas de grande porte sejam resolvidos de forma eficiente. Como
88
exemplo, tem-se o modelo de alocação ótima de vagões em ferrovias proposto por
Fukasawa et al. (2002).
4.6 IMPLEMENTAÇÃO E ESTUDO DE CASO
O estudo de caso de aplicação do modelo utilizou dados reais vindos de
uma fábrica de dutos localizada no Estado do Rio de Janeiro e levantados por Dos
Santos (2017). O plano de produção compreende todas as 684 atividades que
devem ser executadas para a produção de 77 dutos, correspondendo a toda carteira
de projetos do primeiro semestre de 2017. Esse plano de produção gera 607 usos
com início, fim, duração, local inicial, local final e diâmetro mínimo da bobina
conforme detalhado na Tabela 21 do Apêndice.
A fábrica possui quatro workcenters de produção e o workcenter de respool,
tendo um total de 10 máquinas. Na Tabela 22, também encontrada no Apêndice, é
possível encontrar a matriz de correspondência das distâncias entre as 10
máquinas. Para maior precisão no cálculo das distâncias, cada máquina individual
foi considerada como um local, dessa forma, a matriz de distâncias possui dimensão
10 x 10. A fábrica possui um total de 73 bobinas disponíveis para utilização no
processo produtivo, sendo essas distribuídas em cinco diâmetros: 14 ft, 16 ft, 17 ft,
19 ft e 22 ft. A Tabela 20 apresenta a quantidade de bobinas e instantes de liberação
por diâmetro.
Tabela 20 – Quantidade de bobinas e total de instantes de liberação por diâmetro
Diâmetro Quantidade de
bobinas Total de instantes
de liberação
14 43 16
16 11 6
17 7 2
19 1 2
22 1 1
O plano de produção considera um horizonte de 180 dias. Entretanto, alguns
usos começam até o 180º dia e podem se estender além desse horizonte, chegando
ao 249º dia.
89
O CPLEX demorou 733,59 segundos para encontrar a solução ótima do
modelo, que tinha 744.643 variáveis e 3.517 restrições. Essa solução respeita o
intervalo mínimo para movimentação de um dia entre duas alocações consecutivas
de uma bobina. O valor da função objetivo foi de 23.792 metros e representa a
distância total mínima de movimentação de bobinas vazias para cumprir o plano de
produção. É interessante notar que a solução da relaxação linear foi fracionária, mas
com exatamente o mesmo valor da solução inteira ótima. Foram explorados 19 nós
de branch-and-bound para encontrar essa solução inteira. O resultado confirma a
força de modelos de programação inteira baseados em fluxos em rede multi-
commodity.
O semestre do estudo teve um aumento de produção de 10% em relação ao
semestre anterior. É notável que o modelo tenha conseguido encontrar uma solução
viável usando as mesmas 73 bobinas já existentes. Dada a grande dificuldade
encontrada para fazer manualmente a alocação de bobinas para o semestre
anterior, os planejadores haviam estimado que seria necessário adquirir com
urgência 7 novas bobinas. Entretanto, o modelo também verificou que todas as 73
bobinas disponíveis se tornaram indispensáveis, desse modo, a remoção de
qualquer uma delas tornava o plano de produção inviável. Com isso, recomenda-se
a aquisição de somente mais uma bobina, para backup, como forma de lidar com
imprevistos. Assim, estima-se que a aplicação do método proposto permita
economizar um capital de aproximadamente US$ 3 milhões, que seria o custo de
aquisição de seis bobinas adicionais.
A Tabela 23, no Apêndice, apresenta a solução do estudo de caso para a
alocação das bobinas aos usos. As Figuras 21 e 22 representam o Gráfico de Gantt
correspondente à solução ótima do problema. Os usos são identificados pela letra
inicial U e os instantes de liberação pela letra R. Cada linha significa uma bobina
diferente e é identificada por três colunas D, S, ID. A coluna D descreve o diâmetro
da bobina, a coluna S apresenta um código sequencial para o diâmetro e a coluna
ID fornece um código inequívoco para cada bobina. Por exemplo, a quinta linha da
Figura 22 mostra o sequenciamento de uma bobina de diâmetro 16 ft, que é a quinta
de 11 bobinas de 16 ft e tem código inequívoco de 48. Essa bobina é alocada aos
Usos 28, 123, 136, 262, 385, 467 e 608 e está em operação entres os dias 11 e 145.
90
Figura 21 – Diagrama de Gantt dos usos alocados com bobinas de 14 ft
D S ID
14 1 1
14 2 2
14 3 3
14 4 4 U 284
14 5 5
14 6 6
14 7 7
14 8 8
14 9 9
14 10 10
14 11 11
14 12 12
14 13 13
14 14 14
14 15 15
14 16 16
14 17 17
14 18 18
14 19 19
14 20 20
14 21 21
14 22 22
14 23 23
14 24 24
14 25 25
14 26 26
14 27 27
14 28 28
14 29 29
14 30 30 R 30
14 31 31 R 31
14 32 32 R 32
14 33 33 R 33
14 34 34 R 34 U 473
14 35 35 R 35
14 36 36 R 36
14 37 37 R 37
14 38 38 R 38
14 39 39 R 39
14 40 40 R 40
14 41 41 R 41
14 42 42 R 42 U 61
14 43 43 R 43 U 313
U 400 U 464 U 504 U 516 U 545
U 529
U 44 U 126 U 210 U 303 U 322 U 352 U 418
U 32 U 70 U 171 U 204 U 295 U 307 U 413 U 466 U 486 U 503
U 411 U 484 U 525 U 547 U 557 U 595
U 518
U 30 U 161 U 244 U 296
U 199 U 310 U 323
U 8 U 95 U 106 U 173 U 288 U 311 U 368 U 393 U 451 U 483 U 520
U 569
U 26 U 96
U 93 U 224 U 238 U 246 U 278 U 319 U 374 U 450
U 551
U 9 U 127 U 231 U 302
U 213 U 281 U 357 U 412 U 433 U 517 U 540 U 550
U 201 U 243 U 369 U 421 U 455 U 497 U 511
U 533 U 606
U 165 U 432 U 478 U 514
U 17 U 133 U 270 U 349
U 190 U 329
U 607
U 86 U 150 U 245
U 92 U 176 U 197 U 291 U 402 U 424
U 69 U 108 U 120 U 236
U 167 U 265 U 340 U 405 U 425 U 465 U 500
U 118 U 142 U 158 U 316
U 444 U 495
U 113 U 177 U 261
U 87 U 115 U 175 U 422 U 488
U 90 U 137 U 151 U 187 U 273 U 283 U 568
U 200 U 318
U 59 U 144 U 174 U 242 U 255 U 383 U 429
U 581
U 178 U 333 U 342 U 355 U 371 U 446 U 470 U 507
U 152 U 268 U 286 U 327
U 259 U 589
U 68
U 36 U 84 U 301 U 358 U 443 U 476 U 494
U 522 U 544 U 566
U 62 U 83 U 139 U 218 U 346 U 389 U 458 U 539
U 166 U 230 U 253 U 282 U 297 U 381 U 463 U 498
U 23 U 156 U 196 U 289
U 10 U 129 U 159 U 404 U 480 U 509
U 52 U 67 U 202 U 233
U 398
U 140 U 162 U 169 U 237 U 248
U 1 U 66
U 4 U 109 U 146 U 214 U 341 U 456 U 515 U 527
U 3 U 21 U 110 U 186 U 324 U 335
U 570
U 5
U 153 U 254 U 604
U 27 U 56 U 192 U 439 U 454
U 419 U 487
U 16 U 39 U 170 U 258 U 343
U 18
U 12 U 148 U 239 U 287 U 306 U 334 U 359 U 372
R 27
R 4
R 5
R 2
R 3
R 1
R 16
R 13
R 14
R 12
R 10
R 11
R 8
R 9
R 6
R 7
R 22
R 23
R 24
R 25
R 26
R 28
R 29
R 19
R 20
R 21
R 17
R 18
R 15
U 25
U 98
U 35
U 14 U 75
U 101 U 149
U 89 U 154 U 164
U 31 U 112 U 217 U 309 U 356
10080604020 200180
U 597
U 592
U 330 U 380 U 403 U 469 U 524 U 531 U 579
U 336 U 573
U 107 U 147 U 168 U 256
220 240160140120
U 580
U 546
U 528
U 554
U 586
U 582
U 513
U 596
91
Figura 22 – Diagrama de Gantt dos usos alocados com bobinas de 16 ft, 17 ft, 19 ft e 22 ft
D S ID
16 1 44
16 2 45
16 3 46 U 226
16 4 47 U 219 U 449
16 5 48 U 123
16 6 49
16 7 50
16 8 51 U 571
16 9 52
16 10 53
16 11 54
17 1 55
17 2 56
17 3 57
17 4 58
17 5 59
17 6 60
17 7 61
19 1 62
19 2 63 U 317U 325
19 3 64 U 593
19 4 65
19 5 66
19 6 67
19 7 68
19 8 69 U 345
19 9 70
19 10 71
19 11 72 U 222 U 565
22 1 73
U 556
R 71 U 160 U 179 U 249 U 263 U 390 U 426 U 479 U 499 U 535
U 80 U 103 U 163 U 279 U 293 U 367 U 394 U 407 U 431
R 67 U 85 U 119 U 266 U 379 U 392 U 445 U 477 U 510
R 65 U 135 U 195 U 234 U 247 U 351 U 370 U 384 U 441
U 591
R 63 U 143 U 207 U 221 U 337 U 365 U 434 U 447 U 493 U 523
U 235 U 339 U 350 U 364 U 391 U 423 U 489 U 505 U 548
U 272 U 292 U 331 U 395 U 457 U 475 U 496
R 58 U 183 U 414 U 472 U 501
R 56 U 104 U 211 U 251 U 298 U 338 U 386 U 485 U 526
R 53 U 105 U 181 U 194 U 294 U 320 U 373 U 397 U 492
U 590
R 52 U 81 U 91 U 125 U 209 U 227 U 328 U 362 U 420 U 512
R 51 U 78 U 117 U 216 U 257 U 271 U 305 U 377
U 584
U 55 U 76 U 116 U 193 U 212 U 228 U 366 U 406 U 459 U 491 U 521 U 567 U 577
R 49 U 188 U 198 U 215 U 314 U 348 U 416
U 417
U 537
U 442 U 453 U 481 U 552 U 575
U 360 U 388 U 436 U 462
R 48 U 136 U 262 U 385 U 467
U 128 U 155 U 180 U 264
U 72 U 100 U 111 U 134 U 225
R 54 U 79 U 124 U 229 U 564
R 55 U 308 U 344 U 401 U 440 U 562 U 574 U 588
U 277 U 290 U 304 U 376 U 410 U 430 U 519
U 102 U 274 U 561
U 363 U 428
U 553 U 594
R 62 U 172 U 191 U 206
U 603
U 82 U 132 U 138 U 269 U 280 U 396 U 435 U 474 U 549 U 578 U 602
R 61 U 122 U 182 U 267
U 437 U 468 U 543 U 572 U 587
U 559
U 605
U 461 U 471 U 490 U 558
U 438 U 452 U 532 U 555 U 563
U 408 U 482 U 502 U 542 U 585 U 599
U 448 U 534
U 347 U 375 U 399
R 68 U 205
R 72 U 97 U 131 U 232 U 252 U 361 U 378
R 69 U 141 U 189 U 300 U 321 U 332 U 353 U 387 U 415
U 220 U 354 U 382
R 64
R 70
R 73 U 88 U 99 U 184 U 203 U 240
R 66 U 157 U 250 U 276 U 299 U 326
R 57 U 114 U 130 U 260
R 59
R 60
U 94 U 121 U 223
100 120 140 160 180
R 45
R 46
R 47
R 50
U 530 U 541
U 312 U 536 U 601
U 275 U 285 U 315 U 409 U 460 U 538
U 145 U 185 U 208 U 241
20 40 60 80
R 44
U 598
200 220 240
U 560
U 583
U 576
U 600
U 506
U 427 U 508
92
5 CONCLUSÃO E TRABALHOS FUTUROS
Ao longo da Seção 2.2, referente à fundamentação teórica do job shop,
foram identificadas e analisadas as melhores formulações de PI utilizadas para
resolução do problema de sequenciamento de job shop com função objetivo de
minimizar o makespan. No Capítulo 3, duas dessas formulações foram adaptadas ao
caso em que a função objetivo é minimizar o atraso total ponderado.
Após adaptação dos modelos, foram implementadas melhorias com o
objetivo de diminuir o tempo e o esforço computacional na resolução das diferentes
instâncias propostas na metodologia. O foco das melhorias foi o modelo baseado na
formulação com variáveis indexadas no tempo e a estratégia definida para aumentar
a eficiência da nova formulação foi a introdução de restrições como fluxos em rede.
Para comparação do novo modelo, foram realizados testes com três formulações de
referência, o modelo disjuntivo adaptado, o modelo de Kondili adaptado e o modelo
de Kondili adaptado e revisado. Este último teve a inclusão da restrição de
precedência como fluxo em rede.
O novo modelo mostrou-se competitivo para instâncias médias, como a de
10 tarefas e 10 máquinas e com intervalos de processamento das tarefas nas
máquinas entre 1 e 5 UT. Nessas condições, o novo modelo e o modelo de Kondili
adaptado e revisado conseguiram encontrar uma solução ótima muito mais rápido
do que o modelo disjuntivo adaptado.
A introdução de restrições modeladas como fluxos em rede nas formulações
com variáveis indexadas no tempo conferiu um expressivo aumento de desempenho
na resolução das instâncias em comparação ao modelo de Kondili adaptado. Para
algumas instâncias, houve quase 95% de redução do tempo médio para encontrar
uma solução ótima.
Quando se aumenta o intervalo de tempo de processamento das tarefas
pelas máquinas para entre 1 e 10 UT, o novo modelo perde competitividade. Uma
causa para isso seria o aumento das variáveis de decisão em função do tempo total
(H) definido para o problema. Dessa forma, o novo modelo é eficiente em
determinadas condições, sendo capaz de superar as adaptações das melhores
formulações encontradas na literatura.
93
O Capítulo 4 apresentou o modelo proposto para resolução do problema de
alocação de bobinas utilizadas para armazenamento e transporte de dutos flexíveis
ao longo de seu processo de fabricação. Este modelo foi testado em um caso real e
foi capaz de encontrar uma solução ótima da instância analisada.
Os resultados encontrados aplicando-se o método proposto mostram
potencial para uma significativa redução do número de bobinas necessárias no
processo produtivo. No estudo de caso desta dissertação, o problema de alocação
foi resolvido para uma situação em que o plano de produção era 10% maior que o
semestre anterior e a solução ótima encontrada indicava o mesmo número de
bobinas. Isso evidencia a contribuição do modelo no aumento da taxa de uso das
bobinas e na redução do tempo ocioso deste tipo de equipamento.
Com uma melhor utilização dos equipamentos, o investimento que ficaria
imobilizado na compra das bobinas pode ser direcionado para outra finalidade.
Acredita-se que a redução da movimentação das bobinas vazias também contribua
para a redução de custos e para que se tenha um ambiente fabril menos
congestionado. Como em todo processo de automatização de planejamento, o uso
do modelo também gera ganhos gerenciais ao diminuir o tempo gasto neste
processo. Na empresa do estudo de caso, a alocação manual de bobinas era um
processo laborioso que consumia muitas horas de mão de obra especializada.
Como desenvolvimento de trabalhos futuros, o novo modelo proposto para
resolver o problema de sequenciamento de job shop e minimização do atraso total
ponderado pode ser testado com outras funções objetivo a fim de obter uma
avaliação diferente sobre seu desempenho. A tentativa de otimização de outro
indicador pode gerar resultados superiores aos encontrados para o caso do atraso
total ponderado. Outro desafio é a introdução de novas restrições que reduzam
ainda mais os gaps de integralidade antes e depois dos cortes, o que poderia gerar
diminuição do tempo de resolução das instâncias. Por fim, as formulações com
variáveis indexadas no tempo podem ser complementadas com um método capaz
de retornar um horizonte de tempo que permita que a solução ótima seja
encontrada, mas que não seja tão grande a ponto de gerar variáveis de decisão em
excesso e tornar o tempo de resolução inviável.
94
Algumas extensões simples e imediatas do modelo proposto para resolução
do problema de alocações de bobinas seriam:
Considerar também restrições de comprimento dos dutos na alocação
de bobinas. Para tal, seria necessário apenas dividir as bobinas em
mais categorias, levando-se em conta não apenas o diâmetro do seu
tambor, mas também o diâmetro do flange e a largura do transverso.
Isso não foi realizado neste trabalho, uma vez que a questão do
comprimento não era relevante no estudo de caso realizado;
Tornar os custos de movimentações de bobinas vazias dependentes
do tamanho das bobinas, não apenas da distância percorrida. Além
disso, o modelo pode incorporar custos de movimentação de bobinas
cheias que dependam do tamanho da bobina alocada. Ou seja,
apesar da distância de movimentação de uma bobina cheia já estar
fixada no plano de produção, pode ser mais econômico alocar para
essa movimentação bobinas compatíveis menores.
Como um trabalho futuro complexo, seria interessante pesquisar formas de
incorporar o problema da alocação de bobinas dentro do processo de elaboração
dos planos de produção.
95
6 REFERÊNCIAS BIBLIOGRÁFICAS
AHUJA, R.; MAGNANTI, T.; ORLIN, J. Network flows: theory, algorithms, and applications. Englewood Cliffs, N.J: Prentice Hall, 1993.
AKRAM, K.; KAMAL, K.; ZEB, A. Fast simulated annealing hybridized with quenching for solving job shop scheduling problem. Applied Soft Computing, [s. l.], v. 49, p. 510–523, 2016.
BEEMSTERBOER, B. et al. Integrating make-to-order and make-to-stock in job shop control. International Journal of Production Economics, [s. l.], v. 185, p. 1–10, 2017.
BERTSEKAS, D. Network optimization: continuous and discrete methods. Belmont, Mass: Athena Scientific, 1998.
BERTSIMAS, D.; TSITSIKLIS, J. Introduction to linear optimization. Belmont, Mass: Athena Scientific, 1997.
BOWMAN, E. The Schedule-Sequencing Problem. Operations Research, [s. l.], v. 7, n. 5, p. 621–624, 1959.
DOS SANTOS, B. Modelo de Alocação de Bobinas Utilizando Programação Linear
Inteira. 2017. 76f. Trabalho de Conclusão de Curso (Graduação em Engenharia de
Produção)–Faculdade de Engenharia, Universidade Federal Fluminense, Niterói, 2017.
EPE [Empresa de Pesquisa Energética] Balanço Energético Nacional (BEN) 2017: Ano
base 2016, 2017. Disponível em < https://ben.epe.gov.br >. Acesso em 04 fev. 2018.
FUKASAWA, R. et al. Solving the Freight Car Flow Problem to Optimality. Electronic Notes in Theoretical Computer Science, [s. l.], v. 66, n. 6, p. 42–52, 2002.
GIL, A. Como elaborar projetos de pesquisa. São Paulo: Atlas, 2009.
GRAN, S. et al. Mixed Integer Programming model for flexible job-shop scheduling problem (FJSP) to minimize makespan and total machining time. In: 2015 INTERNATIONAL CONFERENCE ON COMPUTER, COMMUNICATIONS, AND CONTROL TECHNOLOGY (I4CT) 2015, Anais... . In: 2015 INTERNATIONAL CONFERENCE ON COMPUTER, COMMUNICATIONS, AND CONTROL TECHNOLOGY (I4CT). [s.l: s.n.]
HAM, A. Flexible job shop scheduling problem for parallel batch processing machine with compatible job families. Applied Mathematical Modelling, [s. l.], v. 45, p. 551–562, 2017.
JAMILI, A. Robust job shop scheduling problem: Mathematical models, exact and heuristic algorithms. Expert Systems with Applications, [s. l.], v. 55, p. 341–350, 2016.
JARAMILLO, F.; ERKOC, M. Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling. Computers & Industrial Engineering, [s. l.], v. 107, p. 109–119, 2017.
JENSEN, I.; MÜNSTER, M.; PISINGER, D. Optimizing the supply chain of biomass and biogas for a single plant considering mass and energy losses. European Journal of Operational Research, [s. l.], v. 262, n. 2, p. 744–758, 2017.
96
KONDILI, E.; PANTELIDES, C.; SARGENT, R. W. H. A general algorithm for short-term scheduling of batch operations—I. MILP formulation. Computers & Chemical Engineering, [s. l.], v. 17, n. 2, p. 211–227, 1993.
KONGCHUENJAI, J.; PROMBANPONG, S. An integer programming approach for process planning for mixed-model parts manufacturing on a CNC machining center. Advances in Production Engineering & Management, [s. l.], v. 12, n. 3, p. 274–284, 2017.
KU, W.; BECK, J. Mixed Integer Programming models for job shop scheduling: A computational analysis. Computers & Operations Research, [s. l.], v. 73, p. 165–173, 2016.
KUSUMA, K.; MARUF, A. Job shop scheduling model for non-identic machine with fixed delivery time to minimize tardiness. IOP Conference Series: Materials Science and Engineering, [s. l.], v. 114, p. 012062, 2016.
LAKATOS, E.; MARCONI, M. Fundamentos de metodologia científica. São Paulo: Atlas, 2003.
LANGE, J.; WERNER, F. Approaches to modeling train scheduling problems as job-shop problems with blocking constraints. Journal of Scheduling, [s. l.], 2017. Disponível em: <http://link.springer.com/10.1007/s10951-017-0526-0>. Acesso em: 13 jan. 2018.
LIAO, C.; YOU, C. An Improved Formulation for the Job-Shop Scheduling Problem. Journal of the Operational Research Society, [s. l.], v. 43, n. 11, p. 1047–1054, 1992.
MANNE, A. On the Job-Shop Scheduling Problem. Operations Research, [s. l.], v. 8, n. 2, p. 219–223, 1960.
MAZRAEH FARAHANI, M. et al. Capacitated network-flow approach to the evacuation-location problem. Computers & Industrial Engineering, [s. l.], v. 115, p. 407–426, 2018.
NGUYEN, N. et al. Total completion time minimization for machine scheduling problem under time windows constraints with jobs’ linear processing rate function. Computers & Operations Research, [s. l.], v. 90, p. 110–124, 2018.
PAN, C. A study of integer programming formulations for scheduling problems. International Journal of Systems Science, [s. l.], v. 28, n. 1, p. 33–41, 1997.
PESSOA, A.; UCHOA, E. UFFLP: Integrando Programação Inteira Mista e Planilhas de
Cálculo. 2011. (Curso de curta duração ministrado/Extensão). XLIII Simpósio Brasileiro de
Pesquisa Operacional, Ubatuba. Disponível em:
<http://www.logis.uff.br/~artur/UFFLP/Pessoa_Uchoa-UFFLP.pdf>. Acesso em: 21
mar.2016.
PINEDO, M. Planning and scheduling in manufacturing and services. New York, NY: Springer, 2005.
PINEDO, M. Scheduling. Cham: Springer International Publishing, 2016. Disponível em: <http://link.springer.com/10.1007/978-3-319-26580-3>. Acesso em: 12 mar. 2017.
POCHET, Y.; WOLSEY, L. Production planning by mixed integer programming. New York ; Berlin: Springer, 2006.
97
SAMARGHANDI, H.; BEHROOZI, M. On the exact solution of the no-wait flow shop problem with due date constraints. Computers & Operations Research, [s. l.], v. 81, p. 141–159, 2017.
SCHEFFLER, R.; STREHLER, M. Optimizing Traffic Signal Timings for Mega Events. In: OASICS-OPENACCESS SERIES IN INFORMATICS 2016, Anais... : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
TAN, Y.; MÖNCH, L.; FOWLER, J. A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines. Journal of Scheduling, [s. l.], 2017. Disponível em: <http://link.springer.com/10.1007/s10951-017-0530-4>. Acesso em: 1 out. 2017.
TORJAI, L.; KRUZSLICZ, F. Mixed integer programming formulations for the Biomass Truck Scheduling problem. Central European Journal of Operations Research, [s. l.], v. 24, n. 3, p. 731–745, 2016.
VENKATADRI, U.; ELASKARI, S.; KURDI, Raed. A multi-commodity network flow-based formulation for the multi-period cell formation problem. The International Journal of Advanced Manufacturing Technology, [s. l.], v. 91, n. 1–4, p. 175–187, 2017.
WAGNER, H. An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly, [s. l.], v. 6, n. 2, p. 131–140, 1959.
YAZDANI, M. et al. Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem. Computers & Industrial Engineering, [s. l.], v. 107, p. 12–24, 2017.
ZHANG, L. et al. Mathematical modeling and evolutionary generation of rule sets for energy-efficient flexible job shops. Energy, [s. l.], v. 138, p. 210–227, 2017.
98
7 APÊNDICES
Tabela 21 – Dados dos usos considerados no trabalho
Fonte: Adaptado de Dos Santos (2017)
Uso Início do uso (UT)
Fim do uso (UT)
Duração (Dias)
Local de início
Local de fim
Diâmetro mínimo da bobina
(Polegadas)
1 2 20 19 6 8 14
2 2 16 15 5 7 14
3 2 5 4 8 4 14
4 2 34 33 4 10 14
5 2 29 28 7 8 14
6 2 28 27 2 5 14
7 3 6 4 5 5 19
8 3 13 11 1 5 14
9 3 35 33 4 10 14
10 3 22 20 6 8 14
11 4 6 3 8 4 14
12 4 40 37 4 10 14
13 5 19 15 5 7 19
14 5 15 11 1 5 14
15 5 7 3 8 4 14
16 5 12 8 3 5 14
17 6 40 35 4 10 14
18 6 25 20 6 8 14
19 6 23 18 7 8 14
20 7 9 3 8 4 14
21 7 30 24 5 7 14
22 7 23 17 2 5 14
23 7 41 35 4 10 14
24 9 11 3 8 4 14
25 9 41 33 4 9 14
99
26 10 30 21 7 8 14
27 10 16 7 1 5 14
28 11 35 25 3 5 14
29 11 13 3 8 4 14
30 11 47 37 4 9 14
31 12 32 21 7 8 14
32 12 18 7 1 5 14
33 12 33 22 5 7 14
34 12 14 3 8 4 14
35 12 48 37 4 10 14
36 13 25 13 2 5 14
37 13 14 2 5 5 19
38 14 34 21 7 8 14
39 14 48 35 4 10 14
40 14 16 3 8 4 14
41 14 22 9 5 7 19
42 15 16 2 5 5 19
43 16 23 8 5 7 19
44 16 37 22 1 5 14
45 16 18 3 8 4 14
46 16 54 39 4 9 14
47 17 18 2 5 5 19
48 17 24 8 5 7 19
49 17 43 27 7 8 19
50 17 19 3 8 4 14
51 17 54 38 4 9 14
52 17 21 5 2 5 14
53 18 41 24 7 8 19
54 19 19 1 5 5 19
55 19 20 2 8 4 14
100
56 19 54 36 4 10 14
57 19 26 8 5 7 19
58 20 40 21 7 8 19
59 20 34 15 2 5 14
60 20 22 3 5 5 19
61 21 21 1 4 4 14
62 21 23 3 8 4 14
63 21 47 27 7 8 19
64 21 87 67 4 10 14
65 22 28 7 5 7 19
66 23 29 7 2 5 14
67 23 55 33 4 10 14
68 23 25 3 8 4 14
69 23 33 11 1 5 14
70 23 50 28 5 7 14
71 23 45 23 7 8 19
72 24 31 8 1 5 14
73 24 48 25 7 8 19
74 24 27 4 8 4 14
75 24 60 37 4 9 14
76 24 36 13 5 7 14
77 25 44 20 7 8 19
78 25 36 12 2 5 14
79 26 38 13 5 7 14
80 26 32 7 8 4 14
81 26 28 3 4 4 14
82 27 39 13 7 8 19
83 27 41 15 5 7 14
84 28 92 65 4 9 14
85 28 36 9 8 4 14
101
86 29 44 16 5 7 14
87 29 35 7 7 8 14
88 30 31 2 8 4 14
89 30 45 16 2 5 14
90 30 40 11 1 4 14
91 30 36 7 5 6 14
92 31 51 21 8 4 14
93 31 61 31 4 9 14
94 31 37 7 7 8 14
95 32 33 2 4 4 14
96 32 62 31 6 8 14
97 32 37 6 5 6 14
98 33 49 17 1 4 14
99 33 52 20 8 4 14
100 33 35 3 4 4 14
101 33 44 12 2 5 14
102 34 59 26 7 8 14
103 34 46 13 5 7 14
104 34 61 28 4 10 14
105 35 53 19 8 4 14
106 35 46 12 5 7 14
107 35 41 7 1 4 14
108 36 37 2 4 4 14
109 36 43 8 5 6 14
110 36 54 19 8 4 14
111 37 40 4 5 6 14
112 37 61 25 6 8 14
113 37 50 14 7 8 14
114 37 39 3 4 4 14
115 38 47 10 2 5 14
102
116 38 55 18 8 4 16
117 38 62 25 4 10 14
118 38 43 6 1 4 14
119 38 68 31 5 7 14
120 39 64 26 5 7 14
121 39 64 26 6 8 14
122 39 52 14 7 8 14
123 40 40 1 4 4 14
124 40 66 27 5 7 14
125 40 61 22 8 4 16
126 41 61 21 4 7 14
127 41 66 26 6 8 14
128 41 45 5 1 4 14
129 41 46 6 2 5 14
130 41 71 31 5 7 14
131 41 62 22 8 4 16
132 41 42 2 4 4 14
133 42 56 15 7 8 14
134 42 63 22 8 4 16
135 42 52 11 4 7 14
136 43 74 32 5 7 14
137 43 44 2 4 4 14
138 44 77 34 5 7 14
139 44 61 18 8 4 14
140 44 47 4 1 4 14
141 44 55 12 4 7 14
142 45 46 2 5 6 14
143 45 53 9 2 5 14
144 45 46 2 4 4 14
145 45 54 10 7 8 14
103
146 45 61 17 8 4 14
147 45 48 4 5 6 14
148 45 68 24 6 8 14
149 46 58 13 4 7 14
150 46 69 24 8 4 14
151 46 51 6 5 6 14
152 46 81 36 1 5 14
153 47 59 13 7 8 14
154 47 48 2 4 4 14
155 47 52 6 5 6 14
156 47 57 11 7 8 14
157 47 69 23 6 8 14
158 48 70 23 8 4 14
159 48 113 66 4 6 14
160 48 52 5 2 5 14
161 49 71 23 6 8 14
162 49 50 2 4 4 14
163 49 74 26 8 4 14
164 50 115 66 4 6 14
165 51 124 74 7 8 14
166 51 67 17 4 10 14
167 51 79 29 1 5 14
168 51 75 25 8 4 14
169 52 67 16 4 10 14
170 52 73 22 6 8 14
171 53 54 2 5 6 14
172 53 56 4 2 5 14
173 53 76 24 8 4 14
174 53 67 15 4 10 14
175 53 122 70 7 8 14
104
176 53 57 5 5 6 14
177 53 75 23 6 8 14
178 54 99 46 1 5 14
179 54 68 15 4 10 14
180 55 79 25 8 4 14
181 55 57 3 4 6 16
182 55 77 23 6 8 14
183 56 120 65 7 8 14
184 56 57 2 5 5 14
185 56 60 5 2 5 14
186 57 97 41 5 7 14
187 57 83 27 8 4 14
188 57 59 3 6 4 16
189 58 84 27 8 4 14
190 58 98 41 1 5 14
191 58 60 3 4 4 16
192 59 128 70 7 8 14
193 60 61 2 4 9 16
194 60 86 27 8 4 14
195 60 61 2 5 5 14
196 60 88 29 2 5 14
197 60 86 27 8 4 14
198 61 63 3 4 6 14
199 61 94 34 5 7 14
200 61 96 36 1 5 14
201 62 70 9 7 5 14
202 62 65 4 6 4 14
203 62 64 3 4 6 14
204 62 90 29 8 4 14
205 62 65 4 6 4 14
105
206 62 64 3 4 6 16
207 62 65 4 4 6 16
208 62 66 5 6 4 16
209 63 65 3 4 6 16
210 63 92 30 8 4 14
211 64 68 5 6 4 16
212 64 67 4 6 4 16
213 64 83 20 2 5 14
214 64 100 37 4 9 14
215 65 94 30 8 4 14
216 65 71 7 7 5 14
217 66 94 29 1 5 14
218 66 100 35 4 10 14
219 66 66 1 4 4 16
220 67 103 37 4 10 16
221 67 96 30 8 4 14
222 67 67 1 4 4 16
223 67 85 19 2 5 14
224 67 69 3 7 5 14
225 68 104 37 4 9 16
226 68 68 1 4 4 16
227 69 98 30 8 4 14
228 69 107 39 4 10 16
229 69 162 94 5 8 14
230 69 73 5 7 5 14
231 69 92 24 1 5 14
232 69 72 4 4 6 14
233 70 163 94 5 8 14
234 70 72 3 4 6 14
235 70 100 31 8 4 14
106
236 71 165 95 5 8 14
237 71 73 3 6 4 14
238 71 72 2 6 4 14
239 72 87 16 2 5 14
240 72 101 30 8 4 14
241 72 167 96 5 8 14
242 72 75 4 7 5 14
243 73 107 35 4 10 14
244 73 90 18 1 5 14
245 73 111 39 4 10 14
246 74 75 2 4 10 14
247 74 103 30 8 4 14
248 75 169 95 5 8 14
249 75 78 4 7 5 14
250 75 82 8 2 4 14
251 75 78 4 4 9 14
252 76 105 30 8 4 14
253 76 78 3 4 4 14
254 76 169 94 1 5 14
255 77 112 36 4 9 14
256 78 170 93 5 8 14
257 79 81 3 4 4 14
258 79 102 24 2 5 14
259 79 168 90 1 5 14
260 79 80 2 5 5 14
261 80 167 88 1 5 14
262 80 109 30 5 6 14
263 80 114 35 4 9 14
264 81 82 2 5 5 14
265 82 99 18 4 7 14
107
266 82 111 30 5 6 14
267 82 159 78 1 5 14
268 83 85 3 4 10 14
269 83 84 2 5 5 14
270 83 104 22 2 5 14
271 84 92 9 5 7 14
272 84 86 3 4 10 14
273 85 86 2 5 5 14
274 85 161 77 1 5 14
275 85 86 2 4 10 14
276 86 88 3 5 7 14
277 87 88 2 4 4 14
278 87 95 9 7 8 14
279 87 88 2 5 5 14
280 87 115 29 4 9 14
281 88 106 19 2 5 14
282 88 90 3 5 6 14
283 88 163 76 1 5 14
284 89 89 1 5 5 14
285 89 93 5 6 8 14
286 89 97 9 7 8 14
287 89 92 4 4 4 14
288 89 93 5 5 6 14
289 90 151 62 1 5 14
290 90 91 2 5 5 14
291 91 117 27 4 9 14
292 91 99 9 6 8 14
293 91 108 18 2 5 14
294 91 95 5 5 6 14
295 92 93 2 5 5 14
108
296 93 118 26 4 10 14
297 93 111 19 8 4 14
298 93 101 9 7 8 14
299 93 97 5 5 6 14
300 93 96 4 4 4 14
301 94 104 11 6 8 14
302 94 153 60 1 5 14
303 94 95 2 5 5 14
304 94 110 17 2 5 16
305 94 110 17 8 4 14
306 95 100 6 5 6 14
307 95 120 26 4 9 14
308 95 102 8 7 8 14
309 96 106 11 6 8 14
310 96 97 2 5 5 14
311 96 108 13 8 4 14
312 96 155 60 1 5 14
313 97 97 1 4 4 14
314 97 102 6 5 6 14
315 97 113 17 2 5 16
316 97 153 57 4 9 14
317 98 98 1 5 5 14
318 98 129 32 7 8 14
319 98 108 11 6 8 14
320 98 109 12 8 4 14
321 98 99 2 4 4 14
322 99 104 6 5 6 14
323 99 156 58 4 9 14
324 99 100 2 5 5 14
325 100 100 1 4 4 14
109
326 100 107 8 8 4 14
327 100 157 58 1 5 14
328 100 107 8 5 6 14
329 101 157 57 4 9 14
330 101 110 10 6 8 14
331 101 115 15 2 5 16
332 101 103 3 5 5 14
333 101 102 2 4 4 14
334 102 106 5 8 4 14
335 102 157 56 4 9 14
336 102 165 64 1 5 14
337 103 107 5 5 7 14
338 103 111 9 6 8 14
339 103 104 2 4 4 14
340 103 118 16 8 4 14
341 104 131 28 7 8 14
342 104 105 2 5 5 14
343 104 159 56 4 9 14
344 104 117 14 2 5 16
345 105 105 1 4 4 14
346 105 113 9 6 8 14
347 105 109 5 5 7 14
348 105 119 15 8 4 14
349 106 162 57 4 9 14
350 106 107 2 5 5 14
351 106 108 3 4 6 14
352 107 120 14 8 4 14
353 107 113 7 5 7 14
354 107 112 6 6 4 14
355 107 109 3 4 6 14
110
356 108 115 8 6 8 14
357 108 120 13 7 5 14
358 108 129 22 2 5 14
359 108 109 2 5 5 14
360 108 113 6 6 4 14
361 108 110 3 4 6 14
362 109 121 13 8 4 14
363 109 111 3 4 6 14
364 109 114 6 6 4 14
365 109 115 7 5 7 14
366 110 117 8 6 8 14
367 110 115 6 6 4 14
368 110 113 4 4 6 14
369 110 121 12 7 5 14
370 110 112 3 5 5 19
371 111 122 12 8 4 14
372 111 116 6 6 4 14
373 111 114 4 4 6 14
374 111 131 21 2 5 14
375 111 116 6 5 7 19
376 112 119 8 6 8 14
377 112 121 10 4 9 14
378 112 128 17 8 4 14
379 113 114 2 5 5 19
380 113 117 5 6 4 14
381 113 123 11 4 9 14
382 114 119 6 5 7 19
383 114 122 9 7 5 14
384 114 124 11 4 9 14
385 114 129 16 8 4 14
111
386 114 126 13 6 8 14
387 115 116 2 5 5 19
388 115 125 11 4 9 14
389 115 132 18 2 5 14
390 116 124 9 7 5 19
391 116 121 6 5 7 19
392 116 128 13 4 9 14
393 116 130 15 8 4 14
394 117 118 2 5 5 19
395 117 130 14 4 9 14
396 117 125 9 7 5 19
397 118 142 25 8 4 14
398 118 120 3 4 6 14
399 118 122 5 5 7 19
400 118 134 17 2 5 14
401 119 121 3 4 6 14
402 119 123 5 6 4 14
403 119 133 15 5 8 14
404 120 139 20 8 4 14
405 120 121 2 4 6 14
406 120 124 5 6 4 14
407 120 126 7 7 5 19
408 121 135 15 5 8 14
409 121 122 2 4 6 14
410 121 125 5 6 4 14
411 121 140 20 8 4 14
412 122 123 2 4 6 14
413 122 126 5 6 4 14
414 122 136 15 2 5 14
415 122 128 7 7 5 19
112
416 122 137 16 5 8 14
417 123 127 5 6 4 14
418 123 131 9 4 9 14
419 123 141 19 8 4 14
420 123 139 17 5 8 16
421 124 131 8 4 9 14
422 124 138 15 2 5 14
423 125 141 17 5 8 16
424 125 134 10 4 9 14
425 125 135 11 8 4 14
426 126 136 11 4 9 14
427 126 143 18 5 8 16
428 127 134 8 8 4 14
429 127 137 11 4 9 14
430 127 144 18 5 8 16
431 128 130 3 4 6 14
432 128 139 12 2 5 14
433 129 148 20 8 4 14
434 129 130 2 5 5 19
435 129 131 3 4 6 14
436 129 131 3 6 4 14
437 130 133 4 5 7 19
438 130 132 3 4 6 14
439 130 132 3 6 4 14
440 130 161 32 8 4 14
441 131 146 16 7 8 19
442 131 132 2 5 5 14
443 131 138 8 4 9 14
444 131 141 11 2 5 14
445 131 133 3 6 4 14
113
446 132 136 5 5 7 14
447 132 141 10 4 9 14
448 132 152 21 8 4 14
449 133 133 1 5 5 14
450 133 143 11 4 9 14
451 133 138 6 5 7 14
452 134 154 21 8 4 14
453 134 136 3 4 6 14
454 134 135 2 5 5 14
455 134 143 10 7 5 14
456 135 149 15 2 4 14
457 135 137 3 6 4 14
458 135 137 3 4 6 14
459 135 142 8 5 7 14
460 136 155 20 8 4 14
461 136 137 2 5 5 14
462 136 138 3 6 4 14
463 137 144 8 7 5 14
464 137 144 8 4 9 14
465 137 143 7 5 7 14
466 138 139 2 5 5 14
467 138 144 7 4 9 14
468 138 156 19 8 4 16
469 138 150 13 2 4 14
470 139 145 7 5 7 14
471 139 142 4 4 6 14
472 139 145 7 7 5 14
473 140 140 1 5 5 14
474 140 157 18 8 4 16
475 140 142 3 4 6 14
114
476 140 143 4 6 4 14
477 140 148 9 5 7 14
478 141 143 3 4 6 14
479 141 144 4 6 4 14
480 141 142 2 5 5 14
481 142 159 18 8 4 16
482 142 145 4 6 4 14
483 142 144 3 4 6 14
484 142 149 8 5 7 14
485 142 151 10 2 4 14
486 143 147 5 7 5 14
487 143 148 6 5 8 14
488 143 147 5 4 9 14
489 143 147 5 6 4 14
490 144 160 17 8 4 16
491 144 150 7 5 8 14
492 144 149 6 4 9 14
493 144 148 5 7 5 14
494 145 152 8 5 8 14
495 145 150 6 4 9 14
496 145 177 33 8 4 16
497 146 149 4 7 5 14
498 146 151 6 4 9 14
499 146 154 9 5 8 14
500 147 179 33 8 4 14
501 148 163 16 4 9 14
502 148 156 9 5 8 14
503 149 152 4 4 6 14
504 149 150 2 7 5 14
505 149 158 10 5 8 14
115
506 149 240 92 2 5 14
507 149 180 32 8 4 14
508 150 172 23 6 8 14
509 150 156 7 4 6 14
510 150 160 11 5 8 14
511 151 158 8 4 6 14
512 151 193 43 1 5 14
513 151 241 91 2 5 14
514 151 181 31 8 4 14
515 151 152 2 5 5 14
516 152 156 5 4 6 14
517 152 155 4 5 7 14
518 153 174 22 6 8 14
519 153 194 42 1 5 14
520 153 182 30 8 4 14
521 153 163 11 6 4 14
522 153 156 4 4 6 14
523 153 177 25 7 8 14
524 153 154 2 5 5 14
525 154 157 4 5 7 14
526 155 157 3 4 6 14
527 155 164 10 6 4 14
528 155 242 88 2 5 14
529 155 183 29 8 4 14
530 155 156 2 5 5 14
531 156 166 11 6 4 14
532 156 158 3 4 6 16
533 156 179 24 7 8 14
534 156 159 4 5 7 14
535 157 195 39 1 5 14
116
536 157 176 20 6 8 14
537 157 168 12 6 4 16
538 157 160 4 4 6 16
539 157 184 28 8 4 14
540 157 158 2 5 5 14
541 158 181 24 7 8 14
542 158 169 12 6 4 16
543 158 162 5 4 6 16
544 158 162 5 5 7 14
545 159 185 27 8 4 14
546 159 243 85 1 5 14
547 159 160 2 5 5 14
548 160 171 12 6 4 16
549 160 163 4 4 6 16
550 160 182 23 7 8 14
551 160 163 4 5 7 14
552 161 163 3 4 6 14
553 161 172 12 6 4 16
554 161 203 43 8 4 14
555 161 162 2 5 5 14
556 162 165 4 5 7 14
557 162 174 13 6 4 14
558 162 164 3 4 9 14
559 163 244 82 2 5 14
560 163 204 42 8 4 14
561 163 184 22 7 8 14
562 163 164 2 5 5 14
563 164 166 3 4 9 14
564 164 186 23 7 8 14
565 164 164 1 8 4 14
117
566 164 167 4 5 7 14
567 165 166 2 5 5 14
568 165 169 5 4 9 14
569 166 187 22 7 8 14
570 166 168 3 5 6 14
571 166 166 1 8 4 14
572 167 168 2 5 5 14
573 167 189 23 6 8 14
574 167 169 3 4 4 16
575 168 171 4 5 6 14
576 168 208 41 8 4 14
577 169 171 3 4 9 16
578 169 172 4 5 6 14
579 169 175 7 5 6 14
580 169 246 78 1 5 14
581 169 191 23 6 8 14
582 170 209 40 8 4 14
583 170 245 76 2 5 14
584 170 172 3 4 9 16
585 171 175 5 8 4 14
586 172 245 74 2 5 14
587 172 192 21 6 8 14
588 172 174 3 4 9 16
589 173 194 22 6 8 14
590 173 196 24 8 4 14
591 173 176 4 4 9 14
592 173 200 28 2 4 14
593 175 175 1 8 4 14
594 175 176 2 4 4 14
595 176 178 3 4 10 14
118
596 177 201 25 2 4 14
597 177 212 36 8 4 14
598 177 248 72 1 5 14
599 177 178 2 4 6 16
600 178 219 42 8 4 14
601 178 186 9 6 4 16
602 178 181 4 4 6 14
603 180 187 8 6 4 14
604 180 183 4 4 6 14
605 180 218 39 8 4 14
606 181 188 8 6 4 14
607 181 184 4 4 6 14
119
Tabela 22 – Matriz distância entre máquinas
Fonte: Adaptado de Dos Santos (2017)
Carcaça 1 Carcaça 2 Carcaça 3 Extrusora 1 Extrusora 2 Espiraladora 1 Espiraladora 2 Armadora Respool 1 Respool 2
Carcaça 1 0 8,0 8,0 168,5 39,0 200,5 211,0 28,5 280,0 295,0
Carcaça 2 8,0 0 16,0 160,5 31,0 192,5 203,0 20,5 272,0 287,0
Carcaça 3 8,0 16,0 0 176,5 47,0 208,5 219,0 36,5 288,0 303,0
Extrusora 1 168,5 160,5 176,5 119 10,5 151,0 161,5 21,5 230,5 245,5
Extrusora 2 39,0 31,0 47,0 10,5 140 21,5 32,0 150,5 146,0 161,0
Espiraladora 1 200,5 192,5 208,5 151,0 21,5 183 198,0 17,5 167,5 182,5
Espiraladora 1 211,0 203,0 219,0 161,5 32,0 198,0 204 28,5 178,0 193,0
Armadora 28,5 20,5 36,5 21,5 150,5 17,5 28,5 159 250,5 265,5
Respool 1 280,0 272,0 288,0 230,5 146,0 167,5 178,0 250,5 0 15,0
Respool 2 295,0 287,0 303,0 245,5 161,0 182,5 193,0 265,5 15,0 0
120
Tabela 23 – Solução ótima da alocação de bobinas aos usos
Uso Bobina Tamanho da
bobina (Polegadas)
Ordem do Uso
Instante de liberação
(Dias)
1 30 14 1 1
2 50 16 1 17
3 31 14 1 1
4 32 14 1 1
5 33 14 1 1
6 56 17 1 23
7 64 19 1 25
8 34 14 1 1
9 24 14 1 2
10 25 14 1 2
11 65 19 1 25
12 35 14 1 1
13 73 22 1 27
14 21 14 1 3
15 66 19 1 25
16 36 14 1 1
17 19 14 1 4
18 37 14 1 1
19 51 16 1 17
20 67 19 1 25
21 31 14 2 1
22 52 16 1 17
23 22 14 1 3
24 68 19 1 25
25 38 14 1 1
26 26 14 1 2
27 39 14 1 1
121
28 48 16 1 18
29 69 19 1 25
30 40 14 1 1
31 41 14 1 1
32 42 14 1 1
33 53 16 1 17
34 70 19 1 25
35 18 14 1 5
36 17 14 1 6
37 68 19 2 25
38 57 17 1 23
39 36 14 2 1
40 71 19 1 25
41 72 19 1 25
42 69 19 2 25
43 66 19 2 25
44 43 14 1 1
45 62 19 1 26
46 58 17 1 23
47 65 19 2 25
48 70 19 2 25
49 63 19 1 26
50 54 16 1 17
51 49 16 1 18
52 27 14 1 2
53 69 19 3 25
54 71 19 2 25
55 50 16 2 17
56 39 14 2 1
57 67 19 2 25
122
58 65 19 3 25
59 10 14 1 11
60 62 19 2 26
61 42 14 2 1
62 23 14 1 3
63 68 19 3 25
64 55 17 1 24
65 73 22 2 27
66 30 14 2 1
67 27 14 2 2
68 15 14 1 8
69 11 14 1 10
70 42 14 3 1
71 71 19 3 25
72 47 16 1 19
73 62 19 3 26
74 72 19 2 25
75 21 14 2 3
76 50 16 3 17
77 66 19 3 25
78 51 16 2 17
79 54 16 2 17
80 70 19 3 25
81 52 16 2 17
82 64 19 2 25
83 23 14 2 3
84 17 14 2 6
85 67 19 3 25
86 15 14 2 8
87 5 14 1 13
123
88 73 22 3 27
89 37 14 2 1
90 6 14 1 13
91 52 16 3 17
92 16 14 1 7
93 30 14 3 1
94 59 17 1 23
95 34 14 2 1
96 26 14 2 2
97 72 19 3 25
98 28 14 1 2
99 73 22 4 27
100 47 16 2 19
101 33 14 2 1
102 60 17 1 23
103 70 19 4 25
104 56 17 2 23
105 53 16 2 17
106 34 14 3 1
107 3 14 1 15
108 11 14 2 10
109 32 14 2 1
110 31 14 3 1
111 47 16 3 19
112 41 14 2 1
113 8 14 1 12
114 57 17 2 23
115 5 14 2 13
116 50 16 4 17
117 51 16 3 17
124
118 4 14 1 14
119 67 19 4 25
120 11 14 3 10
121 59 17 2 23
122 61 17 1 23
123 48 16 2 18
124 54 16 3 17
125 52 16 4 17
126 43 14 2 1
127 24 14 2 2
128 45 16 1 21
129 25 14 2 2
130 57 17 3 23
131 72 19 4 25
132 64 19 3 25
133 19 14 2 4
134 47 16 4 19
135 65 19 4 25
136 48 16 3 18
137 6 14 2 13
138 64 19 4 25
139 23 14 3 3
140 29 14 1 2
141 69 19 4 25
142 4 14 2 14
143 63 19 2 26
144 10 14 2 11
145 46 16 1 20
146 32 14 3 1
147 3 14 2 15
125
148 35 14 2 1
149 33 14 3 1
150 15 14 3 8
151 6 14 3 13
152 13 14 1 9
153 38 14 2 1
154 37 14 3 1
155 45 16 2 21
156 22 14 2 3
157 66 19 4 25
158 4 14 3 14
159 25 14 3 2
160 71 19 4 25
161 40 14 2 1
162 29 14 2 2
163 70 19 5 25
164 37 14 4 1
165 18 14 2 5
166 28 14 2 2
167 12 14 1 10
168 3 14 3 15
169 29 14 3 2
170 36 14 3 1
171 42 14 4 1
172 62 19 4 26
173 34 14 4 1
174 10 14 3 11
175 5 14 3 13
176 16 14 2 7
177 8 14 2 12
126
178 9 14 1 12
179 71 19 5 25
180 45 16 3 21
181 53 16 3 17
182 61 17 2 23
183 58 17 2 23
184 73 22 5 27
185 46 16 2 20
186 31 14 4 1
187 6 14 4 13
188 49 16 2 18
189 69 19 5 25
190 20 14 1 4
191 62 19 5 26
192 39 14 3 1
193 50 16 5 17
194 53 16 4 17
195 65 19 5 25
196 22 14 3 3
197 16 14 3 7
198 49 16 3 18
199 33 14 4 1
200 7 14 1 13
201 21 14 3 3
202 27 14 3 2
203 73 22 6 27
204 42 14 5 1
205 68 19 4 25
206 62 19 6 26
207 63 19 3 26
127
208 46 16 3 20
209 52 16 5 17
210 43 14 3 1
211 56 17 3 23
212 50 16 6 17
213 26 14 3 2
214 32 14 4 1
215 49 16 4 18
216 51 16 4 17
217 41 14 3 1
218 23 14 4 3
219 47 16 5 19
220 68 19 5 25
221 63 19 4 26
222 72 19 5 25
223 59 17 3 23
224 30 14 4 1
225 47 16 6 19
226 46 16 4 20
227 52 16 6 17
228 50 16 7 17
229 54 16 4 17
230 28 14 3 2
231 24 14 3 2
232 72 19 6 25
233 27 14 4 2
234 65 19 6 25
235 62 19 7 26
236 11 14 4 10
237 29 14 4 2
128
238 30 14 5 1
239 35 14 3 1
240 73 22 7 27
241 46 16 5 20
242 10 14 4 11
243 21 14 4 3
244 40 14 3 1
245 15 14 4 8
246 30 14 6 1
247 65 19 7 25
248 29 14 5 2
249 71 19 6 25
250 66 19 5 25
251 56 17 4 23
252 72 19 7 25
253 28 14 4 2
254 38 14 3 1
255 10 14 5 11
256 3 14 4 15
257 51 16 5 17
258 36 14 4 1
259 14 14 1 9
260 57 17 4 23
261 8 14 3 12
262 48 16 4 18
263 71 19 7 25
264 45 16 4 21
265 12 14 2 10
266 67 19 5 25
267 61 17 3 23
129
268 13 14 2 9
269 64 19 5 25
270 19 14 3 4
271 51 16 6 17
272 57 17 5 23
273 6 14 5 13
274 60 17 2 23
275 45 16 5 21
276 66 19 6 25
277 59 17 4 23
278 30 14 7 1
279 70 19 6 25
280 64 19 6 25
281 26 14 4 2
282 28 14 5 2
283 6 14 6 13
284 4 14 4 14
285 45 16 6 21
286 13 14 3 9
287 35 14 4 1
288 34 14 5 1
289 22 14 4 3
290 59 17 5 23
291 16 14 4 7
292 57 17 6 23
293 70 19 7 25
294 53 16 5 17
295 42 14 6 1
296 40 14 4 1
297 28 14 6 2
130
298 56 17 5 23
299 66 19 7 25
300 69 19 6 25
301 17 14 3 6
302 24 14 4 2
303 43 14 4 1
304 59 17 6 23
305 51 16 7 17
306 35 14 5 1
307 42 14 7 1
308 55 17 2 24
309 41 14 4 1
310 33 14 5 1
311 34 14 6 1
312 44 16 1 22
313 43 14 5 1
314 49 16 5 18
315 45 16 7 21
316 4 14 5 14
317 63 19 5 26
318 7 14 2 13
319 30 14 8 1
320 53 16 6 17
321 69 19 7 25
322 43 14 6 1
323 33 14 6 1
324 31 14 5 1
325 63 19 6 26
326 66 19 8 25
327 13 14 4 9
131
328 52 16 7 17
329 20 14 2 4
330 1 14 1 16
331 57 17 7 23
332 69 19 8 25
333 9 14 2 12
334 35 14 6 1
335 31 14 6 1
336 2 14 1 16
337 63 19 7 26
338 56 17 6 23
339 62 19 8 26
340 12 14 3 10
341 32 14 5 1
342 9 14 3 12
343 36 14 5 1
344 55 17 3 24
345 69 19 9 25
346 23 14 5 3
347 73 22 8 27
348 49 16 6 18
349 19 14 4 4
350 62 19 9 26
351 65 19 8 25
352 43 14 7 1
353 69 19 10 25
354 68 19 6 25
355 9 14 4 12
356 41 14 5 1
357 26 14 5 2
132
358 17 14 4 6
359 35 14 7 1
360 47 16 7 19
361 72 19 8 25
362 52 16 8 17
363 66 19 9 25
364 62 19 10 26
365 63 19 8 26
366 50 16 8 17
367 70 19 8 25
368 34 14 7 1
369 21 14 5 3
370 65 19 9 25
371 9 14 5 12
372 35 14 8 1
373 53 16 7 17
374 30 14 9 1
375 73 22 9 27
376 59 17 7 23
377 51 16 8 17
378 72 19 9 25
379 67 19 6 25
380 1 14 2 16
381 28 14 7 2
382 68 19 7 25
383 10 14 6 11
384 65 19 10 25
385 48 16 5 18
386 56 17 7 23
387 69 19 11 25
133
388 47 16 8 19
389 23 14 6 3
390 71 19 8 25
391 62 19 11 26
392 67 19 7 25
393 34 14 8 1
394 70 19 9 25
395 57 17 8 23
396 64 19 7 25
397 53 16 8 17
398 35 14 9 1
399 73 22 10 27
400 41 14 6 1
401 55 17 4 24
402 16 14 5 7
403 1 14 3 16
404 25 14 4 2
405 12 14 4 10
406 50 16 9 17
407 70 19 10 25
408 68 19 8 25
409 45 16 8 21
410 59 17 8 23
411 37 14 5 1
412 26 14 6 2
413 42 14 8 1
414 58 17 3 23
415 69 19 12 25
416 49 16 7 18
417 51 16 9 17
134
418 43 14 8 1
419 35 14 10 1
420 52 16 9 17
421 21 14 6 3
422 5 14 4 13
423 62 19 12 26
424 16 14 6 7
425 12 14 5 10
426 71 19 9 25
427 73 22 11 27
428 66 19 10 25
429 10 14 7 11
430 59 17 9 23
431 70 19 11 25
432 18 14 3 5
433 26 14 7 2
434 63 19 9 26
435 64 19 8 25
436 47 16 9 19
437 72 19 10 25
438 69 19 13 25
439 39 14 4 1
440 55 17 5 24
441 65 19 11 25
442 51 16 10 17
443 17 14 5 6
444 7 14 3 13
445 67 19 8 25
446 9 14 6 12
447 63 19 10 26
135
448 70 19 12 25
449 47 16 10 19
450 30 14 10 1
451 34 14 9 1
452 69 19 14 25
453 51 16 11 17
454 39 14 5 1
455 21 14 7 3
456 32 14 6 1
457 57 17 9 23
458 23 14 7 3
459 50 16 10 17
460 45 16 9 21
461 66 19 11 25
462 47 16 11 19
463 28 14 8 2
464 41 14 7 1
465 12 14 6 10
466 42 14 9 1
467 48 16 6 18
468 72 19 11 25
469 1 14 4 16
470 9 14 7 12
471 66 19 12 25
472 58 17 4 23
473 34 14 10 1
474 64 19 9 25
475 57 17 10 23
476 17 14 6 6
477 67 19 9 25
136
478 18 14 4 5
479 71 19 10 25
480 25 14 5 2
481 51 16 12 17
482 68 19 9 25
483 34 14 11 1
484 37 14 6 1
485 56 17 8 23
486 42 14 10 1
487 35 14 11 1
488 5 14 5 13
489 62 19 13 26
490 66 19 13 25
491 50 16 11 17
492 53 16 9 17
493 63 19 11 26
494 17 14 7 6
495 7 14 4 13
496 57 17 11 23
497 21 14 8 3
498 28 14 9 2
499 71 19 11 25
500 12 14 7 10
501 58 17 5 23
502 68 19 10 25
503 42 14 11 1
504 41 14 8 1
505 62 19 14 26
506 65 19 12 25
507 9 14 8 12
137
508 73 22 12 27
509 25 14 6 2
510 67 19 10 25
511 21 14 9 3
512 52 16 10 17
513 35 14 12 1
514 18 14 5 5
515 32 14 7 1
516 41 14 9 1
517 26 14 8 2
518 39 14 6 1
519 59 17 10 23
520 34 14 12 1
521 50 16 12 17
522 22 14 5 3
523 63 19 12 26
524 1 14 5 16
525 37 14 7 1
526 56 17 9 23
527 32 14 8 1
528 17 14 8 6
529 42 14 12 1
530 47 16 12 19
531 1 14 6 16
532 69 19 15 25
533 24 14 5 2
534 70 19 13 25
535 71 19 12 25
536 44 16 2 22
537 49 16 8 18
138
538 45 16 10 21
539 23 14 8 3
540 26 14 9 2
541 47 16 13 19
542 68 19 11 25
543 72 19 12 25
544 22 14 6 3
545 41 14 10 1
546 13 14 5 9
547 37 14 8 1
548 62 19 15 26
549 64 19 10 25
550 26 14 10 2
551 25 14 7 2
552 51 16 13 17
553 61 17 4 23
554 21 14 10 3
555 69 19 16 25
556 70 19 14 25
557 37 14 9 1
558 66 19 14 25
559 67 19 11 25
560 45 16 11 21
561 60 17 3 23
562 55 17 6 24
563 69 19 17 25
564 54 16 5 17
565 72 19 13 25
566 22 14 7 3
567 50 16 13 17
139
568 6 14 7 13
569 27 14 5 2
570 32 14 9 1
571 51 16 14 17
572 72 19 14 25
573 2 14 2 16
574 55 17 7 24
575 51 16 15 17
576 56 17 10 23
577 50 16 14 17
578 64 19 11 25
579 1 14 7 16
580 11 14 5 10
581 8 14 4 12
582 32 14 10 1
583 46 16 6 20
584 49 16 9 18
585 68 19 12 25
586 29 14 6 2
587 72 19 15 25
588 55 17 8 24
589 14 14 2 9
590 51 16 16 17
591 62 19 16 26
592 3 14 5 15
593 64 19 12 25
594 61 17 5 23
595 37 14 10 1
596 39 14 7 1
597 1 14 8 16
140
598 73 22 13 27
599 68 19 13 25
600 61 17 6 23
601 44 16 3 22
602 64 19 13 25
603 63 19 13 26
604 38 14 4 1
605 68 19 14 25
606 24 14 6 2
607 12 14 8 10
