Técnicas de Otimização Aplicadas em Problemas de ...livros01.livrosgratis.com.br/cp106220.pdf · Ficha catalográfica elaborada pela Biblioteca da UTFPR ... Resumo xvii Abstract

Universidade Tecnologica Federal do ParanaPrograma de Pos-Graduacao em Engenharia Eletrica e Informatica Industrial

Tecnicas de Otimizacao Aplicadas emProblemas de Scheduling dos Recursos de

Estocagem

Tese de Doutorado

por

Sergio Leandro Stebel

Banca Examinadora:

Presidente e Orientador:Prof. Dr. Flavio Neves Junior UTFPR

Examinadores:Prof. Dr. Virgılio Jose Martins Ferreira Filho UFRJProf. Dr. Felipe Martins Muller UFSMDr. Marcel Joly PETROBRASProf.a Dra. Lucia Valeria Ramos de Arruda UTFPR

Curitiba, Parana04 de maio de 2006

SERGIO LEANDRO STEBEL

Tecnicas de Otimizacao Aplicadas emProblemas de Scheduling dos Recursos de

Estocagem

Tese de doutorado apresentada ao Programa dePos-Graduacao em Engenharia Eletrica e Infor-matica Industrial da Universidade TecnologicaFederal do Parana, na area de concentracao deInformatica Industrial, como parte dos requisitospara obtencao do tıtulo de Doutor em Ciencias.

Orientador: Prof. Dr. Flavio Neves Junior

Curitiba, Parana04 de maio de 2006

Ficha catalográfica elaborada pela Biblioteca da UTFPR – Campus Curitiba

S811t Stebel, Sérgio Leandro Técnicas de Otimização aplicadas em problemas de Scheduling dos recursos de estocagem / Sérgio Leandro Stebel. Curitiba. UTFPR, 2006 XIX, 132 f. : il.; 30cm Orientador: Prof. Dr. Flávio Neves Junior Tese (Doutorado) – Universidade Tecnológica Federal do Paraná. Curso de Pós-Graduação em Engenharia Elétrica e Infrormática Industrial. Curiti- ba, 2006 Bibliografia: f. 119-127 1. Programação matemática. 2. Programação linear. 3. Métodos heurís- ticos. 4. Sistemas Fuzzy. 5. Algoritmos genéticos. 6. Scheduling. 7. Méto- dos híbridos. I. Neves Junior, Flávio, orient. II. Universidade Tecnológica Federal do Paraná. Curso de Pós-Graduação em Engenharia Elétrica e Infor- mática Industrial. III. Título. CDD: 519.72

ParaSelma e Joao Henrique

iii

iv

Agradecimentos

A Deus, por ter me dado forca e equilıbrio nos momentos de maior dificuldade.

Ao meu orientador Prof. Flavio, pelas revisoes, sugestoes e principalmente pelaliberdade que me conferiu para desenvolver este trabalho. Alem disso, pela sua cons-tante disposicao em desbravar novos projetos.

A prof.a Valeria, pelas revisoes e comentarios, sempre pertinentes, dispensadosno desenvolvimento deste trabalho.

A prof.a Debora, por ter participado do meu exame de qualificacao e ter contri-buıdo com suas observacoes para conclusao desta tese.

Aos meus pais Joao e Teresa, que tiveram a formacao e educacao dos filhos comoprincipal objetivo de suas vidas.

A minha esposa Selma, pelo apoio e compreensao incondicionais. Ao meu filhoJoao Henrique, por tornar a minha vida mais completa.

Ao amigo Leandro, pelas consideracoes e sugestoes, sempre ponderadas, que meauxiliaram muito no desenvolvimento desta tese.

A todos os integrantes que fizeram ou fazem parte do LASCA/CPGEI/UTFPR,que direta ou indiretamente me ajudaram.

Por fim, aos professores do DAELN/UTFPR por terem me possibilitado concluiresta tese. Em particular, os professores Ubiradir, Guilherme e Simone.

v

vi

Apoio financeiro da Agencia Nacional do Petroleo e do CTPetro/Financiadorade Estudos e Projetos - UTFPR/PRH10.

vii

viii

Sumario

Lista de Figuras xi

Lista de Tabelas xiii

Siglas xv

Resumo xvii

Abstract xix

1 Introducao 1

1.1 Motivacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Contribuicoes e Objetivos . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Organizacao do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Revisao Teorica: PSRP 7

2.1 Conceitos Gerais sobre Scheduling . . . . . . . . . . . . . . . . . . . . 7

2.2 Caracterısticas dos Problemas de Scheduling . . . . . . . . . . . . . . 9

2.3 Caracterısticas dos Modelos de Scheduling . . . . . . . . . . . . . . . 12

2.4 Divisao dos PSRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5 Modelos para os PSRP . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.6 Consideracoes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Revisao Teorica: Metodos de Solucao para os PSRP 21

3.1 Programacao Matematica . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1.1 Programacao Linear Inteira Mista . . . . . . . . . . . . . . . . 24

3.2 Programacao Logica por Restricoes . . . . . . . . . . . . . . . . . . . 28

3.2.1 Otimizacao com PLR . . . . . . . . . . . . . . . . . . . . . . 35

3.3 Metodos Heurısticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.4 Metodos Hıbridos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.4.1 PLIM X PLR . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.4.2 Algoritmos Geneticos X PLR . . . . . . . . . . . . . . . . . . 41

3.5 Sistemas Fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.5.1 Tratamento de Incertezas . . . . . . . . . . . . . . . . . . . . 42

3.5.2 Conceitos e Definicoes . . . . . . . . . . . . . . . . . . . . . . 43


ix

4 Modelagem Matematica para um PSRE 494.1 Descricao do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . 504.2 Representacao da Estrutura do Modelo . . . . . . . . . . . . . . . . . 534.3 Modelo Matematico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.3.1 Funcao Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . 574.3.2 Restricoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.4 Ordem do Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.5 Pre-processamento dos Dados . . . . . . . . . . . . . . . . . . . . . . 684.6 Consideracoes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5 Modelagem das Variaveis Linguısticas do PSRE 735.1 Motivacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.2 Construcao do Sistema Fuzzy . . . . . . . . . . . . . . . . . . . . . . 74

5.2.1 Variavel de Saıda . . . . . . . . . . . . . . . . . . . . . . . . . 755.2.2 Variaveis de Entrada . . . . . . . . . . . . . . . . . . . . . . . 755.2.3 Base de Regras . . . . . . . . . . . . . . . . . . . . . . . . . . 775.2.4 Mecanismo de Inferencia . . . . . . . . . . . . . . . . . . . . . 805.2.5 Parametros Inseridos na FO do Modelo PLIM . . . . . . . . . 80


6 Abordagem Hıbrida: PLIM-PLR 896.1 Modelo em PLR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896.2 Modelo Hıbrido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6.2.1 Heurıstica na Geracao da Arvore de Busca . . . . . . . . . . . 946.3 Consideracoes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

7 Resultados 997.1 Resultados Computacionais do Capıtulo 4 . . . . . . . . . . . . . . . 101

7.1.1 Comentario dos Resultados . . . . . . . . . . . . . . . . . . . 1037.2 Resultados Computacionais do Capıtulo 5 . . . . . . . . . . . . . . . 105

7.2.1 Comentario dos Resultados . . . . . . . . . . . . . . . . . . . 1067.3 Resultados Computacionais do Capıtulo 6 . . . . . . . . . . . . . . . 108

7.3.1 Modelo em PLR . . . . . . . . . . . . . . . . . . . . . . . . . 1087.3.2 Modelo Hıbrido . . . . . . . . . . . . . . . . . . . . . . . . . . 1097.3.3 Comentario dos Resultados . . . . . . . . . . . . . . . . . . . 110

7.4 Comparativo dos Modelos . . . . . . . . . . . . . . . . . . . . . . . . 1117.5 Consideracoes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

8 Conclusoes 1138.1 Contribuicoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1158.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

Referencias Bibliograficas 127

A Complexidade Computacional 129

B Sugestoes para Modelagem de PSRP utilizando PLIM ou PLR 131

x

Lista de Figuras

1.1 Esquema generico de uma refinaria de petroleo. . . . . . . . . . . . . 2

2.1 Representacao do tempo. . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1 Representacao de uma arvore de busca. . . . . . . . . . . . . . . . . . 253.2 Exemplo da tecnica de consistencia do no (sem a restricao). . . . . . 343.3 Exemplo da tecnica de consistencia do no (com a restricao X > Y ). . 343.4 Exemplo da tecnica de consistencia do arco. . . . . . . . . . . . . . . 353.5 Espaco de busca para o algoritmo backtracking simples. . . . . . . . . 363.6 Espaco de busca para o algoritmo BB. . . . . . . . . . . . . . . . . . 373.7 Espaco de busca para o algoritmo BB com limite justo. . . . . . . . . 383.8 Variavel linguıstica de temperatura. . . . . . . . . . . . . . . . . . . . 443.9 Sistema fuzzy generico. . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.1 Inter-relacoes da TE. . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2 Tomada de decisao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.3 Grafo ilustrativo do processo. . . . . . . . . . . . . . . . . . . . . . . 544.4 Custo eletrico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.5 Variaveis binarias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.6 Variaveis contınuas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.1 Representacao geral do sistema fuzzy. . . . . . . . . . . . . . . . . . . 755.2 Base de regras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765.3 Custo de troca. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765.4 Dificuldade da manobra. . . . . . . . . . . . . . . . . . . . . . . . . . 775.5 Manobras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.6 Turnos de trabalho. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.7 Superfıcie dos custos de troca A. . . . . . . . . . . . . . . . . . . . . 825.8 Superfıcie dos custos de troca B. . . . . . . . . . . . . . . . . . . . . . 835.9 Variacao do custo de troca. . . . . . . . . . . . . . . . . . . . . . . . 85

6.1 Ordem de selecao das variaveis. . . . . . . . . . . . . . . . . . . . . . 956.2 Ordem de selecao dos valores do domınio. . . . . . . . . . . . . . . . . 96

7.1 Tempo computacional X diferenca de integralidade. . . . . . . . . . . 1027.2 Carta de gantt do modelo sem custo eletrico. . . . . . . . . . . . . . . 1047.3 Carta de gantt do modelo com custo eletrico. . . . . . . . . . . . . . . 1047.4 Carta de gantt do modelo sem custo de troca. . . . . . . . . . . . . . 1077.5 Carta de gantt do modelo com custo de troca. . . . . . . . . . . . . . 107

xi

B.1 Recomendacoes para modelagem de PSRP. . . . . . . . . . . . . . . . 132

xii

Lista de Tabelas

3.1 Relacao logica entre variaveis. . . . . . . . . . . . . . . . . . . . . . . 273.2 Dados do problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.3 Variavel linguıstica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.1 Base de regras A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.2 Base de regras B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.3 Base de regras C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.4 Variacao do custo de troca. . . . . . . . . . . . . . . . . . . . . . . . 84

7.1 Dados de entrada da instancia 1. . . . . . . . . . . . . . . . . . . . . 1007.2 Dados de entrada da instancia 2. . . . . . . . . . . . . . . . . . . . . 1007.3 Dados de entrada da instancia 3. . . . . . . . . . . . . . . . . . . . . 1017.4 Tempo computacional X diferenca de integralidade. . . . . . . . . . . 1027.5 Comparativo da DI em funcao da instancia. . . . . . . . . . . . . . . 1027.6 Resultados computacionais do capıtulo 4. . . . . . . . . . . . . . . . 1037.7 Atributos das variaveis para area de GLP. . . . . . . . . . . . . . . . 1057.8 Custo de troca. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1067.9 Resultados computacionais do capıtulo 5. . . . . . . . . . . . . . . . 1087.10 Resultados computacionais a partir do modelo em PLR. . . . . . . . 1097.11 Geracao da arvore de busca. . . . . . . . . . . . . . . . . . . . . . . . 1107.12 Resultados computacionais a partir do modelo hıbrido. . . . . . . . . 110

xiii

xiv

Siglas

AG algoritmos geneticosBB branch and boundDI diferenca de integralidadeDF domınios finitosFO funcao objetivoGLP gas liquefeito de petroleoPIM programacao inteira mistaPL programacao linearPLIM programacao linear inteira mistaPNL programacao nao linearPNLIM programacao nao linear inteira mistaPLR programacao logica por restricoesPM programacao matematicaPR programacao por restricoesPSR problemas de satisfacao de restricoesPSRE problemas de scheduling dos recursos de estocagemPSRP problemas de scheduling em refinarias de petroleoRR resolucao de restricoesRTN rede estado tarefaSR satisfacao de restricoesSTN rede recurso tarefaTE transferencia e estocagem

xv

xvi

Resumo

Este trabalho pretende contribuir no desenvolvimento de modelos de otimizacaopara o problema de scheduling da transferencia e estocagem (TE) em refinarias depetroleo. O scheduling diario da TE e uma tarefa difıcil, realizado em geral por umespecialista, baseado na experiencia profissional e com a utilizacao de calculos ma-nuais. Para determinar o scheduling o especialista considera varios espectos como:topologia da planta, balanco de massa, polıticas de transferencia de material, trocasde tanques, restricoes fısicas e de demanda, entre outras. O principal objetivo destetrabalho e diminuir a distancia entre os modelos teoricos e as necessidades praticas,em especial aquelas vivenciadas diariamente nas refinarias de petroleo. Inicialmentee proposto um modelo em programacao linear inteira mista (PLIM) com tempocontınuo. A representacao do problema e baseada nos estados possıveis dos tanquesdurante o horizonte de scheduling. Esta representacao permite explorar outras ca-racterısticas do problema, como a questao do custo eletrico diferenciado. Alem disso,os custos qualitativos da operacao da TE, considerando-se aspectos de execucao dastarefas, sao modelados atraves de sistemas fuzzy e representados na funcao objetivodo modelo matematico. Por fim, para reducao do tempo computacional, e propostauma estrutura hıbrida que combina PLIM com programacao logica por restricoes(PLR). Esta estrutura contempla ainda heurısticas que sao utilizadas na geracao daarvore de busca. Os resultados demonstram que a estrutura hıbrida apresenta boassolucoes em poucos segundos. Os modelos implementados podem ser utilizados para,alem de determinar o scheduling diario, testar novos pontos de operacao da TE.

Palavras-chave: Scheduling, PLIM, PLR, Transferencia e Estocagem, Sistemas Fuzzy.

xvii

xviii

Abstract

This work develops optimization models to the tank farm scheduling problem inthe oil industry. The short term scheduling of tank farm is a hard task because thespecialist has to take into account issues concerning plant topology, mass balances,transfer policies, resource constraints, demand patterns, and changeovers. So thisoperational decision-making in tank farm scheduling is still based on experiencewith the aid of manual computations. The main goal of this work is to reduce thedifference between a theoretical model and the practical needs. Initially, the problemis modeled as a mixed integer linear programming (MILP) model, using continuoustime formulation, the proposed approach is based on the different possible statesof tank during time line. This representation allows modeling other aspects as theelectrical cost variation. Besides that, it is possible to represent some considerationsabout qualitative variables in the model objective function with a fuzzy system, thisformulation addresses a new aspect related to the human resources needs to the tankfarm operation. Finally, the scheduling problem is modeled in a hybrid framework,which uses Constraint Logic Programming (CLP) and MILP to reduce the CPUtime. This approach has still some heuristics that are used in the generation of searchtree. The computational experiment demonstrated that the hybrid framework (CLPand MILP) was able to define a good solution in few seconds. The implementedmodels can be used to test new operation points of the refinery tank farm.

Keywords: Scheduling, Constraint Logic Programming (CLP), Mixed Integer LinearProgramming (MILP), Tank Farm, Fuzzy Systems.

xix

Capıtulo 1

Introducao

A programacao diaria das atividades de uma refinaria de petroleo, denominada

na literatura pelo termo short term scheduling, tem recebido uma atencao especial

nos ultimos anos, tanto por parte da comunidade cientıfica quanto por empresas do

ramo. Este fato tem ocorrido em funcao das refinarias de petroleo operarem com

cargas cada vez maiores, devido ao crescente aumento na demanda dos derivados

de petroleo (Tavares, 2005). O impacto deste aumento ocorre principalmente na

unidade de transferencia e estocagem, nem sempre novos tanques sao construıdos

quando uma nova unidade de processo e projetada. Deste modo, para gerenciar todos

os recursos envolvidos e indispensavel um planejamento sistemico, estruturado em

varios nıveis de informacao.

Com base na dinamica do sistema e das informacoes disponıveis deve-se de-

terminar a polıtica de utilizacao dos tanques. Cabe destacar que as atividades de

transferencia e estocagem sao programadas diariamente atraves de calculos manuais

baseados na experiencia profissional (Stebel, 2001).

E possıvel generalizar uma refinaria de petroleo, conforme a figura 1.1, sendo

composta por unidades de processo, transferencia e estocagem de produtos e utilida-

des. O que muda de uma refinaria para outra e, basicamente, a carga processada e,

consequentemente, o numero e as caracterısticas das unidades de processo. O fluxo

de informacoes dentro de uma refinaria parte de um planejamento, que determina,

em nıvel macroscopico, as campanhas de petroleo que serao processadas durante um

perıodo de tempo, que pode ser mensal, semestral ou ate mesmo anual. Em seguida,

2 Capıtulo 1. Introducao

as informacoes do planejamento sao refinadas caracterizando o scheduling da refi-

naria, que e dividido entre as unidades envolvidas, entre elas a de transferencia e

estocagem que e o foco desta tese de doutorado.

Unidades deProcesso

Transferência eEstocagem

UTILIDADES

MercadoFornecedor

MercadoConsumidor

refinaria

Figura 1.1: Esquema generico de uma refinaria de petroleo.

1.1 Motivacao

Nos ultimos anos ocorreu um numero crescente de publicacoes em problemas

de scheduling da industria quımica. Porem, a maioria dos trabalhos estao concentra-

dos em industrias de processos em batelada. Orcun et al. (2001) justificam este fato

pelo aumento de popularidade, nas ultimas decadas, dos processos em batelada. Em

muitas areas da industria quımica, como de tintas, alimentos, farmaceutica, quımica

fina, esquemas de producao em batelada sao sempre preferıveis por causa da habili-

dade em responder rapidamente as mudancas nas condicoes de mercado e pelo facil

controle da mesma. Segundo Orcun et al. (2001), um processo em batelada requer

menos investimento do que um processo contınuo, sendo preferido onde ocorre uma

introducao de uma variedade enorme de novos produtos no mercado. Normalmente

a demanda para produtos novos e incerta e nao e bem estabelecida.

1.2. Contribuicoes e Objetivos 3

Em funcao dos motivos citados anteriormente existe uma carencia muito grande

de trabalhos em problemas de scheduling de processos contınuos. Como maior repre-

sentante deste tipo de processo estao as refinarias de petroleo. Os trabalhos nesta

area (capıtulo 2) apontam algumas dificuldades para implantacao dos modelos de-

senvolvidos em ambientes industriais:

• A explosao do tempo computacional, bem como a instabilidade dos algoritmos

de solucao de problemas mistos (Moro, 2000).

• O numero excessivo de restricoes e regras operacionais resultantes de situacoes

particulares do processamento. Um grau elevado de inter-relacionamento de

eventos devido as relacoes de sequencia de execucao a que estes estao subme-

tidos (Pinto, 2000).

• Finalmente sao destacadas as divergencias entre as pessoas que desenvolvem

um modelo e aquelas que o aplicam efetivamente (Pinto, 2000). Estas divergen-

cias surgem no entendimento do problema, ou seja, na passagem de informacoes

do especialista do processo para o especialista matematico.

Os pontos anteriormente destacados aliado ao fato de tratar-se de um pro-

blema complexo relacionado ao processo produtivo serviram como motivacao para

o desenvolvimento desta tese de doutorado. Dentro deste contexto, os problemas de

scheduling em refinarias de petroleo (PSRP), segundo Kallrath & Wilson (1997),

pertencem a uma categoria de problemas dos mais difıceis, dado o carater combina-

torio.

1.2 Contribuicoes e Objetivos

Esta tese pretende contribuir no desenvolvimento de modelos de otimizacao e

metodos de solucao para os problemas de scheduling da transferencia e estocagem,

mais especificamente no scheduling dos tanques de estocagem. Estes modelos podem

ser utilizados como base para sistemas de suporte a tomada de decisao operacional

em refinarias. Este trabalho pode ser dividido em quatro partes que resultam em


quatro contribuicoes, sendo que todas elas tem por objetivo diminuir a distancia

entre os modelos teoricos e as necessidades praticas, em especial aquelas vivenciadas

no dia-a-dia das refinarias de petroleo. As contribuicoes sao as seguintes:

• A primeira delas explora as vantagens, ja comprovadas, dos modelos de pro-

gramacao linear inteira mista (PLIM) com tempo contınuo (representacao

do tempo) para os problemas de scheduling. Uma inovacao e inserida na re-

presentacao do problema, sendo esta baseada nos estados possıveis que cada

tanque passa durante o horizonte de scheduling, sao eles: pronto para receber,

recebendo, pronto para enviar e enviando. Cada tanque esta sempre associado

com um destes estados. Esta representacao tem como benefıcio uma reducao

da diferenca de integralidade e consequente reducao do tempo computacional,

permitindo assim explorar detalhes do problema.

• A segunda contribuicao trata de um destes detalhes, que e a questao do custo

eletrico diferenciado. Para problemas de scheduling com representacao discreta

do tempo a insercao deste custo e trivial, o que nao ocorre no caso da represen-

tacao contınua do tempo. A modelagem do custo eletrico diferenciado proposta

permite avaliar melhor os custos envolvidos.

• A terceira contribuicao ressalta a preocupacao em oferecer um scheduling que

seja efetivamente cumprido na pratica. Isto e possıvel atraves da modelagem de

variaveis qualitativas do problema representando o custo de troca, sendo este

inserido na funcao objetivo do modelo de otimizacao, tornando o modelo mais

fiel a realidade. Esta representacao procurou explorar aspectos de mao-de-obra

envolvidos na execucao das operacoes de transferencia e estocagem.

• A quarta contribuicao trata das vantagens de um modelo hıbrido, particular-

mente a PLIM e a programacao logica por restricoes (PLR) na solucao do

problema. Ainda em relacao ao modelo hıbrido, e utilizada uma heurıstica na

geracao da arvore de busca, que influencia diretamente o desempenho compu-

tacional.

1.3. Organizacao do Trabalho 5

1.3 Organizacao do Trabalho

Esta tese e organizada do seguinte modo. O capıtulo 2 apresenta uma revisao

bibliografica sobre os PSRP, onde sao apresentados alguns conceitos gerais sobre

scheduling, destacando a diferenca com o planning. Ainda neste capıtulo, sao apre-

sentadas as caracterısticas dos problemas e modelos de scheduling. Por fim, sao

destacados os principais modelos existentes para os PSRP.

No capıtulo 3 e apresentada uma revisao bibliografica sobre as principais tec-

nicas de otimizacao utilizadas na modelagem e solucao dos PSRP, em particular a

programacao linear inteira mista e a programacao logica por restricoes. Ainda neste

capıtulo, sao apresentados alguns conceitos sobre sistemas fuzzy que sao utilizados

nesta tese na modelagem de variaveis linguısticas.

O capıtulo 4 apresenta uma modelagem utilizando programacao linear inteira

mista com representacao contınua do tempo, para um problema de scheduling dos

recursos de estocagem (PSRE) de uma refinaria de petroleo. O modelo desenvolvido

contempla, entre outros custos, a variacao do custo eletrico em funcao do horario de

pico de consumo de energia eletrica.

O capıtulo 5 apresenta o desenvolvimento de um sistema fuzzy utilizado para

determinar os parametros do custo de troca representado na funcao objetivo do

modelo matematico do capıtulo 4.

No capıtulo 6 o PSRE e modelado em PLR e tambem em uma estrutura hıbrida

(PLIM-PLR). As funcionalidades da linguagem OPL Studio 3.6.1 (ILOG, 2002b)

sao utilizadas na modelagem e solucao dos modelos obtidos. Ainda neste capıtulo,

sao utilizadas heurısticas na geracao da arvore de busca para se obter um melhor

desempenho computacional.

O capıtulo 7 apresenta simulacoes computacionais para todos os modelos de-

senvolvidos nos capıtulos 4, 5 e 6 respectivamente. Neste capıtulo e demonstrado,

atraves dos resultados, que a abordagem hıbrida com a utilizacao de heurısticas

possui um melhor desempenho computacional do que as demais tecnicas separada-

mente.


Por fim, no capıtulo 8 sao apresentadas as conclusoes desta tese, destacando-se

as caracterısticas de cada modelo apresentado. Ainda neste capıtulo sao apresentadas

algumas sugestoes para trabalhos futuros.

Capıtulo 2

Revisao Teorica: PSRP

A seguir sao apresentados varios conceitos, sobre os problemas de scheduling,

utilizados em refinarias de petroleo. Cabe ressaltar que embora muitos conceitos

possuam um escopo geral, a intencao aqui e apresentar apenas os conceitos que sao

utilizados nesta tese.

2.1 Conceitos Gerais sobre Scheduling

Na industria petroquımica, tanto a palavra planning (planejamento) como

scheduling referem-se aos procedimentos de alocacao, num determinado perıodo de

tempo, de recursos e equipamentos para executar o processamento de tarefas (Pekny

& Zentner, 1993). Optou-se por nao traduzir a palavra scheduling, oriunda da lıngua

inglesa, para evitar uma confusao com a palavra programacao que e usada em muitas

areas do conhecimento. Usualmente o planejamento define metas de producao rela-

tivas a perıodos de tempo mais longos, como meses ou anos, considerando, para isto,

tanto as previsoes do mercado como a disponibilidade de recursos (Reklaitis, 1992).

O scheduling considera perıodos de tempo menores, como por exemplo dias ou sema-

nas, sendo requerido quando existe competicao entre atividades por recursos limita-

dos dentro de um horizonte de tempo definido. O scheduling possui tres elementos

chaves (Reklaitis, 1992):

• Designacao dos recursos: a designacao dos recursos envolve a selecao do recurso

8 Capıtulo 2. Revisao Teorica: PSRP

apropriado para uma atividade conhecida, quando ha mais de um equipamento

capaz de realizar a tarefa.

• Sequenciamento de atividades: define a ordem de execucao das atividades de-

signadas para os recursos.

• Determinacao do tempo de utilizacao dos recursos pelas respectivas atividades:

o componente tempo envolve a determinacao dos tempos de inıcio e final de

cada atividade.

Na forma mais geral, um problema de scheduling consiste de uma estrategia ope-

racional; de um conjunto de equipamentos da planta; de um conjunto de recursos:

humanos, utilidades e materiais; de um conjunto de receitas de produtos e a relacao

de precedencia na producao; de uma demanda de produtos e de um ou mais criterios

da planta que necessitam ser otimizados (Reklaitis, 1992). Existem muitas razoes

de ordem tecnica e financeira que justificam o desenvolvimento e a implantacao de

ferramentas computacionais direcionadas ao scheduling em refinarias de petroleo,

conforme Magalhaes et al. (1998):

• A selecao de misturas otimas de petroleo e produtos intermediarios auxilia na

obtencao de produtos finais, com parametros dentro de uma faixa estreita e

estavel de especificacao.

• A utilizacao otimizada do parque de armazenagem reduz as perdas em tanca-

gem. Estas perdas podem ser funcao do tempo que o produto fica depositado

no tanque, contribuindo para a formacao de emulsoes (dispersao de gotıculas

de um lıquido em outro imiscıvel).

• Expansao da capacidade de monitoramento/tomada de decisao no processo

como um todo, bem como em situacoes de instabilidade. Como exemplo desta

situacao pode-se citar uma oscilacao no processo de refino, tirando de especi-

ficacao alguns produtos finais ou intermediarios.

• Possibilidade de rapida adaptacao ao fornecimento de produtos requeridos em

situacoes especiais.

2.2. Caracterısticas dos Problemas de Scheduling 9

• Possibilidade teorica de obtencao de qualidade assegurada ao produto que sai

do processo, o que pode conduzir ao fornecimento direto as distribuidoras.

• Possibilidade de adocao de uma polıtica just-in-time indo ao encontro das

necessidades das distribuidoras.

• Reducao da necessidade de inventarios aliada a melhora na comunicacao e

resposta entre as unidades operacionais da planta.

2.2 Caracterısticas dos Problemas de Scheduling

Entende-se por caracterısticas dos problemas de scheduling aquelas que tra-

tam da topologia da planta, do balanco de massa, das polıticas de transferencia de

material, das restricoes de recursos, dos padroes de demanda, das transicoes e dos

modos de operacao da planta.

Topologia da planta

A topologia da planta esta relacionada as caracterısticas dos produtos, sendo

que estas caracterısticas ditam a sequencia de transformacoes fısico-quımicas que

deverao ser efetuadas durante o processamento industrial. Podem ser classificadas

em dois tipos (Pinto, 2000):

• Plantas seriais: onde o produto passa por uma sequencia de estagios de pro-

cessamento pre-definida. Plantas com estas caracterısticas sao tambem deno-

minadas flow shop.

• Plantas em rede: onde a linha de produtos nao possui uma trajetoria especı-

fica durante o processamento. Plantas com estas caracterısticas sao tambem

conhecidas como job shop.

As plantas seriais podem ser usadas tanto para processos contınuos quanto

para batelada. Ja para as plantas em rede, o processo tem de ser do tipo batelada.


Balanco de massa

O balanco de massa e elaborado em funcao das caracterısticas do processa-

mento. Podendo ser de modo descontınuo, semicontınuo ou contınuo. Nos dois pri-

meiros casos o equacionamento e escrito para bateladas ou lotes. Para plantas con-

tınuas ha um fluxo de materia ininterrupto atraves de um volume de controle onde

geralmente nao e verificada variacao de massa (Joly, 1999).

Polıticas de transferencia de material

A polıtica de transferencia de material e definida com base no estado final de

uma tarefa, podendo ser dividida do seguinte modo (Reklaitis, 1992) :

• No intermediate storage (sem estoque intermediario): a estocagem pode ser

feita na propria unidade de processamento, enquanto esta aguarda uma nova

tarefa a ser processada.

• Finite intermediate storage (estoque intermediario finito): ha um ou mais tan-

ques apos cada estagio de processamento com capacidade limitada.

• Unlimited intermediate storage (estoque intermediario ilimitado): ha um ou

mais tanques apos cada estagio de processamento, com capacidade ilimitada

frente as quantidades produzidas.

• Zero wait (espera zero): o produto intermediario vai para o estagio seguinte

imediatamente apos a conclusao do processamento.

Restricoes de recursos

As tarefas devem ser executadas com os recursos disponıveis. Os recursos po-

dem ser variaveis ao longo do tempo, sendo classificados como (Pinto, 2000):

• sem restricoes;

• com restricoes discretas: consumidos em um nıvel constante ao longo do pro-

cessamento de um dado produto;

2.2. Caracterısticas dos Problemas de Scheduling 11

• com restricoes contınuas: as demandas pelos recursos variam com o tempo de

processamento.

Padrao de demanda

Quando a planta deve atender a um conjunto de pedidos diferentes a cada

perıodo, com uma demanda variavel, o scheduling e chamado short term scheduling.

Por outro lado, se a demanda e constante, o scheduling pode ser realizado para

perıodos de tempo maiores, conhecido como long term scheduling (Kondili et al.,

1993). Existe ainda o scheduling cıclico (cyclic scheduling) que ocorre quando a

demanda obedece a um padrao previsıvel nos varios perıodos (Alle, 2003).

Transicoes

Quando ocorre transicao entre produtos, as unidades de processo podem neces-

sitar de uma limpeza ou set-up para atender as condicoes de seguranca ou qualidade

dos produtos. A natureza dos produtos e das unidades de processo indicarao a ne-

cessidade ou nao de realizar-se transicoes (Pinto, 2000).

Modos de operacao das plantas

Dentro do contexto de plantas petroquımicas, os processos podem ser divididos

do seguinte modo:

• Batelada: nas ultimas decadas os processos em batelada tem ganhado consi-

deravel popularidade. As especificacoes de produtos estao se tornando cada

vez mais rigorosas e os volumes envolvidos sao cada vez maiores. Alem disso,

os consumidores estao tornando-se cada vez mais exigentes, assim como a de-

manda por produtos com especificacoes diversas (Orcun et al., 2001).

• Semicontınuos: processos onde as partidas (bateladas) do mesmo produto sao

feitas uma apos a outra ou onde uma parte do processamento e feito em bate-

lada e a outra parte e feita de forma contınua.


• Contınuos: sistemas de producao contınua normalmente envolvem a producao

de poucos produtos. O maior exemplo de plantas contınuas sao as refinarias

de petroleo (Moro, 2000).

2.3 Caracterısticas dos Modelos de Scheduling

As caracterısticas dos modelos de scheduling dizem respeito a representacao do

problema com relacao ao tempo, a estrutura do modelo e tambem a incerteza dos

parametros.

Representacao do tempo

Pinto & Grossmann (1995) apontam a representacao do tempo como ques-

tao fundamental para a modelagem de um problema de scheduling. Nos trabalhos

existentes e possıvel classificar a representacao do tempo em discreta e contınua.

• Discreta: A representacao discreta consiste em dividir o horizonte de scheduling

em intervalos de tempo fixos e uniformes, ou seja, em intervalos de mesmo ta-

manho, conforme ilustrado na figura 2.1. O numero e a duracao dos intervalos

de tempo devem ser definidos previamente de modo que as decisoes ocorram

na fronteira entre dois intervalos de tempo. Os problemas em que as decisoes

possuem diferentes tamanhos exigem um numero muito elevado de intervalos,

tendo como consequencia uma explosao combinatoria, pelo aumento das va-

riaveis binarias (Kondili et al., 1993). A forma de se determinar a duracao do

intervalo de tempo e atraves do uso do maximo divisor comum entre os tempos

de processamento que devem ser considerados. O modelo discreto e potencial-

mente mais rapido que o contınuo, mas apresenta uma perda de otimalidade se

houver aproximacao dos tempos de processo para evitar um numero excessivo

de intervalos (Moro, 2000). A representacao discreta do tempo e a mais comum

entre os modelos matematicos existentes. Alguns exemplos destas formulacoes

podem ser encontados em Lee et al. (1996), Joly (1999), Moro (2000), Stebel

et al. (2002), Magatao et al. (2004) e Magalhaes (2004).

2.3. Caracterısticas dos Modelos de Scheduling 13

• Contınua: na formulacao contınua os intervalos de tempo assumem extensoes

variaveis, o numero de tarefas e conhecido previamente, evitando deste modo

uma geracao desnecessaria do numero de intervalos, conforme ilustrado na

figura 2.1. Uma tendencia nos trabalhos atuais e o desenvolvimento de algo-

ritmos, com formulacoes contınuas do tempo, que explorem as caracterısticas

peculiares de cada problema (Pinto & Grossmann, 1995; Mockus & Reklai-

tis, 1997; Ierapetritou & Floudas, 1998a; Ierapetritou & Floudas, 1998b; Iera-

petritou & Floudas, 1999; Moro, 2000; Mendez & Cerda, 2002; Stebel et al.,

2003; Magatao, 2005).

1 2 3 4 NN-1N-2

NN-11 2

tempo

tempo

representação discreta do tempo

representação contínua do tempo

N-3

Figura 2.1: Representacao do tempo.

Estrutura do modelo

As representacoes da estrutura do modelo mais utilizadas dentro do contexto

de processos quımicos sao as seguintes:

• STN - State Task Network (Rede Estado Tarefa): desenvolvida por Kondili

et al. (1993), esta representacao na forma de grafo e composta por dois tipos de

nos: os nos Estado e os nos Tarefa, os primeiros representam a materia-prima,

os produtos finais e os intermediarios, e os segundos representam as operacoes

de processamento.

• RTN - Resource Task Network (Rede Recurso Tarefa): proposta por Panteli-

des (1994), a RTN e uma extensao da STN, esta representacao nao faz distincao

entre os diferentes tipos de recursos (materia-prima, produtos intermediarios,

produtos finais, utilidades, mao-de-obra, equipamentos do processo, tanques


de armazenamento). Uma vantagem bastante significativa da representacao

RTN sobre a STN em problemas de scheduling e que esta representacao e mais

compacta.

Incerteza dos parametros

Por fim, os modelos de scheduling podem ainda ser caracterizados em estocasti-

cos ou determinısticos, dependendo da inclusao ou nao de incertezas nos parametros

do problema (datas de entrega, taxas de producao, precos, etc.) (Alle, 2003).

Abordagens dos Modelos de Scheduling

No trabalho de Pekny et al. (1990) os modelos de scheduling foram divididos

em duas categorias que sao:

• A elaboracao de modelos de scheduling generalistas, atraves da manipulacao

adequada do conjunto de restricoes contidas no modelo inicialmente proposto.

Estes modelos procuram determinar o plano otimo de programacao de ativida-

des de um problema utilizando os recursos disponıveis dentro de um horizonte

de scheduling pre-determinado. Estes modelos sao baseados em programacao

inteira mista (linear ou nao linear). Os trabalhos nesta area foram inicialmente

apresentados por Kondili et al. (1993) com as representacoes em Rede Estado

Tarefa, para descrever processos quımicos complexos.

• Desenvolvimento de algoritmos especıficos para cenarios de problemas parti-

culares. Alguns destes cenarios incluem estagios multiplos de processamento,

equipamentos com varias condicoes de estocagem de intermediarios. Os tra-

balhos nesse sentido vem sendo difundidos, por utilizarem algoritmos especı-

ficos de cada processo (Grau et al., 1996; Kondili et al., 1993; Pinto & Gross-

mann, 1995; Kudva et al., 1994).

2.4. Divisao dos PSRP 15

2.4 Divisao dos PSRP

Em Castro (2001) e apresentada uma divisao dos problemas de scheduling de

uma refinaria de petroleo do seguinte modo:

• Recebimento de petroleos e mistura: o programador deve definir a melhor

sequencia de recebimento do petroleo disponıvel e a forma de processamento

destas misturas, visando o maximo aproveitamento.

• Modos de operacao das unidades de processo: e de responsabilidade do pro-

gramador de producao a definicao do tipo de carga a ser processada, quais as

variaveis operacionais das unidades e tambem quais os produtos que devem

ser produzidos em um determinado momento.

• Utilizacao da tancagem de componentes intermediarios: o programador de pro-

ducao deve avaliar a adequacao dos estoques de materia-prima para as uni-

dades de processo, visando cumprir as diretrizes estabelecidas no plano de

producao.

• Realizacao de misturas de produtos: em funcao das solicitacoes dos clientes e

das caracterısticas dos componentes disponıveis, o programador de producao

define como, quando e qual o tipo de produto a ser preparado.

Existe ainda o scheduling da transferencia e estocagem em que sao programadas

todas as operacoes de envios e recebimentos, sendo que este tem como entrada de

dados os scheduling citados anteriormente. Ou seja, nesse nıvel deve-se determinar

a programacao de todos os tanques. Esta tese trata justamente o scheduling da

transferencia e estocagem, no capıtulo 4 sao apresentadas as caracterısticas deste

problema.

2.5 Modelos para os PSRP

Existem varios pacotes comerciais disponıveis para o planejamento em refina-

rias de petroleo baseados em programacao linear. Em Magalhaes (2004) e apresen-


tada uma revisao sobre alguns destes. Porem, e destacado por alguns autores (Moro

et al., 1998), que os resultados fornecidos por estas ferramentas, para problemas de

scheduling, sao incompletos por nao representarem particularidades da planta em

consideracao. Frequentemente o planejamento constitui a referencia empregada no

estabelecimento dos dados utilizados para a otimizacao de problemas de schedu-

ling em refinarias como pode ser encontrado em Lee et al. (1996). Um dos sistemas

disponıveis mais importantes para modelagem de problemas de planejamento em

refinarias de petroleo e PIMS (Process Industry Modelling System) baseado em

programacao linear (Joly, 1999). Este sistema possui as seguintes funcionalidades:

determinacao da capacidade necessaria de equipamentos, da realizacao de mistura

entre produtos ou materias-primas, e tambem da configuracao das plantas para in-

dustrias de processamento inorganico, organico, biologico e especialmente refinarias

de petroleo.

Em Rigby et al. (1995) e apresentado um trabalho sobre misturas de produ-

tos, relacionada a producao de gasolina nas refinarias da Texaco. A gasolina e o

produto de maior representatividade economica da refinaria considerada, sendo res-

ponsavel por 60 a 70% do faturamento total. Neste trabalho sao utilizadas tecnicas

de programacao matematica na solucao dos modelos.

Em Shah (1996) e demonstrada a viabilidade de utilizar programacao mate-

matica em problemas de scheduling de alimentacao de oleo cru de um terminal para

uma refinaria atraves de um oleoduto. Esta atividade normalmente era realizada

atraves de simulacao computacional. O autor propos a decomposicao do problema

em modelos de upstream/downstream.1

Lee et al. (1996) tratam de um problema real de scheduling de recebimento de

crus. O modelo de otimizacao resultante deste trabalho e baseado em programacao

linear inteira mista e utiliza uma representacao discreta do tempo.

Em Magalhaes et al. (1998) e descrito o desenvolvimento de um sistema in-

1O termo upstream se refere a todas as atividades de exploracao e producao de hidrocarbonetos,como petroleo e gas natural, ate as unidades de processamento. O termo downstream inclui todas asatividades inerentes ao setor petrolıfero posteriores a obtencao de produtos para uso final, incluindoassim a distribuicao e revenda de derivados (Magalhaes, 2004).

2.5. Modelos para os PSRP 17

tegrado para o scheduling da producao de uma unidade de refino da Petrobras. As

informacoes deste sistema estao baseadas no planejamento da refinaria. Este sistema,

cujo desenvolvimento foi iniciado em 1996, e denominado SIPP e aborda a refinaria

como um todo, abrangendo desde a etapa de recebimento ate a fase de expedicao de

produtos.

No trabalho de Joly (1999) foram apresentados modelos matematicos para

problemas de scheduling em refinarias de petroleo. Neste trabalho existe uma for-

mulacao generica para problemas de producao e distribuicao de produtos e outra

especıfica tratando de um problema referente a producao de oleos combustıveis.

Ambos os modelos utilizam tecnicas de otimizacao linear e nao-linear inteira mista

com discretizacao uniforme do tempo.

Na mesma linha de pesquisa esta inserido o trabalho de Moro (2000) que es-

tuda modelos matematicos de otimizacao lineares e nao lineares para problemas de

planejamento e scheduling da producao em refinarias de petroleo. O autor utiliza

abordagens discretas e contınuas para representar o tempo. A partir de uma for-

mulacao generica desenvolvida, o autor aplica o modelo em problemas reais de uma

refinaria.

Em Pinto (2000) e apresentada uma revisao sobre os diversos aspectos en-

volvendo aplicacoes de planejamento e scheduling da producao para refinarias de

petroleo. Neste trabalho sao sumarizados os principais metodos de solucao dos mo-

delos de otimizacao inteira mista linear e nao-linear.

Em Stebel (2001) foram apresentados dois modelos para as operacoes de trans-

ferencia e estocagem do gas liquefeito de petroleo (GLP). O primeiro modelo e ba-

seado em Redes de Petri e permite ao operador visualizar o comportamento de um

processo de estocagem e distribuicao de GLP. O segundo modelo utiliza tecnicas de

programacao linear inteira mista com discretizacao do tempo para o problema de

scheduling e tem como objetivo a minimizacao dos custos operacionais.

Em Magatao (2001) e Magatao et al. (2004) sao apresentados modelos de

auxılio ao gerenciamento das operacoes de um poliduto. Os modelos de otimizacao

apresentados utilizam programacao linear inteira mista com discretizacao uniforme


do tempo. Estrategias de subdivisao do problema foram empregadas para reducao do

tempo computacional, os resultados computacionais obtidos sao comparados entre

os modelos desenvolvidos.

O trabalho de Mas (2001) aborda problemas de programacao de suprimen-

tos de petroleo contendo portos, refinarias e uma estrutura de oleodutos. Os portos

contem pıeres, tanques de armazenagem e uma rede de tubulacoes. As refinarias

possuem infra-estrutura propria de armazenagem, enquanto unidades de destilacao

de oleo cru consomem petroleo a uma vazao conhecida. O problema trata tambem a

armazenagem intermediaria em subestacoes, tarefas de decantacao e alocacao de pe-

troleo atraves de caracterısticas qualitativas. A resolucao do problema foi abordada

por intermedio de modelos de programacao linear inteira mista com tempo contınuo.

O trabalho de Rejowski (2001) considera um sistema composto por uma refina-

ria de petroleo, um duto e diversos depositos com localizacoes geograficas distintas

conectados a mercados consumidores. Grandes quantidades de gasolina, oleo diesel,

GLP e querosene de aviacao sao transportados atraves deste duto. Foram desen-

volvidos modelos de programacao linear inteira mista, considerando-se condicoes de

balanco de massa, restricoes de demanda e distribuicao dos produtos a serem arma-

zenados e transportados. Os modelos foram baseados na representacao uniforme de

intervalos de tempo, sendo utilizadas formulacoes BIG-M e relacoes logicas.

Em Castro (2001), o problema de scheduling da producao em refinarias de

petroleo e modelado em Algoritmos Geneticos. Segundo o autor esta tecnica e bas-

tante adequada para a otimizacao de problemas nao lineares que envolvem variaveis

discretas e contınuas. O modelo desenvolvido foi testado num sistema de producao

e armazenamento de GLP.

Em Persson (2002), o problema de scheduling dos modos de operacao e mode-

lado utilizando programacao linear inteira mista, tendo como objetivo a minimizacao

dos custos de troca de carga (troca de campanha) da refinaria. No mesmo trabalho

e desenvolvido um modelo utilizando busca tabu para o mesmo problema.

Em Stebel et al. (2003), os autores modelam o mesmo problema apresentado

em Stebel et al. (2002), porem com a representacao contınua do tempo ao inves da

2.5. Modelos para os PSRP 19

discreta, ambos em programacao linear inteira mista. Nestes trabalhos e possıvel

observar uma reducao significativa do numero de variaveis binarias utilizadas na

representacao contınua do tempo, quando comparada com a discreta.

Jia & Ierapetritou (2003) desenvolveram um modelo de programacao linear

inteira mista com representacao contınua do tempo para o short term scheduling

de refinarias de petroleo. A abordagem consiste em decompor o problema em tres

domınios: recebimento e mistura; operacoes de producao e mistura e entrega dos

produtos finais. Um metodo iterativo, baseado em relaxacao lagrangeana, e proposto

para a solucao integrada dos tres subproblemas.

Magalhaes (2004) modela o problema de scheduling de recebimento de pe-

troleo utilizando programacao nao-linear inteira mista com representacao discreta e

contınua do tempo. O cenario considerado e composto de um terminal, um oleoduto,

a area de estocagem de petroleo e tambem pela unidade de processamento.

Cafaro & Cerda (2004) apresentam uma modelagem de programacao linear

inteira mista com representacao contınua do tempo para o problema de scheduling

de um poliduto. Este trabalho traz um comparativo com o trabalho de Rejowski &

Pinto (2003).

Neiro & Pinto (2004) desenvolveram uma estrutura geral para modelagem da

cadeia de suprimentos de petroleo. Nesta estrutura estao representados os tanques de

estocagem, unidades de processo e polidutos, bem como as interligacoes. O modelo

multi-perıodo resultante e de programacao nao linear inteira mista.

Felizari (2004) apresenta uma modelagem para o problema de transferencia e

estocagem de uma refinaria, considerando tempos de atraso nas operacoes e recursos

escassos. O modelo resultante utiliza tecnicas de otimizacao fuzzy com programacao

matematica.

Magatao (2005) aplica estruturas de alto nıvel para modelagem do problema de

scheduling de polidutos. Estas estruturas sao utilizadas em modelos de programacao

linear inteira mista, de programacao logica por restricoes e tambem em um modelo

hıbrido que combina as tecnicas anteriormente citadas.


O trabalho de Barboza (2005) aborda o problema de scheduling da estocagem

e distribuicao de diesel em uma refinaria de petroleo. Neste trabalho foram desen-

volvidas quatro metodologias utilizando metaheurısticas com o objetivo de reducao

do tempo computacional.

2.6 Consideracoes Finais

Este capıtulo apresentou uma revisao teorica sobre os PSRP. Inicialmente, fo-

ram apresentados alguns conceitos sobre scheduling que possuem um escopo geral.

A seguir, foram apresentadas as caracterısticas dos problemas e dos modelos sche-

duling. Por fim, foi apresentada uma divisao dos problemas de scheduling dentro das

refinarias de petroleo, bem como os principais modelos desenvolvidos para resolver

estes problemas.

Capıtulo 3

Revisao Teorica: Metodos deSolucao para os PSRP

O problema de scheduling tratado nesta tese pode ser considerado como um

problema de otimizacao combinatoria, uma vez que visa a utilizacao otima de um

conjunto de recursos, de acordo com a disponibilidade e com o objetivo de mini-

mizacao do custo ou de maximizacao do lucro. Um exemplo classico de problema

de otimizacao combinatoria e o problema do caixeiro-viajante. Em que se pretende

achar um percurso de menor distancia para um vendedor que deve visitar cada uma

das n cidades (sem repeticao), comecando e terminando a viagem pela cidade 1.

O conjunto finito para o problema do caixeiro-viajante com n cidades consiste em

(n − 1)! diferentes viagens possıveis comecando e terminando na cidade 1. Nestes

problemas, quando n e muito grande, uma resposta factıvel ja pode ser considerada

uma boa resposta para o problema. A otimizacao combinatoria esta presente em

muitos outros problemas de decisao, entre eles destaca-se o problema de scheduling

tratado nesta tese.

Existem varias tecnicas para resolver problemas de otimizacao combinatoria.

Entre elas cabe destacar:

• programacao matematica (inteira mista);

• programacao logica por restricoes;

• metodos heurısticos;

22 Capıtulo 3. Revisao Teorica: Metodos de Solucao para os PSRP

• metaheurıstica (algoritmos geneticos, simulated annealing, busca tabu, entre

outros);

• metodos hıbridos.

A diferenca entre programacao matematica e metaheurısticas esta na busca

pelo otimo e pela aceitacao de uma boa resposta. O principal argumento utilizado

pelos adeptos de metaheurısticas e que, como o modelo matematico e uma abstracao

da realidade, o ponto otimo obtido pela programacao matematica (PM) e um ponto

idealizado, nao e real. A primeira justificativa para este fato e que a propria constru-

cao do modelo se baseia em hipoteses que levam a uma simplificacao da realidade.

A segunda e associada aos parametros e dados de entrada utilizados na simulacao

do modelo (Alle, 2003).

Por outro lado, os adeptos de programacao matematica destacam as principais

vantagens da programacao matematica em relacao as demais abordagens (heurısti-

cas, metaheurısticas e de inteligencia artificial), a saber (Alle, 2003):

• A capacidade de traduzir o problema sistematicamente em uma serie de equa-

coes, inequacoes e variaveis, que tornam explıcita a relacao entre os compo-

nentes.

• O vasto numero de algoritmos de solucao disponıvel para a solucao de modelos

de programacao matematica que, no caso, de problemas convexos, asseguram

convergencia para o otimo num numero finito de iteracoes.

• A possibilidade de se obter uma estimativa rigorosa do melhor valor possı-

vel para a funcao objetivo de problemas de programacao inteira mista com

relaxacao convexa.

As tecnicas de otimizacao utilizadas nesta tese sao programacao matematica,

programacao logica por restricoes e um metodo hıbrido que incorpora as caracterıs-

ticas dos dois anteriores. Em funcao disso, a seguir serao apresentadas as principais

caracterısticas destas tecnicas.

3.1. Programacao Matematica 23

3.1 Programacao Matematica

Williams (1999) cita alguns motivos para elaboracao de modelos em programa-

cao matematica, dentre estes cabe destacar que a construcao de um modelo revela

aspectos nao evidentes a priori, propiciando deste modo um melhor entendimento

do problema a ser modelado. Um problema de otimizacao e um problema de pro-

gramacao matematica que procura maximizar ou minimizar uma funcao numerica,

chamada objetivo, de um determinado numero de variaveis (ou funcoes), com as

variaveis (funcoes) sujeitas a certas restricoes. Esta funcao objetivo pode vir a re-

presentar criterios economicos (minimizacao de custos, maximizacao de lucros), ou

operacionais (minimizacao de atrasos). Uma classe de problemas de otimizacao em

que ha duas ou mais funcoes objetivo e denominado de problema de otimizacao

multi-objetivo. Um problema de otimizacao pode possuir um numero de variaveis

igual ou superior ao numero de relacoes matematicas.

Os problemas de scheduling possuem normalmente variaveis contınuas e dis-

cretas e a representacao na forma algebrica possui a forma (Grossmann et al., 2001):

minZ = f(x, y)

s.t. h(x, y) = 0

g(x, y) ≤ 0

x ∈ X, y ∈ {0, 1}m

(3.1)

onde f(x, y) e a funcao objetivo, por exemplo custo operacional, h(x, y) = 0 sao

as equacoes que descrevem o desempenho do sistema e g(x, y) ≤ 0 sao as inequacoes

que definem as especificacoes ou restricoes fısicas da planta, ou restricoes que definem

a viabilidade de uma solucao. As variaveis x sao do tipo contınuas, enquanto as

variaveis y sao do tipo discretas (geralmente sao variaveis binarias).

Um problema de programacao inteira mista (PIM) possui variaveis discretas e

contınuas interligadas por restricoes lineares, denominado programacao linear inteira

mista (PLIM) ou nao-lineares, denominado programacao nao linear inteira mista

(PNLIM). Se existem somente variaveis contınuas o problema PIM passa a ser


programacao linear (PL) ou programacao nao-linear (PNL), dependendo se existem

ou nao funcoes nao lineares.

3.1.1 Programacao Linear Inteira Mista

As solucoes determinadas por PL e PLIM sao otimos globais, ou seja, nao ha a

possibilidade da solucao obtida ser apenas um maximo local, apenas e possıvel que

a solucao otima nao seja unica. Neste caso, pela Teoria dos Poliedros a solucao e

representada por uma aresta, se a solucao e unica entao ela e representada por um

vertice (Nemhauser & Wolsey, 1988). A maior dificuldade destes problemas esta na

natureza combinatoria dos modelos.

Em funcao da natureza combinatoria dos modelos de PLIM, alguns algoritmos

foram desenvolvidos com o objetivo de se examinar apenas um subconjunto das

solucoes viaveis. O algoritmo mais conhecido e o Branch and Bound apresentado a

seguir.

O algoritmo Branch and Bound

O algoritmo denominado branch and bound (BB) (ramificacao e limite) foi

inicialmente proposto por Land & Doig (1960). Ao longo dos anos, este metodo vem

recebendo varias alteracoes, sendo amplamente empregado em softwares comerciais

destinados a solucao de problemas de programacao inteira mista. O metodo e, ba-

sicamente, uma estrategia que divide a regiao factıvel em subregioes mais faceis de

serem manipuladas e, se necessario, divide novamente estas subregioes a fim de en-

contrar a solucao otima. Existem diversos metodos para particionar a regiao factıvel,

o que, consequentemente, geram diversos algoritmos de BB.

Um algoritmo BB analisa todas as alternativas de um modelo PLIM, sem

examinar todas as combinacoes entre as variaveis binarias. A enumeracao desta

combinacao gera a arvore de busca, conforme ilustrado na figura 3.1.

O algoritmo de BB adiciona restricoes ao problema a medida que este e re-

solvido. Para todas as solucoes nao-inteiras, as variaveis contınuas sao obrigadas,


S

S0S1

S01

X1=0 X1=1

S00

X2=0 X2=1 X2=0 X2=1

S11S10

S010S000 S110S100S011S001 S111S101

X3=0 X3=1 X3=0 X3=1X3=0 X3=1X3=0 X3=1

Figura 3.1: Representacao de uma arvore de busca.

atraves de restricoes, a serem maior ou menor que o valor contınuo encontrado, e

o problema e novamente resolvido. Este procedimento e repetido ate que todas as

variaveis declaradas inteiras assumam valores inteiros.

Este metodo envolve inicialmente a relaxacao da integralidade das variaveis do

modelo, ou seja, a transformacao das variaveis inteiras em reais e uma solucao como

um problema de PL de modo a obter o limite superior (problema de maximizacao)

ou inferior (problema de minimizacao). A solucao obtida e conhecida como solucao

relaxada (zr). Quando a solucao por PL violar as restricoes de integralidade, o

algoritmo percorre uma arvore de busca ate encontrar uma solucao inteira otima

(zo).

A diferenca entre o valor da funcao objetivo desta solucao inteira (zo) e o valor

na solucao do modelo relaxado (zr) e conhecida como “relaxation gap” ou diferenca

de integralidade (DI) (Moro, 2000). O tempo de busca tende a ser maior nos modelos

em que a DI seja elevada, em funcao disso alguns autores como Yee & Shah (1998)

propoe metodologias para reduzir esta diferenca. A expressao 3.2 define a DI para

um problema de maximizacao.

DI =

∣∣∣∣zr − zo

zo

∣∣∣∣ .100% (3.2)


A formulacao BIG-M

Na modelagem de problemas de PLIM em que se deseja selecionar uma dada

restricao ou ainda modelar disjuncoes em termos lineares, a utilizacao da formulacao

BIG-M e muito utilizada (Tukkay & Grossmann, 1998). Esta formulacao consiste

na criacao de um parametro M (um numero suficientemente grande), de variaveis

contınuas e discretas interligadas atraves de restricoes lineares. A seguir e apresen-

tado um exemplo com a seguinte relacao logica, se a variavel binaria δ1 = 1 entao a

restricao x ≤ y e verdadeira, as variaveis x e y sao contınuas. Em termos de formu-

lacao BIG-M, a restricao anterior pode ser escrita conforme as inequacoes 3.3, sendo

ε um numero muito pequeno.

x− y ≤ M (1− δ1)

x− y ≥ (−M − ε) δ1 + ε(3.3)

Semelhante a formulacao BIG-M, com a vantagem de ser muito mais rapido

o processo de desenvolvimento de modelos proposto em Magatao (2005) e baseado

num conjunto de estruturas de alto nıvel para modelagem de problemas em PLIM.

Estas estruturas permitem a modelagem de expressoes SE-ENTAO e SE-ENTAO-

SENAO de modo intuitivo, facilitando e muito o processo de modelagem.

Representacao de condicoes logicas

Em Schrage (2000) e apresentada uma formulacao linear obtida a partir de

relacoes logicas entre variaveis. A tabela 3.1 ilustra esta formulacao, sendo A, B e

C variaveis binarias.

Outros algoritmos usados para resolver modelos em PLIM

Existem diferentes metodos utilizados para resolver modelos em PLIM, nor-

malmente o desempenho dos mesmos e associado a um grupo de problemas, a seguir

sao apresentados alguns destes algoritmos.


Tabela 3.1: Relacao logica entre variaveis.Expressao Logica Restricao Matematica

C ≤ AC = (A)and(B) C ≤ B

C ≥ A + B − 1C ≥ A

C = (A)or(B) C ≥ BC ≤ A + B

A → C A ≤ C

Planos de Corte (cutting planes): foi inicialmente proposto por Gomory

(1958). A cada passo do processo, novas restricoes (cortes) sao progressivamente

adicionadas, reduzindo a regiao viavel ate encontrar uma solucao otima binaria.

Decomposicao de Benders: propoe a decomposicao do problema original em

subproblemas. As variaveis sao divididas em complicadoras (inteiras) e nao complica-

doras (contınuas). Este metodo e baseado na solucao de uma sequencia de subproble-

mas de programacao linear com as variaveis complicadoras fixas e problemas mestres

que correspondem a projecoes no espaco das variaveis inteiras baseadas em represen-

tacoes duais do espaco contınuo. Como o problema mestre fornece limites inferiores

validos e os subproblemas de programacao linear, limites superiores, a sequencia de

subproblemas e resolvida ate que os limites sejam igualados (Benders, 1962).

Metodos pseudo-booleanos: tambem conhecidos como baseados em logica,

sao utilizados para representar restricoes disjuntivas ou tecnicas de inferencia para

expressar variaveis booleanas, sendo proposto inicialmente por Hammer (Williams,

1999). Entre os trabalhos nesta area, pode-se destacar o de Raman & Grossmann

(1994).

Modelagem PLIM

Joly (1999) apresenta uma revisao sobre varias ferramentas comerciais (solvers)

utilizadas para resolver modelos de otimizacao. Estes modelos, em particular os

baseados em PLIM, podem ser modelados em varias linguagens, entre as quais pode-

se destacar: OPL (ILOG, 2002a), XPRESS (XPRESS-MP, 2006), GAMS (Brooke

& Meeraus, 1982) e LINGO (Lindo, 2002).


3.2 Programacao Logica por Restricoes

A eficiencia dos metodos de resolucao de problemas que recorrem a restricoes

combinadas com a natureza declarativa da programacao em logica traz a tona a

programacao logica por restricoes (PLR). Esta tecnica tem se mostrado eficaz na

resolucao de problemas que sao intrataveis quando se recorrem a outras tecnicas,

como por exemplo PLIM. Entre esses problemas encontram-se diversas classes de

problemas de natureza combinatoria, tais como os problemas de scheduling, plane-

jamento e de atribuicao de recursos (Tavares, 2000).

De maneira sucinta e possıvel dizer que em PLR, a logica e usada para especi-

ficar um conjunto de possibilidades para a resolucao do problema, enquanto que as

restricoes sao usadas para minimizar o espaco de solucoes do problema.

Programacao Logica

A programacao logica e de natureza declarativa, porque indica os relaciona-

mentos logicos necessarios para resolver um problema. Um sistema baseado em logica

usa um conjunto de regras fornecidas pelo programador para responder as perguntas

que lhe sao enderecadas (Bartak, 2003). Em geral, a programacao logica pode ser

usada para comprovar uma dada afirmacao, ou para determinar qual o conjunto de

variaveis faz com que a uma determinada pergunta seja atribuıda o valor verdadeiro.

A natureza declarativa faz com que a programacao logica esteja proxima do

princıpio base de PR, em que se declara o que tem de ser satisfeito, mas nao como.

Alguns Conceitos Sobre Restricoes

As restricoes sao meios naturais de expressao para formalizar as dependencias

que estao na base dos mundos computacionais e fısicos, bem como nas abstracoes

matematicas. Na atividade humana, as restricoes constituem um ponto chave do

senso comum na conducao do raciocınio. Frases como: “eu posso estar la amanha das

quatro as seis da tarde”englobam uma restricao tıpica usada para o planejamento do

tempo. Dependendo do domınio do problema, pode-se encontrar outros exemplos de

3.2. Programacao Logica por Restricoes 29

restricoes: “a soma dos angulos internos de um triangulo e de 180 graus”;“a soma das

correntes que fluem num no e igual a zero” e “uma resistencia num circuito eletrico

obedece a lei de Ohm” (Hentenryck & Saraswat, 1996).

Uma restricao pode ser considerada como uma condicionante num espaco de

possibilidades. As restricoes matematicas especificam de uma forma clara e precisa

as relacoes entre diversas variaveis desconhecidas, cada uma tomando um dado valor

no domınio considerado. As restricoes estabelecem os valores possıveis que as varia-

veis podem assumir e representam alguma informacao parcial sobre as variaveis em

questao. Estas apresentam algumas propriedades (Hentenryck & Saraswat, 1996):

• As restricoes traduzem informacao parcial sobre um problema, uma vez que

uma restricao, por si so, nao determina o valor das variaveis do problema.

• As restricoes sao aditivas. Uma restricao r1 (por exemplo, X + Y ≥ Z ) pode

ser adicionada a uma outra restricao r2 ( X + Y ≤ Z ). A ordem segundo a

qual as restricoes sao impostas e irrelevante, o que esta em jogo e que no final,

seja atribuıdo o valor de verdadeiro a conjuncao dos termos que denotam as

restricoes.

• As restricoes raramente sao independentes, ou seja, geralmente compartilham

variaveis. A colocacao das restricoes r1 e r2 anteriores resulta na obtencao da

restricao X + Y = Z.

• As restricoes sao ainda nao direcionais: considerando a restricao X + Y = Z,

esta pode ser usada para determinar uma forma equivalente em X(X = Z−Y )

ou Y (Y = Z −X).

• As restricoes sao de natureza declarativa pelo fato de apenas denotarem as

relacoes que devem ser asseguradas entre variaveis, sem especificar um proce-

dimento computacional para estabelecer esse relacionamento.

Programacao por Restricoes

Os primeiros desenvolvimentos que conduziram a programacao por restricoes

(PR) podem ser encontrados no domınio da inteligencia artificial nos anos sessenta e


setenta (Bartak, 2003). Estes avancos focalizavam-se na representacao e manipulacao

explıcita de restricoes em sistemas computacionais. No entanto, apenas na decada

de 80 e 90 se desenvolveu uma crescente conscientizacao de que estas ideias podiam

fornecer a base para uma abordagem em programacao, modelagem e resolucao de

modelos de otimizacao (Bartak, 2003).

Atualmente nota-se o aparecimento de duas correntes para o tratamento da

PR: a satisfacao das restricoes e a resolucao de restricoes. Ambas compartilham da

mesma terminologia, mas possuem origens distintas.

• A satisfacao de restricoes trabalha com os problemas definidos sobre domınios

de valores discretos, do qual fazem parte os domınios finitos, sendo atualmente

a mais utilizada na maioria das aplicacoes industriais (Bartak, 2003).

• A resolucao de restricoes possui todas as propriedades base da PR. No entanto,

a maioria das restricoes e definida sobre domınios infinitos ou mais complexos.

Em vez dos metodos combinatorios para a satisfacao de restricoes, os algo-

ritmos de resolucao de restricoes sao baseados em tecnicas matematicas tais

como a diferenciacao, series de Taylor, metodo de Newton ou a programacao

linear (Bartak, 2003).

Domınios Computacionais da PR

As linguagens da PR tradicionais possuem o domınio baseado em constantes

e sımbolos funcionais. A linguagem de programacao Prolog e um exemplo destas

linguagens sendo, ao mesmo tempo, a mais utilizada (Tavares, 2000). A PLR amplia

a programacao logica de modo a oferecer um ou mais domınios interpretados de

restricoes. A PLR e parametrizada por um ou mais domınios de discurso, sobre os

quais esta a resolucao das restricoes. Muitas das linguagens de PLR baseiam-se em

diversos domınios, destacando-se as restricoes booleanas, sobre domınios finitos, so-

bre intervalos reais e os termos lineares. Em Tavares (2000) e apresentada a seguinte

classificacao das restricoes:

• Restricoes booleanas: sao tratadas por meta-interpretadores de restricoes espe-


cializados, podendo, no entanto, ser considerados como um caso particular das

restricoes associadas a domınios finitos para esse problema. Neste ultimo caso

as variaveis apenas podem tomar dois valores inteiros: 0 (falso) ou 1 (verda-

deiro). Muito uteis para programas de teste sobre circuitos logicos e verificacao

de propridades de sistemas complexos.

• Restricoes sobre domınios finitos (DF): sao utilizadas em muitas areas do co-

nhecimento. Para satisfacao destas restricoes usa-se uma combinacao de tec-

nicas para a preservacao da consistencia e propagacao de valores inteiros, aos

quais e dado o nome de domınio da variavel. Os valores do domınio que le-

vam a inconsistencias sao removidos do domınio das variaveis durante a fase

de propagacao, enquanto que pela busca se tenta instanciar cada variavel do

problema. Adequadas para problemas de scheduling, planejamento e muitos

outros.

• Restricoes sobre intervalos reais: sao equivalentes as consideradas para os DF,

so que aqui trabalha-se com valores reais em vez de valores inteiros. As tecnicas

de remocao de inconsistencias sao similares as tecnicas usadas para os domı-

nios finitos ou, entao, sao baseadas em tecnicas matematicas de diferenciacao

automatica ou as series de Taylor.

• Restricoes lineares: denotam restricoes construıdas a partir de variaveis cujo

domınio e dado pelo conjunto dos numeros reais. Para este tipo de restricao

sao implementados meta-interpretadores de restricoes que utilizam o algoritmo

SIMPLEX como ponto de partida.

Meta-Interpretadores de Restricoes

Segundo Tavares (2000), os meta-interpretadores de restricoes podem ser clas-

sificados em completos e incompletos:

• Meta-interpretadores completos: podem a cada passo computacional esperar

pela satisfacao de qualquer conjunto de restricoes o que e uma caracterıstica

muito desejavel. Porem, a satisfacao de um conjunto de restricoes para um


dado domınio pode ter um custo excessivo ou pode mesmo nao se verificar.

Esta caracterıstica faz com que os meta-interpretadores do tipo completo sejam

quase so usados em domınios bem especıficos.

• Meta-interpretador incompleto: podem ser definidos para os mais variados ti-

pos de domınios do conhecimento, podendo, no entanto, diferir na quantidade

de restricoes e no esforco computacional dispensado.

Problemas de Satisfacao de Restricoes

A resolucao de problemas em termos da PLR com DF faz uso de uma combi-

nacao de tecnicas de verificacao de consistencia e propagacao de restricoes, ao que

se associa um algoritmo de busca com retrocesso. Estas tecnicas de consistencia

e propagacao foram inicialmente desenvolvidas para a resolucao dos problemas de

satisfacao de restricoes (PSR). Um PSR caracteriza-se por possuir (Smith, 1995):

• um conjunto de variaveis X = x1, x2, x3, ..., xn;

• para cada variavel xi o domınio D = d1, d2, ..., dm de valores possıveis;

• um conjunto R = r1, r2, ...rn de restricoes que condicionam os valores que as

variaveis podem admitir simultaneamente.

Estas variaveis sao normalmente designadas por variaveis de domınio e sao

representadas pelo par < xi, di >, onde xi e o sımbolo que identifica a variavel i e di

e um conjunto finito designado por domınio i. Cada restricao e dada pela expressao

de um predicado r(x1, x2, ..., xk) em que os k argumentos denotam as variaveis de

domınio envolvidas na restricao.

Problema de Satisfacao de Restricoes com Domınios Finitos - PSR(DF)

Os meta-interpretadores de PSR(DF) pertencem aos meta-interpretadores de

restricoes incompletos e, deste modo, a enumeracao das restricoes nao e normalmente

suficiente para solucionar um problema. Um meta-interpretador de restricoes deste


tipo necessita ser combinado com procedimentos que atribuam as variaveis de decisao

valores admissıveis. A escolha de um bom procedimento deste tipo e fundamental

para um bom desempenho na resolucao de um problema.

Tecnicas de Consistencia

Uma tecnica para solucionar os PSR passa pela remocao dos valores dos domı-

nios das variaveis de decisao que levam a inconsistencia, ate se obter uma solucao.

Estes metodos, conhecidos por tecnicas de consistencia, sao determinısticos, ao con-

trario dos algoritmos que efetuam busca sistematica. As tecnicas de verificacao de

consistencia vao desde a simples consistencia do no, passando pela muito popular

consistencia de arco, ate a mais complexa e computacionalmente pesada consistencia

de caminho (Tsang, 1996).

A tecnica de verificacao de consistencia mais simples e conhecida como consis-

tencia de no. O no que representa a variavel x no grafo de restricoes e consistente se

para todos os valores do domınio de x, todas as restricoes unarias em x sao satisfeitas.

Se o domınio D da variavel x contem um valor a que nao satisfaz a restricao unaria

em x entao a instanciacao de x com a nao ocorrera. Consequentemente, as inconsis-

tencias de no sao eliminadas simplesmente pela remocao dos valores do domınio D

de cada variavel x que nao satisfacam as restricoes unarias em x.

A seguir e apresentado um exemplo de reducao de domınio pela tecnica de

consistencia do no. Considerando as variaveis X e Y , com os seguintes domınios

[2, 4, 5] e [2, 4, 6] respectivamente, conforme ilustrado na figura 3.2.

Inserindo a restricao X > Y , o espaco de busca fica conforme a figura 3.3, e

possıvel observar uma reducao do numero de nos de 13 para 6.

A consistencia de arco denota a tecnica de consistencia de maior utilizacao.

Um arco (xi, xj) e consistente se para todos os valores a do domınio de xi, existem

valores b no domınio de xj de forma que xi = a e xj = b sejam permitidos pela

restricao binaria entre xi e xj. A consistencia de arco e direcional, ou seja, o fato de o

arco (xi, xj) ser consistente nao significa que o arco (xj, xi) seja tambem consistente.


X[2,4,5]

Y[2,4,6]Y[2,4,6] Y[2,4,6]

[2,2] [2,4] [2,6] [4,2] [4,4] [4,6] [5,2] [5,4] [5,6]

2 54

2 4 6 2 4 6 642

Figura 3.2: Exemplo da tecnica de consistencia do no (sem a restricao).

X[4,5]

Y[2] Y[2,4]

[4,2] [5,2] [5,4]

54

2 42

Figura 3.3: Exemplo da tecnica de consistencia do no (com a restricao X > Y ).


Existem diversos algoritmos para o tratamento da consistencia de arco. Para ilustrar

a consistencia do arco a figura 3.4 apresenta um exemplo adaptado de Bartak (2002),

com as variaveis X, Y e Z com os domınios de [1, ..., 6], e as restricoes X < Y e

Z < X − 2.

X em [1,...,6]

Y em [1,...,6]

Z em [1,...,6]

X em [1,...,5]

Y em [2,...,6]

Z em [1,...,6]

X em [4, 5]

Y em [2,...,6]

Z em [1, 2]

X em [4, 5]

Y em [5, 6]

Z em [1, 2]

X<Y Z<X-2 X<Y

Figura 3.4: Exemplo da tecnica de consistencia do arco.

3.2.1 Otimizacao com PLR

Considerando-se que os meta-interpretadores de PLR sao incompletos na re-

solucao da generalidade dos problemas, o mecanismo de propagacao por si so nao

e capaz de solucionar a grande maioria dos problemas. Muitos problemas reais sao

caracterizados por possuırem mais do que uma solucao, sendo ate frequente haver

muitas solucoes. Nestas situacoes, pretende-se efetuar a escolha da melhor solucao.

Esta solucao e aquela que satisfaz todas as restricoes e que minimiza uma dada

funcao de custo. No PSR(DF) o algoritmo de otimizacao mais amplamente utilizado

e o BB. Este algoritmo se encaixa bem na resolucao de restricoes devido a uma

abordagem incremental e a maior parte dos meta-interpretadores ja possuem uma

implementacao deste algoritmo. Estas implementacoes, nas formas mais simples,

trabalham em conjunto com a estrategia de busca, colocando sempre uma restricao

adicional que impoe a busca de uma nova solucao com um custo melhor do que o

custo da melhor solucao ate entao encontrada.

Para ilustrar a resolucao de um problema de otimizacao modelado em PSR(DF)

a seguir e apresentado um exemplo adaptado de Tsang (1996), para um PSR(DF),

sendo que os dados do mesmo estao na tabela 3.2, sendo cinco variaveis (x1, x2, x3, x4

e x5) que tem domınios numericos especıficos. A funcao objetivo e maximizar a soma

dos valores assumidos pelas variaveis.


Tabela 3.2: Dados do problema.Variaveis Domınio Restricoes

x1 [4, 5]x2 [3, 5] x2 6= x1

x3 [3, 5] x3 = x2

x4 [2, 3] x4 < x3

x5 [1, 3] x5 6= x4

A figura 3.5 mostra o espaco de busca explorado por um algoritmo backtracking

simples. Cada no da arvore representa o valor da soma das variaveis instanciadas e

cada aresta representa a atribuicao de um valor a uma variavel. A busca pelo valor

das variaveis e realizada na seguinte ordem: x1, x2, x3, x4 e x5.

0

5 4

8 79

11 1014

13 1217 16

17 151718 1914 13

n5 4

5 3 5 3

53 5 3 5 3

3 2 3 2 3 2

31

3 1 3 1 3 1

x1

x2( x1)

x3(=x2)

x4(<x3)

x5( x4)

restrição violada

soma dos valores

Figura 3.5: Espaco de busca para o algoritmo backtracking simples.

A Figura 3.6 mostra o mesmo problema, sendo que o espaco de busca ex-

plorado utiliza o algoritmo BB. Cabe destacar que o algoritmo BB tem um melhor

desempenho quando um limite mais justo e encontrado inicialmente. Com o objetivo

de ilustrar o efeito de BB, supoe-se que os nos que representam a atribuicao de valo-

res maiores sao explorados primeiro. O valor da funcao objetivo (FO) em cada no e

calculado como o valor ja instanciado da variavel mais a soma dos valores maximos

para as variaveis ainda nao instanciadas. Por exemplo, a FO de (< x1, 4 > < x2, 5 >)


e 4 + 5 (os valores ja atribuıdos) mais 5 + 3 + 3 (os valores maximos que podem ser

atribuıdos a x3, x4 e x5), totalizando 20. Quando o no (< x1, 5 > < x2, 3 > < x3, 3 >

< x4, 2 > < x5, 3 >) e alcancado, o limite e atualizado (5 + 3 + 3 + 2 + 3 = 16).

Este limite nao tem efeito na metade esquerda da arvore da busca neste exemplo.

Quando o no (< x1, 4 > < x2, 5 > < x3, 5 > < x4, 3 > < x5, 1 >) e alcancado, o

limite fica atualizado em 18. Quando o no (< x1, 4 > < x2, 5 > < x3, 5 > < x4, 2 >

< x5, 3 >) e alcancado, o limite fica atualizado em 19. Quando o no (< x1, 4 >

< x2, 3 >) e examinado, a FO (que esta em 18) e menor que o limite atual (que

e 19). Consequentemente, a ramificacao sob o no (< x1, 4 > < x2, 3 >) e podada.

Apos este corte, (< x1, 4 > < x2, 5 > < x3, 5 > < x4, 2 > < x5, 3 >) encontra-se

a solucao otima. Na figura 3.6, 21 nos foram explorados, ao contrario dos 27 nos

explorados da figura 3.5.

0

5 4

8 79

11 14

13 17 16

16 1718 1914

n5 4

5 3 5 3

53 5 3

3 2 32

31

3 1 3 1

x1

x2( x1)

x3(=x2)

x4(<x3)

x5( x4)

restrição violada

soma dos valoreslimite = 16

limite = 19

limite = 18

h=4+16=20

corte, comoh=7+11=18<limite

h=16+3=19h=17+3=20

h=9+11=20

h=14+6=20

Figura 3.6: Espaco de busca para o algoritmo BB.

A Figura 3.7 mostra a importancia de se encontrar um limite mais justo

em um estagio inicial da busca. Nesta figura supoe-se que < x1, 4 > e explorado

antes de < x1, 5 >, todos os demais nos seguem o mesmo procedimento analisado

anteriormente. A solucao otima e encontrada depois que 10 nos sao explorados. O

limite 19 e usado para podar o ramo (< x1, 4 > < x2, 3 >) (cuja FO e 18) e (< x1, 5 >


< x2, 3 > < x3, 3 >) (cuja FO e 18). Note que se uma unica solucao for requerida, o

ramo (< x1, 5 > < x2, 3 >) e podado porque a FO de (< x1, 5 > < x2, 3 >) e igual

ao limite encontrado. Nesta caso somente 17 nos foram explorados.

0

4 5

7 89

1114

17 16

1718 19

n4 5

5 3 5 3

3 1

x1

x2( x1)

x3(=x2)

x4(<x3)

x5( x4)

restrição violada

soma dos valoreslimite = 19

limite = 19

h=5+16=21


h=16+3=19

3 1

limite= 18

h=8+11=19=limite


5 35 3

h=4+16=20

3 2

Figura 3.7: Espaco de busca para o algoritmo BB com limite justo.

PLR na Resolucao dos Problemas de Scheduling

A area de aplicacao que provavelmente tem encontrado um maior sucesso para

a PLR(DF) tem sido os problemas de scheduling, onde as restricoes conseguem

expressar de forma natural as limitacoes dos problemas reais (Tavares, 2000).

3.3 Metodos Heurısticos

Metodos heurısticos sao metodos aproximados, que utilizam caracterısticas es-

pecıficas do problema atraves de procedimentos iterativos. No caso do problema da

mochila, que consiste em preencher uma mochila com diferentes objetos de diferentes

pesos e valores, com o objetivo de maximizar o valor total transportado, a decisao

e escolher prioritariamente o objeto de maior valor especıfico (relacao entre valor e

3.4. Metodos Hıbridos 39

peso), ate que nao haja mais espaco dentro da mochila (Nemhauser & Wolsey, 1988).

Geralmente os metodos heurısticos podem ser considerados como uma tentativa de

formalizacao das metodologias empregadas por profissionais experientes em deter-

minadas atividades. A principal caracterıstica dos metodos heurısticos e a obtencao

de uma solucao viavel com baixo esforco computacional. Porem, nao existe garantia

de que a solucao otima sera encontrada.

3.4 Metodos Hıbridos

Metodos hıbridos de resolucao de problemas de otimizacao sao abordagens

que incorporam caracterısticas de mais de um metodo de resolucao. O principal

argumento utilizado para se construir um metodo hıbrido e capturar as boas carac-

terısticas dos metodos originais.

3.4.1 PLIM X PLR

A metodologia para combinar PLIM e PLR vem sendo conduzida para reali-

zar a integracao entre os processos de busca das duas abordagens. Existem varias

tentativas de integrar estas abordagens, esta integracao pode interferir ou nao na

estrutura dos algoritmos (Focacci, 2000). A maioria das tentativas de integrar PLIM

e PLR usa propagacao de restricoes junto com a PL em uma unica arvore da busca

para obter limites de modo a reduzir o domınio das variaveis (Rodosek et al., 1999).

Nestas abordagens um modelo completo de PLR e um modelo parcial em PLIM sao

requeridos. Este fato deve-se pela facilidade de modelagem das restricoes em PLR,

sendo que nem todas as restricoes sao facilmente implementadas em PLIM. Estas

abordagens sao redundantes porque em cada no sao resolvidos um PSR e um PL

(Jain & Grossmann, 2001). Para alguns problemas isto se justifica porque estes sao

intrataveis por qualquer um dos dois metodos separadamente. Rodosek et al. (1999)

apresentaram uma aproximacao sistematica para transformar um modelo de PLR

em um modelo correspondente de PLIM. Entretanto, a traducao automatica de um

modelo de PLR em um modelo de PLIM pode resultar em um modelo pobre, em fun-

cao do grande numero de restricoes utilizando BIG-M (relaxacao linear pobre). Se a


traducao automatica nao for usada, deve-se modelar o problema em ambas as abor-

dagens. Bockmayr & Kasper (1998) fizeram uma analise interessante das abordagens

PLIM e PLR numa estrutura unificada. Eles dividiram as restricoes para PLIM e

PLR em duas categorias diferentes: primitivas e nao-primitivas. As restricoes primi-

tivas sao aquelas em que existe um algoritmo de solucao com tempo polinomial, e

as restricoes nao-primitivas sao aquelas que a solucao nao e com tempo polinomial.

Segundo Bockmayr & Kasper (1998) um aspecto interessante sobre esta classifica-

cao e que algumas das restricoes que sao primitivas em PLR sao nao-primitivas em

PLIM e vice-versa.

Outro modo de integracao de PLIM-PLR consiste em formular o problema em

ambos os sistemas e as variaveis de decisao sao interconectadas atraves de modulos

de comunicacao entre os dois solvers. Durante o processo de resolucao, cada software

desenvolve a propria arvore de busca e o modulo de comunicacao gerencia a troca

de mensagens de forma a direcionar o processo de busca (ILOG, 2003).

Existem alguns pacotes comerciais que trabalham com a integracao das tecni-

cas de PIM-PLR. Uma empresa deste segmento e a ILOG (ILOG, 2003). Para tornar

a modelagem do problema mais proxima do usuario a ILOG desenvolveu a linguagem

OPL Studio (Optimization Programming Language). Com a linguagem OPL os pro-

blemas podem ser representados intuitivamente, permitindo a comunicacao entre um

solver de PLR com um solver de PIM. Esta linguagem nao disponibiliza a possibili-

dade do usuario interferir no processo de busca. E como se fosse uma abordagem do

tipo caixa-preta, em que ha possibilidade de se formular o problema atraves de PLR

e PIM e internamente ocorre uma interacao entre as duas abordagens de resolucao.

Na linguagem OPL, a formulacao PIM e utilizada para gerar solucoes relaxadas do

problema e auxiliar o processo de busca de PLR. Caso o usuario queira interferir no

processo de busca e necessario uma programacao de mais baixo nıvel, diretamente

nos solvers de PIM (ILOG-CPLEX) e no de PLR (ILOG-SOLVER), componentes

do ILOG Optimization Suite.

A integracao entre PLR e PIM configura uma tendencia promissora para a

resolucao de problemas combinatorios. A flexibilidade e facilidade de modelagem da

PLR e agregada ao formalismo e precisao da PIM, dando origem a uma ferramenta

3.4. Metodos Hıbridos 41

de modelagem hıbrida.

3.4.2 Algoritmos Geneticos X PLR

As pesquisas no sentido de integrar os algoritmos geneticos (AG) com a PLR

tem como objetivo essencial a otimizacao de problemas combinatorios, que envolvem

um grande numero de restricoes com meta-interpretadores de PLR pelo uso de AG

em alternativa ao algoritmo BB tradicional.

Em geral, uma aplicacao escrita segundo o paradigma da PLR e constituıda

por tres etapas:

• a identificacao das variaveis do problema e o respectivo domınio;

• a colocacao das restricoes envolvendo algumas das variaveis do problema;

• a enumeracao das solucoes ou a busca da melhor solucao segundo uma dada

funcao objetivo.

Esta ultima etapa usa normalmente um algoritmo BB dentro de um meta-

interpretador de PLR. E precisamente nesta etapa de otimizacao que se pretende

usar um AG em vez de um algoritmo BB padrao. Em termos de arquitetura, a

metodologia possui algumas caracterısticas semelhantes ao metodo de hibridizacao

proposto por Cotta et al. (1995) em que um algoritmo BB trabalha para um AG na

resolucao de problemas do caixeiro viajante. Neste metodo de hibridizacao, os ope-

radores geneticos desenvolvidos implementam uma forma restrita de um algoritmo

BB.

Segundo Tavares (2000), a integracao entre AG e PLR tem por objetivo solu-

cionar todos os tipos de problemas de otimizacao baseados em restricoes pelo uso de

meta-interpretadores. Esta metodologia impoe que os operadores geneticos do AG

devem ser implementados segundo o paradigma da PLR, embora nao defina nenhum

metodo em particular para os implementar. O desenvolvimento de uma aplicacao

para solucionar problemas de otimizacao que segue esta metodologia requer que se

efetue a escolha da representacao mais adequada das solucoes e o desenvolvimento,


para essa representacao, de metodos baseados no paradigma da PLR que implemen-

tem os operadores geneticos.

3.5 Sistemas Fuzzy

Na modelagem de problemas de scheduling, em particular das refinarias de pe-

troleo, uma das primeiras dificuldades que aparece e traduzir todas as consideracoes

feitas pelo especialista em um modelo que retrate os detalhes do problema. Alem

disso, algumas destas consideracoes tratam de aspectos imprecisos ou aproximados,

como por exemplo: evitar que uma tarefa inicie muito proxima da outra. Para tra-

duzir, em termos matematicos, a informacao imprecisa, expressa por um conjunto

de regras linguısticas, pode-se utilizar um sistema de inferencia fuzzy. Se um ope-

rador humano for capaz de expressar o conhecimento como regras na forma SE

ENTAO, um algoritmo fuzzy passıvel de ser implementado em computador pode

ser construıdo. A seguir sao descritos alguns conceitos, definicoes e propriedades dos

sistemas fuzzy que sao utilizados nesta tese.

3.5.1 Tratamento de Incertezas

A incerteza associada aos parametros que compoem os problemas de otimi-

zacao, em particular os problemas de scheduling, dificulta muito a representacao

matematica do problema a ser modelado. Estes parametros tratam de variacoes na

demanda, disponibilidade de produtos, precos, disponibilidade de equipamentos e

principalmente da mao-de-obra na execucao das tarefas. A falta de precisao dos mo-

delos os tornam distantes da realidade, e segundo Pinto (2000) este e um dos fatores

que dificulta a implantacao de modelos de scheduling em ambientes industriais.

Segundo Sahinidis (2004) a incerteza dos parametros num modelo de otimiza-

cao pode ser modelada em programacao estocastica e nao estocastica, a diferenca

entre elas e como a incerteza sera representada. No caso de programacao estocastica,

a incerteza e modelada como funcoes discretas ou contınuas de probabilidade. No

caso de programacao fuzzy as incertezas sao modeladas com numeros fuzzy presen-

3.5. Sistemas Fuzzy 43

tes nas restricoes ou coeficientes da funcao objetivo do modelo de otimizacao. No

caso da incerteza estar presente nos coeficientes da funcao objetivo, eles podem ser

modelados dentro do modelo de otimizacao ou calculados separadamente e depois

inseridos no modelo de otimizacao.

Varios exemplos podem ser encontrados na literatura para modelagem de in-

certezas atraves de sistemas fuzzy, mais especificamente para problemas de planeja-

mento em refinarias de petroleo (Ravi et al., 1998), e para o gerenciamento de oleo

de cru (Escudero et al., 1999), ou ainda em Felizari (2004) que considera atrasos no

tempo de execucao das operacoes de transferencia e estocagem de uma refinaria.

Em Stebel et al. (2006) e apresentada uma nova aplicacao para sistemas fuzzy

na modelagem da mao de obra para o PSRE (ver capıtulo 5). Este modelo serve

para determinar os custos envolvidos na execucao das tarefas. Estes custos sao pos-

teriormente inseridos na funcao objetivo de um modelo em PLIM.

3.5.2 Conceitos e Definicoes

Conjuntos Fuzzy

Na teoria dos conjuntos fuzzy, a pertinencia de um elemento a um conjunto

determina com que grau um elemento x pertence a um conjunto A. Deste modo, um

conjunto fuzzy A em X e um conjunto de pares ordenados, conforme a expressao

3.4, sendo µa(x) e a funcao de pertinencia de x em A (Wang, 1997).

A = (x, µa(x)), x ∈ X (3.4)

Variavel Linguıstica

Uma definicao formal de variavel linguıstica e caracterizada por (X, T, U, M)

(Wang, 1997), onde:

• X e o nome da variavel linguıstica;


• T e o conjunto de valores linguısticos que a variavel X pode asssumir;

• U e o universo de discurso da variavel X, ou seja, o seu domınio;

• M e a regra semantica que associa cada valor linguıstico em T com um conjunto

fuzzy em U .

Uma variavel linguıstica pode ser descrita como uma variavel cujos valores

sao palavras ou sentencas ao inves de numeros, ou seja, elementos qualitativos ao

inves de quantitativos (Pedrycz & Gomide, 1998). A funcao da variavel linguıstica e

fornecer uma maneira de caracterizar fenomenos mal definidos ou aproximados. Por

exemplo, a temperatura de um tanque de petroleo poderia ser uma variavel fuzzy

assumindo os valores alta, media e baixa, conforme ilustrado na figura 3.8. Na tabela

3.3 sao dados alguns exemplos de variaveis linguısticas com os respectivos valores.

0

1

200100 300 temp. (0C)

µ

baixa média alta

Figura 3.8: Variavel linguıstica de temperatura.

Tabela 3.3: Variavel linguıstica.variavel linguıstica predicado

temperatura baixa, media, altanıvel muito baixo, baixo, normal, alto, muito alto

pressao baixa, media, altavelocidade lenta, media, rapida

tempo curto, medio, longo


Em geral, o valor de uma variavel linguıstica e um termo composto, resultado

da concatenacao de outros termos, sendo que estes termos podem ser classificados

em tres grupos (Wang, 1997):

• Termos primarios: termos basicos associados a conjuntos especıficos em X:

alto, baixo, perto, longe, forte e fraco.

• Conectivos e Negacao: E (∧), OU (∨), NAO (¬) , IMPLICA (→) e EQUIVA-

LENCIA (↔).

• Modificadores: muito, pouco, mais ou menos, levemente.

A gramatica define como os termos primarios serao associados aos modifica-

dores e/ou conectivos.

Regra Fuzzy

A regra fuzzy e uma unidade capaz de capturar algum conhecimento especıfico,

e um conjunto de regras e capaz de descrever um sistema fuzzy em varias possibili-

dades. Cada regra fuzzy, da mesma forma que uma afirmacao classica, e composta

por uma parte antecedente (SE) e uma parte consequente (ENTAO), resultando

em uma estrutura do tipo (3.5) (Babuska & Verbruggen, 1996):

R : SE A ENTAO B

= A → B

= A x B

(3.5)

A relacao fuzzy A x B denota, neste caso, a implicacao A → B no produto

cartesiano dos dois universos X x Y = (x, y), x ∈ X, y ∈ Y .

Um sistema fuzzy e uma combinacao de todas as relacoes fuzzy provenientes

de diversas regras, sendo que esta combinacao envolve um operador de agregacao de


regras (3.6) (Pedrycz & Gomide, 1998):

R : agreg(R1, R2, ..., Ri, ..., Rn) (3.6)

Regra de Inferencia Composicional

Em Wang (1997) e apresentada uma definicao da regra de inferencia composi-

cional sugerida por Zadeh (regras 3.7):

Dadas duas relacoes fuzzy :

R1 : SE A ENTAO B

R2 : SE B ENTAO C(3.7)

Estas regras podem ser compostas de forma a resultar em (regra 3.8):

R12 : SE A ENTAO C (3.8)

A composicao R12 = R1 ◦ R2 pode ser definida tanto por uma regra do tipo

max−min (regra 3.9):

µR12(x, z) = ∨y(µR1(x, y) ∧ µR2(y, z)) (3.9)

Quanto por uma do tipo max− produto (regra 3.10):

µR12(x, z) = ∨y(µR1(x, y) · µR2(y, z)) (3.10)

Quando conjuntos fuzzy sao empregados, as operacoes (regras 3.9 e 3.10) sao

equivalentes ao produto interno de duas matrizes, com a multiplicacao e a soma


substituıdas pelas operacoes min (primeiro caso) e max, respectivamente. Para as

funcoes de implicacao envolvendo somente operadores max e min, emprega-se a

regra composicional max − min. No caso de implicacoes que envolvam operadores

aritmeticos, pode-se usar a regra max− produto (Pedrycz & Gomide, 1998).

Sistema de Inferencia Fuzzy

A base de regras junto com a base de dados formam a base de conhecimento de

um sistema fuzzy. O mapeamento das entradas e saıdas e realizado por uma maquina

de inferencia, que a partir de um conjunto fuzzy de entradas deriva um conjunto fuzzy

de saıdas atraves da base de regras fuzzy (Babuska & Verbruggen, 1996). A figura

3.9 ilustra um sistema fuzzy generico adaptado de Babuska & Verbruggen (1996),

utilizado para fuzzificacao e defuzzificacao.

Filtro

Fuzzificador Defuzzificador

Filtrobase de regras

base de dados

máquina de inferência fuzzy

conhecimento

X

dadosnuméricos

dadosnuméricos

Y

conjuntosfuzzy

conjuntosfuzzy

entrada saída

Figura 3.9: Sistema fuzzy generico.

Metodo de defuzzificacao

A defuzzificacao e um procedimento que permite interpretar o mapeamento das

entradas/saıdas de um modelo linguıstico fuzzy de forma quantitativa. A defuzzifica-

cao fornece um valor numerico que captura o significado essencial desse mapeamento.

A defuzzificacao pode ser feita por varios metodos, segundo Wang (1997) os mais

utilizados sao:


• Criterio do maximo: escolhe o ponto onde a funcao inferida tem o maximo.

• Media dos maximos: a saıda determinıstica denominada µMOM e obtida atra-

ves da media entre os elementos extremos no universo que correspondem aos

maiores valores da funcao de pertinencia.

• Centro de Gravidade: o centro de gravidade a saıda µCOG e o valor do universo

que divide a area sob a curva da funcao de pertinencia em duas partes iguais.


Neste capıtulo foram apresentados os principais metodos utilizados para re-

solver os PSRP, foi dada uma enfase para os metodos utilizados nesta tese. Em

especial, a programacao logica por restricoes foi mais detalhada por existir pouca

literatura disponıvel sobre este assunto em portugues. Por fim, foram apresentados

alguns conceitos sobre sistemas fuzzy que sao utilizados nesta tese.

Capıtulo 4

Modelagem Matematica para umPSRE

A representacao do tempo e a estrutura do modelo sao os dois principais as-

pectos que devem ser observados quando se utiliza PLIM para resolver problemas

de scheduling. A principal restricao na representacao discreta do tempo e na geracao

de um numero muito elevado de variaveis binarias. Na representacao contınua do

tempo o numero de variaveis binarias e reduzido significativamente quando compa-

rado com a representacao discreta. Uma abordagem PLIM baseada na representacao

contınua do tempo e proposta nesta tese para um problema de scheduling dos re-

cursos de estocagem de uma refinaria de petroleo. Este trabalho trata o scheduling

sob o ponto de vista da estocagem, ou seja, esta baseado nos diferentes estados que

os tanques podem assumir durante o horizonte de scheduling. Sao eles: pronto para

receber, recebendo, pronto para enviar e enviando. Cada tanque esta sempre asso-

ciado com um destes estados. Esta abordagem possui uma estrutura geral que pode

ser aplicada em problemas de scheduling dos recursos de estocagem em refinarias de

petroleo.

50 Capıtulo 4. Modelagem Matematica para um PSRE

4.1 Descricao do Problema

Uma refinaria de petroleo tıpica tem aproximadamente cem tanques1, sendo

estes agrupados em areas, de acordo com a finalidade. O conjunto destas areas,

dentro da refinaria, que gerencia todos os tanques e chamado de transferencia e

estocagem (TE). As areas sao normalmente divididas em:

• Area de cru: responsavel por receber o petroleo do terminal, armazena-lo e

prepara-lo para ser processado na unidade de processo correspondente.

• Area intermediaria: responsavel por receber alguns produtos intermediarios2,

armazena-los e prepara-los para serem enviados para as unidades de processo

ou para area final.

• Area final: responsavel por receber produtos finais, armazena-los e prepara-los

para serem enviados para o mercado consumidor.

• Area de GLP (gas liquefeito de petroleo): responsavel por receber produtos

finais, armazena-los e prepara-los para serem enviados para o mercado consu-

midor.

• Area de asfalto: responsavel por receber produtos intermediarios3 e finais,

armazena-los e prepara-los para serem enviados para o mercado consumidor.

As inter-relacoes da TE podem ser observadas na figura 4.1. A TE pode

enviar/receber produtos das unidades de processo, dos terminais e/ou de poliduto(s),

interligando a refinaria a outras localidades.

Um problema encontrado nas refinarias de petroleo diz respeito ao scheduling

dos tanques, caracterizando-se como um problema de scheduling dos mais difıceis,

dado o carater combinatorio (Stebel, 2001). Neste trabalho, o cenario base de es-

tudo envolve a TE de diferentes derivados de petroleo. Para a operacao do sistema

1Os tanques podem ser de teto fixo ou flutuante, dependendo do tipo de produto que e arma-zenado no mesmo.

2Produtos que irao passar por mais um processo, antes de serem enviados ao mercado consu-midor, por exemplo: gasoleo, resıduo de vacuo e naftas.

3Estes produtos serao misturados para obter um produto final.

4.1. Descricao do Problema 51

Estação de carregamentorodoviário (ECR)

Área de asfalto

Área de GLP

Área final

Área intermediária

Área de cru

DestilaçãoAtmosférica

Utilidades

Desasfaltação

CraqueamentoCatalítico

Uni

dade

s de

Pro

cess

o

Transferênciae Estocagem (TE)

Terminalpara

recebimentode cru

Terminal

Clienteslocais

Terminal

Refinaria

Figura 4.1: Inter-relacoes da TE.


de estocagem (armazenamento), o recebimento e o envio de produto dos tanques

implicam em varias decisoes a serem tomadas pelo programador (especialista) da

TE. Do ponto de vista da otimizacao da planta, a tomada de decisao por parte do

programador e dificultada pela complexidade e dinamica do sistema (Stebel, 2001),

conforme a figura 4.2.

PROGRAMADOR

Restriçõesoperacionais

Espaçodisponível nos

tanques

Demanda deenvio para

clientes locais

Volume inicialde cada produto

Vazões derecebimentoe de envio

Cota derecebimentode poliduto

Demanda deenvio para

poliduto

Acerto daespecificaçãodos produtos

Figura 4.2: Tomada de decisao.

Algumas consideracoes/decisoes a serem feitas por parte do progra-

mador sao:

• verificar o volume de produto em cada tanque;

• verificar o espaco disponıvel nos tanques para receber produto;

• considerar as restricoes operacionais, como por exemplo volumes mınimos e

maximos dos tanques;

• determinar as cotas de recebimento de produto das unidades de processo e de

poliduto;

• determinar as cotas de envio para clientes locais e para poliduto;

• considerar as vazoes mınimas e maximas de envio e de recebimento.

4.2. Representacao da Estrutura do Modelo 53

4.2 Representacao da Estrutura do Modelo

E possıvel observar que o processo de tomada de decisao operacional em uma

refinaria de petroleo e uma tarefa muito complexa. Atualmente o tratamento do pro-

blema e baseado em experiencia profissional com a utilizacao de calculos manuais.

Deste modo, torna-se justificavel a elaboracao de modelos que auxiliem a tomada

de decisao operacional para o PSRE. Existem alguns modelos que foram desenvol-

vidos para satisfazer as caracterısticas dos problemas de scheduling em refinarias de

petroleo, conforme apresentado na secao 2.5. Este mesmo problema ja foi tratado

por Stebel (2001) com uma abordagem PLIM, com representacao discreta do tempo.

Assim como nos demais trabalhos, e destacada a explosao do tempo computacional

como um desafio a ser superado. Um dos principais pontos a ser explorado na ques-

tao do tempo computacional e relacionado com a diferenca de integralidade (DI)

(ver expressao 3.2, pagina 25), que e a diferenca existente entre a funcao objetivo

da solucao inteira otima e da solucao relaxada. A formulacao PLIM com DI menor

normalmente requer menos iteracoes no algoritmo BB (Wolsey, 1998). Deste modo

qualquer modelo PLIM deve levar a DI em consideracao.

Neste trabalho e proposta uma abordagem que procura diminuir esta dife-

renca, atraves da representacao dos estados possıveis dos recursos (tanques) e do

ciclo operacional envolvido na TE, conforme pode ser observado na figura 4.3. A re-

presentacao dos estados possıveis dos tanques, atraves de variaveis binarias, permite

determinar as operacoes de envio e recebimento de diferentes tanques. A quanti-

dade de produto a ser manipulado, em cada operacao de envio ou de recebimento, e

igual ao volume do tanque, com os respectivos tempos de inıcio e termino. A figura

4.3 ilustra o ciclo operacional, a partir de um instante de tempo inicial (t = 1) no

qual um tanque esta recebendo (RR = 1). O tanque fica neste estado ate encher

completamente. Em seguida o tanque pode assumir dois estados: liberado para en-

viar (FD = 1), enquanto o tanque permanecer parado cheio; ou tanque enviando

(RD = 1), se o tanque iniciar o envio de produto para algum destino. Caso o tanque

atinja o estado de liberado para o envio (FD = 1), ele fica neste estado enquanto o

tanque permanecer parado. Quando o tanque estiver enviando (RD = 1), deve faze-


lo ate o nıvel mınimo operacional4 do tanque. Apos esse perıodo, o tanque podera

assumir dois estados: liberado para receber (FR = 1), enquanto o tanque perma-

necer parado e vazio; ou tanque recebendo (RR = 1), se apos o tanque iniciar o

recebimento.

RD FRRR

FD

t=1

RR – tanque recebendoFD – tanque liberado para enviarRD – tanque enviandoFR – tanque liberado para receber

Figura 4.3: Grafo ilustrativo do processo.

Consideracoes de modelagem:

• uma consideracao razoavel e que os tanques sao dedicados, ou seja, eles arma-

zenam sempre os mesmos produtos. Deste modo, o scheduling sera concebido

por produto.

• os volumes estocados nos tanques, bem como as demandas de envio e recebi-

mento sao conhecidos no inıcio do scheduling.

• os tempos de set-up dos equipamentos e de transicao entre as tarefas sao

desprezados.

• o custo da energia eletrica sofre variacoes em funcao da existencia de picos de

consumo, chamado de tarifacao horossazonal.

4O nıvel mınimo operacional, conhecido como lastro varia em funcao do tipo e tamanho dotanque, sendo normalmente superior a 1 metro.

4.3. Modelo Matematico 55

4.3 Modelo Matematico

A tecnica de otimizacao utilizada para o desenvolvimento do modelo mate-

matico foi PLIM com tempo contınuo. Uma tendencia nos trabalhos atuais e o

desenvolvimento de modelos, com formulacoes contınuas do tempo, que explorem as

caracterısticas peculiares de cada problema (Schilling & Pantelides, 1996; Pinto &

Grossmann, 1996; Ierapetritou & Floudas, 1998a; Ierapetritou & Floudas, 1998b; Ie-

rapetritou & Floudas, 1999; Mendez & Cerda, 2002). As decisoes sao modeladas por

variaveis binarias e contınuas, interligadas atraves de restricoes lineares. O modelo

proposto tem como objetivo a minimizacao dos custos operacionais, sendo represen-

tados pelos custos de envio e recebimento. Estes custos sao avaliados considerando-se

a existencia de uma tarifacao de energia eletrica em funcao do horario (ver pagina

62). Deste modo os diferentes custos exercerao uma influencia distinta sobre o mo-

delo (Stebel, 2001). E tambem avaliada a funcao objetivo que trata a maximizacao

do lucro do sistema (lucro representado pelo volume do tanque para cada destino).

As restricoes sao oriundas de procedimentos operacionais, de restricoes fısicas da

planta e de demanda.

Baseado nas consideracoes de operacao do sistema segue-se o equacionamento

da funcao objetivo, das restricoes operacionais e de demanda do sistema, de acordo

com a nomenclatura das variaveis utilizadas no modelo.

Nomenclatura

Indices

r recursoi estadon eventoh horario

Conjuntos

R conjunto de recursos, no caso tanquesIa conjunto de estados de recebimento (origem)Ib conjunto de estados de envio (destino)Ic conjunto de estados paradosI Ia

⋃Ib

⋃Ic


N conjunto de eventosHP conjunto formado pelos horarios de ponta

Variaveis

RRr,i,n variavel binaria que trata o recebimento no tanque r doestado i ∈ Ia no evento n

RDr,i,n variavel binaria que trata o envio do tanque r para oestado i ∈ Ib no evento n

FRr,n variavel binaria que indica se o tanque r esta liberadopara recebimento no evento n

FDr,n variavel binaria que indica se o tanque r esta liberadopara envio no evento n

V Ar,n,r′,n′,i variavel binaria utilizada para evitar a sobreposicaode eventos distintos (n 6= n′) em recursos distintos (r 6= r′)para o mesmo estado i

TFr,i,n tempo final de operacao do recurso r do estado i no evento n (h)TSr,i,n tempo de inıcio de operacao do recurso r do estado i

no evento n (h)Y 1i,n variavel auxiliar do estado i ∈ Ia no evento nY 2i,n variavel auxiliar do estado i ∈ Ib no evento nVr,i,n,h variavel binaria utilizada para indicar se o TFr,i,n e

menor ou igual ao TFHPh

Wr,i,n,h variavel binaria utilizada para indicar se o TSr,i,n emenor ou igual ao TSHPh

Ar,i,n,h variavel que assume valor binarioCr,i,n,h variavel que assume valor binarioDr,i,n,h variavel que assume valor binarioEr,i,n,h variavel que assume valor binarioXr,i,n,h variavel contınua que armazena o tempo da operacao dentro do

horario de ponta (h)

Parametros

nr numero de recursosnn numero de eventosno numero de estados de recebimentond numero de estados de envioni numero de total de estados ni = no + nd + 1H horizonte de scheduling (h)FMAXi vazao maxima do estado i ∈ (Ia ∪ Ib) (m3/h)TSHPh tempo de inıcio do horario de ponta h (h)TFHPh tempo final do horario de ponta h (h)ϕmin taxa adimensional de mınima vazaoϕmax taxa adimensional de maxima vazaoM um numero positivo suficientemente grande


eps um numero positivo suficientemente pequenoV Ur volume util dos tanques (m3)DRi demanda total de recebimento por estado i ∈ Ia (m3)DDi demanda total de envio por estado i ∈ Ib (m3)CN custo de bombeamento normalizado ($/h)CHPh custo de bombeamento em funcao do horario de

ponta h ($/h)lucroi lucro obtido em relacao ao estado de envio i ∈ Ib ($/m3)

Parametros calculados no pre-processamento

nhp numero de intervalos de horario de ponta (HP)TRr,i tempo de referencia5 para o recebimento no recurso r

do estado i ∈ Ia (h)TDr,i tempo de referencia para o envio do recurso r para o

estado i ∈ Ib (h)Hmin horizonte mınimo de scheduling (h)

4.3.1 Funcao Objetivo

A funcao objetivo (FO) (equacao 4.1) consiste na minimizacao do custo opera-

cional do sistema, sendo representada pelos custos de envio e recebimento, e ainda

considerando-se as variacoes em funcao do horario horossazonal (horario de ponta).

O recurso r representa os tanques, o estado i esta associado a operacao de recebi-

mento (i ∈ Ia) ou de envio (i ∈ Ib) e o evento n representa a ocorrencia do mesmo.

min CUSTO

=∑r∈R

∑i∈(Ia

⋃Ib)

∑n∈N

CN · (TFr,i,n − TSr,i,n)

+∑r∈R

∑i∈(Ia

⋃Ib)

∑n∈N

∑h∈HP

CHPh · (Xr,i,n,h)

(4.1)

A funcao objetivo pode tambem ser representada como uma funcao de ma-

ximizacao do lucro do sistema (equacao 4.2), sendo representada pelo volume de

5Utilizado para calculo do tempo de recebimento ou de envio, uma vez que as vazoes envolvidassao constantes e os tanques possuem um volume conhecido.


produtos enviados da refinaria para os respectivos clientes.

max LUCRO =∑r∈R

∑n∈N

RDr,i,n · lucroi (4.2)

4.3.2 Restricoes

Cada recurso deve estar em apenas um estado em cada evento, ou seja, cada

tanque deve estar recebendo (RRr,i,n = 1), enviando (RDr,i,n = 1), liberado para

receber (FRr,n = 1) ou liberado para enviar (FDr,n = 1), conforme a expressao 4.3.

O mesmo estado pode ocorrer mais de uma vez no mesmo recurso, porem em eventos

distintos, durante o horizonte de scheduling (restricao 4.3). Por exemplo o tanque 1

(recurso r = 1) recebeu do estado 2 (i = 2) no eventos 2 e 5 (n = 2 e n = 5).

∑i∈Ia

RRr,i,n +∑i∈Ib

RDr,i,n + FRr,n + FDr,n = 1

∀r ∈ R, n ∈ N

(4.3)

Os eventos relacionados com o recebimento devem ser sequenciais (restricao

4.4 e 4.5).

∑r∈R

RRr,i,n − Y 1i,n = 0 ∀i ∈ Ia, n ∈ N (4.4)

Y 1i,n − Y 1i,n−1 ≤ 0 ∀i ∈ Ia, n ∈ N | n > 1 (4.5)

Os eventos relacionados com o envio devem ser sequenciais (restricao 4.6 e 4.7).

∑r∈R

RDr,i,n − Y 2i,n = 0 ∀i ∈ Ib, n ∈ N (4.6)

Y 2i,n − Y 2i,n−1 ≤ 0 ∀i ∈ Ib, n ∈ N | n > 1 (4.7)


O fluxo de recebimento (restricao 4.8) e de envio (restricao 4.9) devem estar

entre os limites superior e inferior de vazao, sendo que ϕmin e ϕmax respectivamente

representam a taxa de variacao mınima e maxima admissıvel de vazao:

RRr,i,n · TRr,i · ϕmin ≤ TFr,i,n − TSr,i,n

TFr,i,n − TSr,i,n ≤ RRr,i,n · TRr,i · ϕmax

∀r ∈ R, i ∈ Ia, n ∈ N

(4.8)

RDr,i,n · TDr,i · ϕmin ≤ TFr,i,n − TSr,i,n

TFr,i,n − TSr,i,n ≤ RDr,i,n · TDr,i · ϕmax

∀r ∈ R, i ∈ Ib, n ∈ N

(4.9)

Os tempos finais de todos os eventos devem ser positivos (restricao 4.10).

TFr,i,n ≥ 0 ∀r ∈ R, i ∈ I, n ∈ N (4.10)

Para o mesmo recurso r, mesmo estado i e mesmo evento n o tempo final de

qualquer evento deve ser maior ou igual ao tempo de inıcio para o mesmo recurso r,

mesmo estado i e mesmo evento n(restricao 4.11).

TFr,i,n − TSr,i,n ≥ 0 ∀r ∈ R, i ∈ I, n ∈ N (4.11)

Quando um tanque (recurso r) iniciar o recebimento ele deve terminar antes

do final do horizonte de scheduling H (restricao 4.12).

TFr,i,n −H ·RRr,i,n ≤ 0 ∀r ∈ R, i ∈ Ia, n ∈ N (4.12)

Os estados “livre para enviar” ou “livre para receber” devem terminar antes do


final do horizonte de scheduling (restricao 4.13).

TFr,i,n −H · FDr,n −H · FRr,n ≤ 0

∀r ∈ R, i ∈ Ic, n ∈ N(4.13)

Quando um tanque (recurso r) iniciar o envio, ele deve terminar antes do final

do horizonte de scheduling H (restricao 4.14).

TFr,i,n −H ·RDr,i,n ≤ 0

∀r ∈ R, i ∈ Ib, n ∈ N(4.14)

As restricoes 4.15 e 4.16 estabelecem o ciclo operacional, ou seja, em 4.15 se o

tanque (recurso r) estiver enviando (RDr,i,n = 1) ou livre para enviar (FDr,n = 1)

no evento n, o mesmo tanque estava recebendo (RRr,i,n−1 = 1) ou livre para enviar

(FDr,n−1 = 1) no evento anterior n − 1. Em 4.16 se o tanque (recurso r) estiver

recebendo (RRr,i,n = 1) ou livre para receber (FRr,n = 1) no evento n, o mesmo

tanque estava enviando (RDr,i,n−1 = 1) ou livre para receber (FRr,n−1 = 1) no

evento anterior n− 1.

∑i∈Ib

RDr,i,n + FDr,n −∑i∈Ia

RRr,i,n−1 − FDr,n−1 = 0

∀r ∈ R, n ∈ N | n > 1

(4.15)

∑i∈Ia

RRr,i,n + FRr,n −∑i∈Ib

RDr,i,n−1 − FRr,n−1 = 0

∀r ∈ R, n ∈ N | n > 1

(4.16)

Como cada tanque (recurso r) so pode estar em um estado em cada evento, a

restricao a seguir diz que para cada novo estado o tempo de inıcio deve ser maior

ou igual ao tempo final do evento anterior (restricao 4.17).

∑i∈I

TSr,i,n −∑i∈I

TFr,i,n−1 ≥ 0

∀r ∈ R, n ∈ N | n > 1

(4.17)


Apos o recebimento no tanque (recurso r), o produto armazenado deve per-

manecer em repouso para analise das caracterısticas do produto por um perıodo de

tempo de no mınimo 4 horas. Essa restricao e modelada na expressao 4.18.

∑i∈I

TSr,i,n −

(∑i∈I

TFr,i,n−1 + 4 ·∑i∈Ia

RRr,i,n−1

)≥ 0

∀r ∈ R, n ∈ N | n > 1

(4.18)

As demandas de recebimento DRi (restricao 4.19) e de envio DDi (restricao

4.20) devem ser atendidas dentro do horizonte de scheduling. Estas expressoes per-

mitem um pre-processamento dos dados, reduzindo deste modo a arvore de busca

do modelo (mais detalhes ver secao 4.5).

∑r∈R

∑n∈N

RRr,i,n · V Ur −DRi = 0 ∀i ∈ Ia (4.19)

∑r∈R

∑n∈N

RDr,i,n · V Ur −DDi = 0 ∀i ∈ Ib (4.20)

As retricoes 4.21 e 4.22 sao utilizadas para modelar o paralelismo de eventos

em recursos distintos (r 6= r′) e evitar a sobreposicao dos mesmos. Estas restricoes

sao nao lineares.

|TFr,i,n − TFr′,i,n′| ≥ (RRr,i,n + RRr′,i,n′ − 1) · TRr′,i

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(4.21)

|TFr,i,n − TFr′,i,n′| ≥ (RDr,i,n + RDr′,i,n′ − 1) · TDr′,i

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(4.22)

Para modelar as restricoes 4.21 e 4.22 como lineares, atraves de BIG-M (ver

pagina 26), foi necessario inserir mais uma variavel binaria no modelo (V Ar,n,r′,n′,i).

Cabe destacar que esta variavel possui cinco indices (r, n, r′, n′, i), elevando deste


modo a ordem do modelo, conforme sera apresentado no decorrer deste capıtulo.

Inicialmente e necessario identificar a precedencia dos eventos atraves dos tempos

de inıcio (TSr,i,n). As restricoes 4.23 e 4.24 sao utilizadas neste sentido. Em seguida

sao modeladas as operacoes semicontınuas atraves das restricoes 4.25 e 4.26.

TFr,i,n − TFr′,i,n′ ≥ (1− V Ar,n,r′,n′,i) · (−M)

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(4.23)

TFr,i,n − TFr′,i,n′ ≤ V Ar,n,r′,n′,i · (M + eps)− eps

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(4.24)

TSr,i,n − TFr′,i,n′ ≥ (1− V Ar,n,r′,n′,i) · (−M)

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(4.25)

TSr,i,n − TFr′,i,n′ ≤ V Ar,n,r′,n′,i · (M + eps)− eps

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(4.26)

Existem algumas operacoes na TE que sao contınuas, por exemplo, o recebi-

mento de produto da unidade de processo implica em um recurso r estar recebendo

durante o horizonte de scheduling. Para modelar esta restricao sem aumentar ainda

mais as variaveis binarias foi inserida a restricao 4.27.

TFr,i,n ≤(

DRi

FMAXi

)∀r ∈ R, i = 1, n ∈ N (4.27)

Custo Eletrico

Normalmente o custo da energia eletrica e representado na FO do modelo PLIM

agregado a outros fatores, sendo considerado fixo ao longo do tempo. Em problemas


de scheduling em que a tarifacao de energia eletrica esta sujeita a uma tarifacao ho-

rossazonal6, esta variacao do custo deve ser considerada na modelagem do problema,

o que nao e verificado nos modelos existentes em PLIM com tempo contınuo. Para

suprir esta lacuna, a seguir e proposta uma modelagem que contempla a tarifacao

horossazonal (Stebel, 2003). Uma modelagem semelhante pode ser encontrada em

Magatao (2005).

A figura 4.4 ilustra todas as possibilidades de um estado i (envio ou recebi-

mento) estar dentro do horario de ponta no evento n. Conforme a figura 4.4 existem

seis arranjos possıveis. Comparando-se os tempos de inıcio e final das operacoes com

os respectivos tempos de inıcio e final dos horarios de ponta foi possıvel reduzir para

quatro o numero de possibilidades, isto e possıvel porque duas possibilidades sao

contempladas pelas demais.

HHP(h)

TSr,i,n TFr,i,n

TSr,i,n

TSr,i,n

TSr,i,n

TSr,i,n

TSr,i,n

TFr,i,n

TFr,i,n

TFr,i,n

TFr,i,n

TFr,i,n

HP(h+1) HP(nh)

TSHPh TFHPh TSHPh+1 TFHPh+1 TFHPnhTSHPnh

(a)

(b)

(c)

(d)

(e)

(f)

Figura 4.4: Custo eletrico.

Para identificar a posicao dos eventos dentro do horizonte de scheduling foi

necessario criar variaveis binarias. Estas variaveis fazem a verificacao dos tempos de

inıcio (TSr,i,n) com relacao ao tempo de inıcio do horario de ponta correspondente

6As tarifas horossazonais tem precos diferenciados em relacao as horas do dia (ponta e fora deponta) e aos perıodos do ano (umido e seco) (COPEL, 2006).


TSHPh (inequacoes 4.28 e 4.29) e tambem do tempo final (TFr,i,n) com relacao ao

tempo final do horario de ponta correspondente TFHPh (inequacoes 4.30 e 4.31).

TSr,i,n − TSHPh ≥ (1−Wr,i,n,h) · (−M)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.28)

TSr,i,n − TSHPh ≤ Wr,i,n,h · (M + eps)− eps

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.29)

TFr,i,n − TFHPh ≥ (1− Vr,i,n,h) · (−M)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.30)

TFr,i,n − TFHPh ≤ Vr,i,n,h · (M + eps)− eps

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.31)

A primeira possibilidade envolve as situacoes (a) e (b) ilustradas na figura 4.4.

As restricoes 4.32, 4.33, 4.34 e 4.35 sao utilizadas para modelar esta possibilidade.

Ar,i,n,h ≤ (1− Vr,i,n,h)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.32)

Ar,i,n,h ≤ (1−Wr,i,n,h)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.33)

Ar,i,n,h ≥ 1− Vr,i,n,h −Wr,i,n,h

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.34)

Xr,i,n,h − TFr,i,n + TSHPh ≥ (1− Ar,i,n,h) · (−M)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.35)


A segunda possibilidade envolve a situacao (c) ilustrada na figura 4.4. As res-

tricoes 4.36, 4.37, 4.38, 4.39 e 4.40 sao utilizadas para modelar esta possibilidade.

Cr,i,n,h ≤ Vr,i,n,h

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.36)

Cr,i,n,h ≤ (1−Wr,i,n,h)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.37)

Cr,i,n,h ≥ Vr,i,n,h −Wr,i,n,h

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.38)

Xr,i,n,h − TFHPh + TSHPh ≤ (1− Cr,i,n,h) ·M

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.39)

Xr,i,n,h − TFHPh + TSHPh ≥ (1− Cr,i,n,h) · (−M)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.40)

A terceira possibilidade envolve a situacao (d) ilustrada na figura 4.4. As res-

tricoes 4.41, 4.42, 4.43, 4.44 e 4.45 sao utilizadas para modelar esta possibilidade.

Dr,i,n,h ≤ (1− Vr,i,n,h)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.41)

Dr,i,n,h ≤ Wr,i,n,h

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.42)

Dr,i,n,h ≥ Wr,i,n,h − Vr,i,n,h

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.43)


Xr,i,n,h − TFr,i,n + TSr,i,n ≤ (1−Dr,i,n,h) ·M

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.44)

Xr,i,n,h − TFr,i,n + TSr,i,n ≥ (1−Dr,i,n,h) · (−M)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.45)

A quarta e ultima possibilidade envolve as situacoes (e) e (f) ilustradas na

figura 4.4. As restricoes 4.46, 4.47, 4.48 e 4.49 sao utilizadas para modelar esta

possibilidade.

Er,i,n,h ≤ Vr,i,n,h

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.46)

Er,i,n,h ≤ Wr,i,n,h

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.47)

Er,i,n,h ≥ Vr,i,n,h + Wr,i,n,h − 1

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.48)

Xr,i,n,h − TFHPh + TSr,i,n ≥ (1− Er,i,n,h) · (−M)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(4.49)

4.4 Ordem do Modelo

No sentido de visualizar a complexidade7 computacional (Apendice A, pagina

129) do modelo foram comparadas tres situacoes distintas. A primeira denominada

modelo basico tem como funcao objetivo a expressao 4.2 e utiliza as restricoes de

7Para mais detalhes ver Garey & Johnson (1979).

4.4. Ordem do Modelo 67

4.3 ate 4.20. A segunda denominada modelo basico com custo eletrico tem como

FO a expressao 4.1 e utiliza as restricoes do modelo basico mais as restricoes de

4.28 ate 4.49. Por fim, a terceira, denominada de modelo completo tem como FO

a expressao 4.1 e utiliza as restricoes de 4.3 ate 4.49. As expressoes 4.50, 4.51

e 4.52 e a figura 4.5 apresentam as caracterısticas de cada modelo (basico, ba-

sico com custo eletrico e completo) com relacao ao numero de variaveis binarias

(NV BMB, NV BMBCE, NV BMC). O crescimento do numero de variaveis e avaliado

em funcao da instancia8 do problema para cada modelo, conforme ilustrado na figura

4.5.

NV BMB = nr · nn · (no + nd + 2) (4.50)

NV BMBCE = 2 · nr · ni · nn · nhp + nr · nn · (no + nd + 2) (4.51)

NV BMC =nr · (nr − 1) · nn2 · (ni− 1) + 2 · nr · ni · nn · nhp+

nr · nn · (no + nd + 2)(4.52)

As expressoes 4.53, 4.54 e 4.55 e a figura 4.6 apresentam as caracterısticas

de cada modelo (basico, basico com custo eletrico e completo) com relacao ao nu-

mero de variaveis contınuas (NV CMB, NV CMBCE, NV CMC). Nas figuras 4.5 e 4.6

e possıvel observar que a medida que o modelo se torna mais refinado o crescimento

das variaveis se torna elevado. Para instancias muito grandes do problema o numero

de variaveis binarias e contınuas se torna elevado, inviabilizando uma solucao para

o modelo, isto fica evidenciado nas simulacoes computacionais que sao apresentadas

no capıtulo 7.

NV CMB = 2 · nn · (nr · ni + 1) (4.53)

8A palavra instancia e utilizada para representar o conjunto de valores assumidos pelos para-metros de entrada do problema, por exemplo nr = 5, ni = 5 e nr = 6.


0

1000

2000

3000

4000

5000

6000

7000

8000

9000

1 2 3 4 5 6 7 8

instância do problema

vari

ávei

s b

inár

ias

modelo completo

modelo com custo elétrico

modelo básico

Figura 4.5: Variaveis binarias.

NV CMBCE = 5 · nr · ni · nn · nhp + 2 · nn · (nr · ni + 1) (4.54)

NV CMC =2 · nr · (nr − 1) · nn2 · (ni− 1) + 5 · nr · ni · nn · nhp+

2 · nn · (nr · ni + 1)(4.55)

A principal responsavel pelo crescimento do numero de variaveis, particula-

mente das binarias, sao as restricoes de 4.23 ate 4.27, utilizadas para evitar a sobre-

posicao de eventos n em recursos distintos r 6= r′. Deste modo, e possıvel caracteriza-

las como restricoes complicadoras. Estas restricoes sao identificadas como restricoes

de sequenciamento em paralelo para um mesmo estado i. Uma alternativa, que e

proposta no capıtulo 6, e a modelagem destas restricoes em PLR, atraves de meta-

interpretadores de PLR, que foram desenvolvidos para este tipo de modelagem.

4.5 Pre-processamento dos Dados

O pre-processamento dos dados e uma tarefa indispensavel em modelos PLIM,

uma vez que pode reduzir significativamente o tempo computacional. Esta tarefa

4.5. Pre-processamento dos Dados 69

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

20000

1 2 3 4 5 6 7 8

instância do problema

vari

ávei

s co

ntí

nu

as

modelo completo

modelo com custo elétrico

modelo básico

Figura 4.6: Variaveis contınuas.

consiste basicamente na reducao do tamanho do problema atraves da eliminacao de

redundancias, insercao de limites superiores e inferiores as variaveis do problema e

eliminacao de infactibilidades do problema. Na pratica o que ocorre e uma reducao

do numero de linhas e colunas do modelo matematico do problema. Esta tarefa esta

presente em varios pacotes comerciais, entre eles pode-se destacar (ILOG, 2002b) e

(Lindo, 1999).

Um pre-processamento no modelo de scheduling dos recursos de estocagem

ocorre inicialmente atraves da representacao do estado inicial dos tanques da TE,

ou seja, o que cada tanque (∀r) esta fazendo no instante inicial de simulacao de uma

determinada instancia (∀TSr,i,n). Esta imposicao melhora a eficiencia do modelo,

uma vez que reduz a arvore binaria de busca.

Outro pre-processamento dos dados ocorre nas restricoes 4.19 e 4.20. Nestas

restricoes a partir das demandas de recebimento (DRi) e de envio (DDi) e pos-

sıvel determinar o numero de variaveis binarias relacionadas com as operacoes de

recebimento (RRr,i,n) e de envio (RDr,i,n). Por exemplo, se DD3 = 10400m3 e o

V Ur = 2600m3, serao necessarios 4 eventos de envio para o destino 3 durante o


horizonte de scheduling, conforme a expressao 4.56.

∑r∈R

∑n∈N

RDr,3,n = 4 (4.56)

Os tempos relacionados com as operacoes de recebimento TRr,i e de envio

TDr,i, normalmente estao relacionadas ao produto que sera bombeado e ao numero

de bombas que serao utilizadas na operacao. Deste modo, e possıvel calcular previ-

amente os tempos envolvidos para vazoes maximas ja que os volumes dos recursos r

sao previamente conhecidos. As expressoes 4.57 e 4.58 sao utilizadas neste sentido.

TRr,i =V UTILr

FMAXi

∀i ∈ Ia (4.57)

TDr,i =V UTILr

FMAXi

∀i ∈ Ib (4.58)

O horizonte de scheduling e fornecido a priori, porem em funcao das demandas

de recebimento e de envio pode-se calcular um tempo mınimo para que as operacoes

sejam realizadas de acordo as expressoes 4.59 e 4.60.

Hmin = max

(DRi

FMAXi

,DD′

i

FMAX ′i

)∀i ∈ Ia, i

′ ∈ Ib (4.59)

H > Hmin (4.60)

O numero total de variaveis binarias (do ciclo operacional do tanque) assu-

mindo o valor 1 e dado pela expressao 4.61.

∑r∈R

∑i∈Ia

∑n∈N

RRr,i,n +∑r∈R

∑i∈Ib

∑n∈N

RDr,i,n+∑r∈R

∑n∈N

FRr,n +∑r∈R

∑n∈N

FDr,n = nr · nn(4.61)

4.6. Consideracoes Finais 71


Este modelo deve ser inserido num ambiente computacional adequado para ser

utilizado por um operador da planta real, para experimentar seus planos de rece-

bimento e envio e encontrar a programacao mais adequada, de modo a detectar (e

corrigir) possıveis problemas que venham a ser encontrados. Devido a complexidade

do modelo, fica claro que o processo de scheduling nao e trivial e a possibilidade

de visualizacao grafica do processo facilita muito o teste dos planos. Alem disto,

o proprio processo de modelagem permite a deteccao dos pontos mais crıticos no

sistema como gargalos. Com a alteracao de algumas restricoes, este modelo pode

ser aplicado para resolver outros problemas de scheduling de recursos de armaze-

namento. A estrategia de representacao dos estados dos tanques e a determinacao

do ciclo operacional tornaram o modelo bastante eficiente para instancias reduzidas

com relacao ao tempo computacional, conforme pode ser observado no capıtulo 7

(secao 7.1).


Capıtulo 5

Modelagem das VariaveisLinguısticas do PSRE

Uma das etapas para o desenvolvimento de um modelo de PLIM e a especifica-

cao de uma funcao custo que corresponda ao problema real tratado. Neste capıtulo,

e apresentado um sistema fuzzy, baseado no conhecimento do especialista, que pos-

sibilita parametrizar alguns dos componentes de custo da funcao objetivo utilizada

nesta tese, com a finalidade de minimizar as diferencas entre o modelo teorico e

as necessidades praticas. Deste modo, os diferentes custos exercerao uma influencia

distinta sobre o modelo matematico.

5.1 Motivacao

A estrutura da funcao objetivo num modelo PLIM influencia o comportamento

numerico do algoritmo. Deste modo, coletar diferentes contribuicoes de custos em

variaveis que representem bem os problemas de scheduling e fundamental para obter,

alem de respostas viaveis, solucoes que possam ser implementadas na pratica.

Como dito no capıtulo 4, os problemas de scheduling da TE nas refinarias sao

tratados baseados na experiencia profissional com a utilizacao de calculos manuais.

Em funcao disso, existem alguns modelos sendo desenvolvidos para satisfazer as

caracterısticas destes problemas (ver secao 2.5). Porem, a principal limitacao destes,

alem da explosao do tempo computacional, e que os modelos existentes so levam em

74 Capıtulo 5. Modelagem das Variaveis Linguısticas do PSRE

consideracao aspectos fısicos da planta, nao contemplam caracterısticas de mao de

obra para operacao da mesma. Estes fatores, que ja sao um refinamento do modelo,

nao podem ser deixados de lado.

Na modelagem da mao de obra na execucao do scheduling foi necessario es-

colher uma tecnica que permitisse representar as informacoes qualitativas do pro-

blema. Dentro deste contexto utiliza-se sistemas fuzzy para representar uma parte

dos custos da funcao objetivo do modelo de scheduling. A teoria de conjuntos fuzzy,

introduzida por Zadeh (1965) e uma generalizacao da teoria de conjuntos convenci-

onal. Ela permite representar conceitos vagos e imprecisos. A interpretacao fuzzy de

estruturas de dados e modelada e resolvida de modo natural em varios problemas

do mundo real. A principal vantagem de uma formulacao fuzzy comparada com uma

formulacao crisp e que o especialista pode dar uma formulacao qualitativa sobre o

problema a ser modelado. Cabe ressaltar que esta aplicacao nao se caracteriza como

otimizacao linear fuzzy, os modelos PLIM e fuzzy sao independentes. O sistema fuzzy

e utilizado apenas para criar uma superfıcie de decisao a partir do conhecimento do

especialista. A partir desta superfıcie, ao final, e preenchida uma matriz custo de

troca (ver pagina 84). Por fim, esta matriz custo de troca e inserida no modelo

PLIM como parametro de entrada.

5.2 Construcao do Sistema Fuzzy

O problema de scheduling modelado no capıtulo 4 foi utilizado neste capıtulo

com uma alteracao na funcao objetivo. A funcao objetivo do modelo matematico

e composta por tres custos: custo de transferencia, custo eletrico e custo de troca.

Os dois primeiros sao modelados no capıtulo 4. O custo de troca, por representar

aspectos qualitativos da planta, foi modelado atraves de um sistema fuzzy.

O sistema fuzzy resultante do custo de troca e composto por 3 variaveis de

entrada (dificuldade, manobras e turno) e pela variavel de saıda (custo de troca).

Na figura 5.1 e possıvel ter uma visualizacao geral do sistema, onde a maquina

de inferencia Mamdani inclui modulos de interface que transformam as variaveis de

entrada em variaveis fuzzy e, posteriormente, as variaveis fuzzy geradas em variaveis

5.2. Construcao do Sistema Fuzzy 75

numericas, adequadas para o sistema em questao.

Mamdani

dificuldade

manobras

turno

custo de troca

fuzzificador

defuzzificadorbasede

regras

máquinade

inferência

Figura 5.1: Representacao geral do sistema fuzzy.

A partir de informacoes de um especialista foi feita uma base de regras para

mapear o custo de troca a partir de entradas conhecidas, conforme a figura 5.2.

5.2.1 Variavel de Saıda

A variavel de saıda (custo de troca) trata do inıcio das operacoes de envio e

de recebimento, durante todas as horas do dia. Esta variavel possui cinco predica-

dos representados por funcoes de pertinencia do tipo triangular. Estas funcoes de

pertinencias fazem o mapeamento dos valores que a variavel pode assumir com os

atributos mınimo, baixo, medio, alto, maximo, conforme a figura 5.3.

5.2.2 Variaveis de Entrada

Dificuldade: a dificuldade para abrir/fechar uma valvula manual ou motori-

zada. Esta variavel possui tres predicados representados por funcoes de pertinencia

do tipo triangular normalizada entre 0 e 1. Estas funcoes de pertinencias fazem o

mapeamento dos valores que a variavel pode assumir com os atributos baixa, media,


conhecimentodo especialista

base deregras

mapeamentode entrada/saída

Figura 5.2: Base de regras.

0 0.25 0.5 0.75 1

1.0

0.5

0

mínimo baixo médio alto máximoµ

Figura 5.3: Custo de troca.


alta, conforme a figura 5.4. Os atributos da variavel Dificuldade sao associados as

operacoes (estados) de recebimento (i ∈ Ia) e de envio (i ∈ Ib).

Baixa Média Alta

1

0.5

0 0.5 1

Figura 5.4: Dificuldade da manobra.

Manobras: o numero de valvulas e bombas1 necessarias para executar uma

operacao. Esta variavel possui tres predicados representados por funcoes de perti-

nencia do tipo triangular normalizada entre 0 e 1. Estas funcoes de pertinencias

fazem o mapeamento dos valores que a variavel pode assumir com os atributos pou-

cas, algumas, bastante, conforme a figura 5.5. Os atributos da variavel Manobras

sao associados as operacoes (estados) de recebimento (i ∈ Ia) e de envio (i ∈ Ib).

Turno: as refinarias trabalham em tres turnos intermitentes de 8 horas. Sendo

o primeiro turno 23-7hs, o segundo turno 7-15hs e o terceiro 15-23hs. Para repre-

sentar os tres turnos e as transicoes entre os mesmos foi necessario representar sete

atributos, conforme mostrado na figura 5.6.

5.2.3 Base de Regras

A base de regras resultante possui um total de 63 regras. Para facilitar a

visualizacao foram montadas tres tabelas. Na primeira (tabela 5.1) a variavel DI-

FICULDADE assume o termo “baixa”. Na segunda (tabela 5.2) a variavel DIFI-

1Equipamento que aspira um fluido por meio de uma boca de aspiracao e o expulsa por meiode outra boca, de impulsao, permitindo o transporte do fluido de um lugar para outro.


Poucas Algumas Bastante

1

0.5

0 0.5 1

Figura 5.5: Manobras.

fimT1 TR1 T2 TR2 T3 TR3 iniT1

1

0.5

0 7 15 23 24 horas

Figura 5.6: Turnos de trabalho.


CULDADE assume o termo “media”. Na terceira (tabela 5.3) a variavel DIFI-

CULDADE assume o termo “alta”.

As abreviacoes utilizadas na base de regras sao as seguintes: fim T1 (final do

primeiro turno), ini T1 (inıcio do primeiro turno), T2 (segundo turno), T3 (terceiro

turno), TR1 (troca entre o primeiro e o segundo turno), TR2 (troca entre o segundo

e o terceiro turno), TR3 (troca entre o terceiro e o primeiro turno).

Tabela 5.1: Base de regras A.MANOBRAS

poucas algumas bastantefim T1 mınimo baixo medio

T TR1 medio alto altoU T2 mınimo mınimo baixoR TR2 alto alto maximoN T3 mınimo mınimo medioO TR3 alto maximo maximo

ini T1 mınimo baixo medio

Tabela 5.2: Base de regras B.MANOBRAS

poucas algumas bastantefim T1 baixo medio alto

T TR1 alto alto altoU T2 mınimo baixo baixoR TR2 alto alto maximoN T3 mınimo baixo medioO TR3 alto maximo maximo

ini T1 baixo medio alto

Tabela 5.3: Base de regras C.MANOBRAS

poucas algumas bastantefim T1 medio medio alto

T TR1 alto alto maximoU T2 mınimo baixo medioR TR2 alto maximo maximoN T3 baixo medio medioO TR3 maximo maximo maximo

ini T1 medio medio alto

Atraves da base de regras e possıvel determinar o custo de troca, pelo mapea-

mento das variaveis de entrada e saıda, conforme ilustrado a seguir:


SE DIFICULDADE e ALTA E MANOBRAS POUCAS E TURNO TR3

ENTAO CUSTO DE TROCA e MAXIMO.

5.2.4 Mecanismo de Inferencia

A composicao possui um papel importante nos procedimentos de inferencia

usados em sistemas baseados em regras. Existem varias formas de implementar uma

composicao como, por exemplo, os metodos max−min e max−produto (ver pagina

46). Neste trabalho sera utilizado o metodo max−min de composicao, cuja sequencia

de acoes e a que segue:

• inicialmente atribui-se o mınimo dos graus de pertinencia (operador Min) na

agregacao dos antecedentes;

• a seguir atribui-se o mınimo (operador Min) na implicacao (regra de Mam-

dani);

• em seguida atribui-se o maximo (operador Max) dos graus de pertinencia ao

resultado da combinacao de varias regras, ou seja, no processo de agregacao

das regras;

• por fim, utiliza-se o operador MOM na defuzzificacao.

O metodo de defuzzificacao MOM (Media dos Maximos) foi escolhido por

aproximar a superfıcie do custo de troca de um plato. Neste metodo a saıda e

obtida atraves da media entre os elementos extremos no universo que correspondem

aos maiores valores da funcao de pertinencia. A implemetacao do sistema fuzzy

descrito neste capıtulo foi realizada no software MATLAB, mais especificamente na

ferramenta chamada sistema de inferencia fuzzy (MATLAB, 2006).

5.2.5 Parametros Inseridos na FO do Modelo PLIM

Atraves do metodo de defuzzificacao e possıvel obter os valores dos custos de

troca. Nas figuras 5.7 e 5.8 pode-se vizualizar o comportamento destes custos em

funcao da variacao dos atributos das variaveis de entrada, gerando-se uma superfıcie


de custos de troca. As superfıcies das figuras 5.7 e 5.8 foram aproximadas por um

plato2.

Para obter os custos de troca atraves do sistema fuzzy e depois inseri-los no

modelo PLIM sao seguidos alguns passos, descritos a seguir:

• Inicialmente e escolhida em qual area (GLP, diesel, gasolina ou querosene)

sera realizado o scheduling. Para cada area e associado um grau de pertinencia

com relacao a realizacao das tarefas, considerando-se as variaveis dificuldade

e manobras, sendo que estas variam em funcao das operacoes de recebimento

(i ∈ Ia) e de envio (i ∈ Ib).

• Para a outra variavel, turno, sao avaliadas as operacoes em relacao ao horario

em que serao executadas, cabe destacar que as variacoes se repetem a cada 24

horas.

• Por fim, os custos de troca sao obtidos atraves de uma matriz custo, que repre-

senta uma variacao do custo de troca em funcao das operacoes de recebimento

(i ∈ Ia) ou de envio (i ∈ Ib) e do horario (TSr,i,n) em que as mesmas ocorrem

dentro do horizonte de scheduling.

A variavel tempo de inıcio (TSr,i,n) das operacoes, do modelo PLIM, e utilizada

para identificar o custo de troca correspondente. A tabela 5.4 ilusta a variacao do

custo de troca em funcao das operacoes (i ∈ Ia ∪ Ib) e dos tempos de inıcio (TSr,i,n)

das operacoes.

Para facilitar o entendimento de quantos parametros serao representados pelo

sistema fuzzy resultante considere o seguinte exemplo. Determinar os custos de troca

para uma area de GLP, com horizonte de scheduling de 96 horas (4 dias), ou seja,

ocorrem 6 variacoes do custo de troca para cada operacao (i ∈ Ia ∪ Ib) a cada 24

horas, ou seja, 24 variacoes para cada operacao (i ∈ Ia ∪ Ib) dentro do horizonte de

scheduling. Entao, no total o custo de troca sera formado por uma matriz com 96

(24x4) elementos (parametros).

2Esta consideracao de modelagem tem por finalidade manter a linearidade do modelo PLIM docapıtulo 4.


Alta Dificuldade

Média Dificuldade

Baixa Dificuldade

TurnoManobras

Cus

to d

e Tr

oca

Cus

to d

e Tr

oca

TurnoManobras

TurnoManobras

Cus

to d

e Tr

oca

Figura 5.7: Superfıcie dos custos de troca A.


Bastante Manobras

Algumas Manobras

Poucas Manobras

Cus

to d

e Tr

oca

Cus

to d

e Tr

oca

Cus

to d

e Tr

oca

TurnoDificuldade

TurnoDificuldade

TurnoDificuldade

Figura 5.8: Superfıcie dos custos de troca B.


Tabela 5.4: Variacao do custo de troca.Estados (i ∈ Ia ∪ Ib)

Faixa de horario (h) i = 1 i = 2 i = 3 i = 40 ≤ TSr,i,n < 6, 5 CF1,1 CF2,1 CF3,1 CF4,1

6, 5 ≤ TSr,i,n < 7, 5 CF1,2 CF2,2 CF3,2 CF4,2

7, 5 ≤ TSr,i,n < 14, 5 CF1,3 CF2,3 CF3,3 CF4,3

14, 5 ≤ TSr,i,n < 15, 5 CF1,4 CF2,4 CF3,4 CF4,4

15, 5 ≤ TSr,i,n < 22, 5 CF1,5 CF2,5 CF3,5 CF4,5

22, 5 ≤ TSr,i,n < 23, 5 CF1,6 CF2,6 CF3,6 CF4,6

23, 5 ≤ TSr,i,n < 30, 5 CF1,7 CF2,7 CF3,7 CF4,7

30, 5 ≤ TSr,i,n < 31, 5 CF1,8 CF2,8 CF3,8 CF4,8

31, 5 ≤ TSr,i,n < 38, 5 CF1,9 CF2,9 CF3,9 CF4,9

38, 5 ≤ TSr,i,n < 39, 5 CF1,10 CF2,10 CF3,10 CF4,10

39, 5 ≤ TSr,i,n < 46, 5 CF1,11 CF2,11 CF3,11 CF4,11

46, 5 ≤ TSr,i,n < 47, 5 CF1,12 CF2,12 CF3,12 CF4,12

• • • • •• • • • •• • • • •• • • • •

TSHFf ≤ TSr,i,n < H CF1,f CF2,f CF3,f CF4,f

Para utilizar a matriz, contendo todos os parametros do custo de troca, no

modelo PLIM foi necessario inserir algumas restricoes adicionais ao modelo. Estas

restricoes, todas lineares, sao apresentadas a seguir. A nomenclatura utilizada nas

variaveis do modelo e a mesma do capıtulo 4 com algumas variaveis e parametros

adicionais que sao destacados a seguir.

Nomenclatura

Indices

r recursoi estadon eventof custo f

Conjuntos

R conjunto de recursos, no caso tanquesIa conjunto de estados de recebimento (origem)Ib conjunto de estados de envio (destino)Ic conjunto de estados paradosI Ia

⋃Ib

⋃Ic

N conjunto de eventos


HF conjunto formado pelos custos F

Variaveis

TSr,i,n tempo de inıcio do recurso r do estado i no evento n (h)V F1r,i,n,f variavel binaria utilizada para indicar se o TSr,i,n e

maior ou igual ao TSHFf

V F2r,i,n,f variavel binaria utilizada para indicar se o TSr,i,n emenor ou igual ao TSHPh

Fr,i,n,f variavel que assume valor binario

Parametros

H horizonte de scheduling (h)TSHFf tempo de inıcio para o custo f (h)TFHFf tempo final para o custo f (h)M um numero positivo suficientemente grandeeps um numero positivo suficientemente pequenoCFi,f custo de bombeamento dentro da faixa f ($/h)nhf numero de intervalos utilizados para representar as variacoes

da variavel turno no horizonte de scheduling

Inicialmente e necessario identificar a posicao dos tempos de inıcio (TSr,i,n)

com relacao ao custo de troca associado. A figura 5.9 ilustra a variacao do custo

de troca em funcao do horizonte de tempo, bem como as variaveis e paramentros

envolvidos.

CFi,1

TSHF1TFHF1=TSHF2

TSr,i,n ≥ TSHFfà VF1r,i,n,f TSr,i,n ≤ TFHFfà VF2r,i,n,f

VF1r,i,n,f AND VF2r,i,n,fà Fr,i,n,f

TSr,i,n

CFi,2 CFi,3 CFi,4 CFi,5 CFi,6 CFi,f

TFHF2=TSHF3

TFHF3=TSHF4

TFHF4=TSHF5

TFHF5=TSHF6

TFHF6=TSHF7

TFHFf-1=TSHFf

TFHFf

H

Figura 5.9: Variacao do custo de troca.


As restricoes 5.1, 5.2, 5.3 e 5.4 identificam a posicao dos tempos de inıcio

(TSr,i,n) com relacao ao tempo de inıcio TSHFf e tempo final TFHFf do HF

correspondente.

TSr,i,n − TSHFf ≥ (1− V F1r,i,n,f ) · (−M)

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(5.1)

TSr,i,n − TSHFf ≤ V F1r,i,n,f · (M + eps)− eps

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(5.2)

TFHFf − TSr,i,n ≥ (1− V F2r,i,n,f ) · (−M)

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(5.3)

TFHFf − TSr,i,n ≤ V F2r,i,n,f · (M + eps)− eps

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(5.4)

As restricoes 5.5, 5.6 e 5.7 sao utilizadas para satisfazer a expressao logica

(AND) entre as variaveis binarias V F1r,i,n,f e V F2r,i,n,f , ou seja, quando ambas

assumirem valor 1 a variavel Fr,i,n,f assume tambem o valor 1 que possui um custo

de troca correspondente.

Fr,i,n,f ≤ V F1r,i,n,f

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(5.5)

Fr,i,n,f ≤ V F2r,i,n,f

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(5.6)

Fr,i,n,f ≥ V F1r,i,n,f + V F2r,i,n,f − 1

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(5.7)


A funcao objetivo (5.8) consiste na minimizacao do custo operacional do sis-

tema, sendo a FO (equacao 4.1) do capıtulo 4 acrescida pelo custo de troca (obtido

pelo sistema fuzzy) conforme pode ser visto a seguir.

min CUSTO

= custos de envio e recebimento

+ custo eletrico

+∑r∈R

∑i∈(Ia

⋃Ib)

∑n∈N

∑f∈HF

CFi,f · (Fr,i,n,f )

(5.8)


A dificuldade existente no scheduling das atividades operacionais, em especial

na industria do petroleo, aliada a falta de um suporte computacional, influencia dire-

tamente o gerenciamento de plantas industriais. Dentro deste contexto estao varios

problemas de scheduling das operacoes de uma refinaria. Esta atividade, alem de

exigir tempo e muito esforco, nao garante, muitas vezes, um bom scheduling. Nesse

sentido, este capıtulo tem por objetivo propor um refinamento dos modelos para

a atividade de scheduling de modo a reduzir as diferencas entre o modelo teorico

e as necessidades praticas. Cabe ressaltar que nao adianta fornecer um scheduling

teorico, se este nao sera seguido na execucao das tarefas. Alem disso, o nao cum-

primento do scheduling pode inserir gargalos dinamicos3 no sistema. Por exemplo,

para um scheduling fornecido que preve o inıcio de uma operacao na troca de turnos,

por uma questao de conveniencia esta atividade sera adiantada ou atrasada, como

esta consideracao nao foi previamente modelada, o scheduling sera completamente

comprometido.

Com relacao a modelagem do sistema fuzzy, uma dificuldade encontrada foi a

escolha das variaveis de entrada relevantes para o sistema. Outra dificuldade foi a

utilizacao dos custos fuzzy no modelo matematico.

Os resultados obtidos que comprovam a importancia de coletar custos, muitas

3Estes gargalos ocorrem pelo atraso ou adiantamento de algumas tarefas.


vezes desprezados, nos modelos de scheduling, estao no capıtulo 7. Cabe destacar,

que embora a modelagem do custo de troca possa ser feita atraves de um sistema

especialista, a utilizacao de sistemas fuzzy mostrou-se adequada para tal.

Capıtulo 6

Abordagem Hıbrida: PLIM-PLR

O principal objetivo em desenvolver modelos e metodos hıbridos e usar recursos

complementares, no caso especıfico de PLIM e PLR para resolver os problemas que

sao intrataveis quando qualquer um destes dois metodos e utilizado sozinho.

O mesmo problema apresentado no capıtulo 4 foi modelado em PLR e PLIM-

PLR. Estes modelos sao apresentados, destacando-se as diferencas com o modelo

PLIM. Inicialmente o modelo em PLIM e reescrito em PLR, em seguida uma combi-

nacao das duas metodologias numa estrutura hıbrida e modelada. Por fim, e inserido

no modelo hıbrido uma heurıstica para geracao da arvore de busca, de modo a en-

contrar solucoes viaveis o mais breve possıvel.

6.1 Modelo em PLR

Para explorar as funcionalidades da PLR, as expressoes do capıtulo 4 foram

reescritas na linguagem OPL Studio 3.6.1 (ILOG, 2002a). Esta linguagem de mode-

lagem utiliza como otimizador o ILOG Solver1 (ILOG, 2001).

Na modelagem do capıtulo 4, as expressoes que utilizavam a formulacao BIG-

M sao substituıdas por implicacoes (→) e equivalencias (↔).

1Ao lado de ILOG CPLEX, o ILOG Solver e uma das bibliotecas em C++ da suite de otimi-zacao da ILOG e resolve problemas de otimizacao modelados em PLR. Resolve as aplicacoes, denatureza combinatoria, do mundo real que sao intrataveis com metodos de programacao matema-ticos tradicionais. O ILOG Solver pode ser usado sozinho, ou com ILOG CPLEX, ou ainda comobase para outros solvers.

90 Capıtulo 6. Abordagem Hıbrida: PLIM-PLR

Inicialmente as restricoes 4.15 e 4.16, que modelam o ciclo operacional foram

reescritas em PLR do seguinte modo (restricoes 6.1, 6.2, 6.3 e 6.4).

∑i∈Ib

RDr,i,n = 1 →∑i∈Ia

RRr,i,n+1 ∨ FRr,n+1

∀r ∈ R, n ∈ N | n < nn

(6.1)

∑i∈Ia

RRr,i,n = 1 →∑i∈Ib

RDr,i,n+1 ∨ FDr,n+1

∀r ∈ R, n ∈ N | n < nn

(6.2)

FRr,n = 1 →∑i∈Ia

RRr,i,n+1 ∨ FRr,n+1

∀r ∈ R, n ∈ N | n < nn

(6.3)

FDr,n = 1 →∑i∈Ib

RDr,i,n+1 ∨ FDr,n+1

∀r ∈ R, n ∈ N | n < nn

(6.4)

O conjunto de restricoes (4.23 ate 4.27) que sao utilizadas para modelar a sobre-

posicao de eventos bem como os processos contınuos e semi-contınuos sao reescritas

conforme as restricoes 6.5 e 6.6.

(TFr,i,n ≥ TFr′,i,n′) ∧ (TFr,i,n 6= 0) ∧ (TFr′,i,n′ 6= 0) ↔ (V Ar,n,r′,n′,i = 1)

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(6.5)

V Ar,n,r′,n′,i = 1 → TSr,i,n ≥ TFr′,i,n′

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(6.6)

As restricoes utilizadas para modelar a variacao do custo eletrico (restricoes

4.28 ate 4.49) sao reescritas em PLR do seguinte modo (restricoes 6.7 ate 6.12).

Vr,i,n,h = 1 ↔ TFr,i,n ≥ TSHPh

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(6.7)

6.1. Modelo em PLR 91

Wr,i,n,h = 1 ↔ TSr,i,n ≥ TSHPh

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(6.8)

(Vr,i,n,h = 0) ∧ (Wr,i,n,h = 0) → (Xr,i,n,h ≥ TFr,i,n − TSHPh)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(6.9)

(Vr,i,n,h = 1) ∧ (Wr,i,n,h = 0) → (Xr,i,n,h ≥ TFHPh − TSHPh)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(6.10)

(Vr,i,n,h = 0) ∧ (Wr,i,n,h = 1) → (Xr,i,n,h ≥ TFr,i,n − TSr,i,n)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(6.11)

(Vr,i,n,h = 1) ∧ (Wr,i,n,h = 1) → (Xr,i,n,h ≥ TFHPh − TSr,i,n)

∀r ∈ R, i ∈ I, n ∈ N, h ∈ HP(6.12)

As restricoes utilizadas para inserir o custo de troca, modeladas no capıtulo 6,

(restricoes 5.1 ate 5.7) sao reescritas em PLR do seguinte modo (restricoes 6.13 ate

6.15):

(V F1r,i,n,f = 1) ↔ (TSr,i,n ≥ TSHFf )

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(6.13)

(V F2r,i,n,f = 1) ↔ (TFr,i,n ≥ TSHFf )

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(6.14)

(V F1r,i,n,f = 1) ∧ (V F2r,i,n,f = 1) → (FUZZYr,i,n,f = 1)

∀r ∈ R, i ∈ I, n ∈ N, f ∈ HF(6.15)


6.2 Modelo Hıbrido

Em termos de abordagem hıbrida utilizando PLIM e PLR, a modelagem pode

ser feita de dois modos. O primeiro consiste em escrever todas as restricoes nos dois

metodos, um exemplo desta abordagem pode ser encontrado em Magatao (2005). O

segundo, que e utilizado neste trabalho, consiste em escrever algumas restricoes em

PLIM outras em PLR e finalmente algumas restricoes sao utilizadas para promover

o enlace entre PLIM e PLR (Stebel et al., 2006), conforme ilustrado a seguir.

FO:minimize with linear relaxation ( 6.20)PLIMRestricoes:4.3 ate 4.144.17 ate 4.204.27PLRRestricoes:6.1 ate 6.15Enlace entre PLIM e PLRRestricoes:6.16 ate 6.19

O modelo hıbrido, tambem escrito na linguagem ILOG OPL Studio 3.6.1

(ILOG, 2002a), utiliza alem do ILOG Solver, outros algoritmos, o Hybrid (ILOG,

2002a) utilizado na relaxacao linear das variaveis e tambem um componente cha-

mado ILOG Scheduler2 que traz varias funcionalidades para problemas de scheduling

(ILOG, 2001). A primeira delas e chamada de activity, sendo composta por tres

itens: o tempo de inıcio do scheduling, a duracao e o tempo final do scheduling.

Deste modo, a variavel operacaor,i,n passa assumir a funcao de activity, conforme

ilustrado a seguir.

• scheduleOrigin = 0;

• scheduleHorizon = H;

2O ILOG Scheduler e uma biblioteca adicional em C++ sobre o ILOG Solver. Ela foi de-senvolvida especificamente para aplicacoes de scheduling, e possui algoritmos para manipular osequenciamento de atividades no tempo.

6.2. Modelo Hıbrido 93

• Activity operacao[RES];

As expressoes 6.16 e 6.17 associam o tempo de inıcio TSr,i,n e o tempo final

TFr,i,n com a activity operacaor,i,n respectivamente.

TSr,i,n = operacaor,i,n.start

∀r ∈ R, i ∈ I, n ∈ N(6.16)

TFr,i,n = operacaor,i,n.end

∀r ∈ R, i ∈ I, n ∈ N(6.17)

As expressoes 6.18 e 6.19 exploram outra funcionalidade da linguagem OPL

Studio 3.6.1, chamada precedes utilizada para modelar a precedencia de eventos.

(V Ar,n,r′,n′,i = 1) → operacaor′,i,n′ precedes operacaor,i,n

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(6.18)

(V Ar,n,r′,n′,i = 1) → operacaor,i,n.start ≥ operacaor′,i,n′ .end

∀(r, r′) ∈ R | r 6= r′, i ∈ I, (n, n′) ∈ N(6.19)

Os modelos em PLIM e PLR formulados na linguagem OPL Studio 3.6.1 sao

interconectados atraves de modulos de comunicacao entre os dois otimizadores, o

ILOG CPLEX3 e ILOG Solver (ILOG, 2001). A principal vantagem da utilizacao do

modelo PLIM e a relaxacao linear das variaveis, que introduz limites nas variaveis em

cada no da arvore de busca. Enquanto PLR tem a vantagem de poder expressar seus

procedimentos de busca (ILOG, 2002a). Esta integracao se da atraves de algumas

3O software ILOG CPLEX contem rotinas otimizadoras que permitem resolver diversos pro-blemas de programacao matematica: problemas de programacao linear, inteira, inteira mista equadratica, com milhoes de restricoes e variaveis contınuas e, dependendo da estrutura do pro-blema, com um numero elevado de variaveis inteiras e/ou binarias.


palavras-chave, no caso especıfico e utilizado o comando with linear relaxation

na funcao objetivo do modelo hıbrido, conforme ilustrado na expressao 6.20.

minimize with linear relaxation

=∑r∈R

∑i∈(Ia

⋃Ib)

∑n∈N

CN · (TFr,i,n − TSr,i,n)

+∑r∈R

∑i∈(Ia

⋃Ib)

∑n∈N

∑h∈HP

CHPh · (Xr,i,n,h)

+∑r∈R

∑i∈(Ia

⋃Ib)

∑n∈N

∑f∈HF

CFi,f · (Fr,i,n,f )

(6.20)

6.2.1 Heurıstica na Geracao da Arvore de Busca

Segundo Smith (1995) varias heurısticas tem sido desenvolvidas para a ordem

de selecao de variaveis. Sendo que a mais comum e baseada no princıpio falhar-

primeiro (fail-first). Este princıpio pode ser melhor entendido considerando a se-

guinte expressao: para ter sucesso, tentar primeiro onde e mais provavel falhar

(Haralick & Elliott, 1980). Com isto, pretende-se selecionar em primeiro lugar a

variavel que possui o menor numero de alternativas possıveis. Assim, a ordem de

instanciacao das variaveis e, em geral, diferente em diferentes ramificacoes da arvore

de busca, sendo determinada dinamicamente. O que se pretende e que, num dado

momento, se a solucao parcial nao originar uma solucao completa, entao e melhor

obter essa conclusao o mais cedo possıvel. A Figura 6.1 mostra como a ordem de se-

lecao de variaveis modifica a forma de uma arvore de busca. Se forem escolhidos em

primeiro lugar, valores para x1 e so depois valores para x2, entao a arvore de busca

tem uma dada forma particular. Caso contrario, se forem escolhidos em primeiro

lugar valores para x2 e so depois para x1, entao se obtem uma arvore de busca com

uma forma diferente. E possıvel, ainda, verificar se os domınios das variaveis pos-

suem tamanhos diferentes, nesse caso a ordem de selecao de variaveis pode mudar

o numero de nos internos da arvore. Para minimizar o numero de nos, as variaveis

que possuem os menores domınios devem ser tentadas primeiro. Quando as variaveis

possuem o mesmo numero de valores no domınio usa-se uma outra heurıstica para

desempatar. Esta baseia-se tambem no princıpio de explorar em primeiro lugar os

6.2. Modelo Hıbrido 95

casos mais difıceis, tratando inicialmente a variavel que participa no maior numero

de restricoes.

x1

x2x2

0 1

110 02 2 33

x2

x1 x1 x1x1

10 2 3

10 10 10 10

Figura 6.1: Ordem de selecao das variaveis.

Depois da selecao da variavel segue-se a escolha de um valor do domınio atual

para instancia-la. Segundo Smith (1995), a ordem pela qual e feita a escolha dos

valores pode ter um impacto substancial no tempo gasto para encontrar uma solucao.

Percebe-se, no entanto, que se todo o espaco de busca tem de ser explorado entao

a ordenacao de valores e indiferente. O uso de uma diferente ordenacao de valores

provoca um rearranjo das ramificacoes que surgem a partir de cada no da arvore

de busca. Este rearranjo constitui uma vantagem se for possıvel assegurar que uma

dada ramificacao permite encontrar uma solucao mais rapidamente do que outra.

No melhor caso, se o modelo possui pelo menos uma solucao, e se o valor correto

para cada variavel e selecionado, entao a solucao e encontrada sem necessidade de

retrocesso. A figura 6.2 mostra como a ordenacao de valores do domınio pode mudar

a ordem de visita aos nos conforme a figura 6.1.

O comando utilizado, em OPL Studio 3.6.1 (ILOG, 2002a), para gerar uma

arvore de busca a partir de uma variavel, previamente escolhida, e o generate. Deste


x1

x2x2

1 0

312 10 0 23

Figura 6.2: Ordem de selecao dos valores do domınio.

modo, para escolha desta variavel foram testadas algumas variaveis que estivessem no

maior numero de restricoes possıveis e com menores domınios, para serem tentadas

em primeiro lugar. A geracao da arvore de busca a partir de algumas variaveis esta

apresentado nas expressoes 6.21, 6.22, 6.23 e 6.24. A variavel que apresentou

o melhor desempenho (conforme secao 7.3) em relacao a obtencao de respostas o

mais breve possıvel foi a RDr,i,n, expressao 6.22. No capıtulo 7 (secao 7.3) sao

apresentados os resultados computacionais obtidos em funcao destas variaveis.

generate (RRr,i,n) ∀r ∈ R, i ∈ Ia, n ∈ N (6.21)

generate (RDr,i,n) ∀r ∈ R, i ∈ Ib, n ∈ N (6.22)

generate (FRr,n) ∀r ∈ R, n ∈ N (6.23)

generate (FDr,n) ∀r ∈ R, n ∈ N (6.24)



Neste capıtulo foram exploradas a PLR e a modelagem Hıbrida (PLIM-PLR).

A principal motivacao destes modelos foi a reducao do tempo computacional (ver

capıtulo 7, secao 7.3)). Em especial o modelo hıbrido apresenta os melhores resulta-

dos. A interferencia no processo de busca e propagacao de restricoes foi fundamental

na busca por solucoes o mais breve possıvel. Em termos praticos, o especialista da

TE pode se basear nas solucoes encontradas para formalizar o scheduling, mesmo

que a solucao otima nao tenha sido obtida ate o tempo de 1 hora4.

4Tempo em que o especialista pode aguardar por uma solucao para o problema.


Capıtulo 7

Resultados

Este capıtulo apresenta os resultados computacionais obtidos, em ordem cro-

nologica, com os modelos desenvolvidos nos capıtulos 4, 5 e 6 respectivamente. As

implementacoes e a resolucao de instancias do problema modeladas nos capıtulos 4

e 5 foram realizadas em duas ferramentas comerciais o solver LINGO Extended 8.0

(Lindo, 1999) e o ILOG OPL Studio 3.6.1 (ILOG, 2002b), para o capıtulo 6 somente

o ILOG OPL Studio 3.6.1 (ILOG, 2002b) foi utilizado. Para padronizar os resulta-

dos todas as instancias do problema foram resolvidas em uma mesma plataforma

computacional: Pentium IV, 2.8GHz, 1Gbyte RAM.

Para permitir uma comparacao entre os modelos desenvolvidos foram feitas

algumas consideracoes:

• O numero de estados de recebimento foi fixado em 2 (no = 2), ou seja, cada

recurso r pode receber de duas origens distintas.

• O numero de estados de envio foi fixado em 2 (nd = 2), ou seja, cada recurso

r pode enviar para dois destinos distintos.

• O numero total de recursos (nr) e de eventos (nn) depende da instancia que

sera resolvida, conforme as tabelas 7.1, 7.2 e 7.3.

• O horizonte de scheduling considerado depende da instancia que sera resolvida,

conforme as tabelas 7.1, 7.2 e 7.3.

100 Capıtulo 7. Resultados

• O numero de horarios de ponta nhp depende do horizonte de scheduling con-

siderado, conforme as tabelas 7.1, 7.2 e 7.3.

• O numero de intervalos utilizados para representar as variacoes da variavel

turno depende do horizonte de scheduling, conforme as tabelas 7.1, 7.2 e 7.3.

• As demandas de recebimento DRi e de envio DDi dependem da instancia que

sera resolvida, conforme as tabelas 7.1, 7.2 e 7.3.

• O volume util dos recursos e 2600m3 (V Ur = 2600 ∀r).

• O custo da energia eletrica no horario de ponta e considerado quatro vezes

maior do que no horario normal.

Tabela 7.1: Dados de entrada da instancia 1.H = 50 nr = 4 ni = 5 nn = 4 nhp = 2 nhf = 13

Estado Inicial (n = 1) i = 1 i = 2 i = 3 i = 4 i = 5RRr,i,n r = 1 r = 4RDr,i,n r = 2FRr,n r = 3FDr,n

DRi(m3) 7800 10400

DDi(m3) 7800 10400

FMAX(m3/h) 200 430 260 370


Estado Inicial (n = 1) i = 1 i = 2 i = 3 i = 4 i = 5RRr,i,n r = 1 r = 4RDr,i,n r = 2 r = 5FRr,n r = 3FDr,n

DRi(m3) 13000 10400

DDi(m3) 10400 10400

FMAX(m3/h) 200 430 260 370

7.1. Resultados Computacionais do Capıtulo 4 101


Estado Inicial (n = 1) i = 1 i = 2 i = 3 i = 4 i = 5RRr,i,n r = 1 r = 4RDr,i,n r = 2 r = 5FRr,n r = 3FDr,n r = 6

DRi(m3) 10400 13000

DDi(m3) 13000 13000

FMAX(m3/h) 200 430 260 370

7.1 Resultados Computacionais do Capıtulo 4

As abordagens PLIM com representacao contınua do tempo tendem a possuir

uma DI maior quando comparadas a representacao discreta. Em funcao disso, e

indispensavel buscar formulacoes que possuam uma DI reduzida, como aquela apre-

sentada no capıtulo 4. Para verificar o comportamento da DI associado ao tempo

computacional foi resolvida a instancia 1, variando-se apenas o horizonte de schedu-

ling, de 411 ate 50 horas, os resultados estao na tabela 7.4 e na figura 7.1. Atraves da

observacao dos resultados da tabela 7.4 e da figura 7.1 percebe-se um crescimento

do tempo computacional em relacao ao horizonte de scheduling. Esta importante

constatacao foi utilizada no pre-processamento dos dados (ver secao 4.5). Outra

constatacao e a relacao da DI com o tempo computacional, como ja comentado

existe uma tendencia de crescimento com o horizonte de scheduling verificada na

figura 7.1, porem em H = 45 e H = 47 percebe-se um crescimento maior do tempo,

isto ocorre em funcao das DI’s associadas DI = 35, 17% e DI = 36, 47% respecti-

vamente serem maiores. Ainda em relacao a DI na tabela 7.5 sao apresentados os

resultados da DI para as instancias 1, 2 e 3.

Os demais resultados computacionais das instancias 1, 2 e 3 estao apresenta-

dos na tabela 7.6. Fica evidente a explosao do tempo computacional em funcao

da entrada de dados, ou seja, para instancias maiores o tempo computacional fica

1Este valor e o tempo mınimo (Hmin) para realizar todas as operacoes dentro do horizonte descheduling.


Tabela 7.4: Tempo computacional X diferenca de integralidade.H zo zr DI = |(zo− zr)/zo| (%) tempo computacional (s)41 157 136,69 12,93 1742 157 143,01 8,91 5843 153 139,74 8,67 8644 145 125,43 13,49 8845 145 196 35,17 29946 145 125,01 13,78 14547 145 92,11 36,47 42248 141 168,55 19,53 27549 141 120,45 14,57 85050 137 124,05 9,45 696

Plan1 Gráfico 3

Page 1

0

5

10

15

20

25

30

35

40

41 42 43 44 45 46 47 48 49 50

Horizonte de scheduling (horas)

Dif

eren

ça d

e in

teg

ralid

ade

0

100

200

300

400

500

600

700

800

900

Tem

po

co

mp

uta

cio

nal

Diferença de integralidade (%) Tempo computacional (s)

Figura 7.1: Tempo computacional X diferenca de integralidade.

Tabela 7.5: Comparativo da DI em funcao da instancia.zo zr DI = |(zo− zr)/zo| (%)

instancia 1 137 124,05 9,45instancia 2 173 157 9,2instancia 3 208 167 19,7


proibitivo. Este crescimento ocorre pelo aumento das variaveis binarias (ver secao

4.4).

Tabela 7.6: Resultados computacionais do capıtulo 4.Instancia 1 Instancia 2 Instancia 3

numero total de variaveis 2190 4206 8744numero de variaveis binarias 1180 2646 5612numero de restricoes 6993 14121 30049numero de iteracoes 907060 > 2.106 > 10.106

tempo computacional (s) 696 12520 *custo ($) 137 173 208* solucao encontrada ate 24 h

Para destacar a influencia da modelagem do custo eletrico diferenciado sao

apresentados os resultados da instancia 2 (ver tabela 7.2). Na figura 7.2 e apresen-

tado o resultado do modelo PLIM (sem o custo eletrico) e na figura 7.3 o resultado

da modelo PLIM (com o custo eletrico). Nestas figuras, os horarios de ponta sao

destacados com um retangulo tracejado. Fica evidente na figura 7.2 que muitas das

operacoes sao realizadas dentro do horario de ponta, o que nao ocorre na figura 7.3

onde e possıvel visualizar que as operacoes ocorrem fora do horario de ponta, com

excecao da operacao de recebimento da“Origem 1”, que representa um processo con-

tınuo, nao podendo deste modo ser interrompido, as demais operacoes nao ocorrem

neste perıodo.

7.1.1 Comentario dos Resultados

O problema de scheduling da TE, modelado em PLIM com tempo contınuo, foi

resolvido no solver LINGO Extended 8.0 (Lindo, 1999) e no ILOG OPL Studio 3.6.1

(ILOG, 2002b). Os resultados apresentados nas tabelas 7.6 sao referentes ao ILOG

OPL Studio 3.6.1 (ILOG, 2002b). Cabe destacar que, nas instancias resolvidas, o

ILOG OPL Studio 3.6.1 (ILOG, 2002b) foi em media tres vezes mais rapido do que

o LINGO Extended 8.0 (Lindo, 1999).

Na busca por solucoes, foram testadas varias configuracoes de dados em que se

variava apenas o horizonte de scheduling, nelas foi possıvel observar a relacao direta

do horizonte com o crescimento do tempo computacional.


horas65605550454035302520151050

tanques

Origem 1

Origem 2

Destino 1

Destino 2

HP1 HP2

Figura 7.2: Carta de gantt do modelo sem custo eletrico.

horas65605550454035302520151050

tanques

Origem 1

Origem 2

Destino 1

Destino 2

HP1 HP2

Figura 7.3: Carta de gantt do modelo com custo eletrico.


Por fim, os resultados demonstram o potencial envolvido na modelagem das

operacoes de TE de uma refinaria de petroleo. O modelo permite a identificacao de

novos pontos de operacao para o sistema, minimizando os custos.


Para determinar os parametros que serao inseridos na funcao objetivo do mo-

delo PLIM sao necessarios alguns passos. Inicialmente a area de GLP e definida

(instancia 2, ver tabela 7.2) como problema a ser resolvido. Nesta area as variaveis

fuzzy de entrada Dificuldade e Manobras possuem os atributos variando em fun-

cao da operacao (recebimento i ∈ Ia ou envio i ∈ Ib), para se obter uma saıda crisp

foram consideradas as entradas crisp conforme ilustrado na tabela 7.7. A variavel

fuzzy Turno tem seus atributos variando em funcao do horizonte de scheduling, ou

seja, tera 17 variacoes em 66 horas (ver pagina 77).

Tabela 7.7: Atributos das variaveis para area de GLP.Variaveis

Estado Dificuldade Manobrasi = 1 0,2 0,3i = 2 0,9 0,9i = 3 0,5 0,8i = 4 0,5 0,4

A tabela 7.8 ilusta a variacao do custo de troca em funcao das operacoes

(i ∈ Ia ∪ Ib) e dos tempos de inıcio (TSr,i,n) das operacoes. O custo de troca e

formado por uma matriz com 68 (17x4) elementos (parametros).

Para visualizar a influencia dos parametros do custo de troca, obtido pelo sis-

tema fuzzy, no modelo de scheduling, sao apresentados os resultados da instancia 2

(ver tabela 7.2), com e sem a presenca do custo de troca. Na figura 7.4 e apre-

sentada uma carta de gantt do modelo do capıtulo 4, ou seja, sem os custos de

troca obtidos pelo sistema fuzzy das operacoes de transferencia e estocagem de uma

refinaria. Na figura 7.5 a carta de gantt apresenta a influencia dos custos de troca.

E possıvel observar atraves das cartas de gantt uma alteracao no scheduling a ser

efetuado, principalmente com relacao as tarefas entre turnos. No modelo onde nao


Tabela 7.8: Custo de troca.Estados (i ∈ Ia ∪ Ib)

Faixa de horario (h) i = 1 i = 2 i = 3 i = 40 ≤ TSr,i,n < 6, 5 0, 25 0, 75 0, 75 0, 49

6, 5 ≤ TSr,i,n < 7, 5 0, 75 0, 98 0, 75 0, 757, 5 ≤ TSr,i,n < 14, 5 0, 1 0, 49 0, 25 0, 2514, 5 ≤ TSr,i,n < 15, 5 0, 75 0, 98 0, 95 0, 7515, 5 ≤ TSr,i,n < 22, 5 0, 1 0, 49 0, 5 0, 2522, 5 ≤ TSr,i,n < 23, 5 0, 95 0, 98 0, 95 0, 9823, 5 ≤ TSr,i,n < 30, 5 0, 25 0, 75 0, 75 0, 4930, 5 ≤ TSr,i,n < 31, 5 0, 75 0, 98 0, 75 0, 7531, 5 ≤ TSr,i,n < 38, 5 0, 1 0, 49 0, 25 0, 2538, 5 ≤ TSr,i,n < 39, 5 0, 75 0, 98 0, 95 0, 7539, 5 ≤ TSr,i,n < 46, 5 0, 1 0, 49 0, 5 0, 2546, 5 ≤ TSr,i,n < 47, 5 0, 95 0, 98 0, 95 0, 9847, 5 ≤ TSr,i,n < 54, 5 0, 25 0, 75 0, 75 0, 4954, 5 ≤ TSr,i,n < 55, 5 0, 75 0, 98 0, 75 0, 7555, 5 ≤ TSr,i,n < 62, 5 0, 1 0, 49 0, 25 0, 2562, 5 ≤ TSr,i,n < 63, 5 0, 75 0, 98 0, 95 0, 7563, 5 ≤ TSr,i,n ≤ 66 0, 1 0, 49 0, 5 0, 25

sao considerados os custos de troca ocorrem cinco operacoes a serem realizadas en-

tre turnos, destacadas com um cırculo na figura 7.4. A proposito, no modelo com

custos de troca ocorre somente uma operacao, destacada com um cırculo na figura

7.5. Esta ocorrencia e devido ao fato do processo de recebimento da “Origem 1” ser

contınuo, nao podendo deste modo ser alterado.

Os resultados computacionais das instancias 1, 2 e 3 estao apresentados na

tabela 7.9. Fica evidente a explosao do tempo computacional em funcao da entrada

de dados, ou seja, para instancias maiores o tempo computacional fica proibitivo.

Para a instacia 3, nenhuma solucao viavel foi obtida ate o tempo de 1 hora.


Os resultados comprovaram a adequacao de sistemas fuzzy no problema em

questao por representarem bem uma ponte de ligacao entre o simbolico e o numerico

atraves de regras linguısticas. Foi possıvel observar atraves das cartas de gantt que

os custos de troca influenciam o scheduling das atividades.


horas65605550454035302520151050

tanques

Origem 1

Origem 2

Destino 1

Destino 2

HP1 HP2TR1 TR3 TR1 TR2 TR3 TR1 TR2TR2

Figura 7.4: Carta de gantt do modelo sem custo de troca.

horas65605550454035302520151050

tanques

Origem 1

Origem 2

Destino 1

Destino 2

HP1 HP2TR1 TR3 TR1 TR2 TR3 TR1 TR2TR2

Figura 7.5: Carta de gantt do modelo com custo de troca.


Tabela 7.9: Resultados computacionais do capıtulo 5.Instancia 1 Instancia 2 Instancia 3

numero total de variaveis 5786 9827 16838numero de variaveis binarias 3580 6396 11012numero de restricoes 15393 27246 48949numero de iteracoes 969628 > 2.106 > 2.106

tempo computacional (s) 1141 1h(*) **custo ($) 154,6 230,9 *** primeira solucao viavel** nenhuma solucao viavel ate 1h

A modelagem do sistema fuzzy foi realizada no software MATLAB, mais espe-

cificamente na ferramenta chamada sistema de inferencia fuzzy (MATLAB, 2006).

Como saıda crisp deste sistema foi obtida uma matriz custo de troca. A matriz custo

de troca foi entao inserida no modelo PLIM do capıtulo 4. O modelo PLIM resul-

tante, foi implementado no solver LINGO Extended 8.0 (Lindo, 1999) e no ILOG

OPL Studio 3.6.1 (ILOG, 2002b). Cabe destacar que os resultados apresentados na

tabela 7.9 sao referentes ao ILOG OPL Studio 3.6.1 (ILOG, 2002b).


Existe por parte de quem executa o scheduling uma exigencia em termos de

tempo computacional em que o mesmo pode aguardar para obter uma resposta. Em

funcao disto, na resolucao das instancias do problema, o tempo computacional e

limitado a 1 hora. Como em alguns casos nao foi possıvel obter-se a solucao otima

ate este perıodo, foram avaliados os tempos para encontrar a primeira solucao viavel

e tambem a solucao encontrada ate 1 hora.

7.3.1 Modelo em PLR

Os resultados computacionais das instancias 1, 2 e 3, a partir do modelo em

PLR, estao apresentados na tabela 7.10. Em relacao aos resultados obtidos com

o modelo PLIM mais custo de troca (ver tabela 7.9), o tempo computacional fica

menor para os resultados obtidos a partir do modelo PLR. Porem para a instancia


3, nenhuma solucao viavel foi obtida ate o tempo de 1 hora.

Tabela 7.10: Resultados computacionais a partir do modelo em PLR.Instancia 1 Instancia 2 Instancia 3

numero total de variaveis 4480 8000 13320numero de restricoes 5989 11360 19925tempo computacional - 1a solucao (s) 3 3 **custo ($) 1a solucao 170,6 225 **custo ($) solucao ate 1 hora 154,6(*) 213 *** solucao otima em 1240s** nenhuma solucao viavel ate 1h

7.3.2 Modelo Hıbrido

Com a finalidade de reduzir ainda mais o tempo computacional e, alem disso,

resolver instancias maiores do problema, chegou-se ao modelo hıbrido. Este modelo

agrega inicialmente recursos desenvolvidos para problemas de scheduling atraves do

ILOG Scheduler (ILOG, 2001). Em seguida e feita a integracao PLIM-PLR, neste

caso algumas variaveis/restricoes sao resolvidas pelo ILOG Solver, outras pelo ILOG

CPLEX, contendo algumas variaveis que integram os modelos. Por fim, a insercao de

heurısticas na geracao da arvore de busca foi fundamental para encontrar solucoes

viaveis o mais breve possıvel, como pode ser observado a seguir.

Utilizacao de heurısticas

Para avaliar a influencia da geracao da arvore de busca em funcao do tempo

computacional foram avaliadas as variaveis binarias presentes no ciclo operacional,

ou seja, RRr,i,n, RDr,i,n, FRr,n e FDr,n. Os resultados ilustrados na tabela 7.11

comprovam a influencia direta da heurıstica na geracao da arvore de busca, para as

instancias avaliadas, sendo que a variavel RDr,i,n apresentou o melhor desempenho.

Este fato justifica-se por esta variavel estar presente no maior numero de restricoes

e ainda possuir domınio reduzido.

Os resultados computacionais das instancias 1, 2 e 3, a partir do modelo hı-

brido, estao apresentados na tabela 7.12. Em relacao aos resultados obtidos com


Tabela 7.11: Geracao da arvore de busca.Tempo computacional da 1a solucao viavel (s)

generate Instancia 1 Instancia 2 Instancia 3generate(RRr,i,n) 3 9 290generate(RDr,i,n) 2 10 20generate(FRr,n) 4 117 1850generate(FDr,n) 2 14 710

os modelos anteriores (ver tabelas 7.9 e 7.10), o tempo computacional fica me-

nor, particularmente para encontrar uma solucao viavel. Cabe ressaltar que, embora

encontre solucoes viaveis rapidamente o modelo apresenta dificuldade em provar a

otimalidade da solucao.

Tabela 7.12: Resultados computacionais a partir do modelo hıbrido.Instancia 1 Instancia 2 Instancia 3

numero total de variaveis (PLIM) 1121 1676 2413numero total de variaveis (PLR) 5232 8875 14580numero de restricoes (PLIM) 357 580 797numero de restricoes (PLR) 7477 14685 25685tempo computacional - 1a solucao (s) 2 10 20tempo computacional - sol. otima (s) 20 3850 39750custo ($) 1a solucao 167,3 203,8 220,4custo ($) solucao ate 1 hora 154,6 183,8 212,4custo ($) solucao otima 154,6 183,8 208,4


O modelo PLR resultante, foi implementado na linguagem ILOG OPL Studio

3.6.1 (ILOG, 2002b), sendo que o otimizador utilizado foi o ILOG Solver (ILOG,

2001). Os resultados apresentados na tabela 7.10 demonstram que a tecnica PLR

utilizada separadamente nao e muito eficiente em termos computacionais. Para su-

prir esta deficiencia chegou-se ao modelo hıbrido (PLIM-PLR). Neste modelo a uti-

lizacao de recursos adicionais do ILOG Scheduler (ILOG, 2001) aliado a relaxacao

linear das variaveis atraves do ILOG CPLEX (ILOG, 2001) e ainda a utilizacao de

heurısticas na geracao da arvore de busca teve um bom desempenho computacional,

conforme apresentado na tabela 7.12.

7.4. Comparativo dos Modelos 111

7.4 Comparativo dos Modelos

A partir dos resultados obtidos, apresentados neste capıtulo, e possıvel fazer

algumas consideracoes em termos comparativos das modelagens desenvolvidas:

• A influencia dos custos na modelagem dos problemas pode ser observada nos

diferentes modelos, evidenciando a importancia de coletar diferentes custos

que melhor representem o problema em questao. Nesse sentido, a consideracao

da variacao do custo eletrico em funcao do horario de ponta (horossazonal) e

a consideracao da mao de obra na execucao das tarefas permitem diminuir as

diferencas entre um modelo teorico e as necessidades praticas.

• Em relacao ao tempo computacional2 de resolucao de instancias do problema,

a modelagem hıbrida apresentou o melhor desempenho computacional.

• Em relacao a modelagem do problema, a abordagem em PLR mostrou-se a

mais simples, sendo que a traducao das restricoes do problema ocorre de modo

natural. Por exemplo, na modelagem em PLIM as expressoes SE-ENTAO

sao feitas com a utilizacao de BIG-M, o que em muitos casos nao e uma tarefa

trivial, as mesmas expressoes escritas em PLR sao feitas atraves de implicacoes

e equivalencias.

• Foi possıvel observar atraves dos modelos desenvolvidos que provar que uma

instancia do problema nao e viavel e normalmente mais oneroso do que encon-

trar alguma solucao a instancia.

• Em relacao as ferramentas comerciais utilizadas para resolver instancias do

problema, o ILOG OPL Studio 3.6.1 (ILOG, 2002b) foi, em media, tres vezes

mais rapido do que o solver LINGO Extended 8.0 (Lindo, 1999).

2Cabe ressaltar que foram mantidos os ajustes padroes nos solvers, para maiores detalhes verILOG (2002b).



As instancias foram definidas a partir de cenarios da TE em refinarias de

petroleo. Como dito na secao 4.1 uma refinaria tıpica possui aproximadamente

100 tanques. Estes sao divididos em areas, sendo que os tanques sao dedicados por

produtos. Deste modo, o scheduling da TE ocorre por areas para um horizonte de 2

a 4 dias. Uma importante constatacao que foi verificada e que existem mais tanques

do que o necessario em funcao das cargas de petroleo processadas. Apenas para

exemplificar, a REPAR3 que foi projetada para processar uma carga de 24000m3/dia

e, atualmente, ja processa 32000m3/dia e, no entanto, nao foram construıdos mais

tanques. Nesta refinaria a area de GLP possui sete esferas de propano. Considerando-

se as operacoes de recebimento e de envio envolvidas com as respectivas vazoes e

volumes das esferas verifica-se que com quatro esferas4 de propano e possıvel realizar

todas as operacoes envolvidas. Entao, mesmo que a carga desta refinaria aumente,

ainda assim, existe uma folga em termos de tancagem que comporta as variacoes

sem a necessidade de construcao de novas esferas.

3Refinaria Presidente Getulio Vargas, localizada em Araucaria, Parana.4Nesta avaliacao nao foi considerada a situacao de recebimento de produto fora de especificacao,

nem esfera em manutencao.

Capıtulo 8

Conclusoes

A possibilidade de utilizacao cada vez maior de modelos de otimizacao em pro-

blemas do mundo real evidencia a importancia do desenvolvimento de novas aborda-

gens para modelagem destes problemas. Dentro deste contexto estao os problemas

de scheduling dos recursos de estocagem em refinarias de petroleo. Este problema

consiste basicamente na determinacao da melhor polıtica de utilizacao dos tanques

de armazenamento disponıveis. O cenario base de estudo utilizado nesta tese envolve

a TE de diferentes derivados de petroleo. Para a operacao do sistema de estocagem

(armazenamento), o recebimento e o envio de produto dos tanques implicam em

varias decisoes a serem tomadas pelo programador (especialista) da TE. Do ponto

de vista da otimizacao da planta, a tomada de decisao por parte do programador

e dificultada pela complexidade e dinamica do sistema. Cabe destacar que na pra-

tica industrial esta atividade e realizada por um especialista da TE, baseado na

experiencia profissional com a utilizacao de calculos manuais. Deste modo, torna-se

justificavel a elaboracao de modelos, como os desenvolvidos nesta tese, que auxiliem

a tomada de decisao operacional para o problema de scheduling.

No capıtulo 2 foi feita uma revisao bibliografica sobre diversos conceitos ine-

rentes ao scheduling em refinarias de petroleo. Neste capıtulo, inicialmente sao des-

tacadas as caracterısticas dos problemas e dos modelos de scheduling encontrados.

A seguir foi apresentada uma divisao dos problemas de scheduling em refinarias de

petroleo, relacionada aos trabalhos cientıficos nesta area. Embora existam alguns

modelos desenvolvidos para satisfazer as caracterısticas dos problemas de scheduling

114 Capıtulo 8. Conclusoes

em refinarias de petroleo, conforme apresentados na secao 2.5, estes deixam algu-

mas lacunas que foram identificadas atraves da revisao bibliografica apresentada no

capıtulo 2. Nesse sentido, esta tese foi desenvolvida, para preencher algumas des-

tas lacunas relacionadas aos modelos de otimizacao, para transferencia e estocagem

nas refinarias de petroleo, com o objetivo principal de reduzir as diferencas entre os

modelos teoricos e as necessidades praticas.

No capıtulo 3 foi feita uma revisao bibliografica sobre os metodos utilizados

para modelar e resolver os problemas de scheduling. Neste capıtulo, sao apresentadas

as tecnicas de otimizacao, bem como os procedimentos auxiliares empregados nos

metodos de solucao destacados pela literatura da area. Os principais conceitos de

PLIM e PLR sao apresentados e ainda sao feitas algumas consideracoes sobre os me-

todos hıbridos, particularmente PLIM-PLR. Este ultimo tem recebido um destaque

na literatura, sendo apontado como uma tendencia na modelagem de problemas de

scheduling. Por fim, sao apresentados os conceitos basicos dos sistemas fuzzy, que sao

utilizados nesta tese na modelagem de variaveis linguısticas do problema tratado.

Os modelos desenvolvidos nesta tese tratam da minimizacao dos custos ope-

racionais. Embora muitas vezes uma minimizacao destes custos nao seja evidente, e

possıvel uma comprovacao atraves da analise de uma situacao pratica. Por exemplo,

um scheduling realizado manualmente, por um especialista, nao permite verificar

o comportamento das restricoes associadas a dinamica do sistema. Neste caso, um

scheduling inadequado pode ser inviavel do ponto de vista operacional ou ainda in-

serir gargalos no sistema. Os gargalos implicam em custos adicionais que poderiam

ser evitados.

Os modelos desenvolvidos nesta tese podem ser utilizados como base para um

sistema computacional, onde o operador da planta real possa experimentar seus pla-

nos de recebimento e de envio e encontrar o scheduling mais adequado, de modo a

detectar (e corrigir) possıveis problemas que venham a ser encontrados. Pela com-

plexidade do modelo, fica claro que o scheduling nao e trivial e a possibilidade de

visualizacao grafica, atraves de cartas de gantt, facilita muito o teste dos planos.

Alem disto, o proprio processo de modelagem permite a deteccao dos pontos mais

crıticos do sistema como gargalos.

8.1. Contribuicoes 115

Existe ainda a possibilidade dos modelos serem utilizados numa fase de projeto

ou ampliacao da instalacao. De posse das variaveis de entrada, como vazoes envol-

vidas e volume dos tanques, e possıvel determinar o numero mınimo de recursos

(tanques) a serem construıdos. Cabe ressaltar que a reducao de um tanque pode

representar uma economia de alguns milhares de reais.

A seguir sao apresentadas as principais contribuicoes desta tese.

8.1 Contribuicoes

Em problemas de scheduling modelados em PLIM dois aspectos devem ser

levados em conta na elaboracao de modelos: a representacao do tempo e a estrutura

do modelo. Nesse sentido, no capıtulo 4 e proposta uma modelagem PLIM com

representacao contınua do tempo e estrutura do modelo baseada nos estados dos

tanques de estocagem.

A representacao contınua do tempo foi escolhida por gerar um numero menor

de variaveis de decisao (binarias) em relacao a representacao discreta do tempo, per-

mitindo deste modo explorar melhor as particularidades do problema. Porem, esta

representacao tende a gerar formulacoes com DI maior em relacao a representacao

discreta do tempo. Para reduzir esta diferenca e proposta uma representacao do

problema baseadas nos estados possıveis dos recursos (tanques) e do ciclo operaci-

onal envolvido na TE. A representacao dos estados possıveis dos tanques, atraves

de variaveis binarias, permite determinar as operacoes de envio e recebimento de

diferentes tanques. Esta abordagem mostrou-se eficaz por apresentar uma DI redu-

zida, como pode ser observado no capıtulo 7 (secao 7.1), considerando-se o fato do

modelo possuir uma representacao contınua do tempo.

Ainda no capıtulo 4, e apresentada uma modelagem para o custo eletrico di-

ferenciado. A variacao do custo da energia eletrica (ver pagina 62) e representada

na funcao objetivo do modelo PLIM acrescido a outros fatores. Em problemas de

scheduling em que a tarifacao de energia eletrica esta sujeita a uma tarifacao ho-

rossazonal, esta variacao do custo deve ser considerada na modelagem do problema,


o que normalmente nao e verificado nos modelos existentes em PLIM com tempo

contınuo. Para suprir esta lacuna, e proposta uma modelagem que contempla a ta-

rifacao horossazonal. Atraves da analise dos resultados no capıtulo 7 (secao 7.1)

percebe-se a influencia deste custo no scheduling resultante. Cabe ressaltar que este

custo dificilmente e considerado em um scheduling feito manualmente, porque sao

muitas variaveis envolvidas, sendo imprescindıvel um modelo de otimizacao para

faze-lo.

Uma das principais dificuldades para implementacao de modelos de schedu-

ling em ambientes industriais (ver pagina 2) e a divergencia entre as pessoas que

desenvolvem um modelo e aquelas que o aplicam efetivamente. Para suprir esta

lacuna, no capıtulo 5, e apresentado um sistema fuzzy, modelado em MATLAB

(MATLAB, 2006), utilizado para representar algumas variaveis linguısticas (Difi-

culdade, Manobras e Turno) que sao responsaveis por considerar aspectos da mao-

de-obra na execucao do scheduling. Estas variaveis foram modeladas num sistema

fuzzy, tendo como variavel de saıda o custo de troca. Este custo e inserido como

uma matriz de parametros na funcao objetivo do modelo PLIM do capıtulo 4. Os

resultados apresentados no capıtulo 7 (secao 7.2) demonstram a viabilidade de

utilizacao de sistemas fuzzy na modelagem das variaveis linguısticas do problema

tratado. Cabe destacar que de nada adianta fornecer um scheduling teorico se na

execucao do mesmo as operacoes serao atrasadas ou adiantadas por uma questao

de conveniencia operacional. Tendo como consequencia a insercao de gargalos no

sistema.

Outra dificuldade apresentada para implementacao de modelos de scheduling

em ambientes industriais (ver pagina 2) e a questao do tempo computacional gasto

para resolver instancias do problema. Pelos resultados obtidos no capıtulo 7 (secoes

7.2 e 7.3) percebe-se que a modelagem PLIM com tempo contınuo (capıtulos 4 e 5),

dependendo da entrada de dados, apresenta um tempo computacional elevado, em

alguns casos e inviavel esperar por uma resposta. Para suprir esta lacuna e proposto

no capıtulo 6 uma estrutura hıbrida (PLIM e PLR) que apresenta resultados (capı-

tulo 7, secao 7.3) num tempo computacional inferior. Esta modelagem realizada na

linguagem OPL Studio 3.6.1 (ILOG, 2002b) permite explorar varias funcionalidades

8.2. Trabalhos Futuros 117

desenvolvidas pela ferramenta especificamente para problemas de scheduling.

Ainda no capıtulo 6, e proposta uma heurıstica utilizada na geracao da arvore

de busca, ou seja, no sentido de orientar o processo de propagacao de restricoes. Com

base nas variaveis do modelo foi realizada uma analise para identificar em primeiro

lugar a variavel que possui o menor numero de alternativas, ou seja, menor domınio

e ainda selecionar em primeiro lugar a variavel que participa no maior numero de

restricoes. Os resultados apresentados no capıtulo 7 (secao 7.3) demonstram a efi-

ciencia da utilizacao destas heurısticas. Atraves da analise destes resultados pode-se

concluir que a ordem pela qual a instanciacao das variaveis do problema sao escolhi-

das influencia significativamente nao so a qualidade das solucoes como o tempo de

processamento necessario para obte-las. Nesse sentido, na modelagem do problema

(estrutura do modelo), deve-se buscar variaveis que possuam um domınio reduzido

e ainda estejam presentes no maior numero possıvel de restricoes.

8.2 Trabalhos Futuros

Este trabalho apresenta alguns resultados que podem servir como base para

utilizacao de outras metodologias na resolucao de problemas de scheduling dos recur-

sos de estocagem. A seguir sao apresentadas algumas sugestoes de trabalhos futuros:

• Nesta tese o foco de modelagem do scheduling foi a TE, entao os modelos

desenvolvidos podem ser aplicados nas diferentes areas de estocagem de pro-

dutos (conforme secao 4.1), porem como pode ser observado na secao 2.4

o scheduling das refinarias de petroleo pode ser dividido em outros nıveis de

abstracao, envolvendo modos de operacao das unidades de processo, polidutos,

terminais e refinarias (ver trabalhos na secao 2.5). Deste modo, a sugestao ini-

cial e integrar os diferentes modelos com o objetivo de ajustar inconsistencias

tidas como premissas de modelagem nos modelos desenvolvidos. Sendo que o

modelo resultante utilizaria somente as variaveis comuns dos demais modelos.

• Os modelos apresentados foram implementados em solvers numa plataforma

com apenas um processador. Deste modo, fica uma sugestao de resolver ins-


tancias do problema em plataformas com mais de um processador. Ou ainda

em sistemas computacionais de 64 bits.

• Com relacao aos modelos desenvolvidos, eles podem servir de base para mo-

delagens do mesmo problema utilizando metaheurısticas como, por exemplo,

algoritmos geneticos, busca tabu e simulated annealing. Alem disso, identi-

ficar outros modos de integracao das abordagens citadas, explorando assim

estruturas hıbridas.

• Para utilizacao das modelagens propostas e necessario um conhecimento de

linguagens matematicas para insercao dos modelos obtidos em ferramentas

comerciais. Em funcao disso, fica uma sugestao de transformar os modelos

desenvolvidos em ferramentas operacionais para serem utilizadas por um ope-

rador do sistema real. Estas ferramentas devem fazer a comunicacao entre os

dados da planta, os modelos matematicos e o operador. Como interface de

saıda o operador pode testar o scheduling de modo amigavel.

• Incorporar aos modelos desenvolvidos a etapa de mistura de produtos (blen-

ding), tanto na mistura em linha como em tanque.

• Por fim, os resultados obtidos podem ser refinados ou melhorados, com a in-

corporacao de novas restricoes ou ainda de novos custos aos modelos desenvol-

vidos.

Referencias Bibliograficas

Alle, A. (2003). Tecnicas de programacao mista-inteira aplicadas ao scheduling de

plantas quımicas, Tese de doutorado, Escola Politecnica da Universidade de Sao

Paulo, Sao Paulo, Brasil.

Babuska, R. & Verbruggen, H. B. (1996). An overview of fuzzy modeling for control,

Control Engineering Practice 4: 1593–1606.

Barboza, A. O. (2005). Simulacao e tecnicas da computacao evolucionaria apli-

cadas a problemas de programacao linear inteira mista, Tese de doutorado,

UTFPR/CPGEI, Curitiba, Brasil.

Bartak, R. (2002). Constraint-based scheduling: An introduction to newcomers, Te-

chnical report tr 2002/2, Charles University in Prague, Faculty of Mathematics

and Physics, Prague.

Bartak, R. (2003). Constraint programming: In pursuit of the holy grail.

http://kti.ms.mff.cuni.cz/bartak/constraints. Pagina visitada em 21/08/2003.

Benders, J. F. (1962). Partitioning procedures for solving mixed integer variables

programming problems, Numerische Mathematik 4: 238.

Bockmayr, A. & Kasper, T. (1998). Branch-and-infer: a unifying framework for in-

teger and finite domain constraint programming, INFORMS Journal on Com-

puting 10: 287–300.

Brooke, A. & Meeraus, A. (1982). On the development of a general algebraic mo-

deling system in a strategic planning environment, Mathematical Programming

Study 20: 1–29.

120 REFERENCIAS BIBLIOGRAFICAS

Cafaro, D. C. & Cerda, J. (2004). Optimal scheduling of multiproduct pipeline sys-

tems using a non-discrete milp formulation, Computers & Chemical Engineering

28: 2053–2068.

Castro, H. P. (2001). Utilizacao de algoritmos geneticos para solucao de problema

de programacao de producao de uma refinaria de petroleo, Dissertacao de mes-

trado, Universidade Federal de Santa Catarina, Florianopolis, Brasil.

COPEL (2006). Companhia paranaense de energia. http://www.copel.com. Pagina

visitada em 09/01/2006.

Cotta, C., Aldana, J. F., Nebro, A. J. & Troya, J. M. (1995). Hybridizing genetic

algorithms with branch and bound techniques for the resolution of the tsp,

Artificial Neural Nets and Genetic Algorithms pp. 277–280.

Escudero, L. F., Quintana, F. J. & Salmeron, J. C. (1999). A modeling and an algo-

rithmic framework for oil supply, transformation and distribution optimization

under uncertainly, European Journal of Operational Research 114: 638–656.

Felizari, L. C. (2004). Otimizacao fuzzy aplicada a problemas da producao de deri-

vados em refinarias de petroleo, Dissertacao de mestrado, CEFET-PR/CPGEI,

Curitiba, Brasil.

Focacci, F. (2000). Solving Combinatorial Optimization Problems in Constraint

Programming, PhD thesis, Universita Degli Studi di Ferrara, Ferrara, Italia.

Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability - A Guide

to the Theory of NP-Completeness, W. H. Freeman and Company, New York,

EUA.

Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear pro-

gramming, Bulletin of the American Mathematical Society 64: 275–278.

Grau, R., Graells, J., Corominas, A., Espuna, A. & Puigjaner, L. (1996). Global stra-

tegy for energy and waste analysis in scheduling and planning of multiproduct

batch chemical processes, Computers & Chemical Engineering 20: 853–868.

REFERENCIAS BIBLIOGRAFICAS 121

Grossmann, I. E., van der Heever, S. A. & Harjunkoski, I. (2001). Discrete opti-

mization methods and their role in the integration of planning and scheduling,

Department of chemical engineering, Carnegie Mellon University Engineering,

Pittsburgh, EUA.

Haralick, R. & Elliott, G. (1980). Increasing tree search efficiency for constraint

satisfaction problems, Artificial Intelligence 14: 263–313.

Hentenryck, P. V. & Saraswat, V. (1996). Strategic directions in constraint pro-

gramming, ACM Computing Surveys 28: 701–726.

Ierapetritou, M. G. & Floudas, C. A. (1998a). Effetive continuous-time formulation

for short term scheduling. 1. multipurpose batch process, Industrial & Engine-

ering Chemistry Research 37: 4341–4359.

Ierapetritou, M. G. & Floudas, C. A. (1998b). Effetive continuous-time formulation

for short term scheduling. 2. continuous and semi-continuous process, Industrial

& Engineering Chemistry Research 37: 4360–4374.

Ierapetritou, M. G. & Floudas, C. A. (1999). Effetive continuous-time formula-

tion for short term scheduling. 3. multiple intermediate due dates, Industrial &

Engineering Chemistry Research 38: 3446–3461.

ILOG (2001). Ilog optimization suite white paper - delivering a competitive advan-

tage. http://www.ilog.com/products/optimization/papers.cfm. Pagina visitada

em 19/01/2006.

ILOG (2002a). ILOG OPL Studio 3.6.1 - Language Manual, ILOG Corporation,

France.

ILOG (2002b). ILOG OPL Studio 3.6.1 - User’s Manual, ILOG Corporation, France.

ILOG (2003). http://www.ilog.com/products/cplex/product/hybrid.cfm. Pagina


Jain, V. & Grossmann, I. E. (2001). Algorithms for hybrid milp/cp models for a class

of optimization problems, INFORMS Journal on Computing 13(4): 258–276.


Jia, Z. & Ierapetritou, M. (2003). Efficient short-term scheduling of refinery opera-

tions based on a continuous time formulation, Proceedings of FOCAPO, EUA,

pp. 327–330.

Joly, M. (1999). Tecnicas de otimizacao mista-inteira para o scheduling e gerencia-

mento da producao em refinarias de petroleo, Dissertacao de mestrado, Escola

Politecnica da Universidade de Sao Paulo, Sao Paulo, Brasil.

Kallrath, J. & Wilson, J. M. (1997). Business Optimisation Using Mathematical

Programming, Macmillian Press.

Kondili, E., Pantelides, C. C. & Sargent, R. W. H. (1993). A general algorithm for

short-term scheduling of batch operations - i. milp formulation, Computers &

Chemical Engineering 17(2): 211–227.

Kudva, G., Elkamel, A., Pekny, . J. F. & Reklaitis, G. V. (1994). Heuristic algorithm

for scheduling batch and semi-continuous plants with productions deadlines,

intermediate storage limitations and equipment changeover costs, Computers

& Chemical Engineering 18(9): 859–875.

Land, A. H. & Doig, A. G. (1960). An automatic method for solving discrete pro-

gramming problems, Econometrica 28: 497–520.

Lee, H., Pinto, J. M., Grossmann, I. E. & Park, I. E. (1996). Mixed-integer li-

near programming model for refinery short-term scheduling of crude oil unloa-

ding with inventory management, Industrial & Engineering Chemistry Research

35: 1630–1641.

Lindo (1999). Lingo User’s Guide, Lindo Systems Inc, Chicago (Illinois).

Lindo (2002). The Modeling Language and Optimizer - User’s Guide, Lindo Systems

Inc, Chicago (Illinois).

Magalhaes, M. V. O. (2004). Refinery Scheduling, PhD thesis, Imperial College

London, London, United Kingdom.


Magalhaes, M. V. O., Moro, L. F. L., Smania, P., Hassimoto, M. K., Pinto, J. M. &

Abadia, G. J. (1998). Sipp - a solution for refinery scheduling, NPRA Computer

Conference, San Antonio, EUA.

Magatao, L. (2001). Programacao matematica aplicada a otimizacao das opera-

coes de um poliduto, Dissertacao de mestrado, CEFET-PR/CPGEI, Curitiba,

Brasil.

Magatao, L. (2005). Mixed integer linear programming and constraint logic pro-

gramming: Towards a unified modeling framework, Tese de doutorado, CEFET-

PR/CPGEI, Curitiba, Brasil.

Magatao, L., Arruda, L. & Neves-Jr., F. (2004). A mixed integer programming

approach for scheduling commodities in a pipeline, Computers & Chemical En-

gineering 28: 171–185.

Mas, R. (2001). Otimizacao da programacao de suprimento de petroleo, Disserta-

cao de mestrado, Escola Politecnica da Universidade de Sao Paulo, Sao Paulo,

Brasil.

MATLAB (2006). http://www.mathworks.com/products/fuzzylogic/?bb=1. Pagina


Mendez, C. A. & Cerda, J. (2002). An efficient milp continuous-time formulation

for short-term scheduling of multiproduct continuous facilities, Computers &

Chemical Engineering 26: 687–695.

Mockus, L. & Reklaitis, G. V. (1997). Mathematical programming formulation

for scheduling of batch operations based on nonuniform time discretization,

Computers & Chemical Engineering 21: 1147–1156.

Moro, L. F. L. (2000). Tecnicas de otimizacao mista-inteira para o planejamento e

programacao de producao em refinarias de petroleo, Tese de doutorado, Escola

Politecnica da Universidade de Sao Paulo, Sao Paulo, Brasil.

Moro, L. F. L., Zanin, A. C. & Pinto, J. M. (1998). A planning model for refinery

diesel production, Computers & Chemical Engineering 22: S1039–S1042.


Neiro, S. M. S. & Pinto, J. M. (2004). A general modeling framework for the operati-

onal planning of petroleum supply chains, Computers & Chemical Engineering

28: 871–896.

Nemhauser, G. L. & Wolsey, L. A. (1988). Integer and Combinatorial Optimization,

John Wiley & Sons, New York, EUA.

Orcun, S., Altinel, I. K. & Hortacsu, O. (2001). General continuous time models for

production planning and scheduling of batch processing plants: Mixed integer

linear program formulations and computational issues, Computers & Chemical

Engineering 25: 371–389.

Pantelides, C. C. (1994). Unified frameworks for optimal process planning and

scheduling, FOCAPO II, Colorado, EUA.

Pedrycz, W. & Gomide, F. (1998). An Introduction to Fuzzy Sets: Analysis and

Design, MIT Press, Cambridge, Massachusetts.

Pekny, J. F., Miller, D. L. & Mcrae, G. J. (1990). An exact parallel algorithm

for scheduling when production costs depend on consecutive system states,

Computers & Chemical Engineering 14(9): 1009–1023.

Pekny, J. F. & Zentner, M. G. (1993). Learning to solve process scheduling problems:

The rule of rigorous knowledge acquisition frameworks, School of Chemical En-

gineering, Purdue University, West Lafayette (EUA).

Persson, J. A. (2002). Production Scheduling and Shipment Planning at Oil Refine-

ries - Optimization Based Methods, PhD thesis, International Graduate School

of Management and Industrial Engineering, Linkoping, Sweden.

Pinto, J. M. (2000). Planejamento e programacao de operacoes de producao e dis-

tribuicao em refinarias de petroleo, Tese de livre docencia, Escola Politecnica

da Universidade de Sao Paulo, Sao Paulo, Brasil.

Pinto, J. M. & Grossmann, I. E. (1995). A continuous time mixed integer linear

programming model for short term scheduling of multistage batch plants, In-

dustrial & Engineering Chemistry Research 34(9): 3037–3051.


Pinto, J. M. & Grossmann, I. E. (1996). A continuous time milp model for short-

term scheduling of batch plants with pre-ordering constraints, Computers &

Chemical Engineering 20: S1197–S1202.

Raman, R. & Grossmann, I. E. (1994). Modelling and computational techni-

ques for logic based integer programming, Computers & Chemical Engineering

18(7): 563–578.

Ravi, V., Reddy, P. & Dutta, D. (1998). Application of fuzzy nonlinear goal program-

ming to a refinery model, Computers & Chemical Engineering 22: 709–712.

Rejowski, R. J. (2001). Programacao de distribuicao dutoviaria de derivados de

petroleo, Dissertacao de mestrado, Escola Politecnica da Universidade de Sao

Paulo, Sao Paulo, Brasil.

Rejowski, R. & Pinto, J. M. (2003). Scheduling of a multiproduct pipeline system,

Computers & Chemical Engineering 27: 1229–1246.

Reklaitis, G. V. (1992). Overview of scheduling and planning of batch process

operations, Nato Advanced Study Institute, Antalya, Turquia, pp. 660–705.

Rigby, B., Lasdon, L. S. & Waren, A. D. (1995). The evolution of texaco’s blending

systems: From omega to starblend, Interfaces 25(5): 64–83.

Rodosek, R., Wallace, M. G. & Hajian, M. T. (1999). A new approach to integra-

ting mixed integer programming and constraint logic programming, Annals of

Operational Research (86): 63–87.

Sahinidis, N. V. (2004). Optimization under uncertainty: state-of-the-art and op-

portunities, Computers & Chemical Engineering 28: 971–983.

Schilling, G. & Pantelides, C. C. (1996). A simplified continuous-time process sche-

duling formulation and a novel solution algorithm, Computers & Chemical En-

gineering 20: S1221–S1226.

Schrage, L. (2000). Optimization Modeling with LINGO, Lindo Systems Inc, Chicago

(Illinois).


Shah, N. (1996). Mathematical programming techniques for crude oil scheduling,

Computers & Chemical Engineering 20: S1227–S1232.

Smith, B. M. (1995). A tutorial on constraint programming, Report 95.14, University

of Leeds - Division of Artificial Intelligence, Leeds, UK.

Stebel, S. L. (2001). Modelagem da estocagem e distribuicao de glp de uma refinaria

de petroleo, Dissertacao de mestrado, CEFET-PR/CPGEI, Curitiba, Brasil.

Stebel, S. L. (2003). Tecnicas de otimizacao aplicadas em problemas de Scheduling

dos recursos de estocagem, Qualificacao de doutorado, CEFET-PR/CPGEI,

Curitiba, Brasil.

Stebel, S. L., Neves-Jr., F. & Arruda, L. V. R. (2006). A hybrid approach using clp

and milp applied to tank farm operation scheduling, ESCAPE-16, Garmisch-

Partenkirchen, Germany.

Stebel, S. L., Neves-Jr., F., Arruda, L. V. R., Fabro, J. A. & Rodrigues, L.

C. A. (2002). Modelling the liquefied petroleum gas storage and distribution,

ESCAPE-12, The Hague, The Netherlands.

Stebel, S. L., Neves-Jr., F., Arruda, L. V. R. & Rodrigues, L. C. A. (2003). Scheduling

de processos contınuos baseado nos recursos de estocagem, XXXV SBPO, Natal,

RN.

Tavares, J. A. R. (2000). Generation of Industrial Systems Configurations by Using

the Constraint Technology and Evolutionary Computation, PhD thesis, Univer-

sidade do Minho, Porto, Portugal.

Tavares, M. E. E. (2005). Analise do refino no brasil: Estado e perspectivas - uma

analise ’cross-section’, Tese de doutorado, Universidade Federal do Rio de Ja-

neiro - COPPE, Rio de Janeiro, Brasil.

Tukkay, M. & Grossmann, I. E. (1998). Tight mixed-integer optimization models for

the solution of linear and nonlinear systems of disjunctive equations, Computers

& Chemical Engineering 22(9): 1229–1239.


Tsang, E. (1996). Foundations of Constraint Satisfaction, Academic Press Limited,

London, UK.

Wang, L. X. (1997). A Course in Fuzzy Systems and Control, Prentice Hall PTR,

London, UK.

Williams, H. P. (1999). Model Building in Mathematical Programming, John Wiley

& Sons Ltd, Chichester, England.

Wolsey, L. A. (1998). Integer Programming, John Wiley & Sons, New Jersey, EUA.

XPRESS-MP (2006). http://www.dashoptimization.com/. Pagina visitada em

02/01/2006.

Yee, K. L. & Shah, N. (1998). Improving the efficiency of discrete time scheduling

formulation, Computers & Chemical Engineering 22: S403–S410.

Zadeh, L. A. (1965). Fuzzy sets, Information and Control 8(3): 338–353.


Apendice A

Complexidade Computacional

Em Garey & Johnson (1979) um estudo sobre algoritmos e as caracterısticas

e realizado tendo como base uma teoria denominada NP-completeness. Essa teoria

obtem resultados que podem ser estendidos tambem para problemas de scheduling.

A seguir serao apresentados alguns conceitos importantes envolvidos na teoria NP-

completeness. Um termo muito utilizado dentro deste contexto e instancia, que nada

mais e que uma especificacao de valores de entrada conhecidos num determinado

momento, satisfazendo as condicoes ou restricoes proprias do problema. O tamanho

de uma instancia e o total de informacoes necessarias a identificacao, considerando o

tipo e a estrutura de dados utilizada. Alem desta, o tamanho de um problema pode

ser avaliado de muitas formas, como pelo numero de variaveis do problema, pelos

valores absolutos dos parametros ou pelo numero de elementos nao-nulos.

Uma definicao muito importante e a de funcao de complexidade temporal, que

esta ligada a um algoritmo em particular. Nemhauser & Wolsey (1988) denominam

a funcao de complexidade temporal de running time. Para uma entrada de dados es-

pecificada, a funcao de complexidade temporal determina o maior tempo necessario

para resolver uma instancia do problema P . Deste modo, a cada algoritmo e asso-

ciada uma funcao de complexidade temporal de acordo com a situacao em estudo

(Garey & Johnson, 1979). Os algoritmos sao divididos em algoritmos de tempo poli-

nomial e em algoritmos de tempo exponencial. Segundo Garey & Johnson (1979) um

algoritmo de tempo polinomial p(n) e assim definido se a funcao de complexidade

temporal O e O(p(n)), onde n e a entrada de dados. Alguns algoritmos, cuja funcao

130 Capıtulo A. Complexidade Computacional

de complexidade temporal nao e limitada, sao chamados de algoritmos de tempo

exponencial. E importante notar que esta diferenciacao entre algoritmos torna-se

significativa apenas para instancias de problemas de dimensao elevada (n)grande.

Embora o algoritmo de tempo polinomial seja preferıvel ao exponencial, exis-

tem alguns algoritmos exponenciais, como e o caso do SIMPLEX para programacao

linear e do Branch and Bound para programacao inteira que sao muito utilizados

na pratica.

Apendice B

Sugestoes para Modelagem dePSRP utilizando PLIM ou PLR

A seguir e apresentado algumas recomendacoes a serem utilizadas na mode-

lagem PSRP utilizando PLIM ou PLR. No desenvolvimento desta tese foi possıvel

identificar varios aspectos que influenciam o desempenho computacional dos mode-

los. A partir desta constatacao, levando-se em conta estes aspectos, e proposto um

roteiro que visa a obtencao de modelos eficazes. Nemhauser & Wolsey (1988) desta-

cam que a formulacao de um bom modelo e fundamental para resolver instancias do

problema. A figura B.1 ilustra os passos a serem seguidos no processo de modelagem

para este tipo de problema.

Concepcao inicial: Identificar no problema o que sera modelado, quais serao

os parametros e as variaveis do modelo. O modelo deve ser desenvolvido a partir de

uma variavel que tenha por caracterıstica estar presente no maior numero possıvel

de restricoes, e ainda possuir um domınio reduzido. Isso sera fundamental na geracao

da arvore de busca.

Restricoes do problema: Inserir as restricoes do problema, considerando o

item anterior.

Funcao objetivo: Escolher uma funcao objetivo que melhor represente o pro-

blema a ser modelado, para que, alem de fornecer solucoes viaveis, encontre solucoes

que possam ser implementadas na pratica pelo usuario final.

132 Capıtulo B. Sugestoes para Modelagem de PSRP utilizando PLIM ou PLR

Concepção Inicial

Restrições do Problema

Pré-processamento dos Dados

Heurísticas

Função Objetivo

Figura B.1: Recomendacoes para modelagem de PSRP.

Pre-processamento dos dados: Muitas das informacoes iniciais do problema

podem ser utilizadas num pre-processamento dos dados, para estabelecer limites (su-

periores, inferiores) as variaveis com o objetivo de reducao do tamanho do problema

e consequente reducao do tempo computacional.

Heurısticas: como o modelo foi concebido a partir de uma variavel (conforme

a concepcao inicial), gerar a arvore de busca a partir desta variavel facilita a busca

por solucoes para o problema.

Resumo

Este trabalho pretende contribuir no desenvolvimento de modelos de otimizacaopara o problema de scheduling da transferencia e estocagem (TE) em refinarias depetroleo. O scheduling diario da TE e uma tarefa difıcil, realizado em geral por umespecialista, baseado na experiencia profissional e com a utilizacao de calculos ma-nuais. Para determinar o scheduling o especialista considera varios espectos como:topologia da planta, balanco de massa, polıticas de transferencia de material, trocasde tanques, restricoes fısicas e de demanda, entre outras. O principal objetivo destetrabalho e diminuir a distancia entre os modelos teoricos e as necessidades praticas,em especial aquelas vivenciadas diariamente nas refinarias de petroleo. Inicialmentee proposto um modelo em programacao linear inteira mista (PLIM) com tempocontınuo. A representacao do problema e baseada nos estados possıveis dos tanquesdurante o horizonte de scheduling. Esta representacao permite explorar outras ca-racterısticas do problema, como a questao do custo eletrico diferenciado. Alem disso,os custos qualitativos da operacao da TE, considerando-se aspectos de execucao dastarefas, sao modelados atraves de sistemas fuzzy e representados na funcao objetivodo modelo matematico. Por fim, para reducao do tempo computacional, e propostauma estrutura hıbrida que combina PLIM com programacao logica por restricoes(PLR). Esta estrutura contempla ainda heurısticas que sao utilizadas na geracaoda arvore de busca. Os resultados demonstram que a estrutura hıbrida apresentaboas solucoes em poucos segundos. Os modelos implementados podem ser utilizadospara, alem de determinar o scheduling diario, testar novos pontos de operacao daTE.

PALAVRAS-CHAVEScheduling, PLIM, PLR, Transferencia e Estocagem, Sistemas Fuzzy.

AREAS / SUB-AREAS DO CONHECIMENTO3.08.02.00-8 Pesquisa Operacional3.08.02.02-4 Programacao Linear, Nao-Linear, Mista e Dinamica3.06.03.16-1 Petroleo e Petroquımica

2006No : 17

Documents

Técnicas de Otimização Aplicadas em Problemas de ...livros01.livrosgratis.com.br/cp106220.pdf · Ficha catalográfica elaborada pela Biblioteca da UTFPR ... Resumo xvii Abstract