UNIVERSIDADE DO NORTE FLUMINENSE
TESE DE DOUTORADO
GERENCIAMENTO DE PROJETO: META-HEURÍSTICAS PARA OTIMIZAÇÃO DO ESCALONAMENTO DE ATIVIDADES NA EXPLORAÇÃO E
PRODUÇÃO DE PETRÓLEO
SÉRGIO VASCONCELLOS MARTINS
[email protected]
CAMPOS DOS GOITACAZES - RJ
Abril - 2000
Centro de Ciência e Tecnologia
Laboratório de Engenharia de Produção
♥ Sérgio Vasconcellos Martins 2000
vi
GERENCIAMENTO DE PROJETO: META-HEURÍSTICAS PARA OTIMIZAÇÃO DO ESCALONAMENTO DE ATIVIDADES NA EXPLORAÇÃO E
PRODUÇÃO DE PETRÓLEO
SÉRGIO VASCONCELLOS MARTINS
“Tese apresentada ao Centro de Ciências e Tecnologia, da Universidade Estadual do Norte Fluminense, como parte das exigências para obtenção
do título de Doutor em Ciências de Engenharia na
área de concentração de Engenharia de Produção”
Orientador: Prof. Geraldo Galdino de Paula Júnior, D.Sc.
CAMPOS DOS GOITACAZES - RJ
Abril - 2000
vii
GERENCIAMENTO DE PROJETO: META-HEURÍSTICAS PARA OTIMIZAÇÃO DO ESCALONAMENTO DE ATIVIDADES NA EXPLORAÇÃO E
PRODUÇÃO DE PETRÓLEO
SÉRGIO VASCONCELLOS MARTINS
“Tese apresentada ao Centro de Ciências e Tecnologia, da Universidade Estadual do Norte Fluminense, como parte das exigências para obtenção
do título de Doutor em Ciências de Engenharia na
área de concentração de Engenharia de Produção”
Aprovada em 06 de Abril de 2000.
Comissão Examinadora:
Prof. Nelson Maculan, Ph.D. – UFRJ
Prof. Nélio Domingues Pizzolato, Ph.D. – PUC-RJ
Prof. José Ramon Arica Chavez, D.Sc. – UENF
Prof. David Mauricio Sanchez, D.Sc. – UNMSM, PUCP
Prof. Geraldo Galdino de Paula Jr., D.Sc. – UENF
Orientador
viii
À minha família, com todo afeto.
ix
Mais importante é como gerenciamos o nosso projeto de vida...
x
Agradecimentos
À minha mãe, Iza Vasconcellos, mestra de minha vida, cujos inspirados conselhos
sempre iluminaram o gerenciamento de meu projeto de vida.
À minha mulher, Andréa, pela insuspeitada paciência com que suportava minhas ausências, tão envolvido estava em meu projeto.
A toda minha família, cujo vibrante encorajamento sempre me animou ao longo de
toda minha vida.
Ao meu orientador, Prof. Dr. Geraldo Galdino, pelo prestimoso suporte e admirável
disposição com que me ouvia sempre.
Ao meu co-orientador, Prof. Dr. David Mauricio, pelo extraordinário estímulo e invencível dedicação, minha mais sentida gratidão.
Ao meu primeiro orientador, Prof. Dr. José Arica, vocação invulgar para a pesquisa e
o magistério.
Aos demais membros da comissão examinadora, Prof. Dr. Nelson Maculan e Prof.
Dr. Nélio Pizzolato, por emprestarem seu prestígio a este trabalho e pelas sábias sugestões que muito contribuíram para aprimorá-lo.
Ao Prof. Dr. Rainer Kolisch, da Universidade de Kiel, Alemanha, pela sua decisiva e
sempre precisa orientação via e-mail.
A todos o professores do Laboratório de Engenharia de Produção da UENF.
Aos muitos amigos conquistados durante o curso, cuja agradável convivência se traduziu em precioso incentivo, representados aqui por Carlos Leonardo, por sua gentil
colaboração na etapa inicial da elaboração de meu código computacional.
Aos funcionários da UENF, especialmente ao bibliotecário Antônio Soares, cujo interesse e disposição para ajudar concorreram para a minimização do makespan do
meu projeto.
Ao CEFET Campos, à UENF e à Petrobras, que de fato viabilizaram este projeto.
Por último, mas não por fim, ao proprietário destas instituições, o povo brasileiro,
cuja generosidade nunca conheceu limites.
xi
Centro de Ciência e Tecnologia................................................................................vi
Laboratório de Engenharia de Produção..................................................................vi
Prof. Nelson Maculan, Ph.D. – UFRJ..................................................................viii
Prof. José Ramon Arica Chavez, D.Sc. – UENF.................................................... viii
Prof. Geraldo Galdino de Paula Jr., D.Sc. – UENF.................................................viii
Introdução....................................................................................................................1
1.1 O Gerenciamento de Projeto no Brasil e no Mundo............................................1
1.2 Produção de Petróleo e Gerenciamento de Projeto...........................................3
1.3 Escalonamento de Projeto e Otimização Matemática ....................................... 5
1.4 O Caso Estudado................................................................................................5
1.5 Objetivos da Pesquisa.........................................................................................6
1.6 Organização do texto...........................................................................................6
Capítulo 2.....................................................................................................................8
O Gerenciamento de Projeto......................................................................................8
2.1 Estrutura Geral do Gerenciamento de Projeto....................................................8
2.1.1Conceituação Básica.....................................................................................8
2.1.2 O Gerenciamento de Projeto......................................................................11
2.1.3 Fases e Ciclo de Vida do Projeto ...............................................................13
2.2 Processos do Gerenciamento de Projeto..........................................................14
2.2.1 Processo de Iniciação.................................................................................15
2.2.2 Processos de Planejamento.......................................................................15
2.2.3 Processos de Execução..............................................................................16
2.2.4 Processos de Controle................................................................................16
2.2.5 Processos de Encerramento.......................................................................17
2.3 Áreas de Conhecimento do Gerenciamento de Projeto....................................18
2.3.1 Gestão da Integração do Projeto................................................................18
2.3.2 Gestão do Escopo do Projeto.....................................................................18
2.3.3 Gestão dos Tempos do Projeto..................................................................19
2.3 4 Gestão dos Custos do Projeto....................................................................21
2.3.5 Gestão da Qualidade do Projeto.................................................................21
2.3.6 Gestão dos Recursos Humanos do Projeto............................................... 22
2.3.7 Gestão das Comunicações do Projeto....................................................... 22
2.3.8 Gestão dos Riscos do Projeto.................................................................... 23
2.3.9 Gestão das Contratações do Projeto..........................................................23
2.4 Sistemas Comerciais de Gerenciamento de Projeto ....................................... 23
2.5 Avanços no Campo do Gerenciamento de Projeto...........................................25
O Problema de Escalonamento de Projeto - PSP..................................................27
3.1 Definições para Ambiente de Job shop.............................................................28
3.2O Problema de Escalonamento de Projeto........................................................30
3.2.1 Elementos do PSP......................................................................................31
3.2.2Descrição do PSP .......................................................................................34
3.2.3 Modelo Conceitual do PSP.........................................................................36
3.2.4 Modelo Matemático MIP do PSP Multiprojeto............................................38
3.2.5 Representação de um PSP........................................................................ 41
3.2.6 Notação e Classificação do PSP................................................................43
3.2.7 Medidas Regulares de Desempenho......................................................... 44
3.2.8 Classificação de Escalonamentos: Viável, Ativo, Semi-ativo e Sem-atraso
..............................................................................................................................45
xii
3.3 Métodos para Resolução do PSP..................................................................... 47
3.3.1 Algoritmos de Solução Exata para o RCPSP.............................................51
3.3.2Algoritmos de Solução Aproximada para o RCPSP....................................53
3.3.3 Algoritmos de Solução Exata para o MRCPSP..........................................55
3.3.4Algoritmos de Solução Aproximada para o MRCPSP.................................55
3.4 O Caso do PSP com Duração Estocástica das Atividades...............................58
3.5 O Caso do PSP com Tarefas Preemptivas ......................................................59
3.6 Novos modelos para o PSP ..............................................................................60
O PSP de Alocação de Recursos Críticos na E&P de Petróleo .......................... 62
4.1 Modelagem do Problema...................................................................................64
4.1.1 Modelo Físico..............................................................................................64
4.1.2 Modelo Matemático.....................................................................................66
4.2 Conjuntos e Geradores de Instâncias ..............................................................67
4.3 O Gerador de Instâncias ProGen......................................................................68
4.3.1 Parâmetros de Problema............................................................................69
4.4 Instâncias Geradas para Teste das Heurísticas............................................... 71
Heurísticas Desenvolvidas para o MRCPSP em Estudo.......................................77
5.1. Esquemas de Geração de Escalonamento .....................................................78
5.1.1 SGS em série...........................................................................................78
5.1.2 SGS paralelo............................................................................................80
5.2 Regras de Prioridades.......................................................................................81
5.3 Algoritmos do tipo Aleatório Puro......................................................................83
5.3.1 Algoritmo Aleatório Proposto...................................................................84
5.4 GRASP..............................................................................................................84
5.4.1 Algoritmo GRASP Proposto.....................................................................85
5.5 Algoritmos Evolucionários.................................................................................88
5.5.1Genética, Evolução e Otimização................................................................89
5.5.2 Algoritmo Genético Proposto...................................................................91
5.5.2 Heurística Híbrida Proposta.....................................................................97
Experimentos Numéricos.........................................................................................98
6.2 Configuração das Meta-heurísticas...................................................................98
6.1.1 Ajuste dos parâmetros................................................................................99
GRASP J50 - 30 s......................................................................................................99
AG J50 - 30 s............................................................................................................100
6.1.2 Definição do Operador Mutação ..............................................................101
AG J50 - 30s – POP = 20, Pmut = 0,4 ....................................................................101
6.2 Experimentos Numéricos Comparativos.........................................................102
6.2.1 Testes com o conjunto J50.......................................................................102
J50 - 30 s..................................................................................................................102
6.2.2 Testes com o conjunto J100.....................................................................102
J100 - 120 s..............................................................................................................103
6.2.3 Testes com o conjunto J200.....................................................................103
J200 - 300 s..............................................................................................................103
J200 – 480 s.............................................................................................................104
6.2.4 Eficiência dos Algoritmos..........................................................................104
J200 – 480 s.............................................................................................................104
xiii
J200 – 480 s.............................................................................................................105
6.2.5 Efeitos dos Parâmetros de Problema RF e RS........................................106
6.3 Considerações Finais......................................................................................109
Conclusões, Recomendações e Futuras Pesquisas...........................................110
7.1 Conclusões......................................................................................................110
7.2 Recomendações .............................................................................................112
7.3 Futuras Pesquisas...........................................................................................112
Simbologia & Definições........................................................................................114
Bibliografia.........................................................................................................116
Anexo........................................................................................................................127
Análise de Complexidade do PSP.........................................................................127
Transformação Polinomial e Prova de Complexidade...................................... 129
Teorema.............................................................................................................130
O problema de viabilidade do MRCPSP é NP-completo para |N| ≥ 2 e Mj ≥ 2, 1 ≤
j ≤ J.....................................................................................................................130
Lista de Tabelas
Tabela 3.1:
Modelo Conceitual do PSP.............................................................
37
Tabela 3.2:
Modelo Matemático MIP do PSP multiprojeto................................
38
Tabela 4.1:
Modelo Matemático MIP do MRCPSP em estudo..........................
66
Tabela 4.2:
Combinação dos parâmetros RF-RS...............................................
72
Tabela 4.3:
Parâmetros básicos do conjunto de instâncias com 50 tarefas.....
72
Tabela 4.4:
Parâmetros básicos do conjunto de instâncias com 100 tarefas...
72
Tabela 4.5:
Parâmetros básicos do conjunto de instâncias com 200 tarefas...
72
Tabela 5.1:
Regras de prioridade......................................................................
83
Tabela 6.1:
Calibração do parâmetro κ.............................................................
99
Tabela 6.2:
População inicial, POP, e Probabilidade de Mutação, Pmut .............
100
Tabela 6.3:
Teste comparativo entre operadores mutação...............................
101
Tabela 6.4:
Teste comparativo entre as heurísticas com o conjunto J50.........
102
Tabela 6.5:
Teste comparativo entre as heurísticas com o conjunto J100.......
103
Tabela 6.6:
Teste comparativo entre as heurísticas com o conjunto J200 em
xiv
Tabela 6.7:
Tabela 6.8:
Tabela 6.9:
300 s...............................................................................................
103
Teste comparativo entre as heurísticas com o conjunto J200 em
480 s...............................................................................................
104
Desvio médio das heurísticas em relação ao limitante inferior
CPM................................................................................................
104
Número médio de escalonamentos avaliados pelas heurísticas
em 480 s.........................................................................................
105
xv
Lista de Figuras
Figura 2.1:
Custo como função do prazo do projeto........................................
13
Figura 3.1:
Métodos de representação para o PSP: (a) gráfico de Gantt; (b)
rede do tipo atividade-no-arco (AOA); (c) rede do tipo atividadeno-vértice (AON).............................................................................
42
Figura 4.1:
Modelo AON genérico do PSP em estudo.....................................
65
Figura 4.2:
Exemplo de arquivo de entrada para o gerador ProGen para instância com 8 tarefas reais..........................................................
75
Exemplo de arquivo de saída do ProGen com instância de 8 tarefas reais....................................................................................
77
Esquema de geração de escalonamento em série
(SSS)..............................................................................................
80
Esquema de geração de escalonamento em paralelo
(PSS)..............................................................................................
81
Figura 5.3:
Pseudocódigo da fase de construção da GRASP..........................
87
Figura 5.4:
Pseudocódigo da fase de melhoria da GRASP..............................
88
Figura 5.5:
Pseudocódigo do algoritmo genético proposto..............................
94
Figura 6.1:
Instância vs. makespan comparando todas as heurísticas............
107
Figura 6.2:
Resultados do makespan com todas as heurísticas para as 30
primeiras instâncias........................................................................ 108
Figura 4.3:
Figura 5.1:
Figura 5.2:
xvi
Resumo
O estudo do Gerenciamento de Projeto, como um conjunto de ações integradas de
planejamento, programação e controle das atividades de um projeto com vista à consecução eficaz de seus objetivos, ainda se encontra numa fase incipiente no Brasil.
Em contraste, as nações desenvolvidas dedicam ao tema mais e mais atenção,
como medida de sobrevivência em meio à frenética disputa entre as organizações
pela primazia no lançamento de produtos e serviços. No estratégico setor petróleo, a
meta brasileira é de elevação da produção interna, objetivando a auto-suficiência e
conseqüente independência energética. Nesse campo, com a recente flexibilização
do monopólio estatal, a competição só faz recrudescer, culminando com novos e
grandes projetos, que obrigam condução eficiente no que tange a custo, tempo e
qualidade, fatores decisivos de sucesso.
Utilizando como veículo o caso da alocação de recursos críticos nas intervenções
marítimas de exploração e produção de hidrocarbonetos na bacia de Campos, RJ,
este trabalho contribui com um estudo do problema multimodo de escalonamento de
projeto com restrição de recursos (MRCPSP), integrante da área de conhecimento
da gestão dos tempos de um projeto e sabidamente intratável. O problema real é
descrito e modelado matematicamente. Três conjuntos de instâncias de teste são
criados com o uso de um gerador computacional já existente, num total de 1080 problemas artificiais que, com a adequada modulação de parâmetros específicos, buscam reproduzir as condições práticas das operações de exploração e produção da
indústria de petróleo. São propostas e experimentadas três meta-heurísticas de solução: Algoritmo Genético, GRASP e uma Heurística Evolucionária Híbrida – as duas
últimas inéditas. Um algoritmo puramente aleatório também é implementado, como
forma de produzir soluções de referência para os experimentos numéricos dos métodos. Por fim, tem-se uma breve discussão acerca da complexidade, sob o prima da
pesquisa operacional, do problema de escalonamento de projeto (PSP), classificado
como NP-difícil.
xvii
Abstract
The study of Project Management as an array of integrated actions of planning,
scheduling, and controlling of project activities to effectively meet its objectives
completion is still incipient in Brazil. Conversely, the developed nations devote more
and more attention to the matter as survival measure within the frenetic struggle
among organizations to be ahead on releasing products and services. At the
strategic petroleum sector, the brazilian goal is to expand the internal production until
achieving self-sufficiency and consequent energetic independence. On this field, with
the recent state monopoly flexibility, the competition tends to increase followed by
large projects requesting effective management with respect to cost, time, and
quality, decisive factors of success.
By using as a vehicle the case of critical resources allocation to the petroleum
offshore exploration and production interventions in Campos basin, RJ, this work
contributes with a study of the multi-mode resource constrained project scheduling
problem (MRCPSP), a component of the project time management knowledge area
and notoriously intractable. The real problem is described and mathematically
modeled. Three test instances data sets are created via an existing computational
generator, resulting in a total of 1,080 artificial problems that, with suitable
modulation of specific parameters, are intended to reproduce the practical conditions
of petroleum industry projects. Furthermore, three meta-heuristic approaches for
solution are proposed and experimented: Genetic Algorithm, GRASP and a Hybrid
Evolutionary Heuristic – two latter are new. A pure random algorithm is implemented
as well, as mean of producing benchmark solutions for the numerical experiments of
the methods. Finally, this work briefly discusses the complexity of the project
scheduling problem (PSP), rather under operational research point of view, classified
as NP-hard.
xviii
Simbologia & Definições
CPM
: método do caminho crítico
PERT
: técnica de revisão e avaliação de programa
JSP
: problema de job shop
PSP
: problema de escalonamento de projeto
RCPSP
: problema de escalonamento de projeto com restrição de recursos
MRCPSP
: problema multimodo de escalonamento de projeto com restrição de
recursos
p = 1, ..., P
: projetos
πj (εj)
: release date (due date) da tarefa j
πp (εp)
: release date (due date) do projeto p
cjmt
: fluxo de caixa induzido pela tarefa j no modo m e término em t
cp
: custo por período se o projeto p se concluir após seu prazo devido
α
: campo referente ao ambiente das máquinas (recursos)
β
: campo referente ao processamento e às restrições
γ
: campo referente ao critério de desempenho
FJp (LJp)
: numero da primeira (última) tarefa do projeto p
J
: conjunto das tarefas j, |J|=J+2
J
: número de tarefas reais (i. é, não-fictícias)
j = 0 (J+1)
: única fonte (sumidouro) da rede
Pj (Sj)
: conjunto dos predecessores (sucessores) imediatos da tarefa j
At
: conjunto das tarefas ativas (em execução) no tempo t
ESTj (LSTj)
: tempo mais cedo (mais tarde) de início da tarefa j
EFTj (LFTj)
: tempo mais cedo (mais tarde) de conclusão da tarefa j
STj
: tempo de início da tarefa j
FTj
: tempo de conclusão da tarefa j
xix
SC
: vetor com uma permutação viável das tarefas j ∈ J
ST
: vetor escalonamento com os tempos de início STj
FT
: vetor escalonamento com os tempos de conclusão FTj
M
: vetor de designação dos modos de execução mj
T
: limitante superior do makespan do projeto (horizonte de tempo)
R(N,D)
: conjunto dos recursos renováveis (não-renováveis, duplamente restritos)
r ∈ R(N,D)
: índice do recurso demandado (consumido)
Mj
: número de modos pelos quais a tarefa j pode ser executada
mj = 1, ..., Mj
: modo de execução da tarefa j
djm
: duração da tarefa j executada no modo m
ρ
k jmr
: uso por período do recurso renovável (duplamente restrito) r exigido
para executar a tarefa j no modo m
k νjmr
: consumo total do recurso não-renovável (duplamente restrito) r para
executar a tarefa j no modo m
K rρ
: disponibilidade por período do recurso renovável (duplamente restrito) r
K νr
: disponibilidade total do recurso não-renovável (duplamente restrito) r
RF
: fator recurso de um PSP
RS
: potência de recursos de um PSP
κ
: parâmetro de relaxação da GRASP
RCL
: lista restrita de candidatos da GRASP
Pmut
: probabilidade de mutação para AG e HH
SGS
: esquema de geração de escalonamento
AP
: algoritmo puramente aleatório
GRASP
: Greedy Randomized Adaptive Search Procedure
AG
HH
: algoritmo genético
: heurística evolucionária híbrida
xx
Capítulo 1
Onde se argumenta sobre o tema e se tem a sinopse da dissertação
Introdução
N
os dias que correm, vive-se um ambiente de atordoante competição entre as
organizações, fruto da mundialização da economia, que exorbita tudo quanto
se viu antes na história humana. Na quadra de transição da sociedade pós-industrial
para a do conhecimento, agora que o século finda, é lícito antever que esta dinâmica
atinja ritmo paroxístico. Como todo organismo vivo, o conjunto das organizações e
empresas está em permanente estado transiente, de transformação, perseguindo a
própria sobrevivência. Isso obriga administração marcada pela mutabilidade em seu
métodos, processos, serviços e produtos em benefício da adaptação e da subsistência – aliás, o cenário evoca o darwinismo, mais adiante rapidamente tratado neste
trabalho, mas por razões outras.
Qualidade, custo e prazo assumem relevo como nunca dantes. Naturalmente, todos
os agentes envolvidos disso se dão conta, e o componente diferencial torna-se então a excelência e a agilidade com que são conduzidas as mudanças, buscando sobretudo tornar disponíveis produtos e serviços de maior utilidade e menor preço em
um tempo concorrencialmente competitivo.
Mas, qualquer que seja a direção das transformações e sua natureza, quase sempre
implicarão um projeto. Como motor de inovações, os projetos são componentes críticos na órbita das organizações, de importância que não pode ser exagerada. Parece
óbvio ser imprescindível o constante aperfeiçoamento da metodologia e dos processos voltados para boa condução dos projetos como um todo. É precisamente dessa
matéria que é feito o gerenciamento de projeto.
1.1
O Gerenciamento de Projeto no Brasil e no Mundo
A experiência brasileira não tem sido exatamente de boa memória. Alguns exemplos
pregressos conjuguem exasperante negligência com inexcedível incompetência. A
1
esse propósito, apenas na área de energia, despontam casos notórios tais como as
usinas nucleares de Angra dos Reis e a hidrelétrica de Porto Primavera, em São
Paulo, os quais converteram-se em prejuízos colossais. No mundo desenvolvido,
também alguns exemplos de falhas graves e fracassos podem ser pinçados, como o
caso do gasoduto do Alasca (Lewis, 1998) ou o conhecido como projeto Taurus
(Drummond, 1999). Este, havido na renomada City de Londres, antes do seu inexplicável naufrágio, já se notabilizava pela surpreendente inabilidade gerencial.
O complexo nuclear de Angra dos Reis teve orçamento original de US$ 3 bilhões,
mas consumiu US$ 12 bilhões apenas para concluir um terço do projeto. A usina de
Porto Primavera foi orçada em US$ 1,4 bilhão para um prazo previsto de conclusão
de seis anos. Entrou em operação comercial finalmente em janeiro de 1999, acabou
custando US$ 10,3 bilhões após dezoito anos de obras – e ainda faltando instalar
quinze turbinas. A obra foi seis vezes interrompida, o contrato foi renegociado dezenas de vezes, houve falhas gritantes no cronograma e o custo com a desapropriação
dos terrenos resultou em US$ 500 milhões além do planejado. Em função do atraso,
US$ 2 bilhões foram destinados ao armazenamento dos equipamentos e US$ 5 bilhões gastos em juros.
O projeto Taurus envolveu cifras mais modestas. Foi apenas um retumbante fiasco
do tamanho de quase US$ 1,0 bilhão para a Bolsa de Valores de Londres e corretoras locais. Tivera como intento agilizar as operações de securitização dos títulos.
Mesmo alertados no decorrer do projeto que o fracasso seria inevitável, seus gerentes e as partes envolvidas, com inquebrantável teimosia, perseveraram adiante. Foi
finalmente cancelado em março de 1993, após cinco anos de percalços. Fez-se célebre como o pior fracasso do gênero na Europa em todos os tempos.
Formam um fascinante campo de estudo os motivos pelos quais alguns projetos fracassam e o modo como o fazem. De saída, é bom dizer que se deve a priori estabelecer os critérios para se caracterizar o fracasso de um projeto. Isso não é consenso
universal e deve ser explicitado ainda na fase de planejamento e estudo de viabilidade. Nem sempre um projeto muito atrasado pode ser considerado um projeto fracassado. São diversos os estudos nesta área e não há unanimidade a respeito; alguns
autores antes preferem dar um enfoque menos depreciativo e falar dos fatores de
sucesso dos projetos. Não importa, por ora o que se pretende aqui é apenas sublimar a importância do bom gerenciamento de projeto, notadamente com relação aos
2
seus tempos. Afinal, ao contrário da Torre de Babel, nenhum projeto malogra por desígnio divino.
No mundo desenvolvido, o gerenciamento de projeto vem sendo reconhecido cada
vez mais como uma disciplina distinta da administração. Programas na matéria, do
tipo MBA e em nível de pós-graduação stricto sensu, são oferecidos pelas universidades em número crescente. As corporações já começam a exigir de firmas contratadas certificados do tipo PMP1 para profissionais que vão chefiar seus projetos.
O Brasil não conta com cursos de formação de gerentes de projetos, ao contrário de
alguns outros países. O indivíduo que aqui exerce este papel pretende ser, por assim dizer, componente ad hoc, o que costuma acarretar perda de um bom técnico e
aquisição de um pseudogerente. Em boa medida pela gestão inepta dos recursos
humanos. (Um traço marcante deste cargo é ter muita responsabilidade sem poder
contar com autoridade na mesma proporção. Isso impõe a habilidade com as relações humanas como atributo principal de um gerente de projeto). Em verdade, não
há sequer um estudo formal e sistemático de gerenciamento de projeto no ambiente
universitário brasileiro, onde é abordado apenas mediatamente, em iniciativas esporádicas e esparsas na forma de cursos de extensão. Também carecemos de associações e institutos que congreguem os profissionais do ramo.
Soa agora e evidente a aguda necessidade da formalização e disseminação do
aprendizado do gerenciamento de projeto em nosso pais, combinado com mais pesquisa no campo de otimização de escalonamento2 de projeto. Daí a oportunidade de
trabalhos nesse campo também tencionando voltar a atenção da comunidade acadêmica e especialistas para a relevância da matéria. Tudo isso compõe o que se poderia considerar a motivação para o tema de estudo da presente tese: otimização do
escalonamento dos recursos críticos na exploração e produção (E&P) de petróleo.
1.2
Produção de Petróleo e Gerenciamento de Projeto
Nos últimos anos, o Brasil experimentou espetacular incremento na capacidade de
produção e de refino de hidrocarbonetos fluidos mas, ainda assim, não tem sido o
bastante para fazer frente às necessidades internas. Os preços internacionais do petróleo, de ordinário tão gravosos e sempre impactando tão diretamente a economia
1
Project Management Professional, conferido pelo Instituto de Gerenciamento de Projeto (Project Manegement Institute, PMI) americano.
2
Neste texto, o termo escalonamento refere-se tanto ao ato quanto ao efeito da programação das atividades de um projeto. Corresponde no inglês às palavras scheduling (ato) e schedule (efeito).
3
interna, autorizam supor maciços investimentos nesta área. Atingir a auto-suficiência, ficando a salvo da dependência externa, significa aumentar em muito o grau de
liberdade de ações no setor, com repercussão imediata beneficiando toda a cadeia
econômica.
Mas os tempos são outros, o modelo de exclusividade para apenas uma companhia
de petróleo como agente administrador do monopólio3 estatal do petróleo não mais
vigora e empresas congêneres entram em cena, disputando o mercado. Inevitavelmente, o próximo século assistirá a renhida competição em todos os segmentos da
indústria de petróleo: E&P, refino, transporte, comercialização e distribuição.
Compelidas de um lado pela natural premência em se descobrir e produzir petróleo
rumo à auto-suficiência para suprir as demandas energéticas brasileiras e, de outro,
pela inescapável necessidade de exploração dos blocos das bacias sedimentares
brasileiras que lhes couberem, as companhias de petróleo correm contra o tempo.
Por via de conseqüência, suas carteiras de projetos mais e mais tendem a crescer.
Assim sendo, o gerenciamento de projeto de qualidade, com ações centradas na eficiência e redução de custos, desempenhará papel de destaque no retorno para a sociedade e maximização da remuneração de capital dos seus acionistas.
Projetos no setor petróleo são particularmente importantes em vista do traço estratégico de que se revestem. O que está em jogo, em última análise, é a disponibilidade
de energia, imprescindível para fruição dos bens e serviços de uma sociedade industrializada, que a ciência e a tecnologia não cessam de suscitar e dispor.
Em particular, a região de Campos, no norte fluminense, tem especial interesse pelo
setor. Sua bacia sedimentar offshore é a que mais produz hidrocarbonetos no país e
exibe indícios auspiciosos, dando conta de que continuará sendo alvo de grandes
projetos. Com isso, a questão ganha contornos ainda mais complicados, visto que
no ambiente marinho, notadamente de águas profundas, como é o caso, todas as
operações são muito mais laboriosas e demasiado dispendiosas. Outra vez, os fatores tempo e custo são determinantes se se objetivam preços competitivos, o que torna decisiva sua boa gerência. De qualquer modo, os benefícios de se lograr antecipar a produção de dezenas de poços, mesmo que em uns poucos dias, fruto de uma
programação otimizada de utilização dos recursos envolvidos – todos excessivamente caros – nos projetos, podem importar receita antecipada da ordem de milhões
de dólares. É exatamente disso que trata a presente pesquisa: otimização do escalo3
O mandato de ação exclusiva da Petrobras na administração do monopólio estatal do petróleo foi invalidado pelo Congresso Nacional, em 1995, por emenda constitucional.
4
namento dos recursos na E&P de petróleo, com conseqüente redução de custos e
tempos. Isso materializa o estudo de caso do trabalho, formatado como o problema
de escalonamento de projeto (Project Scheduling Problem, PSP)
1.3
Escalonamento de Projeto e Otimização Matemática
O senso comum erroneamente presume que gerenciamento de projeto se reduz
apenas à programação de suas atividades (escalonamento). Isto está longe de ser
verdade, conquanto seu mérito não deva ser minimizado. O escalonamento é um
dos processos do gerenciamento de projeto e na verdade é melhor estudado nos domínios da pesquisa operacional como um problema de otimização combinatória. Otimização significando maximizar ou minimizar uma dada função matemática – referida como função-objetivo – refletindo algum critério de desempenho de um problema
sujeito a determinadas restrições (Chong, 1996). Otimização combinatória é o ramo
da matemática aplicada que combina técnicas de análise combinatória, programação linear e teoria dos algoritmos para resolver problemas de otimização sobre estruturas discretas (Nemhauser & Wolsey, 1988; Cook et al., 1998).
1.4
O Caso Estudado
Estudos do PSP no âmbito acadêmico, não raro, são algo descolados da realidade,
seja nas suas singularidades, seja no limitado porte dos problemas com que trabalham, daí a oportunidade de pesquisas conectadas com projetos reais.
O estudo de caso empreendido se refere ao ambiente real da Petrobras na bacia de
Campos. O caso é modelado como um PSP. Sondas e navios são cotados como recursos críticos, em virtude de sua escassez e alto custo. As intervenções nos poços
são tomadas como as atividades do projeto.
Um complicador é que, em razão de determinados recursos terem sua atuação condicionada à lâmina d’água da locação, as atividades acabam por dispor de modos alternativos de execução, cada um dos quais implicando trade-off entre duração e recursos. Semelhante problema de otimização tem o seguinte enunciado: “Alocar os K
recursos renováveis a cada uma das J atividades do projeto multimodo de maneira a
minimizar sua duração total”. Com isso, o PSP é modelado como o denominado
“problema multimodo de escalonamento de projeto com restrição de recursos” –
MRCPSP. Problemas de otimização matemática inteira dessa natureza estão entre
5
os de mais difícil tratamento, sendo classificados como NP-completos. Algoritmos de
solução exata existem apenas para os casos de instâncias de pequeno porte (até 15
atividades). Tipicamente, problemas reais envolvem centenas de intervenções.
As instâncias que aproximam condições reais são construídas através de um programa gerador de instâncias. Quatro heurísticas, i.é, procedimentos de solução aproximada, são sugeridas e implementadas em código computacional. O critério de performance é a minimização da duração total do projeto (makespan). Experimentos
numéricos com os quais se comparar o desempenho destes algoritmos são conduzidos e relatados. Antes, porém, o caso é situado em seu contexto, na esfera de ação
do gerenciamento de projeto, de maneira que permita ser apreendido em toda sua
plenitude.
1.5
Objetivos da Pesquisa
À luz de quanto foi dito, os objetivos principais deste trabalho podem ser assim resumidos:
•
Despertar a comunidade acadêmica e especialistas para a importância do
estudo regular do gerenciamento de projeto;
•
Investigar para efeito de aplicação, o estado da arte dos métodos de solução dedicados ao PSP;
•
Modelar casos reais, de grande porte, do PSP;
•
Desenvolver, implementar e experimentar métodos matemáticos aproximados de otimização voltados para solução de tais problemas.
1.6
Organização do texto.
Como se viu, o leitmotiv da presente pesquisa diz respeito à gestão dos tempos de
um projeto. Mais detidamente, referido a um estudo de caso da Petrobras no que
tange à otimização de alocação de recursos críticos às intervenções no poços de
óleo e gás. Com isso, o restante deste documento se organiza da seguinte maneira:
O capítulo 2 expõe o estado da arte do gerenciamento de projeto. Seus fundamentos e metodologia são apresentados e tendências são identificadas e comentadas
neste capítulo, que também se presta à inserção do PSP em seu contexto.
6
O capítulo 3 faz uma descrição detalhada do PSP. Seus elementos e modelos são
apresentados, bem como sua representação, classificação e notação. Comenta-se
sobre os métodos mais comuns empregados para sua solução exata e aproximada.
Termina com exposição de alguns casos especiais e de modelos que emergiram recentemente.
O capítulo 4 expõe e modela física e matematicamente o caso em estudo. Geradores de instancias são tratados juntamente com os conjuntos mais comuns atualmente disponíveis. Os chamados parâmetros de problemas de escalonamento são discutidos e, ao final, se descrevem os conjuntos de instâncias geradas para emular o
caso real e submeter as heurísticas codificadas a experimentos computacionais.
No capítulo 5 são descritas detalhadamente quatro meta-heurísticas propostas para
solução aproximada do PSP em causa, nomeadamente Algoritmo Aleatório Puro,
GRASP, Algoritmo Genético e Heurística Evolucionária Híbrida. Antes, os algoritmos
básicos, ditos esquemas de geração de escalonamento, SGS, são estudados e as
chamadas regras de prioridade são introduzidas .
O capítulo 6 discorre sobre os resultados dos experimentos computacionais cumpridos com as meta-heurísticas desenvolvidas para a solução do PSP objeto de estudo. Inicialmente o parâmetro de relaxação da GRASP e a probabilidade de mutação
dos algoritmos evolucionários são devidamente calibrados. Um entre dois operadores mutação é criteriosamente selecionado para uso nos testes. Os ensaios englobam os três conjuntos produzidos e definem a heurística de maior eficiência. Experimentos com respeito aos efeitos dos chamados parâmetros de problema também
são efetuados.
Por fim, o capítulo 7 mostra as ilações extraídas a partir do trabalho e conclui com
algumas recomendações e sugestões julgadas úteis para futuros trabalhos na área.
A dissertação também inclui um anexo, no qual se examina muito brevemente a
complexidade dos problemas de otimização, com enfoque de pesquisa operacional,
particularmente daqueles da família do difícil problema de escalonamento de projeto.
7
Capítulo 2
Onde se trata do contexto do Problema de Escalonamento de Projeto
O Gerenciamento de Projeto
M
uito brevemente faz-se aqui uma incursão pelo gerenciamento de projeto. A
partir de conceituação básica e descrição de seus métodos e processos,
tem-se uma visão panorâmica do tema, mais que nunca indispensável à boa condução de empreendimentos na órbita do moderno mundo corporativo.
Pretende-se com isso cumprir dois objetivos: ao mesmo tempo em que se busca difundir os fundamentos do gerenciamento de projeto, situa-se o problema de escalonamento de projeto, PSP – detalhadamente tratado nos capítulos subseqüentes –,
em seu contexto, mais precisamente na área de conhecimento da gestão dos tempos do projeto.
Sempre com respeito ao gerenciamento de projeto, o capítulo obedece ao seguinte
roteiro: a seção 2.1 apresenta sua estrutura geral, introduzindo sua conceituação e
algumas de suas definições básicas; a seção 2.2 trata dos seus grupos
convencionais de processos: iniciação, planejamento, execução, controle e
encerramento; na seção 2.3, suas áreas de conhecimento são brevemente
abordadas; a seção 2.4 discute resumidamente os recursos e limitações dos
sistemas comerciais com esse fim; na seção 2.5, finalmente, os avanços e
perspectivas nesta área são enfocados.
2.1
Estrutura Geral do Gerenciamento de Projeto
2.1.1 Conceituação Básica
Prevenindo-se quanto ao risco de confusão, é oportuno desde já situar os significados de administração, gerência e gestão adotados neste texto. Observando o que
8
preconiza Valeriano (1998), estes termos se distinguem segundo seu nível de competência:
•
Administração: diz respeito a ações em nível organizacional: finanças e contabilidade, vendas e marketing, pessoal e etc.;
•
Gerenciamento: sinônimo de gerência, situa-se ao nível do próprio projeto:
planejamento, controle e etc.;
•
Gestão: refere-se aos subníveis do gerenciamento, i.é, parcelas específicas
das atribuições do gerente de projeto: da qualidade, dos tempos, dos custos
e etc. (cf. seção 2.4)
Projeto
Projetos no mais das vezes são componentes críticos da estratégia de negócios de
uma organização. Projeto é uma seqüência de atividades com começo e fim limitadas por tempo, recursos e resultados. Pode-se dizer que a mais distintiva marca de
um projeto4 seja o seu caráter inovador. Uma vez concluído o projeto, a organização
dispõe de algo realmente novo. As operações rotineiras de uma empresa ou organização compartilham muitos traços em comum com um projeto. O que distingue ambos é que enquanto as operações são progressivas e repetitivas, os projetos são
transitórios e únicos.
A melhor definição para projeto talvez seja que “projeto é um esforço temporário empreendido para criar um produto – ou serviço – que é único”. Temporário estabelecendo que o projeto tem começo e fim bem definidos; único significando que o produto – ou serviço – incorpora uma característica que não divide com nenhum outro
similar.
Tipicamente, um projeto origina-se a partir de uma ou mais das contingências a seguir:
•
Exigência do cliente
•
Demanda de mercado
•
Avanço tecnológico
•
Necessidades do negócio
•
Obrigações legais
4
O termo projeto, de que trata o presente estudo, referir-se-á sempre ao seu sentido estrito, sob um
ponto de vista organizacional.
9
Usualmente a equipe envolvida é temporária, i.é, existe enquanto o projeto existir.
Exemplos são: viagem a Marte, elaboração de um novo produto, o desenvolvimento
de um campo de petróleo, aquisição um novo sistema de comunicação, construção
de uma unidade fabril, implantação de um novo procedimento nos negócios, pesquisa de um novo medicamento e etc.
Se um empreendimento reúne as cinco características a seguir, pode-se assumir
que se trata de um projeto:
(1) Começo e fim bem definidos;
(2) Tem recursos que foram especificamente alocados para aquele fim;
(3) Os resultados finais têm metas especificas de qualidade e desempenho;
(4) Segue uma predeterminada abordagem planejada e organizada para alcançar seus objetivos;
(5) Geralmente envolve uma equipe formada para aquele fim.
Certos tipos de empreendimentos são similares a projeto. Um programa é um grupo
de projetos gerenciados de modo coordenado para obter benefícios que não estariam ensejados por um projeto individualmente (p. ex., o programa nuclear brasileiro).
Um subprojeto resulta da divisão de um projeto que o supera e o comporta. Em geral, são contratados de uma outra empresa ou de outra unidade funcional das organizações (e.g., testes automatizados de programas de computador num projeto de
desenvolvimento de software).
Recursos
São o tempo, pessoas, dinheiro, máquinas, equipamentos e instalações utilizados
para implementação de um projeto. Segundo disponibilidade e consumo, podem ser
enquadrados em quatro categorias: renováveis, não-renováveis, duplamente restritos e parcialmente renováveis (cf. subseção 3.2.1)
Escopo5
O escopo pode se referir tanto ao produto quanto ao projeto:
•
Escopo do produto: características e funções que devem ser agregadas ao
produto (ou serviço);
5
Do inglês “scope”: alcance, raio de ação. Não se deve confundir com a acepção comum deste vocábulo em português: alvo, intuito; intenção.
10
•
Escopo do projeto: todo o trabalho que deve ser empreendido de modo a gerar um produto (ou serviço) com as características e funções especificadas.
Atividade ou Tarefa
Até o momento não há consenso entre os especialistas acerca da relação entre os
termos atividade e tarefa em gerenciamento de projeto. Neste documento, ambos os
temos são aplicados indistintamente. Uma atividade (ou tarefa) real sempre consome tempo e, quase sempre, recursos e pode ser entendida como uma unidade de
trabalho do projeto.
Stakeholders6 do Projeto
São os indivíduos e organizações que estão ativamente envolvidos com o projeto ou
cujos interesses podem ser positiva ou negativamente afetados como conseqüência
da execução do projeto ou por sua exitosa completação. Uma das mais destacadas
atribuições da equipe de gerenciamento de projeto é identificar os stakeholders, determinar seus interesses e expectativas e então influenciar de modo a ter um projeto
bem-sucedido. O gerente do projeto, os clientes, os beneficiários, a empresa hospedeira do projeto, os financiadores do projeto e representantes de agências governamentais formam alguns exemplos de stakeholders. Talvez um dos maiores desafios
do gerenciamento de projeto seja encontrar solução para os pleitos conflitantes de
alguns stakeholders. Em geral, incompatibilidades de demandas e necessidades de
stakeholders devem ser decididas em favor dos clientes.
2.1.2 O Gerenciamento de Projeto
A aplicação pioneira dos métodos e processos do gerenciamento de projeto tal como
aqui se apresenta é atribuída à construção do primeiro submarino nuclear pela Marinha dos EEUU, em meados da década dos 50.
A visão geral é a de que o gerenciamento de projeto é nada além de programação
(ou escalonamento) das tarefas. Nada mais falso. A programação das tarefas é tãosomente um dos processos da gestão dos tempos do projeto, que sequer deve ser
considerado como o mais relevante de todos.
6
Intraduzível, posto que não há termo correspondente no vernáculo.
11
O gerenciamento de projeto deve ser entendido como a aplicação de conhecimentos, habilidades e técnicas para dirigir as atividades de modo a alcançar ou mesmo
exceder as necessidades e expectativas dos stakeholders.
Os projetos diferem das operações ordinárias das organizações e reclamam técnicas especiais de gerência para chegarem a bom termo. Decorre daí que boa parte
do conhecimento aplicado ao gerenciamento de projeto é exclusiva. A especial atenção ao escalonamento das atividades, p. ex., é uma característica que diferencia o
gerenciamento de projeto do administração geral. A despeito disso, esta última compartilha com o gerenciamento de projeto diversos conhecimentos, tais como técnicas
de planejamento e previsões financeiras, por exemplo. Na verdade, a administração
geral fornece indispensáveis conhecimentos para o gerenciamento de projeto. Há
muitas habilidades desenvolvidas para a administração geral e que, muito provavelmente, afetam qualquer projeto. Como exemplo, liderança, comunicação, negociação, entre outros.
Projetos são, tipicamente, parte de organizações maiores do que eles – corporações, agências governamentais e associações profissionais, entre outras. A estrutura especifica de cada organização tende a influenciar o próprio projeto. A natureza
desta influência varia sobremodo. Organizações baseadas em projeto, como as firmas de engenharia, têm operações primariamente voltadas para projetos. Nesse
caso, tais organizações têm sistemas de administração que favorece o gerenciamento de projeto. Como exemplo, sua contabilidade é formatada de modo a considerar projetos múltiplos e simultâneos. Nos demais tipos de organização – companhias de petróleo, montadoras, etc. –, isso não é tão sistematizado, o que torna o
gerenciamento de projeto mais difícil. Essas organizações apenas podem contar, às
vezes, com departamentos ou divisões que na verdade operam como organizações
baseadas em projeto. Características socio-econômicas também podem afetar muito
o gerenciamento de projeto – legislação local, idioma, diferenças culturais, políticas,
e étnicas e etc.
Objetivos do Gerenciamento de Projeto
Segundo Lewis (1997), o gerenciamento de projeto resume-se em “planejamento,
programação e controle das atividades do projeto para atingir seus objetivos”. Estes
objetivos se traduzem em metas de:
•
Custo;
12
•
Desempenho;
•
Escopo;
•
Tempo;
Os quatro objetivos se relacionam da seguinte forma:
Custo = f (Desempenho, Escopo, Tempo).
O custo é função do desempenho, do escopo e do tempo. O custo é diretamente
proporcional ao desempenho e ao escopo: o custo cresce, se um ou ambos crescem. Todavia, a relação com o tempo não é linear. Até um valor ótimo para o tempo,
o custo aumenta à medida que se diminui o prazo de conclusão do projeto; em contrapartida, o custo tende a aumentar para prazos crescentes a partir desse ponto.
Existe, então, um prazo de conclusão ótimo para o projeto, no qual ocorre a melhor
performance de todos os recursos. O gráfico da figura 2.1 ilustra tal relação.
Custo vs . Tempo do Projeto
120
100
Custo
80
60
40
20
0
1
2
3
4
5
6
Tempo
7
8
9
10
Figura 2.1: Custo como função do prazo do projeto.
2.1.3 Fases e Ciclo de Vida do Projeto .
Como todo projeto é sempre um empreendimento inédito, envolve um certo grau de
incerteza. A organização detentora (ou hospedeira) do projeto usualmente vai dividilo em várias fases de modo a melhor controle de sua administração e interação com
outras de suas operações. Como é feita essa divisão, depende de especificidade de
cada organização. Uma fase se distingue pela conclusão de um produto de trabalho
tangível e verificável tal como um estudo de viabilidade ou a execução de um protótipo. A caracterização das fases não é algo rígido e universal, mas cada empresa
13
pode ter seu próprio método para estabelecer e denominar cada fase. Ilustrativamente, numa forma compacta e muito difundida pelos compêndios, pode-se dividir o
projeto em cinco fases: iniciação ou conceptual, planejamento, implementação ou
execução, controle e encerramento. Neste caso, as fases não são estanques e sucessivas, mas se superpõem parcialmente em algum período, no decurso do projeto,
havendo alternância no predomínio de cada uma delas, conforme o trabalho avança.
As fases do projeto, quando tomadas em conjunto, recebem o nome de ciclo de vida
do projeto, o qual circunscreve seu período de início e término.
Os ciclos de vida de projetos, via de regra, compartilham algumas características:
•
Os níveis de custo e pessoal são baixos no início, bem mais altos no estágio intermediário e caem vertiginosamente com a proximidade do fim do
projeto;
•
Os riscos e as incertezas são mais expressivos no início. A probabilidade de
sucesso cresce enquanto o projeto progride;
•
O poder dos stakeholders de influenciar o produto final e os custos do projeto diminui à medida que o projeto tem seu curso, porque os custos de alteração crescem com o progresso do projeto.
2.2
Processos do Gerenciamento de Projeto
O gerenciamento de projeto traduz-se em um esforço integrado onde qualquer ação
– ou omissão – em uma área pode afetar outras de suas áreas componentes. Suas
interações e seu concatenamento devem ser diretos e bem entendidos, sob pena de
suscitar atrasos e equívocos. Por exemplo, uma mudança no escopo quase sempre
afeta os custos e pode afetar ou não a qualidade do produto. Essas interações implicam trade-offs entre os objetivos do projeto: pode ser que o desempenho de uma
área será melhorado apenas em detrimento de outra. Entendendo um processo
como uma sucessão de ações visando a um resultado, o gerenciamento de projeto
assume a dinâmica de processos específicos, que interagem continuamente. Isso dá
a medida da natureza integrativa do gerenciamento de projeto.
Conforme estabelece o Project Management Institute (1996) no seu Corpo de Conhecimento do Gerenciamento de Projeto – PMBOK7 –, os processos atinentes ao
gerenciamento de projeto e que são aplicáveis à maioria dos projetos na maior parte
7
Aprovado como normalização americana ( American National Standard) para gerenciamento de projeto pelo ANSI (American National Standards Institute) em setembro de 1999.
14
do tempo, podem ser dispostos em cinco grupos, de um ou mais processos. Cada
uma das cinco subseções a seguir trata de um desses grupos.
2.2.1 Processo de Iniciação
Essencialmente, diz respeito ao reconhecimento de que um projeto – ou uma de
suas fases – deve ser autorizado e implica o compromisso em fazê-lo. Essa iniciação formal conecta o projeto com as operações rotineiras da organização. Muitas
vezes, requer tomada de decisão com relação ao projeto de maior prioridade entre
outros do portfólio da organização. Isso feito, há que se definir metas especificas
para o projeto e identificar os riscos e restrições que podem vir a lhe causar problemas, uma vez iniciado. Este grupo tem um único processo, que lhe dá o nome e cujas ações típicas são:
•
Reconhecimento que um projeto deve ser implementado;
•
Determinar o que o projeto deve empreender;
•
Definição das metas globais do projeto;
•
Definição de expectativas gerais dos stakeholders;
•
Definição do escopo geral do projeto;
•
Seleção dos membros iniciais da equipe, inclusive o gerente de projeto.
2.2.2 Processos de Planejamento
Em razão do ineditismo de um projeto, o grupo de planejamento é o que, em geral,
apresenta maior numero relativo de processos. Trata dos processos que se voltam
para definição de recursos requeridos para completar o projeto, elaboração da programação das tarefas e desenvolvimento do orçamento. Podem Inclui também definição das necessidades dos stakeholders e são estabelecidos os meios para satisfazê-las. Alguns dos processos mais representativos deste grupo são:
•
Refinamento do escopo do projeto, o que obriga balanço entre resultados,
tempo e recursos;
•
Listagem e seqüenciamento das atividades integrantes do projeto de modo
o mais eficiente;
•
Desenvolvimento da programação de tarefas trabalhável e elaboração de
orçamento visando à alocação de recursos;
•
Elaboração do plano de projeto, formalizado em um documento;
•
Obtenção de aprovação do plano pelo stakeholders.
15
Os ditos processos de facilitação, embora intermitentes e executados conforme a
necessidade durante o planejamento de projeto, também interagem e não são facultativos. Como exemplos, podem ser citados os processos de planejamento de qualidade, comunicação e risco.
2.2.3 Processos de Execução
Neste grupo estão os processos diretamente relacionados com o gerenciamento da
equipe e de outros recursos objetivando o cumprimento do que foi planejado. Alguns
processos deste grupo são descritos a seguir:
•
Execução do plano de projeto, o que implica o cumprimento propriamente dito
das atividades do projeto conforme planejadas;
•
Verificação do Escopo, que é a formalização da aceitação do escopo do projeto;
•
Garantia de Qualidade, na forma de avaliação global e continuada da performance do projeto de modo a assegurar que o projeto vai satisfazer os padrões
de qualidade estipulados;
•
Capacitação dos recursos humanos, com desenvolvimento individual ou em grupo da qualificação da equipe, visando a realçar a performance do projeto;
•
Disseminação da Informação, disponibilizando tempestivamente a informação
para os stakeholders;
•
Seleção de Fornecedores via escolha entre fontes potenciais;
•
Gerência de contratos e relacionamento com os fornecedores.
2.2.4 Processos de Controle
Este grupo de processos se dedica, grosso modo, à vigilância do projeto. Assegura
que os objetivos do projeto são alcançados ao monitorar e medir o progresso confrontando com o planejado e tomando ações corretivas quando necessário. Com
isso, alguns imprevistos de atraso, custo e escopo são contornados. O gerente de
projeto deve optar, entre algumas alternativas, aquela que melhor corrija a questão.
Por exemplo, uma atividade com atraso obriga decisão entre manter equipe em
hora-extra e sobrecarregar o custo ou alterar o cronograma, previamente concebido,
e ter repercussão no prazo de alguma das várias fases do projeto. Controle também
implica tomada de decisões preventivamente, antecipando-se a alguns problemas
possíveis. Alguns dos processos que se destacam neste grupo são assim descritos:
16
•
Controle de alterações globais, que coordena mudanças intercorrentes em
geral, inclusive aquelas afetas ao escalonamento, aos custos e à resposta
aos riscos do projeto;
•
Controle de alterações do escopo;
•
Controle de custo, em função do que consta do orçamento;
•
Controle da programação das atividades, comparando com o escalonamento predefinido;
•
Controle de Qualidade, ao monitorar resultados específicos do projeto vis-àvis os padrões de qualidade e identificar e eliminar causas de desempenho
insatisfatório.
2.2.5 Processos de Encerramento
Nesse grupo estão incluídos os processos que formalizam a aceitação da materialização do projeto – ou de uma de suas fases – e o conduzem ordenadamente para
um término. Um projeto deve ser bem concluído, no sentido ser objeto de análise e
discussões, também porque as técnicas, os procedimentos e os processos que nele
foram empregados eventualmente podem ser melhorados e adaptados para projetos
futuros. Além disso, o próprio produto gerado pelo projeto em causa pode demandar,
posteriormente, registros que, se bem relatados e analisados, contribuem para seu
bom desempenho. Os principais processos deste grupo são:
•
Conferir realizações e resultados;
•
Fechar operações e dispensar equipes;
•
Aprender pela experiência do projeto;
•
Revisão dos processos e efeitos do projeto nos stakeholders;
•
Elaboração do relatório final.
Como ultimo comentário acerca do assunto, os grupos de processos estão conectados pelos efeitos que produzem: o resultado de um torna-se o insumo (input) de outro. Os grupos de processos não são meramente um evento, mas atividades que se
interpenetram e ocorrem em variados níveis de intensidade através de cada fase de
um projeto. Embora não tão evidente, isso também acontece com os processos de
iniciação e encerramento, ainda que em menor grau.
17
2.3
Áreas de Conhecimento do Gerenciamento de Projeto
Ainda com base no enfoque processual adotado pelo Project Management Institute
(1996), assume-se que o gerenciamento de projeto encerra aplicação sistematizada
de um elenco de práticas e conhecimentos, os quais podem ser enquadrados em
áreas, segundo seus processos componentes. Estes últimos interagem e demandam
esforços, individuais ou de equipe, em função das necessidades do projeto. As assim chamadas áreas de conhecimento do gerenciamento de projeto se agrupam em
nove módulos de gestão específica: Integração, Escopo, Tempos, Custos, Qualidade, Recursos Humanos, Comunicações, Riscos e Contratações. Por incluir o tema
central do presente trabalho, a área de gestão dos tempos do projeto merece abordagem um pouco mais detalhada.
2.3.1 Gestão da Integração do Projeto
Inclui os processos requeridos para assegurar que os vários elementos do projeto
sejam adequadamente coordenados. A integração pode ser dar em vários níveis
como com as operações rotineira da organizações, os escopos do produto e do projeto, os resultados gerados por diferentes especialidades funcionais – p. ex. informática, elétrica, mecânica. Isso também pode exigir decisões que envolvem balanceamento de trade-offs entre objetivos e alternativas que são intrinsecamente conflitantes. Os processos seguintes, por serem primordialmente integrativos, são os mais
importantes desta área: desenvolvimento do plano do projeto, execução do plano do
projeto e controle de mudanças globais do projeto.
2.3.2 Gestão do Escopo do Projeto
Considera os processos indispensáveis para que o projeto inclua todo o trabalho requerido, e somente o trabalho requerido, para sua exitosa consecução . Primordialmente, refere-se à definição e controle do que está ou não está incluído no projeto.
Um projeto consiste de um único produto, mas este último pode incluir elementos
subsidiários, cada qual com seu escopo exclusivo, porém todos interdependentes. A
ferramenta básica para explicitação do escopo é a chamada estrutura de decomposição do trabalho (EDT). Consiste em listagem detalhada discriminando os elementos constitutivos do projeto, que organiza e define seu escopo total: o trabalho não
incluído na EDT está automaticamente fora do escopo do projeto. A EDT é produzida no processo de definição do escopo (cf. Lewis e Dennis). Os processos referidos
18
ao escopo são, principalmente: iniciação, planejamento, definição, verificação e controle de alterações.
2.3.3 Gestão dos Tempos do Projeto
Integram a gestão dos tempos de um projeto os processos requeridos para garantir
a sua conclusão dentro do prazo planejado. No que concerne ao cronograma das tarefas, é o próprio foco da pesquisa de tese presente, traduzido no Problema de Escalonamento de Projeto (PSP). Os principais processos envolvidos na gestão dos
tempos do projeto são:
Definição das Atividades
A definição das atividades envolve identificação e documentação das atividades especificas que devem ser conduzidas visando ao cumprimento do elementos do projeto discriminados na EDT. Implícito neste processo é a necessidade de se definir as
atividades de modo que os objetivos do projeto sejam alcançados. Ao final deste
processo, tem-se uma listagem de todas as atividades integrantes do projeto.
Seqüenciamento das Atividades
Este processo reflete o encadeamento lógico das atividades, considerando as restrições de precedência, e trata de identificar e documentar as interdependências entre
as atividades. Da precisa condução deste processo depende a elaboração de um
escalonamento realista e de boa qualidade. Como insumos, este processo recebe a
lista de atividades, a descrição do produto, as dependências das atividades. Ao final
deste processo ter-se-á o diagrama de rede do projeto (cf. figura 3.1 (c) e (b)), quase
sempre gerado por computador, expressando as dependências entre as tarefas.
Estimação de Duração das Atividades
Envolve estimativa, por especialistas, do provável período de trabalho necessário
para completar cada tarefa listada. São levados em conta, para tanto, dados históricos e requisitos e disponibilidades de recursos, entre outros fatores. Uma das técnicas empregadas é a simulação, como a Analise de Monte Carlo (Hillier, 1995). Ao
cabo deste processo, ter-se-á cada atividade com seu quantitativo de períodos estimados para sua duração.
19
Desenvolvimento da Programação das Atividades
É precisamente neste processo que se insere o problema de escalonamento de projeto, PSP. Neste texto, o escalonamento (ou programação das atividades) significa a
definição completa, mediante uso de ferramentas e técnicas, das datas inicial e final
de execução de cada atividade, tomando em conta as restrições de recursos e de
precedência – estas também ditas lógicas ou tecnológicas – entre as atividades (cf.
subseção 3.2.8).
Este processo freqüentemente deve ser repetido – juntamente com os processos relativos às estimativas de duração e de custo – antes que se tenha o efetivo escalonamento empregado no projeto. No decurso do projeto, além disso, deve ser atualizado quando imprescindível, no processo de controle adiante mencionado. Como
ferramentas e técnicas coadjuvantes na montagem do escalonamento, tem-se
PERT, CPM, simulação, nivelamento, compressão das atividades e heurísticas, entre outras, quase todas incorporadas em aplicativos comerciais de gerenciamento de
projeto, os quais vão de fato gerar o escalonamento. Enquanto se dedica a próxima
seção a estes sistemas comerciais, a seguir se comenta sobre PERT e CPM8
Tais ferramentas executam o cálculo. teórico do tempos mais cedo (EST e EFT) e
tempos mais tarde (LST e LFT) de inicio e fim de uma atividade, sem levar em conta
limitações de recursos. Calculam tão-somente o caminho crítico (cf. subseção 3.2.5)
e a janela de tempo em que cada atividade deve ser executada, quando posteriormente se consideram as restrições de recurso. Conseqüentemente, seu resultado
não pode ser considerado o escalonamento do projeto.
Método do Caminho Critico (Critical Path Method, CPM). Calcula as datas determinísticas com base na lógica da rede, nas durações predefinidas – mais prováveis –
de cada tarefa e em dado horizonte de tempo do projeto, T , que, p. ex., pode ser
obtido pelo somatório das durações das atividades. O algoritmo é útil para o cômputo das chamadas folgas das tarefas e definição do caminho crítico (cf. subseção
3.2.5).
Técnica de Revisão e Avaliação de Programa (Program Evaluation and Review Technique, PERT). Igualmente se vale das restrições de precedência expressas no diagrama de rede. Entretanto, computa o período de conclusão do projeto a partir da
8
E.I. Du Pont Company em meados da década dos 50, nos EUA, desenvolveu o CPM para gerenciamento do projeto de uma grande planta química; pouco depois, num esforço conjunto para desenvolvimento do míssil Polaris, a marinha americana e a empresa de consultoria Booz, Allen, and Hamilton
criaram o PERT. Comum na Europa e análogo ao CPM é o MPM, Metra-Potencial Method.
20
estimação da duração média ponderada das atividades que figuram no caminho crítico, num processo probabilístico. Portanto, difere do CPM essencialmente pelo uso
do valor esperado para as durações, em vez do mais provável. O PERT propriamente dito raramente é usado hoje em dia porque, entre outras limitações, tende a subestimar a duração média do projeto (cf. Morton, 1993).
Como resultado final deste processo, tem-se o escalonamento básico do projeto,
que deve incluir, no mínimo, as datas previstas de começo e fim de cada atividade.
Pode ser apresentado na forma tabular ou gráfica, nos formatos de diagrama de
rede ou gráfico de Gantt (figura 3.1(a)).
Controle da Programação das Atividades
Este processo deve ocorrer integrado com outros processos de controle das outras
áreas. Resulta em atualizações e revisões do escalonamento básico, com conseqüentes ações corretivas e lições aprendidas. Basicamente, tenta influenciar os
fatores que produzem alterações no cronograma, garantindo que as mudanças serão benéficas e gerencia tais mudanças.
2.3 4 Gestão dos Custos do Projeto
Inclui todos os processos que garantem a conclusão do projeto dentro dos parâmetros do orçamento aprovado. Volta-se precipuamente para os custos dos recursos
necessários para completação das tarefas, mas também se refere aos custos das
decisões do projeto no que tange ao uso de seu produto. As diferentes necessidades de informação dos stakeholders igualmente devem ser consideradas. Uma descrição, definindo tipos e quantidades, dos recursos requeridos para cada elemento
da EDT é resultante desta área. Compõe-se de vários processos, dos quais os mais
importantes são: planejamento de recursos, estimação de custos, orçamentação de
custos e controle de custos.
2.3.5 Gestão da Qualidade do Projeto
Abrange aqueles processos requeridos para a segurança de que o projeto vai corresponder às necessidades com as quais está comprometido. Inclui “todas as atividades da função gerencial que determinam a política da qualidade, os objetivos e as
responsabilidades e os implementam por meios tais como planejamento da qualida21
de, controle da qualidade, garantia da qualidade e melhoria da qualidade, dentro do
sistema da qualidade”, conforme a gestão da qualidade é conceituada pelas normas
da série ISO 9000, que norteia esta área de conhecimento, em conjunto com a série
ISO 10000. A propósito, Icmeli e Rom (1998), a partir de uma ampla enquête com
gerentes de projeto dos EUA, concluem que a mais importante função-objetivo de
um projeto é aquela que tem a qualidade como critério de performance (cf. subseção
3.2.1). Os principais processos pertinentes à gestão da qualidade são: planejamento
da qualidade, garantia da qualidade e controle da qualidade.
2.3.6 Gestão dos Recursos Humanos do Projeto
Esta área comporta os processos que visam ao mais efetivo uso das pessoas envolvidas no projeto, incluindo os stakeholders. Um ingrediente decisivo no sucesso de
um projeto é ter as pessoas certas no trabalho e gerenciá-las apropriadamente. A
par das técnicas gerais de RH aplicáveis no âmbito organizacional e de ampla literatura (incorporar novos paradigmas, desenvolver novas tecnologias e formular estratégias flexíveis alinhadas com a organização), o gerenciamento de projeto tem especificidades com respeito aos recursos humanos que exigem tratamento especial e
não devem ser negligenciadas. Por exemplo, o caráter efêmero do projeto implica
que as relações pessoais e organizacionais, além de novas, são igualmente temporárias. O gerente de projeto deve adotar técnicas que sejam adequadas para esta
singularidade do relacionamento. Os processos mais relevantes na gestão dos recursos humanos são: planejamento organizacional, seleção do pessoal e desenvolvimento da equipe.
2.3.7 Gestão das Comunicações do Projeto
A gestão das comunicações comporta os processos necessários para, tempestiva e
apropriadamente, assegurar geração, coleta, disseminação, estocagem e disponibilidade final da informação do projeto. Provê ligações críticas entre pessoas, idéias e
informações que são necessárias ao êxito do projeto. Envolve um corpo de conhecimentos, não exclusivos do gerenciamento de projeto, voltados para elementos tais
como seleção dos meios de comunicação, estilo de redação, liderança de reuniões,
técnicas de apresentação, entre outros. Seus processos principais são: planejamento das comunicações, distribuição da informação, relatório de desempenho e encerramento gerencial.
22
2.3.8 Gestão dos Riscos do Projeto
O risco deve ser entendido como a possibilidade de ocorrência de efeitos indesejáveis como resultado de um evento qualquer. Como todo projeto implica algo novo,
envolve razoável grau de incerteza, o que potencializa a exposição ao risco. A gestão dos riscos compreende os processos atinentes à identificação, análise e resposta ao riscos potenciais do projeto. Essencialmente, objetiva maximizar os resultados
de eventos benéficos e minimizar as conseqüências dos eventos adversos (Tavares,
1998). Esses processos são: identificação do risco, quantificação do risco, desenvolvimento de resposta ao risco e controle de resposta ao risco.
2.3.9 Gestão das Contratações do Projeto
Aplica-se aos processos exigidos para aquisição de produtos e serviços externos necessários à execução do projeto. Abrange as relações de contratos, compras e suprimentos. Também pode incluir as relações cliente/fornecedor com outras unidades
da organização hospedeira. Seus principais processos são: planejamento do aprovisionamento, seleção de fornecedores e contratados e gerência de contratos.
2.4
Sistemas Comerciais de Gerenciamento de Projeto
Introduzidos a partir da década dos 60, os últimos anos testemunharam a emergência de um sem número de software comerciais voltados para o gerenciamento de
projeto. Variam em capacidade desde aqueles para simples geração de gráfico de
Gantt até outras aplicações para mainframe, que trabalham integrados com outros
sistemas de gerenciamento corporativo; mas a diferença entre eles é menor a cada
dia.
Atualmente, torna-se muito difícil, para alguns projetos mais complexos, prescindir
do concurso de instrumentos que automatizem alguns métodos e processos do gerenciamento de projeto, que de outra forma seria extremamente trabalhoso e tedioso. Deixar que o computador se encarregue de suporte táticos na forma de cálculo
de caminho crítico, planilhas de orçamentação, gráficos e diagramas, propicia ao gerente maior disponibilidade de tempo para pensar os processos inerentes ao projeto.
Como agravante, o gerenciamento de projeto em si é um formidável gerador de relatórios, e disso os software se incumbem de modo inigualável, com grande flexibilidade para elaboração de modelos sob medida para diferentes projetos e diferentes exi23
gências dos stakeholders. Contudo, mesmo os mais sofisticados pacotes não substituem a boa liderança ou a tomada de decisão judiciosa e, de per si, são incapazes
de resolver conflitos, seja de tarefas seja de pessoal. A despeito disso, tanto para
elaboração quanto para a atualização de alguns processos, os aplicativos hoje existentes tornam-se indispensáveis, notadamente para ambiente multiprojeto. Alinhamse entre os tipos de software mais vendidos no mundo.
As pesquisas no campo dos sistemas comerciais de gerenciamento de projeto costumam acontecer em duas vertentes: análise da capacidade geral de gerenciamento
de projeto do aplicativo e sua capacidade de alocação de atividade/recursos, a saber, geração de escalonamento de boa qualidade em face das restrições do projeto.
Trabalhos do primeiro tipo podem ser encontrados , por exemplo, em (Assad, 1986 e
de Wit, 1990). Todavia, as peculiaridades de recursos funcionais destes programas
não são aqui examinadas9. O que se pretende, em vista do interesse do estudo em
causa, é concisamente discuti-los sob o ponto de vista da otimização matemática.
Os pacotes comerciais são, evidentemente, proprietários, de código fechado, com o
que a metodologia de solução neles embutida não é de conhecimento geral. Mas
sabe-se que todos eles , via o assim – inapropriadamente – chamado nivelamento
(leveling), meramente calculam uma solução viável para o escalonamento (Pyron,
1997). Para este fim, empregam diferentes algoritmos baseados em alguma regra de
prioridade (cf. seção 5.2), e não geram necessariamente o escalonamento mínimo
no que tange ao prazo de encerramento do projeto – makespan (cf. subseção 3.2.1).
Apenas em anos recentes pesquisas do segundo tipo vieram à tona (Johnson, 1992;
Maroto, 1994; Farid, 1996). Isso decorreu da ausência de capacidade de alocação
de recursos nos aplicativos anteriores à década dos 90. Além disso, os pesquisadores não dispunham de métodos de solução exata com que derivar soluções benchmark para instâncias de porte realista com as quais cotejar seus resultados (cf. seção 3.3). O estudo mais recente deve-se a Kolisch e Hempel (1996), onde o desempenho de sete aplicativos comerciais é aferido comparativamente. Testes estatísticos nesse trabalho detectaram um desvio médio de até 9,76% da solução ótima,
para instâncias simples e de pequeno porte (variando em conjuntos de 10, 20 e 30
tarefas, num total de 160 instâncias), tendo como função-objetivo a minimização do
makespan. A performance dos aplicativos é fortemente influenciada por alguns parâmetros de problema (cf. subseção 4.3.1). Por exemplo, os resultados se deterioram
9
Entidades tais como o Project Management Institute periodicamente divulgam avaliações destes
programas.
24
fortemente à medida que o número de tarefas do projeto cresce. Conquanto tenham
evoluído muito nos últimos anos, também com relação à capacidade de geração de
escalonamentos de melhor qualidade, estes software estão ainda longe dos resultados obtidos por heurísticas divulgadas mais recentemente, mencionadas no capítulo
3.
2.5
Avanços no Campo do Gerenciamento de Projeto
Muito da eficácia do gerenciamento de projeto está condicionado à sua habilidade
em identificar e integrar o vasto inventário de informações e conhecimentos gerados
nas últimas décadas nesta área. Nesse particular, avanços espetaculares têm acontecido. Em seu dia-a-dia, um gerente de projeto é permanentemente instado a tomar
decisões, todas acabando por repercutir nos objetivos do projeto: custo, tempo, escopo e desempenho. Na maioria das vezes, bom senso basta para julgar as melhores opções. Todavia, tanto melhor se, em lugar de mera intuição, o gerente puder
dispor de instrumentos para subsidiá-lo, quantitativa e quantitativamente, e guiá-lo
em direção à melhor escolha entre as várias existentes. Os métodos de análise de
decisão são concebidos para ajudar no ordenamento de complexas alternativas com
base em critérios antes tangíveis que subjetivos.
Graças aos implacáveis avanços da tecnologia em geral e, em particular, a dos computadores e também à evolução de métodos e modelos, presentemente já se pode
contar com os Sistemas de Apoio à Decisão (DSS) dedicados ao gerenciamento de
projeto. Tais sistemas facultam ao usuário a tomada de decisão mais acertada, com
base em conhecimentos previamente adquiridos de uma forma integrada. Enquanto
muito das ferramentas e produtos hoje disponíveis sustentam tomada de decisão individual, surgem continuamente sistemas coadjuvantes na decisão para grupos e organizações. Adicionalmente, essas ferramentas estão estendendo as fronteiras de
pesquisa e aplicação ao incorporar capacidade de inteligência artificial nas deliberações das gestões de contratações, custos, riscos e tempos do projeto (cf. Lewis,
1998).
No que se refere especificamente à gestão dos tempos do projeto, Antonisse et al.
(1988) estão entre os primeiros a perceber que o escalonamento de projeto é uma
área fértil para o apoio à decisão. Desde então, um grande número de protótipos
acadêmicos vem surgindo. Os esforços bem sucedidos em combinar Machine Learning (cf. Langley, 1996) e abordagens de otimização na tomada de decisão na ma25
nufatura sugeriram aplicações correlatas em escalonamento de projeto. Outras iniciativas são relatadas em Davis (1992), Slowiński (1994), Jüngen, (1995) e Norbis,
(1996).
O capítulo não estaria suficientemente completo se não mencionasse a emergência
da Internet como vetor de ampliação dos horizontes do gerenciamento de projeto,
como de resto de todos os campos do conhecimento. E este fenômeno esta apenas
começando. O uso da rede global (WWW) e tecnologias da Internet para coletar, organizar e dispor componentes de DSS para pesquisa e prática vem experimentando
progresso sem paralelo. O amplo alcance da rede internacional favorece troca de
conhecimentos nas áreas de dados, modelos e soluções benchmark para pesquisadores em todo o mundo. O longo tempo decorrido entre os resultados alcançados e
sua disponibilidade para os especialista tem encurtado dramaticamente. Caminham
nessa direção as iniciativas acadêmicas do tipo MMM (Günther, 1997), na Alemanha
e DecisionNet (Bhargava, 1996), nos EUA, protótipos de sistemas de difusão mundial de componentes de software e tecnologia de decisão. Outro exemplo é site ftp da
Universidade de Kiel (Kolisch e Sprecher, 1996), na Alemanha, que serve como repositório de conjuntos de dados e programas geradores de instâncias do PSP, para
propósito de testes computacionais, amplamente utilizado no presente trabalho (cf.
seção 4.3).
Some-se a isso que a troca de informações com os fornecedores para suprimentos
do projeto também estão sendo sensivelmente afetadas pela rede mundial, com conseqüentes reflexos nos tempos do projeto. Colocações de pedido, pagamentos de
faturas, notificações de despacho e muitas outras transações rotineiras no gerenciamento de projeto já podem ser efetuadas usando padrões de mensagens do tipo intercâmbio eletrônico de dados (eletronic data interchange, EDI), que agiliza e aperfeiçoa a troca de informações entre empresas, aproximando fronteiras globais e reduzindo substancialmente o volume de burocracia e papel.
26
Capítulo 3
Onde se apresentam os fundamentos do Problema de Escalonamento de Projeto
O Problema de Escalonamento de Projeto - PSP
O
s processos integrantes da gestão dos tempos de um projeto envolvem primordialmente ações direcionadas ao escalonamento (ou programação) das
tarefas. Escalonamento e seqüenciamento são formas de tomada de decisão que se
referem à alocação racional de recursos escassos a atividades dependentes no decurso do tempo. Esta área, mais do que qualquer outra da pesquisa operacional, se
caracteriza por virtualmente ilimitados tipos de problemas e tem sido alvo de densa
pesquisa desde a década dos 50, tendo como conseqüência um expressivo número
de artigos. Tal fascínio se prende ao elevado nível de dificuldade na solução exata
dos modelos, aliado a sua larga possibilidade de aplicação prática, o que faz surgir
uma miríade de modelos e estratégias de solução.
Com os recentes avanços ao longo dos anos, os pesquisadores têm relaxado muitos
dos pressupostos restritivos do problema original e introduzido novas e mais realistas características de problemas. Num primeiro momento, os problemas dispunham
de recursos infinitos. Mais tarde, o modelo incorporou a possibilidade de limitação de
recursos e daí surgiu o problema de escalonamento de projeto com restrição de recursos, RCPSP. Mais recentemente, com a noção de modos de execução de tarefas, este último estendeu-se para o caso mais geral do MRCPSP. O estudo do PSP,
além de ser útil para a prática do gerenciamento de projeto, também se aplica a sistemas de planejamento e programação da produção e ambiente de manufatura automatizada.
O restante deste capítulo se organiza tal como se segue: visto que tudo começou
com a programação de tarefas de manufatura, na seção 3.1 tem-se uma breve descrição de casos afetos a este ambiente; na seção 3.2, o problema de escalonamento
de projeto propriamente dito é caracterizado, com muito mais detalhes, antes que
27
seus métodos de solução sejam discutidos, o que ocorre na seção 3.3; as seções
3.4 e 3.5 se dedicam aos casos estocáticos e preemptivos, respectivamente, também de grande importância para o gerenciamento de projeto. O capítulo se conclui
com a seção 3.6, na qual dois novos modelos de PSP, julgados de interesse, são
sucintamente descritos.
3.1
Definições para Ambiente de Job shop
Quando a programação de tarefas é um processo que existe em sistemas de manufatura e produção, bem como em ambientes de processamento de dados, é referida
como problema de job shop, JSP – também se usa a expressão machine scheduling. Consiste de um grupo de diferentes máquinas que executam operações em
jobs. Dado um conjunto de jobs a serem processados em um dado ambiente de máquinas, o problema é seqüenciar os jobs, sujeitos a determinadas restrições, de maneira que um (ou mais) critério de desempenho seja otimizado. Cada job tem uma
ordem especificada de processamento pelas máquinas, i.e., um job se traduz por
uma lista de operações seqüenciadas, cada operação definida pela máquina requerida e tempo de execução. Adicionalmente, há algumas restrições relacionadas com
JSP. Por exemplo, não há precedência entre operações de diferentes jobs e uma
operação não pode ser interrompida e retomada tempos depois (não-preemptiva). É
perfeitamente conhecido tratar-se de problema NP-difícil dos mais intratáveis (Lenstra e Rinnooy Kan, 1979). Para uma investigação aprofundada das técnicas de solução dedicadas ao JSP, convencionais e avançadas, consulte-se Blażewicz et al.
(1996).
O seguinte esquema de classificação de problemas do JSP (Grahan et al., 1979 e
Pinedo, 1995) tem experimentado ampla aceitação. Um problema de escalonamento
é descrito por um terno α | β | γ . O campo α diz respeito ao ambiente das máquinas
e contém um único dado; o campo β refere-se a características do processamento e
restrições e pode conter um ou mais dados ou mesmo nenhum dado; os detalhes
acerca do critério de desempenho (cf. subseção 3.2.1) se encontram no campo γ,
que geralmente contém uma única entrada.
Segue-se uma seleta de modelos para JSP, com. as correspondentes entradas, entre parêntesis, para o campo α:
28
Job shop (Jm).
Cada job tem sua própria rota a percorrer através das m máqui-
nas. São de dois tipos: um job pode visitar qualquer máquina apenas uma vez ou
pode ser reprocessado em mais de uma máquina, assim permitindo-se recirculação.
Flow shop (fm).
As máquinas são disposta em série e todas as tarefas (job) têm
de ser processadas em cada uma das m máquinas. Todos os jobs têm o mesmo itinerário e devem ser processados em seqüência, primeiro na máquina 1, depois na
máquina 2 e assim por diante. Após completado em um processador, um job deve
aguardar na fila. Via de regra, usa-se o padrão FIFO (first in first out – o primeiro a
chegar será o primeiro a ser atendido) para a fila, i.e., um job não pode furar a fila.
Flexible flow shop (FFs).
Trata-se de generalização do ambiente flow shop.
Em vez de m máquinas em série, há s estágios em série, contendo determinado número de máquinas em paralelo cada um deles. Em cada estágio um job requisita
uma única máquina e, na maior partes das vezes, qualquer máquina pode processar
qualquer job.
Open shop (Om).
Análogo ao flow shop puro, exceto que agora os jobs po-
dem ter tempo de processamento nulo e, também, seguir qualquer rota no ambiente
de máquinas, quer dizer, diferentes jobs podem ter diferentes rotas.
Algumas possíveis entradas para o campo β , que se referem às restrições do processamento, são:
Preempções (prmp).
o processamento do job pode ser interrompido em qual-
quer tempo e retomado mais tarde, conforme conveniência do escalonamento. Enquanto isso, um outro job toma lugar na máquina.
Restrições de precedências (prec).
Obriga que um ou mais jobs tenham que ser
completados antes que determinado job possa ter permissão para iniciar seu processamento.
Para o campo γ, referente ao objetivo a ser minimizado, algumas possíveis entradas
podem ser:
29
Makespan (Cmax). Se se consideram n jobs, e Cj é o tempo de processamento do
job j, o makespan é definido como máx(C1 ,...,Cn), equivalente ao tempo de conclusão
do último job a deixar o sistema.
Tempo total ponderado de completação (∑wjCj).
A soma dos tempos pondera-
dos de completação fornece uma indicação do custo de se manter os jobs no sistema em dado escalonamento. O peso wj é um fator de prioridade relativa entre o job j
e os demais. A soma dos tempos de completação também se diz tempo de fluxo,
com o que ∑wjCj pode ser referido como tempo de fluxo ponderado.
Como ilustração da notação, J2||Cmax denota um problema de job shop com duas máquinas e makespan como critério de desempenho ao passo que P3|prmp|∑wjCj descreve uma instância10 com 3 máquinas idênticas em paralelo nas quais os jobs podem ter seu processamento interrompido e o tempo de fluxo ponderado é o objetivo
a ser minimizado.
O problema de escalonamento de projeto é mais geral do que o JSP. Com efeito,
problemas tais como os relacionados com o flow shop, open shop e job shop representam de fato casos particulares do PSP.
3.2
O Problema de Escalonamento de Projeto
Os processos componentes da gestão dos tempos de um projeto (cf. seção 2.x)
guardam relação direta com o problema de escalonamento de suas tarefas. Nos primórdios dos estudos, os problemas de escalonamento de projeto contemplavam
apenas casos em que as tarefas podiam ser executadas de um único modo, a saber,
demandando uma configuração fixa de recursos e com duração imutável. Este modelo denomina-se Problema de Escalonamento de Projeto com Restrição de Recurso - RCPSP.
Somente em fins da década dos 70 (Elmaghraby, 1977) foi introduzida a possibilidade de as atividades serem praticadas de vários modos tal que possibilitasse o consumo de diferentes recursos com reflexos no seu tempo de execução e, consequentemente, seu custo. Dessa forma, a modelagem pôde capturar o ambiente multiprojeto mais geral com condução de atividades cujo desempenho seria função discreta
dos recursos, com modelos implicando trade-offs dos tipos recurso-recurso e recurso-tempo (Sprecher, 1994). As atividades podem ser executadas de um dentre vári10
O conjunto de dados de entrada numéricos de um problema estabelece uma instância em particular.
30
os modos, os quais vão refletir combinações alternativas entre tipos e quantidades
de recursos destinados a cada uma delas. Substituindo-se um tipo de recurso por
outro, pode-se alterar o tempo de execução de uma atividade (trade-off de recursorecurso) ou, alternativamente, aumentando-se a quantidade de determinado recurso,
pode-se diminuir o tempo de execução de uma tarefa (trade-off de tempo-recurso).
O modelo que daí surge, mais geral e mais realista, é denominado Problema Multimodo de Escalonamento de Projeto com Restrição de Recurso- MRCPSP.
3.2.1 Elementos do PSP
Em qualquer caso, o PSP se constitui de interações entre atividades, recursos, relações de precedência e medida de desempenho. Assume-se que todos os dados são
disponíveis, deteminísticos e inteiros (Kolisch e Padman, 1997). O modelo resultante
é uma extensão daquele tradicionalmente empregado no JSP.
Atividades
Todo projeto envolve atividades (também se diz tarefas ou jobs), as quais devem ser
executadas para cumpri-lo com êxito. As atividades podem ser executadas de um ou
vários modos, os quais determinam sua duração, as exigências de recursos de várias categorias e, possivelmente, fluxo de caixa. Uma tarefa se classifica como preemptiva se seu processamento, por interesse do escalonamento, for suscetível a interrupção, com posterior retomada; no caso contrário, a tarefa se diz não-preemptiva. Por vezes a interrupção, com subseqüente alocação do recurso a outra tarefa, é
benéfica à otimização.
Relações de precedência
Restrições tecnológicas impõem, freqüentemente, que uma atividade j somente possa ter inicio após uma outra, dita precedente, já ter sido concluída. Nesse caso, a tarefa j diz-se dependente.
Recursos
Geralmente, as atividades, para sua completação, reclamam recursos, que podem
ser classificados de acordo com categorias, tipos e valor. Por categorias, os recursos podem ser: renováveis, não-renováveis, duplamente restritos e parcialmente renováveis.
31
Renováveis. São restritos numa base periódica (hora, dia, semana, mês), i.e., independentemente do tamanho do projeto, os recursos renováveis são sempre disponível em cada unidade de tempo de projeto. A disponibilidade por período pode ser
constante ou variar de período para período. Maquinas, equipamentos e mão-deobra são exemplos desta categoria;
Não-renováveis.
Considerando o horizonte de tempo inteiro para o projeto, tais
recursos são limitados, i.e., o projeto (ou fase do projeto) dispõe de uma quantidade
inteira para toda sua execução, sem restrição dentro de cada período isolado. O exemplo clássico é o orçamento do projeto. Matéria prima também pertence a esta categoria.
Duplamente restritos.
Sofrem a dupla restrição de serem limitados baseados em
período de tempo e no horizonte de planejamento. Um exemplo seria um orçamento
total do projeto que estipula um valor para o desembolso periódico. Mão-de-obra especializada também pode ser enquadrar como recurso duplamente restrito se, e.g.,
um trabalhador especializado pode permanecer apenas um limitado número de períodos no projeto. Via de regra, tal categoria não é explicitamente considerada, em
vista de poder ser enquadrada simultaneamente em um recurso renovável e um
não-renovável que são então acrescentados às suas categorias correspondentes.
Parcialmente renovável.
Introduzida mais recentemente, esta categoria limita a uti-
lização dos recursos dentro de um subconjunto do horizonte de planejamento. Como
exemplo, pode-se citar o de mão-de-obra especializada somente disponível em um
dado período no projeto (cf. seção 3.6).
A classificação por tipo é especifica para cada projeto e aprofunda a distinção dos
recursos de cada categoria segundo suas funções.
Por fim, cada tipo de recurso tem um valor associado, representando a quantidade
disponível. Sempre que pelo menos uma categoria de recursos apresenta alguma
restrição de disponibilidade, o PSP é rotulado problema de escalonamento com restrição de recursos.
32
Critérios de Desempenho do PSP
Nos domínios da otimização matemática, uma medida (ou critério) de desempenho
(ou performance) diz respeito ao que se pretende otimizar – minimizar ou maximizar. Refere-se, portanto, diretamente à função objetivo e, quando dois ou mais valores são comparados, funciona como uma medida para aferir a qualidade da solução,
e. g., de um problema de escalonamento. A seguir são enumerados alguns dos mais
comuns dentre os vários critérios de desempenho empregados para o PSP.
Minimização de Makespan.
Trata-se do mais pesquisado e largamente aplicado
objetivo da programação de tarefas de um projeto. O makespan se define como o
tempo decorrido entre o inicio da primeira tarefa e o fim da ultima tarefa a ser completada. É, portanto, a própria duração de todo o projeto. Uma vez que usualmente
se assume o instante de tempo t=0 para o inicio do projeto, minimizar o makespan
reduz-se a minimizar o máximo dos tempos de conclusão de todas as tarefas e tomar o tempo de conclusão da última como o valor do makespan. A minimização do
makespan é classificada como medida regular de performance cuja definição vai
mais adiante.
Maximização do Valor Presente Liquido.
Quando nível significante de fluxo de
caixa está presente, representando desembolso para cobrir despesas de iniciação e
progresso do projeto, o Valor Presente Liquido (Net Present Value – NPV) é a medida mais apropriada como critério de performance do projeto. Refere-se ao balanço
entre as despesas para consecução da tarefa e a receita auferida após sua conclusão. A solução de modelos matemáticos deste tipo resulta nos tempos ótimos de inicio para cada tarefa e também no NPV ótimo do projeto. Dada a complexidade desse problema combinatório, a saber, dificuldade na obtenção de modelos matemáticos e sua solução, métodos exatos de solução aplicam-se somente a pequenas instâncias. Mais sobre o tema encontra-se em Herroelen et al. (1997), que conduzem
uma imersiva revisão da literatura sobre a maximização do NVP como critério de
performance, a partir do trabalho pioneiro de Russell (1970).
Maximização da Qualidade.
Icmeli e Ron (1998), em seu trabalho 99, onde exa-
minam empiricamente o ambiente de projetos nos EUA, detectaram que o mais im33
portante dos objetivos, na expectativa do gerente de projeto, é maximizar a qualidade. Com base nisso, em um estudo pioneiro (Icmeli e Ron, 1997), os autores introduzem um modelo de programação linear mista dedicado a maximizar a qualidade do
projeto. A qualidade de um dado projeto é mensurada baseado na quantidade de
tempo e dinheiro despendidos em retrabalho de atividades que não atendem as especificações dos stakeholders.
Minimização do Custo.
Em vista de sua larga aplicação prática, este objetivo tem
atraído enorme atenção dos pesquisadores nos últimos tempos. Os objetivos baseados em custo apresentam duas vertentes: (a) custo das atividades e (b) custo dos
recursos. Em objetivos visando ao primeiro caso, a via pela qual as atividades são
executadas, a saber, o tempo de inicio e/ou os modos escolhidos, resulta em custos
diretos que são minimizados. Exemplos são os tradicionais problemas, contínuos, do
tipo tempo/custo trade-off, e suas extensões discretas (Demeulemeester et al.,
1996).
Com objetivos voltados para o custo dos recursos, o escalonamento das atividades
influencia o custo indiretamente, via recursos. Como exemplo, pode-se citar o caso
clássico de nivelamento de recursos, onde se minimiza o desvio entre o estado de
distribuição de recursos contra um estado desejável (Bandelloni et al., 1994). De forma combinada, o problema também pode ser multicritério, onde duas ou mais destas medidas de performance são simultaneamente otimizadas (cf. Slowiński et al.,
1994 e Deckro & Hebert, 1990).
3.2.2 Descrição do PSP
Antes de tudo descreve-se aqui o modelo mais geral, para o ambiente multiprojeto e,
em seguida, suas simplificações. Consideram-se P projetos, cada um com seus prazos específicos de liberação (release date), πj, e de entrega (due date), εj. O (super-)
projeto global se constitui de um conjunto J = {0,1,...,J,J+1} de atividades (tarefas,
jobs) a serem executadas. Duas tarefas fictícias, j=0 e j=J+1 representam, respectivamente, a tarefa única de partida (fonte) e a única de encerramento (sumidouro) do
projeto global. Ambas executáveis de um único modo, associado com duração zero
e consumo nulo de recursos. A cada tarefa j correspondem dois conjuntos, Pj e Sj,
que reúnem suas tarefas predecessoras imediatas e sucessoras imediatas, respectivamente. As atividades são topologicamente numeradas, com o que um predeces34
sor de j tem um rótulo menor que j. Além disso, em cada projeto as tarefas são rotuladas consecutivamente com FJp (LJp) sendo a primeira (última) tarefa do projeto p.
Desse modo, o projeto p tem FJp-LJp+1 tarefas.
Três categorias de recursos são empregadas para condução do (super-)projeto: o
conjunto dos recursos renováveis, R, o conjunto dos recursos não-renováveis, N, e o
conjunto dos recursos duplamente restritos, D. Cada recurso r ∈ R tem capacidade
periódica de Κ
ρ
r
e cada recurso r ∈ N tem uma capacidade total no projeto de Κ
ν
r
.
Recursos da categoria duplamente restrito são limitados com respeito à capacidade
periódica, Κ
ρ
r
, e capacidade total, Κ
ν
r
.
Cada tarefa real j pode ser processada em um dentre m = 1, ... , Mj modos diferentes. Assume-se que os modos sejam alinhados na ordem não-crescente das durações. Um modo define de forma única uma duração e uma demanda de recursos.
Se a tarefa j é praticada no modo m, sua duração não-preemptiva é de djm11 períodos,
seu uso de recurso renovável (duplamente restritos) r ∈ R em cada período em que
está em execução é de κ
ρ
jmr
unidades e seu consumo de recursos não-renováveis
(duplamente restritos) r ∈ N é de κ
ν
jmr
unidades ao longo de seu processamento.
Observe-se, portanto, que os recursos duplamente restritos não são levados em
conta explicitamente, mas incorporados às outras duas categorias. Os parâmetros
são assumidos inteiros e sumariados na tabela 3.1.
Uma solução viável do problema mais geral deve escalonar cada atividade em um
de seus modos de maneira que as restrições de precedência e as de demanda de
recursos escassos sejam respeitadas.
Mínimo e Máximo Time Lags
Na prática é freqüentemente necessário considerar intervalos de tempo específicos
entre execuções das tarefas e não meramente a relação de precedência pura. Define-se então mínimo e máximo time lag para situações do tipo em que execução simultânea ou sem atraso de várias atividades é exigida; prazos para subprojetos ou
atividades individuais são prescritos; existem janelas de tempo para disponibilidade
11
O subscrito m é suprimido na notação dos parâmetros nos casos em que a atividade dispõe de apenas um modo de execução. Destarte, para os modelos do RCPSP, djm denotar-se-á simplesmente dj.
35
de recursos; ou em escalonamentos voltados para ambientes de produção sob encomenda – make-to-order production.
Com isso, entre os inícios de duas atividades, time lags mínimos e máximos podem
ser especificados. Em geral, estes parâmetros dependem do modo de execução que
se atribui a cada atividade. Sejam i,j ∈ J duas atividades diferentes executadas nos
mín
modos mi e mj , respectivamente. Um time lag mínimo d imi jm j ≥ 0 significa que entre
os instantes de início das atividade i e j deve ser observado um intervalo de, no mínimín
máx
mo, d imi jm j unidades de tempo; Um time lag máximo d imi jm j ≥ 0 quer dizer que entre
os instantes de início das atividade i e j deve ser observado um intervalo de, no mámín
máx
ximo, d imi jm j unidades de tempo. Um mínimo time lag d imi jm j = d imi , equivalente à du-
ração da atividade i, implica que apenas restrição de precedência simples existe entre as atividades i e j enquanto que time lags em geral indicam restrição de tempo.
Nos chamados problemas com restrição de precedência, nenhum máximo time lag
tem que ser observado e qualquer mínimo time lag corresponde à restrição de precedência. Os time lags também podem ter como referência uma outra combinação
entre o início e o fim das duas atividades consideradas. Assim, podem assumir as
modalidades início-início, início-fim, fim-início e fim-fim.
3.2.3 Modelo Conceitual do PSP
No caso mais geral, um PSP implica otimizar um dado critério de desempenho, função dos tempos de início e atribuição dos modos. Isso exige, para cada atividade j ∈
J, determinar o tempo de início e um modo de execução mj ∈ Mj tal que o uso de recursos renováveis pelas atividades executadas simultaneamente não exceda a capacidade destes recursos em qualquer tempo, o consumo dos recursos não-renováveis se restrinja às suas disponibilidades e os time lags, mínimo e máximo, sejam
observados.
Um escalonamento pode ser especificado por um vetor F, dos tempos de conclusão
de cada atividade j ∈ J,
F = (FT0, FT1, ... , FTJ+1)
e um vetor m das designações de modos,
m = ( m0, m1, mj, ... , mJ+1).
36
Minimizar f(F,m)
s. a
FTh ≤ FTj - djm
(1)
j = 1,...,J+1; h ∈ Pj
∑
kjmr ≤ Kr
r∈R;t ≥ 0
∑
kjmr ≤ Kr
r∈N
j∈ A ( t )
j∈ J
(2)
(3)
(4)
F ≥ 0
(5)
Tabela. 3.2 Modelo Conceitual do PSP
Uma vez dado um escalonamento, o conjunto de atividades que estão em progresso
(ativas) no tempo t é dado por A(t) = { j ∈ J | FTj – djm ≤ t < FTj }.
Conceitualmente, um modelo para o PSP (Talbot e Patterson,1978) envolvendo um
único projeto, pode ser representado conforme se exibe na tabela 3.2.
(1) define a função objetivo f(F,m) como função dos tempos de conclusão e da designação dos modos;
(2) é a restrição que estabelece os time lags mínimos e máximos que devem ser observados;
(3) garante que o emprego dos recursos renováveis a cada período não exceda sua
capacidade;
(4) assegura que as restrições de consumo dos recursos não-renováveis sejam obedecidas;
(5) finalmente, define o domínio das variáveis de decisão.
Obviamente, a formulação (1)-(5) é apenas um modelo conceitual, em vista de não
contemplar dispositivo para atribuição dos modos e, além disso, ser o conjunto A(t)
função das variáveis de decisão. Isso obstaculiza a solução do problema por técnicas da programação inteira mista (MIP), utilizando ferramentas do tipo LINDO ou
CPLEX. De modo a se contornar este impeditivo, uma solução deve ser tentada a
partir da formulação 0-1, descrita na próxima seção.
O PSP com modos alternativos de execução das tarefas cujo objetivo seja min
f(F,m):= FTn+1 diz-se Problema de Escalonamento de Projeto Multimodo com Restrições de Recursos com mínimo e máximo time lags e usualmente se denota
MRCPSP/max. Um MRCPSP/max com uma única opção de processamento por atividade é chamado Problema de Escalonamento de Projeto com Restrições de Recursos com mínimo e máximo time lags , resumidamente RCPSP/max. De outra forma, se todas as restrições de tempo em MRCPSP/max e RCPSP/max são do tipo
37
que reflitam meramente as precedências das tarefas, então se obtêm o RCPSP,
Problema de Escalonamento de Projeto com Restrições de Recursos, e o MRCPSP,
Problema de Escalonamento de Projeto Multimodo com Restrições de Recursos,
respectivamente.
3.2.4 Modelo Matemático MIP do PSP Multiprojeto
Seja dado um limitante superior T para o makespan do (super-)projeto correspondente a um horizonte de tempo de planejamento, usualmente sendo calculado pelo
somatório das durações máximas das tarefas. Podem ser usadas as relações de
precedência e os modos de menor duração para derivar uma janela de tempo, i.e., o
intervalo [EFTj, LFTj] que contém os tempos de conclusão viáveis no que tange à
precedência, empregando o tempo mais cedo, EFTj, e o tempo mais tarde, LFTj, de
conclusão de cada tarefa j, j = 0, ...,J+1. Os tempos EFTj e LFTj são calculados pelo
MJ+1
∑
minimizar φ ( x ) =
LFTJ + 1
∑
tx J + 1,mt
m = 1 t = EFTJ + 1
sujeito a:
Mj
LFT j
∑ ∑
m = 1 t = EFT j
Mj
LFT j
∑ ∑
m = 1 t = EFT j
Mj
LFT j
∑ ∑
m = 1 t = EFT
Mi
LFTi
∑ ∑
m = 1 t = EFTi
J
Mj
j= 1
m= 1
J
Mj
j= 1
m= 1
∑ ∑
∑ ∑
x jmt = 1
j = 0, ...,J+1
(6)
p = 1, ..., P; j = FJp, ... , LJp
(7)
p = 1, ..., P; j = FJp, ... , LJp
(8)
j = 0, ...,J+1, i ∈ Pj
(9)
x jmq ≤ K rtρ
r ∈ R ∪ D ; t = 1, ... , T
(10)
x jmt ≤ K νr
r ∈N ∪ D
(11)
j = 0, ...,J+1, m=1, ..., Mj, t = EFTj, ...,LFTj
(12)
( t − d jm ) x jmt ≥ π
tx jmt = ε
t ximt ≤
ρ
k jmr
k νjmr
xjmt ∈ {0,1}
∑
q= t
LFT j
∑
t = EFT j
p
Mj
LFT j
∑ ∑
m = 1 t = EFT j
t + d jm − 1
p
( t − d jm ) x jmt
Tabela 3.3 Modelo Matemático MIP do PSP multiprojeto
método tradicional de recursão avante e em retrocesso, conforme se mostra em
Morton e Pentico (1993). Este mesmo método também computa os tempos mais
38
cedo, ESTj, e mais tarde, LSTj, de início para cada atividade. Com as janelas de tempo tal como exposto, reduz-se substancialmente o número de variáveis do problema,
que agora já pode ser declarado como um problema de programação linear inteira
mista, conforme introduzido por Pritsker et al. (1969) e estendido por Talbot (1982).
Para tanto, são usadas variáveis de decisão binárias do tipo:
 1, se a atividade j é completada no perído t e modo m
x jmt = 
 0 , noutro caso
nas quais j = 0, ...,J+1, m = 1, ..., Mj e t = EFTj , ..., LFTj .
Se o objetivo é encontrar um escalonamento das tarefas de mínimo makespan, i.e.,
tendo o makespan como medida de desempenho, o modelo derivado é aquele exibido na tabela 3.3 , para ambiente multiprojeto sem restrição de time lags específicos.
Como no (super-)projeto têm-se uma única tarefa final (j=J+1, sumidouro), minimizando-se a função objetivo φ ( x ) referida a esta tarefa, de fato minimiza-se o makespan .
Com respeito às restrições associadas, tem-se que:
(6)
garante que a cada tarefa sejam designados exatamente um modo e um tem-
(7)
po de completação dentro de sua janela temporal [EFTj, LFTj];
assegura que nenhuma atividade se inicie antes da data de liberação (release
(8)
date) de seu projeto correspondente;
obriga que nenhuma tarefa se conclua depois do prazo devido (due date) de
seu projeto associado;
(9) força obediência às relações de precedência;
(10) previne o modelo contra inviabilidade no uso dos recursos renováveis e daqueles duplamente restritos;
(11) limita o consumo de recursos não-renováveis e dos duplamente restritos às
suas disponibilidades preestabelecidas;
(12) finalmente, define todas as variáveis de decisão como sendo binárias.
Observe-se que, como já foi apontado, os recursos duplamente restritos não têm de,
explicitamente, ser formulados, de vez que podem ser facilmente tomados em conta
apenas aumentando apropriadamente o conjunto dos recursos renováveis e não-renováveis.
Esta formulação incorpora alguns problemas de escalonamento com restrições, de
precedência e de recursos. Se se tem um único projeto, a classe de problema do
39
tipo RCPSP , no qual cada tarefa dispõe de um único modo de execução, estaria caracterizada tomando-se P =1, Mj=1, N=D=0, πp = 0 e εp = T . Igualmente para um único projeto, se cada tarefa pode ser processada em mais de um modo, tem-se o
MRCPSP, o qual seria modelado fazendo P =1, πp = 0 e εp = T . Ainda, os problemas
de escalonamento de produção do tipo job shop, flow shop e open shop bem como
aqueles com uma ou múltiplas máquinas estão incluídos. Com efeito, pode-se demonstrar que o problema de job shop (JSP) clássico, onde m equivale ao número de
máquinas, corresponde a um RCPSP com |R| = m recursos renováveis, cada um dos
quais tendo disponibilidade de uma unidade por período (Sprecher et al., 1995). Assim, o problema faz parte da classe NP-difícil (Kolisch e Sprecher, 1996). Além disso, se |N| > 1 mesmo o problema de viabilidade para (6)-(12) é NP-completo (cf. Anexo).
A mais comum das medidas desempenho é minimização do makespan, que é classificada como regular (cf. subseção 3.2.7). Contudo, outras podem ser consideradas.
Apenas a título de ilustração e sem descer a detalhes, seguem-se algumas outras
medidas:
Denotando πj (εj) a data de liberação (prazo devido/prometido) da tarefa j e fazendo
cmjt o fluxo de caixa produzido pela tarefa j quando processada no modo m e concluída no período t, têm-se:
Minimização dos atrasos ponderados:
1 J+ 1
φ (x) =
∑
J + 1 j= 0
Mj
LFT j
∑ ∑
m= 1 t = ε + 1
( t − ε j ).x jmt
Minimização do tempo de fluxo médio ponderado:
φ (x) =
1 J+ 1
∑
J + 1 j= 0
Mj
LFT j
∑ ∑
m= 1 t = ε + 1
( t − ε j ).x jmt
Maximização do valor presente líquido (NPV):
φ (x) =
J+ 1
Mj
LFT j
j= 0
m = 1 t = EFT j
∑ ∑ ∑
c jmt .x jmt
Dos três exemplos, apenas a maximização do NPV é classificada como medida nãoregular. Outras medidas de performance, regulares e não-regulares, são discutidas
em Brucker et al. (1998a).
40
3.2.5 Representação de um PSP
Além do gráfico de Gantt, como se apresenta na fig. 3.1 (a), em geral dois tipos de
representação são empregados para traduzir a idéia de diagrama de rede de um
projeto: atividade-no-arco(ativity-on-arc, AOA), conforme a fig. 3.1 (b), baseado em
eventos e atividade-no-vértice (activity-on-node, AON), como mostrado na fig. 3.1
(c), baseado em atividades.
Na representação do tipo AOA, os nós representam eventos e os arcos representam
as atividades. Atividades fictícias são acrescentadas para representar o começo e o
término de um projeto além de servir para preservar as relações de precedências
entre as tarefas, como é caso da atividade G na fig. 3.1 (b). Em redes do tipo AON,
as atividades e seus parâmetros são representados pelos nós enquanto arcos direcionados indicam suas relações de precedência. Diferentemente do gráfico de Gantt,
as representações de rede citadas retratam graficamente as interdependências entre
as tarefas.
PSP’s cujo objetivo seja minimizar o makespan quase sempre adotam redes do tipo
AON (cf. fig. 4.1), porque dispensam acréscimos de atividades fictícias para registrar
a relação de precedência, o que contribui para minorar o esforço computacional.
Não é por outra razão que software profissionais de gerenciamento de projeto preferem esta modalidade. Essa vantagem pode ser decisiva quando se consideram
grandes projetos. Em verdade, o problema de modelar uma rede AOA de mínimo
número de atividades fictícias que corresponda a um dado projeto é NP-difícil (Garey
& Johnson, 1979). As razões da superioridade da representação AON sobre a AOA
podem ser encontradas em Neumann e Schwindt (1995).
O emprego de arcos partindo do fim de uma atividade até o início de outra (arcos
tipo fim-início) com peso nulo constitui apenas a forma mais simples de utilização de
redes AON . Significa que tão logo todas suas predecessoras estejam concluídas, a
atividade j pode ter início com respeito à precedência. Quando indispensável, time
lags são introduzidos pela utilização de pesos. Mínimos time lags são marcados por
pesos positivos nos arcos enquanto máximo time lags recebem pesos negativos.
Além daqueles do tipo fim-início, os arcos também podem ser dos tipos fim-fim, início-início e início-fim (Neumann e Schwindt, 1995).
41
tarefa
B
D
A
(a)
F
C
1
2
3
E
4
5
6
tempo
7
8
3
(b)
1
B
tarefa
A
2
2
duração
3
10
11
12
13
D
G
C
4
9
4
5
E
4
F
6
2
1
D
B
tarefa
(c)
4
3
A
2
duraç
E
C
1
F
2
4
Figura 3.1 Métodos de representação para o PSP: (a) gráfico de Gantt; (b) rede
do tipo atividade-no-arco (AOA); (c) rede do tipo atividade-no-vértice
(AON).
Em vista do exposto, tipicamente, um PSP é representado por uma rede AON acíclica e numericamente rotulada de modo que uma atividade j recebe um índice maior
que o de todas as suas predecessoras (cf. figura 4.1). Com isso se tem o chamado
grafo de precedência das tarefas.
Diferentemente do PSP com mínimo makespan como objetivo, quando se lida com o
problema de maximizar o NPV, a representação apropriada da rede é indispensável,
porque a lógica dos fluxos de caixa exige registro preciso. Numerosos artigos estudam e sugerem representação sob medida para situações específicas. Detalhes podem ser encontrados em Kolisch e Padman (1997).
42
Caminho critico
Caminho crítico, em um diagrama de rede do PSP, é definido como o caminho no
grafo de precedência de maior comprimento entre as atividades fictícias de início e
de fim do projeto quando as restrições de recursos são relaxadas. Seu comprimento
corresponde ao makespan para o caso do PSP de recursos ilimitados calculado com
o método CPM (cf. subseção 2.3.3). Nesse caso, todas as atividades, cujos ESTj|LSTj
(ou EFTj|LFTj ) assumam valores que diferem, apresentam as chamadas folgas, representadas pela diferença entre estes tempos. Por extensão, uma atividade incluída no caminho crítico se diz atividade crítica. Da definição de caminho crítico, decorre que uma atividade crítica apresenta folga nula.
3.2.6 Notação e Classificação do PSP
Conforme já salientado, o PSP corresponde ao caso mais geral dos problemas de
escalonamento, em razão de os modelos do JSP (machine scheduling) serem casos
particulares do escalonamento de projeto. Até o trabalho de Brucker et al. (1998a),
não havia nenhum esquema de classificação para o PSP que fosse também compatível com o que é comumente aceito para o machine scheduling [cf. seção 3.1]: diferentes pesquisadores usavam diferente simbologia para representar um mesmo problema. Havia então uma lacuna entre os dois tipos de problemas de escalonamento
com respeito a uma notação unificada bem como a um esquema de classificação.
Sucede que o PSP representa uma generalização dos problemas de escalonamento de atividades (jobs) em ambientes do tipo job shop e flow shop. A nomenclatura
então existente para o JSP (cf. seção 3.1) é adaptada e ampliada pelos os autores
citados de modo a abranger os casos do PSP e identificar precisamente seus problemas. Além de uma notação comum, eles sugerem um esquema de classificação,
i.e., uma descrição do ambiente de recursos (campo α ), das características das atividades (campo β ) e das medidas de desempenho (campo γ ), com o qual se podem
enquadrar os modelos mais importantes. Como exemplo, empregando o esquema
proposto sem exatamente detalhar todas as possíveis entradas para os campos, alguns modelos de escalonamento de projeto que aqui são discutidos recebem a seguinte nomenclatura:
•
PS|prec|Cmax : RCPSP, i.e., PSP monomodo, com makespan como função objetivo;
•
MPS|prec|Cmax : MRCPSP, i.e., PSP multimodo, com makespan como função objetivo;
43
•
PS|temp|Cmax : RCPSP/máx, i.e, PSP com mínimo e máximo time lags, com makespan como função objetivo.
•
F
PS|temp| ∑ c j β
FT j
: PSP com objetivo maximizar o NPV onde β é o fator de des-
F
conto por período e c j é o fluxo de caixa associado à atividade j cuja conclusão
é assumida ocorrer no período FTj = Sj + dj. O fluxo de caixa pode ser positivo,
para pagamento recebido, ou negativo, para custo incorrido.
3.2.7 Medidas Regulares de Desempenho
Quando se tem uma medida regular de desempenho, dois escalonamentos que diferem somente no tempo final de uma atividade permitem comparação para um dado
problema e se pode, por conseguinte, afirmar que o escalonamento que tem o menor tempo de conclusão para esta atividade é no mínimo tão bom quanto o outro,
quer dizer, aquele domina este. Esta seção define medida regular de desempenho
para o caso monomodo (RCPSP) que facilmente se estende para o caso multimodo,
de maior amparo na realidade.
Definição 1
(Sprecher et al. 1995). Sejam, respectivamente, FTo, ..., FTJ+1 os tempos de conclusão das atividades 0, ..., J+1. Uma medida de desempenho é um mapeamento
φ :  ≥J 0+ 2 →  ≥ 0
que associa a cada (J+2)-upla (FTo, ..., FTJ+1), dos tempos de conclusão, um valor de
desempenho φ ( FT0 , , FTJ + 1 ) .
Quando se pretende a minimização, uma medida de desempenho diz-se regular se
φ é monotonicamente crescente com respeito ao ordenamento vetorial dos compo'
'
nentes, i.e., para φ ( FT0 , , FTJ + 1 ) > φ ( FT0 , , FTJ + 1 ) implica
FT j ≥ FT j' ∀ j , 0 ≤ j ≤ J + 1 e FT j > FT j' ∃ j , 0 ≤ j ≤ J + 1 .
Como já observado, a medida regular de desempenho mais comumente utilizada
para o PSP é a minimização do makespan. A noção de medida regular de desempenho pode ser imediatamente estendida ao MRCPSP. Nesse caso, cada atividade
pode ser processada de vários modos, indicando as interações entre custo, duração
e recursos. Uma vez que a cada atividade j seja atribuído um modo, a classificação
do escalonamento reduz-se àquela do RCPSP ora apresentada.
44
3.2.8 Classificação de Escalonamentos: Viável, Ativo, Semi-ativo e Sem-atraso
Antes do trabalho pioneiro de Sprecher et al. (1995), que introduz uma classificação
precisa e geral, na qual se baseia esta seção , a maioria dos pesquisadores não fazia menção à tipificação dos escalonamentos utilizados nos problemas do gerenciamento de projeto. Em alguns casos, apenas se lança mão diretamente da classificação convencional utilizada no contexto do JSP, sem qualquer adaptação. ”A razão
disso é, de certo modo, explicada pela forma como o assunto é apresentado pelos livros-textos mais freqüentemente citados (Baker, 1974 e French, 1982), nos quais as
definições são mais ilustrativas do que formais e assim suscetíveis de ambigüidades
no caso mais geral do RCPSP”, argumentam Sprecher et al. (1995). Entretanto, uma
adequada classificação dos escalonamentos é útil para o estudo do PSP, porque
configura critério coadjuvante na categorização dos procedimentos para sua solução
baseada nos tipos de escalonamento para os quais se voltam. Ao cabo disso, a metodologia estendida se aplica também ao JSP.
Um escalonamento pode ser definido como uma (J+2)-upla S = (ST0 , ..., STJ+1) na qual
STj denota o tempo de início da atividade j, 0 ≤ j ≤ J+1. Considerem-se A(t) o conjunto das atividades ativas, i.e., cujo processamento está em curso no período t,
0≤ t≤ T ,
A(t) := { j ∈ J | STj ≤ t < STj + dj }. e
Pj o conjunto das tarefas predecessoras imediatas de j.
Extraídas de Sprecher et al. [1995], têm-se as seguintes definições:
Definição 2
Um escalonamento S é dito viável se obedece às relações de precedência enquanto
observa as restrições de recursos. Isto é,
STi + d i ≤ ST j , j = 1,...,J+1, i ∈ Pj e
∑
j∈ A( t )
k jr ≤ K rρ
r ∈ R, t = 0 ,...,T .
Definição 3
Um left shift da atividade j, 0 ≤ j ≤ J+1, é uma operação em um escalonamento viável
'
S que resulta um outro escalonamento viável S’ de modo que STi = STi para i,
45
0 ≤ i ≤ J + 1, i ≠ j . Se, após o left shift, STj - ST j' = 1, a operação se diz left shift de
período unitário.
Definição 4
Uma operação do tipo local left shift em j, 0 ≤ j ≤ J+1, é aquela que se obtém após
aplicar-se sucessivamente um ou mais left shift de período unitário no escalonamento viável S .
Definição 5
Um left shift global da atividade j, 0 ≤ j ≤ J+1, é aquele que não pode ser obtido pela
aplicação de um left shift local.
Definição 6
Um escalonamento viável é semi-ativo se nenhuma das atividades j, 0 ≤ j ≤ J+1, é
passível de operação left shift. local.
Definição 7
Um escalonamento viável é ativo se nenhuma das atividades j, 0 ≤ j ≤ J+1, é passível de operação left shift., local ou globalmente.
Cada RCPSP pode ser unicamente transformado em outro do tipo RCPSP de duração de período unitário (UTDRCPSP) no qual cada atividade j, 1 ≤ j ≤ J, é subdividida em dj atividades, cada qual com duração unitária (Davis e Heidorn, 1971) . Desta
forma, um escalonamento viável S de um RCPSP corresponde de modo único a um
escalonamento viável UTDS do UTDRCPSP.
Definição 8
Para o RCPSP, um escalonamento viável S se diz sem-atraso (non-delay) se seu
correspondente escalonamento UTDS é ativo.
46
Teorema
Seja SC o conjunto dos escalonamentos, SV o conjunto dos escalonamentos viáveis,
SSA o conjunto dos escalonamento semi-ativos, SA o conjunto dos escalonamentos
ativos e SND o conjunto dos escalonamento sem-atraso. Então, vale a seguinte relação:
SND ⊆ SA ⊆ SSA ⊆ SV ⊆ SC.
Observações:
•
Se se considera uma medida regular de desempenho φ e um escalonamento S’
se obtém a partir de outro, S, por uma operação left shift de uma atividade j,
0 ≤ j ≤ J + 1 , então S é dominado por S’ com respeito a φ .
•
Dentro de um left shift local, cada escalonamento intermediário tem de ser viável,
por definição.
•
'
Um left shift global de j, 0 ≤ j ≤ J+1, obriga STj - ST j > 1
•
Um escalonamento semi-ativo, em geral não único, pode ser gerado a partir de
um escalonamento viável por uma sucessão de left shift locais.
Finalizando a seção, é de importância salientar que Sprecher et al. (1995) provam
que, quando se considera uma medida regular de performance, o conjunto dos escalonamentos sem-atrasos pode não conter um escalonamento ótimo.
3.3
Métodos para Resolução do PSP
Se o PSP é irrestrito no que se refere aos recursos e tão somente restrições de precedência devem ser observadas, o problema torna-se polinomialmente solucionável
por um simples algoritmo de recursão avante, no qual cada atividade é programada
em seu tempo mais cedo, tendo em conta as relações lógicas da rede associada.
Em razão disso, esta seção trata apenas de solução do problema restrito no sentido
amplo, tema central do presente trabalho.
Adiante se faz uma breve revisão das estratégias mais eficazes difundidas pelos
pesquisadores, com ênfase nos anos 90, inicialmente para o RCPSP seguido do
MRCPSP. Para um histórico do assunto até o início da década dos 70, veja-se o minudente trabalho de Davis (1973). A partir dos 70 e até início dos 90, sugere-se
como fonte de consulta o artigo de Icmeli et al. (1993). Circunscreve-se a investiga47
ção aos métodos que se dedicam àqueles problemas cujo objetivo é a minimização
do makespan que, como se vê nos próximos capítulos, é o escopo do estudo de
caso. Ademais, por igual motivo, métodos de solução heurística são discutidos mais
detidamente.
Os métodos de solução do PSP, para efeito didático, podem ser enquadrados em
uma dentre duas vertentes: exatos e aproximados.
Métodos de Solução Exata
Nesse caso, a meta é o calculo da solução ótima da função objetivo. Os métodos de
solução exata (ou, simplesmente, métodos exatos) têm sido usados mais freqüentemente para geração de soluções benchmark, em face da natural dificuldade de cálculo da solução ótima do problema (cf. Anexo).
As estratégias até agora utilizadas para a minimização do makespan são do tipo:
programação dinâmica, programação zero-um e esquemas de enumeração implícita
com branch & bound. Ultimamente, em razão de seus resultados superiores, há um
nítido predomínio dos métodos enquadrados neste último tipo, o qual pode ser resumidamente descrito como se segue:
Método branch&bound
Suponha-se o problema de seqüenciar n tarefas independentes em um processador, dispondo-se de uma função com a qual se possa calcular o valor numérico da
solução, i. é, a qualidade do escalonamento. O método branch&bound inicia por gerar uma árvore de decisão com n ramos, representando as n opções possíveis para
o primeira tarefa a ser executada, compondo assim o primeiro nível. Ato contínuo,
cada ramo do primeiro nível se ramifica (branch) também, nesse caso n-1 vezes,
construindo o segundo nível, para cobrir todas as possíveis alternativas das n-1 tarefas remanescentes como a segunda a ser processada. Prosseguindo-se dessa forma, sucessivamente, até o n-ésimo nível, a árvore atinge n! ramos, um número que
pode ser gigantesco, a depender, obviamente, da quantidade de tarefas. Em vez,
portanto, de avaliar todas as soluções, o procedimento identifica e suprime (poda)
regiões da árvore nas quais se pode provar não haver solução ótima e, assim, diminui o espaço de enumeração. Essa fase está associada à operação de fixação de limites (bounding), ao envolver o cálculo de limitantes inferiores/superiores para a solução ótima em cada um dos nós gerados na fase anterior (branching). Sucessiva48
mente analisando e podando partes da árvore, o método termina por encontrar a solução exata (se não se esgotar antes o tempo computacional preestabelecido).
Métodos de Solução Aproximada
Os procedimentos cujo propósito é o cômputo de soluções tão próximas quanto possível da solução exata dizem-se métodos de solução aproximada (ou, simplesmente,
métodos aproximados ou sub-ótimos). Também, freqüentemente, são referidos meramente como heurísticas.
Heurística é uma técnica que tenta a resolução de problemas matemáticos via busca
de soluções sub-ótimas, em um razoável custo computacional, sem ser capaz de garantir otimalidade, nem indicar o quão próximo do ótimo a solução encontrada está.
Anos atrás, decidir-se por abordagem heurística era encarado como, por assim dizer, admissão de derrota. Mas, de há muito, já se sabe que a maioria dos problemas
combinatórios de escalonamento são inescapavelmente intratáveis (Garey & Johnson, 1979). “Se se insiste em algoritmos que garantidamente encontrem soluções
ótimas, o atual estado da arte tem somente respostas exponenciais para oferecer.
Por isso, é sem surpresa que a maior parte dos algoritmos para escalonamento são
heurísticos por natureza”, argumenta Schirmer, 1998.
Estratégias heurísticas para o PSP, tendo makespan como objetivo, basicamente
enquadram-se em quatro metodologias: escalonamento baseado em regra de prioridade, branch&baund truncado, conceitos de arcos disjuntivos e abordagens metaheurísticas12.
Métodos baseados em regra de prioridade
Ainda representam a classe mais importante, a despeito de serem já bastante antigos. Isso se deve, entre outras razões, à sua facilidade na elaboração e implementação e baixo custo computacional, em termos de tempo e memória. Essa característica permite integrá-los como sub-rotinas rápidas em abordagens meta-heurísticas
mais sofisticadas. Em verdade, a imensa maioria de programas comerciais de gerenciamento de projeto basea-se em simples regras de prioridades (Kolisch 1996a).
Uma estratégia desse tipo para solução do PSP é formada por dois componentes:
uma regra de prioridade e um esquema de geração de escalonamento. Quanto aos
12
Procedimentos que, tipicamente, exploram o conhecimento adquirido com a avaliação de soluções
previamente visitadas.
49
esquemas de geração de escalonamento, dois tipos se distinguem (cf. seção 5.x): o
método em série ou serial e o método em paralelo. Compostos de J estágios, ambos
terminam por gerar um escalonamento viável, à medida que acrescentam atividades
a um escalonamento parcial. A cada estágio, o esquema constrói o conjunto de todas as atividades escalonáveis, chamado conjunto de decisão. Uma atividade é então tomada desse conjunto, utilizando como critério de escolha uma regra de prioridade específica. Kolisch – 1996b demonstra que, enquanto o esquema em série
gera escalonamentos ativos, o esquema em paralelo produz escalonamentos sematrasos. A depender do número de escalonamentos gerados, um procedimento baseado em regras de prioridade pode ser classificado em monopasse, produzindo
apenas uma solução, ou multipasse, para geração de mais de uma solução.
Branch&bound truncado
Análogo ao esquema enumerativo branch&bound já descrito mas, em vez de rastrear toda a árvore de enumeração, conduz apenas uma exploração parcial. Desse
modo, o processamento é interrompido tão logo seja atingido um critério de parada e
retorna a melhor solução, não necessariamente a exata (e.g., Alvares-Valdés & Tamarit, 1996).
Algoritmos de arcos disjuntivos
Utilizam a metodologia desenvolvida por Balas–1969 [13] para o JSP. A idéia básica
por trás das abordagens derivadas é estender as relações de precedência (o conjunto dos arcos conjuntivos) ao se acrescentarem arcos adicionais (os arcos disjuntivos). Essa fase se dá de maneira que os conjuntos de atividades tecnologicamente
independentes, mas que não podem ser escalonadas simultaneamente por limitação
de recursos (conjuntos proibidos mínimos) sejam destruídos. Desse modo, o escalonamento de menor tempo mais cedo se mantém viável em precedência e recursos.
Estratégias meta-heurísticas exploram o espaço viável de modo global e surgiram
em anos recentes. As de maior destaque são Busca Tabu (TS) –Tabu ou Taboo Search – , Simulated Anealing (SA), GRASP (Feo e Resende, 1994) e Algoritmos Genéticos (GA) (Goldberg, 1989). Estas duas últimas são descritas no capítulo 5, enquanto adiante se faz um resumo funcional das duas primeiras.
Busca Tabu
50
Trata-se de um método de busca local que surgiu a partir do trabalho precursor de
(Glover, 1989 e 1990). Uma lista tabu é um conjunto de soluções definidas por informações das últimas iterações do procedimento. O número de elementos desse conjunto é um valor fixo ou estipulado pela estado da busca ou de um problema em particular. Dada uma solução e sua vizinhança, o algoritmo faz mover para uma outra
solução da vizinhança que apresenta melhor valor para a função objetivo. Contudo,
movimentos que levam a uma solução da lista tabu são proibidos, i.e., são tabu, o
que previne que o método reexamine soluções mais recentemente visitadas. Se não
houver movimento que melhore a solução corrente, a busca tabu executa aquele
que introduz menor mudança no valor da função objetivo.
Um elemento básico na busca tabu é o chamado critério de aspiração, o qual define
quando um movimento, embora constante da lista tabu, é permitido. Todo esse mecanismo permite avaliar maior número de ótimos locais, o que faz crescer a possibilidade de cálculo de solução ótima global. Um critério de parada, além do tempo de
execução e número total de iterações, pode ser imposto por um limite no número de
movimentos consecutivos com os quais não se produz mais nenhuma melhoria.
Simulated Anealing
O método foi proposto por Kirkpatrick et al. (1983) e tem sido amplamente aplicado
na solução aproximada de problemas de otimização. É inspirado na analogia entre a
mecânica estatística e a otimização combinatória e, portanto, tem origem bem diversa da busca tabu mas, em comum, ambos os métodos são fundamentalmente concebidos para evitar ou escapar de ótimos locais.
O termo annealing refere-se ao resfriamento e recristalização de material em processos de sistemas térmicos. A matéria, inicialmente aquecida além de seu ponto de fusão, tem sua temperatura baixada paulatinamente, com base em uma programação
específica (annealing scheduling), até que a vizinhança da temperatura de solidificação seja alcançada, na qual o sistema atinge o seu estado de energia mínima
(ground state). Em última análise, o método SA é uma simples abordagem Monte
Carlo (cf. Hillier, 1995) que simula o comportamento do sistema para alcançar o
equilíbrio térmico a uma determinada temperatura em uma dada programação de
resfriamento.
3.3.1 Algoritmos de Solução Exata para o RCPSP
Exemplos de procedimentos elaborados para minimização do makespan são:
51
•
programação dinâmica (Carruthers & Battersby, 1966);
•
programação zero-um (Pritsker et al.,1969 e Patterson & Huber, 1974);
•
esquemas de enumeração implícita com branch&bound (Talbot & Patterson,
1978; Stinson et al., 1978; Christofides et al.,1987; Demeulemeester et al., 1996;
Simpson & Patterson, 1996).
Segue-se uma rápida discussão a respeito de alguns algoritmos que foram ou são
estado-da-arte e dedicados ao PS | prec | Cmax.
No algoritmo de enumeração de Talbot & Patterson (1978) as atividades são ordenadas numa lista respeitando as relações de precedência. Partindo da primeira tarefa
da lista, o processo de enumeração tenta escalonar a próxima atividade da lista o
mais cedo possível dentro de sua janela temporal e observando limitações de precedência e recursos. A enumeração básica é incrementada por cortes de redes que facultam podar uma parte da árvore de enumeração. Simpson & Patterson (1996) implementam este algoritmo em processadores paralelos.
O algoritmo de Stinson et al. (1978) é do tipo branch & bound baseado na árvore de
enumeração desenvolvida originalmente para o RCPSP com recurso único. Cada nó
da árvore representa um escalonamento parcial viável. A seleção dos nós é governada por um conjunto de seis regras de prioridades.
Demeulemeester et al. (1996) apresentam uma extensão da abordagem de Christofides et. al. (1987). Comparado com o método anterior, de Stinson, se diferencia principalmente pela árvore de enumeração, na qual novos nós são criados considerando
o conjunto das atividades que são adiadas, em vez daquelas que são escalonadas.
Brucker et. al. (1998b), valendo-se da experiência adquirida em trabalho para o ambiente job shop , sugerem uma abordagem branch & bound completamente nova,
quando introduzem um conceito inédito de relações para pares de tarefas: conjuntiva, para pares que não apresentam precedência; disjuntiva para tarefas que não podem ser processadas simultaneamente por limitações de recursos; paralela, para
pares que têm que ser executados simultaneamente pelos menos em um período e,
finalmente, flexibilidade, para pares que não guardam nenhuma das relações anteriores. O método utiliza três tipos de limitantes inferiores: programação linear com relaxação de restrições; metodologia de job shop de duas máquinas ; e seqüência critica de Stinson et al. (1978).
52
Sprecher (1997) adapta seu procedimento exato originalmente criado para o PSP
multimodo e o aplica para o caso RCPSP, sendo o método mais competitvo hoje disponível.
3.3.2 Algoritmos de Solução Aproximada para o RCPSP
Apresenta-se uma revisão sucinta dos algoritmos desenvolvidos para minimização
do makespan:
Procedimentos baseados em regras de prioridades
Referências de trabalhos onde se utilizam os esquemas em série e em paralelo, tanto monopasso quanto o multipasso, podem ser encontrados no alentado trabalho de
Kolisch & Padman (1997). O emprego do método paralelo em um único passo é
mais freqüente do que o serial.
Kolish & Drexl (1996) propõem um procedimento de busca adaptativa que é uma variação do caso multipasso baseado nos esquemas de geração em série e em paralelo. Mausser & Lawrence, (19XX), empregam o método paralelo para gerar uma solução viável em conjunto com estrutura de blocos para melhorar o makespan do escalonamento. Na tentativa de diminuir o tamanho do projeto, o procedimento basicamente reescalona blocos individuais.
Procedimentos baseados em branch & bound truncado
Em Alvares-Valdés & Tamarit (1996), os nós consistem de conjuntos de atividades
que têm que ser atrasadas. Em vez de enumerar todos os nós descendentes, o procedimento, implícita ou explicitamente, elege um nó. Basicamente, nessa heurística
o mecanismo de geração da árvore de enumeração é o mesmo daquele mostrado
em Demeulemeester & Herroelen (1992) e sugerido em sua essência por Christofides et al. (1987).
Procedimentos baseados em Arcos disjuntivos
Exemplos de aplicação podem ser encontrados em Shaffer et al. (1965), Bell & Han
(1991) e Alvares-Valdés & Tamarit (1996). Shaffer et. al. (1965) restringem o escopo
para os conjuntos proibidos nos quais todas as atividades no escalonamento mais
cedo são processadas ao mesmo tempo. Alvares-Valdés & Tamarit (1996) sugerem
quatro diferentes modos de destruir o conjunto mínimo proibido. Bell & Han (1991)
53
apresentam um algoritmo de duas fases. A primeira fase é similar à estratégia de
Shaffer et al. (1965) e a segunda tenta melhorar o resultado gerado na primeira ao
remover arcos redundantes, cancelar as atividades do caminho crítico e repetir a primeira fase.
Procedimentos meta-heurísticos
A abordagem de busca local desenvolvida por Storer et al. (1992) para o ambiente
job shop é explorada nos trabalhos de, e.g., Leon & Balakrishnan (1995) e Cho &
Kim (1997), de modo a adaptá-la ao RCPSP. Essencialmente, se codifica a solução
como uma lista de números que atribui a cada atividade um valor de prioridade. Ao
se utilizar essa lista em um esquema de geração de escalonamento obtêm-se uma
solução viável e um valor para o makespan. Este tipo de codificação pode ser aproveitado para diferentes tipos de métodos de busca local tais como busca tabu, simulated annealing, algoritmo genético e GRASP.
Hartmann (1997b) propõe um algoritmo genético cuja codificação é baseada em permutação que contém conhecimento específico do problema e o compara favoravelmente com outros dois: o algoritmo genético de Lee & Kim (1996), que utiliza uma
codificação baseada no valor da prioridade e com o método de Özdamar (1996),
adaptado para o RCPSP, que se baseia numa representação de regras de prioridade.
Baar et al. (1997) propõem dois algoritmos de busca tabu que diferem pelas vizinhanças. Um codifica uma solução como uma lista de atividades que pode ser convertida em um escalonamento fazendo uso do esquema de geração em série; o outro algoritmo gera sua vizinhança a partir da solução utilizando o método de Brucker
et al. (1998b).
Relatos de comparação entre os métodos aproximados dão conta de que atualmente os que apresentam melhores resultados são o algoritmo de busca adaptativa de
Kolisch e Drexl (1996), a busca tabu de Baar et al. (1997), o algoritmo genético de
Hartmann (1997b) e o método de simulated annealing de Bouleimen & Lecocq
(1998). Segundo resultados de testes conduzidos por Kolish & Hartmann (1998),
avaliando performance de heurísticas em instâncias maiores, os algoritmos de Hartmann (1997b) e Bouleimen e Lecocq (1998) são os mais promissores entre os aqui
examinados. Não obstante, mais recentemente, Hartmann (1999) idealizou uma
heurística evolucionária que supera em desempenho todos os métodos até agora
54
disponíveis para solução do PS | prec | Cmax. Trata-se de um algoritmo genético que,
ao mesmo tempo em que avalia uma solução e tende a computar outra de melhor
qualidade, também escolhe automaticamente o procedimento mais adequado para
resolver o problema, com base no conhecimento específico da instância e, por isso,
recebeu o qualificativo de auto-adaptável.
3.3.3 Algoritmos de Solução Exata para o MRCPSP
Todos os procedimentos exatos para o problema MPS | prec | Cmax são extensões de
métodos branch&bound originalmente propostos para solução do PS | prec | Cmax.
Com base em seu trabalho anterior (Talbot & Patterson, 1978), Talbot (1982) propõe
uma estratégia de solução heurística de duas fases. Na fase um, tarefas, modos e
recursos renováveis são selecionados de sorte que se possa acelerar o procedimento de enumeração da fase seguinte. Na fase dois se emprega uma lista de atividades e se escolhe a próxima atividade da lista para ter início o mais cedo e em seu
modo de menor duração. Alguns trabalhos posteriores são refinamentos deste método. Hartmann & Drexl (1997) generalizaram o procedimento exato de Stinson et al.
(1978) para o contexto multimodo. Sprecher et al. (1997) estendem o esquema de
enumeração de Demeulemeester & Herroelen (1992) para o caso multimodo, sendo
o método que atualmente apresenta melhor desempenho.
Muito embora amplamente estudados, tais métodos têm apenas limitada aplicação
em vista de sua incapacidade para resolução de problemas de grande porte, mais
comuns no mundo real. Em geral, falham ao tentar resolver instâncias com mais de
15 atividades (Kolisch & Drexl, 1997), daí mais largo emprego de métodos heurísticos.
3.3.4 Algoritmos de Solução Aproximada para o MRCPSP
Heurísticas para este caso, no mais das vezes, empregam:
•
regras de prioridade;
•
simulated annealing;
•
algoritmo genético.
55
Procedimentos baseados em regras de prioridades
Boctor (1993), em seu método do tipo multipasso, emprega um esquema de geração
em paralelo modificado, no qual uma atividade está no conjunto de decisão se for
viável nos recursos em pelo menos um modo. A escolha das tarefas é governada
pelos modos de menor duração e pela regra de prioridade MSLK (cf. seção 5.2).
Drexl & Grünewald (1993) sugerem uma abordagem de amostragem aleatória tendenciosa referida como regret-based. O valor regret de um candidato j mede, no pior
caso, as conseqüências que poderiam advir da escolha de outro candidato. Valemse da regra de prioridade SPT e do esquema de geração em série e é considerado o
esquema de amostragem de melhor desempenho. Slowiński et al. (1994) sugerem
uma estratégia multicritério em seu sistema de apoio à decisão (DSS) para o
MRCPSP com objetivos de tempo e custo. O método é fundamentado em três tipos
de heurísticas com base em regras de prioridade, simulated annealing e branch &
bound. Seu ponto chave é a lista de atividades, viável em precedência, e construída
a partir de uma entre doze regras de prioridades. O DSS foi proposto antes como um
protótipo, com o que não se relata nenhum experimento computacional rigoroso.
Özdamar & Ulusoy (1995) ampliam sua abordagem de análise baseada em restrição
local para resolver o caso multimodo com |N|=1. O método usa um esquema de escalonamento paralelo para decidir via as assim chamadas condições essenciais qual
par atividade-modo deve ser escolhido. Os autores relatam resultados que são consistentemente melhores que métodos monopasso baseados em regra de prioridade
e também superior a um do tipo multipasse. A abordagem baseada em restrição sofre de duas desvantagens: (1) a complexidade no tempo do pior caso é exponencial
e (2) mostra-se inadequada para problemas mais restritos no que tange a múltiplos
recursos não-renováveis.
Kolisch & Drexl (1997) apresentam um procedimento de busca local que especialmente leva em conta recursos não-renováveis escassos. O método inicialmente obtém uma atribuição de modos viável seguido de uma busca local executada na designação dos modos. Cada atribuição viável dos modos é avaliada pelo algoritmo de
busca adaptativa dos mesmos autores (1996).
56
Procedimentos meta-heurísticos
Slowiński et al. (1994) foram o pioneiros na tentativa de utilizar o simulated anealing
para solução do PSP multimodo. Com base na lista de escalonamento, eles sugerem uma vizinhança de intercâmbio aos pares onde uma nova lista é gerada ao permutar as posições de duas atividades escolhidas aleatoriamente que não sejam dependentes. O esquema de geração de escalonamento em série é utilizado para converter a lista num escalonamento. Boctor (199X) também sugere um método baseado em simulated annealing que opera em uma lista de escalonamento. A abordagem
é de substituição de vizinhança, na qual uma tarefa eleita ao acaso é deslocada para
uma nova posição na lista que seja viável em precedência.
Özdamar (1996) elabora um algoritmo genético que parte de idéias de Storer et al.
(1992). Uma solução é representada por duas listas, cada um das quais com J+1
componentes. A primeira define o modo de execução para cada tarefa; a segunda
lista especifica, para cada uma das J+1 iterações do esquema de geração em paralelo, a regra de prioridade com a qual uma atividade é selecionada do conjunto de
decisão.
No algoritmo genético de Hartmann (1997a), um indivíduo é representado também
por duas listas. Uma lista de atividades viáveis em precedência e a segunda de designação dos modos. Com base em ambas as listas, o procedimento produz um escalonamento fazendo uso do esquema de geração em série. Novos indivíduos são
criados por cruzamento ao se extrair parte da informação genética da “mãe” e a parte complementar a partir do “pai”. O método genético de Mori & Tseng (1997) é análogo.
Hartmann (1997a) registra excelentes resultados obtidos com seu algoritmo evolucionário. Ele o compara com os algoritmos de Kolisch e Drexl (1997) e Özdamar
(1996). O método de Hartmann produz um desvio médio de 0,22% do makespan ótimo de um conjunto de instâncias-padrão de teste. As estratégias de Kolisch & Drexl
(1997) e Özdamar (1996). apresentaram desempenhos semelhantes com desvio
médio de mais de 0,8%. Assim, o algoritmo genético de Hartmann exibe um desvio
médio que se mostra aproximadamente 4 vezes inferior ao dos outros dois métodos
heurísticos cotejados. É o método aproximado que computa os melhores resultados
atualmente para solução do MRCPSP.
57
Para concluir a subseção, registre-se que, em menor medida, heurísticas baseadas
em programação inteira também têm sido utilizadas. Como exemplo, veja-se Oğuz &
Bala (1994). Além disso, os últimos tempos têm assistido à emergência de estratégias para solução de problemas de Pesquisa Operacional fundadas em abordagens
concebidas para o campo da Inteligência Artificial (IA) (cf. Wall, 1996). No que se refere a escalonamento de tarefas, e.g., Schimer (1998) desenvolve um método de seleção de algoritmos para solução do RCPSP que compila experiência e subsídios de
casos passados (ou seja, instâncias) para solução de novos casos. Trata-se de aplicação do chamado case-based reasoning (CBR) , que originalmente não foi desenvolvido para problemas matemáticos. Com o emprego do CBR, Schirmer (1998) demonstra os benefícios da seleção algoritmo mais adequado para uma dada instância, função de alguns de seus parâmetros como tamanho e fator recurso (RF).
3.4
O Caso do PSP com Duração Estocástica das Atividades
Até aqui, todos os métodos e modelos examinados assumem tempos determinísticos de execução das tarefas do projeto. Contudo, muitas vezes, em projeto da vida
real, não basta calcular bons escalonamentos baseados em tempos determinísticos
de execução porque tal pressuposto raramente se confirma, i.e., os tempos de processamento diferem substancialmente do previsto. Tais tempos são apenas estimação e, portanto, sujeitos a inúmeros imprevistos que os afetam, gerados por fatores
intercorrentes (atrasos de toda ordem, e.g., condições climáticas e impedimentos legais ).
De modo a contornar os inconvenientes emanados do imponderável, assume-se que
o tempo de execução é uma variável aleatória dj com o que se tem d = (d1, d2 ,..., dJ)
como vetor (aleatório) dos tempos de processamentos com distribuição de probabilidade P (GG joint probability distribuition), suposta conhecida a priori, embora haja
métodos de solução que dispensam este pressuposto. Adicionalmente, entre os diferentes tempos individuais dj pode haver dependências estocásticas que são representadas pela distribuição P. O problema estocástico de escalonamento daí resultante se denota PS | prec, pj = sto | Cmax.
A importância de se tomar em conta a natureza probabilística das durações no planejamento do projeto fica patente quando se observa que, nos métodos deteminísticos, há uma sistemática subestimação do valor do makespan, mesmo quando se
58
dispõe de recursos ilimitados. O makespan determinístico, computado a partir do valor esperado dos tempos de processamento, E(dj), é menor que o valor esperado do
makespan, ou seja,
Cmax(E(d1), ... E(dJ)) ≤ E(Cmax (d1, ... ,dJ)),
que pode se tornar arbitrariamente grande com o aumento do número de atividades
reais J, ou, para J fixado, com o incremento da variância dos tempos de processamento (Heller, 1981).
É de se notar que a técnica PERT (cf. subseção 2.3.3) tenta capturar aproximadamente a natureza estocástica das durações das tarefas para casos de recursos infinitos, portanto pouco realistas. Para uma revisão abrangente dos modelos e métodos para casos probabilísticos, com recursos limitados ou ilimitados, veja-se Brucker
et. al. (1998a). Conquanto de especial relevância, casos estocásticos não se incluem
no escopo do presente trabalho.
3.5
O Caso do PSP com Tarefas Preemptivas
Um pressuposto fundamental nos modelos e métodos ótimos e sub-ótimos discutidos até agora é que as tarefas são não-preemptivas. Melhor dizendo, os modelos
clássicos de PSP não consideram os casos de preempção, em que as tarefas podem ser interrompidas numa fase intermediária de sua execução e, posteriormente,
retomadas. Como conseqüência, muito pouco se conhece dos benefícios em potencial que eventualmente poderiam surgir com esta possibilidade de interrupção no
processamento. A introdução de preempção nos problemas de escalonamento de
tarefas aumenta extraordinariamente o número de soluções viáveis.
A literatura sobre este assunto é quase inexistente. Digno de nota é o trabalho de
Demeulemeester & Herroelen (1996), que desenvolvem um procedimento B&B para
o RCPSP sob disponibilidade constante e variável dos recursos e que permanece
como um dos poucos procedimentos dedicados ao modelo. Considera-se que o processamento das atividades pode ser suspenso temporariamente, a qualquer instante
de tempo discreto, e reassumido posteriormente com zero custo de tempo de set
up13. Slowiński (1980) e Weglarz (1981) também sugerem métodos exatos para o
caso preemptivo. Contudo, consideram o modelo que prevê tempo contínuo de execução, e não discreto, para o processamento das diferentes tarefas, o que pode não
13
No caso, tempo de set up compreende o período que vai da decisão de se reiniciar a execução de
uma tarefa até sua retomada efetiva, i.e., tempo de preparação.
59
ser válido em circunstâncias reais. Considerações de ordem prática podem exigir
tempos discretos de execução das tarefas. Até onde se sabe, a literatura não registra pesquisa que cuide do caso PSP multimodo e tarefas preemptivas.
3.6
Novos modelos para o PSP
Recentemente idealizados, existem dois modelos que retratam de forma mais precisa duas condições de tarefas não-preemptivas de projetos que ocorrem com
freqüência na prática (Drexl et al., 1998). Trata-se dos casos em que se têm (1) recursos parcialmente renováveis e (2) identidade de modo de tarefas. Ambos são noções que implicam substancial extensão dos conceitos comuns de programação de
atividades.
(1) Quando se tem que observar disponibilidade variável de recursos, a saber, restrição de capacidade dos recursos para subconjuntos de períodos, o modelo construído é referido como problema de escalonamento de projeto com restrição de recursos parcialmente renováveis (RCPSP/π). Isso constitui uma generalização dos
modelos mais comuns de PS | prec | Cmax e substitui com vantagens todos os tipos
de recursos escassos, tais como os renováveis e os não-renováveis. O conceito torna-se ferramenta valiosa para, e.g., facilitar a solução de problemas de escalonamento de horário (timetable) e turnos de revezamento. Além disso, Schirmer & Drexl
(1997) demonstram que recursos parcialmente renováveis podem ser empregados
para expressar numerosos tipos de relações lógicas no escalonamento de tarefas.
Também vários requisitos práticos podem ser modelados, tais como cotas mínimas
e máximas, bem como matéria referente a calendário.
60
(2) A identidade de modo significa uma expressiva ampliação no tratamento do caso
multimodo, onde o conjunto de todas as atividade é particionado em subconjuntos
disjuntos compreendendo todas as atividades que devem ser processadas em um
mesmo modo. No caso convencional, todas as atribuições de modos são mutualmente independentes no sentido de que, designando um modo a uma tarefa j, não
obriga que qualquer outra tarefa seja executada de um modo específico. Por vezes,
isso não é interessante e, na prática, ocorrem situações em que mais de uma atividade devem ser executadas de um mesmo modo. Isso deu ensejo ao assim chamado problema de escalonamento de projeto com restrição de recursos e identidade de
modo (MIRCPSP), introduzido na literatura de escalonamento de projeto por Salewski et al. (1996). Nesse artigo também se prova que o MPS | prec | Cmax é caso especial daquele mais geral, com identidade de modo. Como exemplo, a situação de escalonamento de estafe de auditores é uma aplicação mais imediata.
61
Capítulo 4
Onde se modela o caso em estudo e se geram as instâncias de teste
O PSP de Alocação de Recursos Críticos na E&P de
Petróleo
E
m vista das peculiaridades geológicas de seu território, os novos projetos de
exploração e produção (E&P) da indústria de petróleo no Brasil compartilham,
entre outras, duas tendências marcantes: crescimento em número e, cada vez mais,
locações marítimas, notadamente em águas ultraprofundas. Sucede que a exploração e a produção nessas circunstâncias é sempre muito complexa e dispendiosa.
Como desde sempre, os recursos mais escassos continuam sendo os financeiros e
baixar custo torna-se crucial no acúmulo de vantagens competitivas entre as empresas em geral, particularmente as companhias de petróleo. Nestas últimas, a maior
parte do orçamento se destina às atividades diretas de E&P, principalmente com dispêndios para contratações, de serviços e de equipamentos, via de regra pagas em
moeda forte. De outro lado, o fator tempo nos projetos atuais assume especial relevância, também em face das exigências contratuais, por parte da ANP14, vinculadas
a prazos de pesquisa das áreas de concessão nas bacias sedimentares.
É precisamente isso que torna oportuno o presente estudo de caso de uma companhia de petróleo: otimização da programação dos recursos críticos no gerenciamento de projetos de E&P com conseqüente redução de tempos e custos. Melhor dizendo, o caso do PSP objeto de estudo se traduz na definição do melhor seqüenciamento das operações em campos15 marítimos de petróleo, com vistas a atender as
metas de produção e estratégia de implantação dos novos projetos, implicando tempos e custos mínimos. Esses temas – gerenciamento de projeto e otimização –,
14
Agência Nacional do Petróleo, autarquia reguladora da indústria do petróleo.
Campo de petróleo é uma área produtora com vários poços. Província petrolífera é a denominação
para uma determinada região produtora, que reúne campos de petróleo e/ou gás natural.
15
62
quando focados em petróleo, têm despertado crescente interesse nos pesquisadores. Os trabalhos de Chung & Carroll (1995), Harding (1997), Zaver (1998), Cortes
(1998) e Turner et al. (1998) são exemplos disso.
Indispensáveis à execução das atividades mencionadas, os – assim chamados no
contexto dos projetos de E&P em consideração – recursos críticos são extremamente caros e, por isso, exigem especial atenção no que concerne ao controle dos gastos globais do projeto. Como exemplo, algumas unidades flutuantes de perfuração.
Trata-se de equipamento de vanguarda tecnológica e porte gigantesco, contratado
de firmas estrangeiras, cujo custo diário pode alcançar cifras além de US$
150,000.00.
Objetivando rigor descritivo e entendimento preciso, sempre que surgem no texto, os
termos da indústria de petróleo sublinhados a seguir devem ser entendidos conforme a definição oficial que se lhes sucede:
•
Exploração: conjunto de operações ou atividades destinadas a avaliar áreas, objetivando a descoberta e a identificação de jazidas de petróleo ou gás natural;
•
Desenvolvimento: conjunto de operações e investimentos destinados a viabilizar
as atividades de produção de um campo de petróleo ou gás;
•
Produção: conjunto de operações coordenadas de extração de petróleo ou gás
natural de uma jazida e de preparo para sua movimentação.
Doravante se tem um detalhamento do PSP estudado e das instâncias criadas para
reproduzi-lo. Para tanto, o capítulo assume a estrutura seguinte: na seção 4.1 o problema é modelado física e matematicamente; um breve histórico de conjuntos de
instâncias fictícias de testes para problemas correlatos e sobre seus software geradores é feito na seção 4.2; na seção 4.3, o código gerador empregado, denominado
ProGen, tem suas características funcionais descritas juntamente com os parâmetros de problemas inerentes; por fim, detalham-se na seção 4.4 as instâncias de testes produzidas sob medida para o caso em estudo e com o intuito de verificação de
desempenho das heurísticas implementadas, de que trata o capítulo próximo.
63
4.1
Modelagem do Problema
Com o propósito de posteriormente se reproduzir nas instâncias de teste, com suficiente fidelidade, sua real estrutura, o PSP considerado tem sua modelagem física e
matemática nos seguintes termos:
4.1.1 Modelo Físico
A caracterização se refere a projetos de exploração e desenvolvimento de campos
produtores da plataforma continental, tais como os da bacia de Campos, localizada
na costa nordeste do estado do Rio de Janeiro e maior província petrolífera do Brasil, responsável por três quartos de sua produção de hidrocarbonetos. Portanto, somente locações no mar (offshore) são levadas em conta.
As atividades típicas inerentes ao problema são:
•
Perfuração de poços;
•
Completação16 de poços;
•
Instalação de Arvore de Natal Molhada17 (ANM);
•
Lançamento de dutos;
•
Interligação de poços.
Exemplos dos principais recursos críticos (processadores) utilizados para a consecução das atividades são:
•
Plataformas de perfuração;
•
Navios de perfuração;
•
Barcos de lançamento de linha.
Levando em conta sua natureza não-consumível, todos os recursos são enquadrados na categoria dos renováveis (cf. seção 3.2.1). Plataformas e navios de perfuração são referidos indistintamente como sondas. As atividades são supostas com duração determinística discretizada em quantidades inteiras, definida a priori como
dado de entrada.
Um diagrama de rede genérico, do tipo AON, aplicável ao caso é delineado na figura
4.x. Em geral, as atividades guardam relação de precedência; por exemplo, a completação somente pode ocorrer uma vez perfurado o poço. Todavia, quando as atividades de intervenção citadas se dão em locações distintas, tornam-se independentes, ou seja, não envolvem relação de precedência. Por isso, a rede associada é do
16
Soma de algumas atividades intermediárias conduzidas entre a perfuração e a produção de um
poço.
17
Conjunto submerso de válvulas, acoplado à cabeça do poço produtor para manobras de movimentação de fluidos.
64
Figura 4.1: Modelo AON genérico do PSP em estudo.
tipo em série (ou em cadeia), não apresentando precedência “cruzada”. Uma
seqüência de atividades começando em j=0 e terminando em j=J+1 representa um
poço, que disputa recursos com os demais. Essa característica, como se comenta
adiante, faz crescer demasiadamente o espaço de busca do problema de otimização
associado.
Tome-se como exemplo uma instância monomodo18 de pequeno porte: supondo 7
poços, cada um com 4 tarefas, num total de J = 28 tarefas, o número de escalonamentos viáveis existentes equivaleria a (7(28-7).7!) = 2,815.1021. Seja tentar resolver tal
problema por enumeração explícita, i.é, varrer todo o espaço viável em busca da solução ótima, utilizando um computador capaz de avaliar um escalonamento em 10-9
s (um nano-segundo) – apenas por digressão, visto que uma máquina tão rápida certamente não estará disponível a médio prazo. Nessas circunstâncias, o processo
exigiria mais de 892 séculos para encontrar a solução. Um problema real de gerenciamento de projeto numa indústria de petróleo, num horizonte de tempo T equivalente
a um ano, pode facilmente englobar centenas de intervenções. Claramente, a solução exata de problemas combinatórios dessa complexidade é pouco sensível à evolução na tecnologia de hardware computacional.
18
J
Se tratado como multimodo, conforme a condição real, o total deve ser multiplicado por ∏ M j .
j= 1
65
4.1.2 Modelo Matemático
minimizar φ ( x) =
MJ+1
∑
LFTJ + 1
∑
tx J + 1,mt
(1)
m = 1 t = EFTJ + 1
sujeito a:
Mj
LFT j
∑ ∑
x jmt = 1
m = 1 t = EFT j
Mi
LFTi
∑ ∑
m = 1 t = EFTi
J
Mj
j= 1
m= 1
∑ ∑
t ximt ≤
k
ρ
jmr
Mj
∑ ∑
m = 1 t = EFT j
t + d jm − 1
x jmt ∈ {0,1}
∑
q= t
LFT j
(t − d jm ) x jmt
x jmq ≤ K rρ
j = 0, ...,J+1
(2)
j = 1, ...,J+1, i ∈ Pj
(3)
r ∈ R, t = 1, ... T
(4)
j = 0, ...,J+1, m=1, ..., Mj, t = EFTj, ...,LFTj (5)
Figura 4.2: Modelo Matemático MIP do MRCPSP em estudo.
As diferentes locações offshore, alvo das intervenções, apresentam profundidade
que tendem atingir algo em torno de 2000 m. As sondas são de atuação diferenciada, conforme sua capacidade de operação, em pequena, média e grande profundidade. As sondas de posicionamento dinâmico, projetadas para operar em poços
mais profundos, também podem ser empregadas nas menores lâminas d’água mas,
logicamente, o contrário não pode acontecer. Conseqüentemente, uma operação, a
depender da profundidade do poço, pode ser executada de até três modos diferentes, refletindo a variação da duração como função dos recursos destinados para
executá-la. É precisamente isso que define os diferentes modos de execução das
atividades e caracteriza o caso como MRCPSP
Sintetizando, semelhante problema de otimização inteira, de código MPS|prec|Cmax,
tem o seguinte enunciado: “Alocar os K recursos renováveis a cada uma das J
tarefas do projeto multimodo de maneira a minimizar sua duração total”. A
formulação matemática correspondente é representada na figura 4.2. O objetivo de
minimizar o makespan é expresso por (1); a restrição (2) obriga a atribuição de
modo e a execução de cada atividade; a obediência às restrições de precedência é
imposta pela restrição (3); em (4), a demanda por período de recursos é limitada à
sua disponibilidade. Sua nomenclatura é MPS|prec|Cmax, i.é, problema de escalonamento multimodo tendo o makespan mínimo como função objetivo.
66
4.2
Conjuntos e Geradores de Instâncias
Nos últimos anos, à medida que eficientes procedimentos computacionais de solução de problemas eram desenvolvidos, surgiu a necessidade de criação de instâncias de dados de problemas fictícias com que compará-los. Consequentemente, programas geradores de instâncias apareceram ultimamente de modo a automatizar e
acelerar o processo, grande parte dos quais não experimentou divulgação e liberação. A princípio mais simples, os geradores lançados mais recentemente incorporam
significantes parâmetros de problemas, úteis na sua estruturação. A coleção de instâncias que guardem determinados característicos em comum forma os conjuntos
que, uma vez reunidos, compõem os chamados bancos de conjuntos de dados.
Conjuntos de instâncias de teste
Davis, (1971), com suas 89 instâncias, foi o precursor na geração de problemas artificiais do PSP para testes e benchmark. Mas, até há pouco tempo, as tradicionais
instâncias de teste para o RCPSP compiladas por Patterson (1984) eram as mais
utilizadas nos trabalhos de escalonamento de projeto (e.g, Bell & Han, 1991; Kolish
& Drexl, 1996; Harding, 1997). Para o objetivo de mínimo makespan, Patterson também calculou as soluções ótimas utilizando os algoritmos disponíveis à época. Num
total de 110 instâncias, resultou da coleção de trabalhos anteriores – como o de Davis (1971), que, com suas 89 instâncias, detém o pioneirismo na geração de problemas artificiais do PSP para testes e benchmark. Essas 110 instâncias, referidas
como problemas de Patterson, prestam-se apenas para estudos de minimização do
makespan do RCPSP e sabe-se hoje, são de baixa dificuldade e já não podem ser
consideradas como benchmarck (Demeulemeester & Herroelen, 1992).
Além de ter possibilitado a disponibilidade dos valores ótimos para o makespan, outro benefício do advento dos problemas de Patterson foi a ampliação do uso do conjunto de teste para avaliação do métodos ótimos e sub-ótimos. Apresentam, contudo, também a desvantagem de as instâncias não terem sido geradas com base em
parâmetros de problemas bem definidos. Tal fato levou Alvares-Valdés & Tamarit
(1996) a produzirem um novo conjunto de teste, contendo 144 instâncias, utilizando
cinco diferentes parâmetros associados aos problemas.
Em resposta à necessidade de problemas completamente parametrizados, Kolisch
et al. (1995) produziram conjuntos de testes para o RCPSP mono e multimodo, o primeiro com 480 e o último com 640 instâncias. Posteriormente, Kolisch & Sprecher
67
(1996) expandiram esses conjuntos para um total de 10000 instâncias benchmark
para o PSP, atualmente os mais completos disponíveis e amplamente utilizados.
Boctor (1993) também apresenta um conjunto para testes, somente aplicável ao problema multimodo com recursos renováveis e já pouco utilizado.
Geradores de Instâncias de teste
O precursor foi o trabalho de Demeulemeester et. al. (1993), específico para redes
de representação AOA, com forte componente aleatório para um dado número de
arcos e nós. Agrawal et. al. (1996) também introduziu um gerador de instâncias para
redes do tipo AOA onde custos, durações e demanda de recursos associados às atividades são gerados aleatoriamente a partir de uma distribuição uniforme. No Brasil,
Cavalcante (1998) desenvolveu um gerador específico para o chamado problema de
escalonamento com restrição de mão-de-obra, SPLC, e disponibiliza suas 23 instâncias, que buscam reproduzir problemas reais. Em seu imersivo trabalho, com as instâncias geradas para o SPLC, somadas a mais duas antes já existentes, estuda limitantes e avalia métodos exatos e meta-heurísticas para o problema citado, também
se valendo de processamento em paralelo.
4.3
O Gerador de Instâncias ProGen
Kolisch et. al. (1995), da Universidade Christian-Albrechts de Kiel, Alemanha, com o
chamado ProGen, foram os primeiros a propor um software gerador de instâncias de
projeto do tipo general purpose, para uma classe geral de diferentes problemas em
uma representação de rede do tipo AON.
Graças a sua versatilidade e abrangência, tal programa cada dia vem ganhando preferência na utilização de problemas específicos. Pode ser reputado como o mais
abrangente e versátil gerador para problemas de escalonamento de projeto de que
se pode dispor na atualidade. Apresenta a vantagem de poder reproduzir instâncias
sob medida para uma ampla variedade de projetos, porque é plenamente adaptável
às inúmeras especificidade das suas variedades da prática.
O programa é capaz de gerar projetos sujeitos a parâmetros de problema bem definidos, o que permite discriminar instâncias fáceis daquelas mais difíceis. Diversas
funções-objetivo podem ser consideradas para PSP mono- ou multimodo, ao fazer
distinção entre as categorias dos recursos. O ProGen é citado como fonte de instâncias de problemas – com características outras que não aquelas originalmente pro68
duzidas por Kolisch et al. (op. cit.) – em numerosos artigos (cf. Kolisch & Padman,
1997). Para o caso alvo do presente trabalho, também foi empregado o ProGen.
4.3.1 Parâmetros de Problema
Nesta seção, os chamados parâmetros típicos de problemas, exigidos como dados
de entrada pelo gerador de instâncias ProGen, são brevemente apresentados. Três
conjuntos de teste, para reprodução de problemas de projeto que emulem as condições real situação do PSP em consideração, com 50, 100 e 200 atividades, foram
produzidos e utilizados neste trabalho para avaliação de performance relativa das
estratégias heurísticas de solução concebidas, descritas no próximo capítulo. Faz-se
a seguir apenas uma sinopse de definições dos parâmetros empregados para a criação das instâncias de teste pelo código gerador e, no que se refere à demanda de
recursos, apenas a categoria dos renováveis é levada em conta, por ser a única demandada no PSP de interesse. Uma descrição pormenorizada dos parâmetros dos
problemas de escalonamento pode ser encontrada em Kolisch et al. (1995), fonte
primária de consulta da presente seção. Os parâmetros considerados são:
J mín ( J máx ): mínimo (máximo) número de atividades reais (não-fictícias) do projeto;
máx
M mín
( M j ): mínimo (máximo) número de modos pelos quais uma atividade j pode
j
ser executada (j=1,...,J).
d mín ( d máx ): mínima (máxima) duração de qualquer atividade j (j=1,...,J).
R mín ( R máx ): mínimo (máximo) número de recursos renováveis considerados.
N mín ( N máx ): mínimo (máximo) número de recursos não-renováveis considerados.
S
mín
0
(S
máx
0
): mínimo (máximo) número de atividades de “partida” da rede.
máx
P J +mín
1 ( P J + 1 ): mínimo (máximo) número de atividades de “chegada” da rede.
S
máx
j
(P j
máx
): máximo número de sucessores (predecessores) de uma atividade j
(j=1,...,J).
NC - Complexidade de Rede (Network Complexity) : reflete as restrições na topologia da rede, i.é, número médio de arcos não-redundantes por vértice e inclui as ativi69
dades fictícias. Foi sugerida por Pascoe (1966) para redes tipo AOA e adaptada por
Davis (1975) para a representação AON. Expressa-se por:
NC =
1 J+ 1
∑ Pj .
J + 2 j= 1
Adicionando-se mais restrições de precedência a uma rede, faz-se diminuir o número de escalonamentos viáveis para um dado horizonte de tempo. Isso reduz a árvore
de enumeração e torna o problema de mais fácil solução. Com o passar dos anos,
estudos computacionais comprovaram que o problema torna-se mais fácil à medida
que o valor de NC aumenta, com o que o termo complexidade aqui soa inadequado
e causa espécie. Não obstante, vem sendo mantido por vários pesquisadores.
QRmín ( Q Rmáx ): mínimo (máximo) número de diferentes recursos da categoria R – renováveis – demandados pela combinação modo-atividade [j,m], (j=1,...,J).e m=1,...,Mj.
U rmín ( U rmáx ) : mínimo (máximo) nível de uso por período do recurso r ∈ R, por uma
combinação atividade-modo [j,m].
RF : Fator recurso (Resource Factor): real que mede a porção média exigida pela
combinação atividade-modo [j,m] dos diferentes recursos da categoria considerada e
equivale à densidade da matriz tridimensional dos kjmr. Foi introduzido por Pascoe
(1966) e para os recursos renováveis r ∈ R, se calcula por
RFR =
1 1
J R
J
∑
j= 1
1
Mj
Mj
∑ ∑
m= 1
r∈ R
 1 se k jmr > 0
 0 , noutro caso .

Dessa forma, RF é normalizado no intervalo [0,1]. Se RF = 1, então cada atividade requisita todos os diferente recursos; se RF = 0, então nenhuma atividade requisita
qualquer recurso, degenerando para o caso irrestrito CPM.
RS - Potência de recurso (Resource Strength): real que reflete a relação entre a demanda e a disponibilidade dos recursos, isto é, mede os efeitos da escassez de uma
dada categoria de recursos. Instituído por Cooper (1976), posteriormente foi normalizado para o intervalo [0,1] (Kolisch et al., 1995). Define-se como o parâmetro de escala na combinação convexa dos níveis mínimo e máximo de demanda do recurso r,
K rmín e K rmáx respectivamente, que computa sua quantidade disponível Kr:
70
Kr = K rmín + RS ( K rmáx - K rmín ).
Desse modo, se RS = 0 , a disponibilidade dos recursos está em seu nível viável mínimo; se RS = 1, a quantidade dos recursos torna-se grande o suficiente para o problema tornar-se irrestrito em recursos, como o caso do CPM.
Para o caso dos recursos renováveis, a demanda mínima se calcula como


ρ
{k jmr
} .
K rmín = max
 min
i= 1
m= 1
J
Mj


A utilização máxima K rmax é calculada como a demanda de pico para o caso do escalonamento viável no qual as atividades dependem de recursos para sua execução
e comecem em seu tempo mais cedo. Cada atividade é executada em seu modo de
menor índice – menor duração – que utilize demanda máxima por período do recurso considerado. A demanda máxima por período de recurso r por parte da atividade
j é expressa por
k
*
jr
Mj
{ }
ρ
,
= max k jmr
m= 1
sendo que o modo de menor duração com esta demanda é
Mj
{
}
ρ
m*jr = min m k jmr
= k *jr .
m= 1
K rmax é determinado pelo pico de utilização por período do recurso r , ou seja,
K
max
r

= max

t= 1

FTJr+ 1

k jm* r  ,
jr
j∈ A t

∑
onde At é o conjunto das atividades ativas no tempo t do escalonamento citado.
4.4
Instâncias Geradas para Teste das Heurísticas
Idealmente, os algoritmos deveriam ser aplicados a problemas reais das companhias de petróleo. Todavia, em face da inacessibilidade de dados dessa natureza, foram gerados problemas fictícios que melhor capturem as condições corporativas.
Com intuito de testar o desempenho relativo dos procedimentos meta-heurísticos
elaborados e implementados computacionalmente para solução sub-ótima do caso
em estudo, foram gerados três conjuntos de instâncias de teste. A faixa dos valores
dos parâmetros empregados para criação das instâncias estão nas tabelas 4.1 a 4.4
a seguir:
71
RF
RS 0,2
0,25
0,4
0,6
0,2
0,50
0,4
0,6
0,75
0,4
0,6
0,2
0,2
1,0
0,4
0,6
Tabela 4.1: Combinação dos parâmetros RF-RS.
Mj
1
dj
1
|R|
mín
J
50
máx
50
3
10
QR
1
S1
Sj
PJ
Pj
4
UR
1
10
1
1
10
6
10
6
10
1
1
10
Tabela 4.2: Parâmetros básicos do conjunto de instâncias com 50 tarefas.
J
Mj
dj
|R|
UR
QR
S1
Sj
PJ
Pj
mín
100
1
1
4
1
1
20
1
1
20
máx
100
3
15
6
14
6
20
1
1
20
Tabela 4.3: Parâmetros básicos do conjunto de instâncias com 100 tarefas.
J
Mj
dj
|R|
UR
QR
S1
Sj
PJ
Pj
mín
200
1
1
4
1
1
40
1
1
40
máx
200
3
15
6
14
6
40
1
1
40
Tabela 4.4: Parâmetros básicos do conjunto de instâncias com 200 tarefas.
Os três conjuntos de teste são: J50, contendo problemas de 50 tarefas; J100, com
100 tarefas e J200, com 200 atividades cada instância. A cada rodada, o gerador criava 30 instâncias com base nos parâmetros predefinidos no arquivo de entrada,
conforme se apresenta na figura 4.3. O RF e o RS se combinavam como é mostrado
na tabela 4.1, num total de 4x3 =12 arranjos, perfazendo 30x12=360 instâncias para
cada conjunto.
Ao final, foi produzido um total de 3x360 = 1080 instâncias para ensaio das heurísticas. Os arquivos correspondentes são codificados em J*[1...360]. Com isso, p. ex.,
a vigésima quinta instância do conjunto contendo MRCPSP’s de 200 tarefas recebeu
o código J20025. A ordem de criação obedeceu à combinação dos parâmetros RFRS conforme aparece na tabela 4.1, da esquerda para a direita. Dessa forma, as 30
72
primeiras instâncias de cada conjunto, e.g., J10015, têm como base RF=0,25 e
RS=0,2, e assim sucessivamente.
Configuração das instâncias
•
Todos os problemas têm complexidade de rede NC = 1, em razão de os problemas reais apresentarem como representação num diagrama de rede esta complexidade, i.é, as redes são do tipo em série (cf. fig. 4.1). Isso significa que, na
prática, não há precedência cruzada e cada atividade tem no máximo um predecessor e um sucessor, o que mantém coerência com a condição real.
•
RF (resource factor) foi modulado entre 0,25 e 1 (tabela 4.1). Assim foi feito porque, com RF menor que 0,25, a solicitação dos recursos se dá num nível baixo e
os problemas se tornam de mais fácil solução.
•
RS (resource strength) assume no máximo o valor 0,6 porque, além disso, a escassez de recursos diminui e os problemas tornam se menos difíceis e até triviais, como é o caso para RS = 1, para o qual podem ser considerados irrestritos.
•
Os três conjuntos de teste J50, J100 e J200 contêm instâncias de 50, 100 e 200
tarefas respectivamente. Trata-se, portanto, de problemas de médio para grande
porte, o que implica grande dificuldade. Problemas de pequeno porte não são tratados, portanto. Pretendeu-se com isso submeter as heurísticas a ambiente de
maior complexidade e, ao mesmo tempo, retratar a realidade.
•
Mj varia de 1 até 3 modos (tabelas 4.2, 4.3 e 4.4), de novo para espelhar as condições reais, nas quais algumas intervenções podem ser conduzidas de até 3
modos, como já explicado.
•
Em vista de limitações do código, a duração das tarefas dj vai de 1 a 15 dias, no
máximo, menor que nos casos reais. Com efeito, atividades como as citadas, típicas em locações offshore, podem durar até um mês. Contudo apresentam, aproximadamente, a mesma diferença entre a duração máxima e a mínima, quer dizer, ordem de grandeza de 14 dias. Com isso, tal discrepância não parece provocar efeitos importantes na complexidade dos problemas e, por via de conseqüência, no desempenho das meta-heurísticas experimentadas.
•
O número de recursos renováveis distintos, |R|, varia de 4 a 6, valores bem próximos dos caso reais, de vez que as sondas e os navios são de tipos diversos.
73
1
3
1
15
: 4
: 4
: 1
: 4
: 4
: 1
: 1.
LABILITY
: 4
: 6
: 0
: 14
: 4
: 6
: 1.
: .6
:
:
:
:
: 1
: 8
: 8
: 0
: 0.0
74
minimal
maximal
minimal
maximal
number of modes
number of modes
duration
duration
requested
requested
resources
resources
Figura 4.3: Exemplo de arquivo de entrada para o gerador ProGen para instância com 8 tarefas reais.
minimal number of renewable
maximal number of renewable
minimal (per period) demand
maximal (per period) demand
minimal number of resources
maximal number of resources
& resource factor
& resource strength
&
&
&
&
&
&
& minimal number of start activities per project
& maximal number of start activities per project
& maximal number of successor per activity
& minimal number of end activities per project
& maximal number of end activities per project
& maximal number of predecessors per activity
& complexity of network
&
&
&
&
& number of projects
& minimal number of jobs per project
& maximal number of jobs per project
& maximal release date
& maximal due date
SAMPLEFILE BASEDATA
PROJEKTS
NrOfPro
MinJob
MaxJob
MaxRelDate
DueDateFactor
MODES
MinMode
MaxMode
MinDur
MaxDur
NETWORK
MinOutSource
MaxOutSource
MaxOut
MinInSink
MaxInSink
MaxIn
Complexity
RESSOURCEREQUEST/AV
Rmin
Rmax
RminDemand
RmaxDemand
RRMin
RRMax
RRF
RRS
•
A demanda UR é bem maior que a real, o que confere um caráter mais genérico
aos problemas testados, como um todo. Assim sendo, não apenas se avalia a
performance comparada dos algoritmos em problemas específicos, mas também
em casos mais gerais.
•
Os número de recursos diferentes solicitados ao mesmo tempo, QR, foi bem maior que a realidade. Muito embora haja manobras conjuntas na prática, nunca
ocorre de, e.g., 4 recursos diferentes serem usados simultaneamente.(O número
de plataformas de exploração – também conhecidas como sondas de perfuração
marítima – varia de acordo com a carteira de projetos das companhias). Mais
uma vez, isso foi feito visando a propiciar maior grau de liberdade ao código gerador, com o que aumentar a diversidade das instâncias. Com isso, os resultados
das heurísticas se tornam mais abrangente.
•
Como se trata de rede com características seriais, cada tarefa real tem precisamente um predecessor e um sucessor. Por isso, Sj = Pj = 1 em todas as instâncias.
•
Por igual motivo, a quantidade de tarefas de “partida” S1 – sucessoras imediatas
da tarefa fictícia j=0 – e a de atividades de “chegada” PJ – predecessoras imediatas da tarefa fictícia de encerramento J+1 – sempre coincide. Também, buscouse impor, em média, 5 atividades por poço em cada instância, o que tem amparo
na vida real. Assim, e.g., para J100, S1 = PJ = 20, o que provoca uma média de 5
tarefas executadas em cada poço. Aliás, por vezes ocorre na prática de algumas
atividades serem desdobradas segundo exigências tecnológicas do equipamento
instalado.
Para concluir e apenas a título de ilustração, a figura 4.4 mostra os dados de saída
do gerador de instâncias com base no arquivo da figura 4.3, o qual é lido como os
dados de entrada pelos algoritmos desenvolvidos. Por brevidade, a instância exibida
tem apenas 8 tarefas reais.
75
file with basedata
: exemplo.bas
initial value random generator: 1427924141
*************************************************************
jobs (incl. supersource/sink ): 10
horizon
: 78
RESOURCES
- renewable
: 5
R
- nonrenewable
: 0
N
- doubly constrained
: 0
D
*************************************************************
PROJECT INFORMATION:
pronr. #jobs rel.date duedate tardcost MPM-Time
1
8
0
20
5
20
*************************************************************
PRECEDENCE RELATIONS:
jobnr.
#modes #successors
successors
0
1
4
1
2
3
4
1
1
1
5
2
3
1
8
3
1
1
6
4
1
1
7
5
3
1
9
6
2
1
9
7
2
1
9
8
2
1
9
9
1
0
*************************************************************
REQUESTS/DURATIONS:
jobnr. mode duration R 1 R 2 R 3 R 4 R 5
------------------------------------------------------------0
1
0
0
0
0
0
0
1
1
11
10
1
3
1
4
2
1
9
13
10
6
12
4
2
9
9
11
6
12
7
3
14
0
10
6
11
1
3
1
4
7
11
6
7
3
4
1
9
10
2
3
9
10
5
1
9
13
6
2
14
11
2
12
13
5
1
9
8
3
14
13
3
1
5
7
6
1
6
12
3
6
5
12
2
13
10
2
3
5
7
7
1
2
6
10
10
8
11
2
5
5
6
3
6
9
8
1
5
4
2
3
5
2
2
8
1
2
0
5
1
9
1
0
0
0
0
0
0
*************************************************************
RESOURCEAVAILABILITIES:
R 1 R 2 R 3 R 4 R 5
32
19
16
22
24
Figura 4.4: Exemplo de arquivo de saída do ProGen com instância de 8 tarefas reais.
76
Capítulo 5
Onde se descrevem os métodos propostos para abordagem do estudo de caso
Heurísticas Desenvolvidas para o MRCPSP em Estudo
D
e posse dos conjuntos de instâncias de teste detalhados no capítulo precedente, os quais guardam estreita relação paramétrica com o problema de es-
calonamento de projeto (PSP) em estudo, aqui são expostas em seus pormenores
as quatro heurísticas desenvolvidas e implementadas para sua solução:
•
Algoritmo Aleatório Puro – AP;
•
GRASP;
•
Algoritmo Genético – AG;
•
Heurística Evolucionária Híbrida – HH.
Seus fundamentos são enfocados, algumas técnicas e alguns conceitos são abordados e se segue uma explanação acerca de suas características funcionais. Antes,
entretanto, trata-se de esquemas de geração de escalonamento e regras de prioridades, imprescindíveis ao tema. O capítulo assume, com isso, a seguinte seqüência:
na seção 5.1, dois algoritmos clássicos para geração de escalonamento (SGS’s) são
descritos e explicados, um dos quais integra, como sub-rotina, todas as heurísticas
implementadas; a seção 5.2 trata de regras de prioridade, componentes indispensáveis para alocação de tarefas na maioria dos métodos subótimos; as seções 5.3,
5.4, 5.5 e 5.6 são dedicadas diretamente às quatro heurísticas desenvolvidas, respectivamente, AP, GRASP, AG e HH.
77
5.1.
Esquemas de Geração de Escalonamento
Tipicamente, os métodos aproximados voltados para solução do PSP apresentam
como procedimento básico um esquema de geração de escalonamento (SGS). O
SGS começa do zero e constrói uma solução à medida que acrescenta tarefas a um
escalonamento parcial, aquele contendo apenas um subconjunto das J+2 tarefas.
Há dois tipos usuais de SGS, os quais se distinguem por incremento de atividade ou
de tempo e ambos são atribuídos a Kelley (1963).
O assim chamado SGS em série (SSS) executa incremento de atividade a partir de
uma lista ordenada e alocando a atividade em seu tempo mais cedo, respeitando as
restrições. De outro modo, o SGS em paralelo (PSS) procede ao incremento temporal, considerando todo o horizonte de planejamento, no que cada estágio i está associado a um período ti. Em cada período ti, escalonam-se todas as atividades que
já podem ter seu processamento iniciado, aquelas que são viáveis em precedência e
recursos.
Quando aplicados a instâncias (viáveis) do RCPSP19, ambos os esquemas geram
escalonamentos viáveis, já que tomam em conta as restrições de precedência e recursos. Se a instância é irrestrita em recursos, tal como o problema expresso por (1),
(2) e (5) da tabela 3.2, os esquemas SSS e PSS resumem-se em uma simples recursão avante e derivam soluções exatas em tempo polinomial.
5.1.1
SGS em série
Discute-se apenas o caso do PSP de interesse, para o qual apenas recursos renováveis são considerados. O SGS em série (ou serial) consiste de i = 1,...,J estágios,
em cada qual um atividade é selecionada e escalonada – seu pseudocódigo é exibido na tabela 5.1. Associados a cada estágio, há dois conjuntos disjuntos: no conjunto escalonado, SCi, estão aquelas atividades que já foram alocadas e, portanto, já fazem parte do escalonamento parcial, e o conjunto de decisão, Di , do qual constam
as atividades ainda não escalonadas mas cujos predecessores já o foram. É, por
isso, o conjunto das atividades elegíveis e, em cada estágio, uma atividade de Di
deve ser selecionada com um critério estabelecido por alguma regra de prioridade
(empates podem ser decididos optando-se pela atividade de menor índice, por exemplo) e alocada em seu menor período viável, considerando precedência e disponibilidade de recursos – linha 2d no pseudocódigo. Isto feito, a atividade escolhida é
19
Recorde-se que, uma vez definidos os modos de execução, todo MRCPSP reduz-se a um RCPSP.
78
removida do conjunto de decisão, Di, e anexada ao conjunto escalonado, SCi. Esta
operação acaba por liberar mais atividades para o conjunto de decisão, de vez que
agora todas suas tarefas predecessoras estão escalonadas. Ao fim da iteração J, o
procedimento pára já que todas as tarefas reais já estão devidamente alocadas e o
makespan do projeto é assumido como o maior tempo de conclusão entre as tarefas
predecessoras imediatas da atividade fictícia J+1 – linha 3 no pseudocódigo.
Para uma descrição formal do SGS serial aplicável ao RCPSP, adicionalmente sejam:
K r (t):= Kr - ∑
j∈ A ( t )
k jr a capacidade remanescente de recurso tipo r no instante t;
Ai = A(ti) = { j ∈ J | FTj – dj ≤ t < FTj} o conjunto das tarefas ativas no instante t;
Algoritmo SerialSGS
// Início
1 FT0 = 0, SC0 = {0}
// Processo
2 Para i = 1 até J faça
a Calcule Di, FTi, K r (t) (r∈ R ; t ∈ FTi)
b Selecione j ∈ Di
c EFTj = max h ∈ P j {FTh} + dj
d FTj = min {t ∈ [EFTj - dj, LFTj - dj] ∩ FTi | kjr ≤ K r (Τ), r ∈ R, Τ ∈ [ t,t+dj [ ∩ FTi}+ dj
e SCi = SCi-1 ∪ {j}
fim-para
3
Compute FTJ+1 = max h ∈ P J + 1 {FTh}, SC=SCJ ∪ {J+1}, FT=FTJ ∪ {FTJ+1}
// Resultado
4 SC, FT, FTJ+1 (makespan)
Figura 5.1: Esquema de geração de escalonamento em série (SSS)
FTi = {FTj | j ∈ SCi}
o conjunto dos tempos finais das tarefas já escalonadas e;
Di = {j ∈ J \ SCi | Pj ⊆ SCi} o conjunto de decisão ou das atividades elegíveis.
Kolisch (1996) demonstra que um SGS serial sempre gera escalonamentos ativos
que, como já visto na seção 3.2, são aqueles onde nenhuma atividade pode ser iniciada mais cedo sem atrasar alguma das demais. Além disso, para PSP com uma me79
dida regular de desempenho, tal como minimização de makespan, a solução ótima
estará sempre no conjunto dos escalonamentos ativos. A complexidade no tempo do
algoritmo SGS serial como exposto é O (J2.K), onde J é o número total de tarefas reais e K =|R| é a quantidade total dos diferentes tipos (itens) de recursos renováveis
(cf. Pinson et al., 1994).
5.1.2
SGS paralelo
Da mesma forma que no esquema anterior, discute-se apenas o caso com recursos
renováveis. No SGS paralelo, para cada iteração i existe um instante de escalonamento ti – seu pseudocódigo é como se mostra na tabela 5.2. Atividades que tenham
sido escalonadas até i são, alternativamente, ou elementos do conjunto de conclusão Ci ou do conjuntos das tarefas ativas Ai. O conjunto de conclusão compreende
todas as atividades que tenham sido completadas até ti. Nesse caso, diferentemente
do serial, o conjunto das tarefas elegíveis Di é formado por todas as tarefas que são
viáveis em precedência e recursos, no instante ti. As expressões correspondentes a
Ci e Di são:
Ci = { j ∈ J | FTj ≤ ti } conjunto das tarefas completadas até ti e;
Di = { j ∈ J \ (Ci ∪ Ai) | Pj ⊆ Ci ∧ rjk ≤ K r (ti) (k ∈ R)} conjunto de decisão.
Algoritmo ParalSGS
// Início
i = 0, ti = 0, A0 = {0}, C0 = {0}, K r (0) = Kr, SC = {0}, FT ={0}
// Processo
1
2
Enquanto ( | Ai ∪
a
Ci | ≤ J ) faça:
b
i := i + 1
ti = min j ∈ A i -1 {FTj}
c
Calcule Ci, Ai,, K r (ti), Di
d
Enquanto ( Di ≠ & )faça:
e
Selecione um j ∈ Di
f
FTj = ti + dj
g
Calcule K r (ti), Ai, Dia, SC = SC ∪ {j}, FT = FT ∪ { FTj },
fim-enquanto
fim-enquanto
3
Compute FTJ+1 = max h ∈ P J + 1 {FTh},
// Resultado
4
80
SC, FT, FTJ+1 (makespan)
Figura 5.2: Esquema de geração de escalonamento em paralelo (PSS)
Cada iteração consiste de duas fases: na linha 2a se determinam o próximo instante
de escalonamento ti, os respectivos conjuntos de tarefas Ci, Ai,, e Di e a capacidade
disponível de recursos K r (ti); em 2d todas as tarefas de Di são escalonadas tendo
início em ti. Note-se que o esquema paralelo faz exatamente J decisões de seleção,
uma para cada tarefa real; contudo, uma execução completa pode envolver menos
de J estágios. Uma vez alocadas todas as tarefas, o makespan do projeto é tomado
como o maior período de conclusão dentre todas as tarefas predecessoras imediatas de J+1 – linha 3 do pseudocódigo.
Foi demonstrado por Kolisch (1996) que o SGS paralelo sempre gera escalonamentos do tipo sem-atraso (non-delay) que, como já explicado no capítulo 3, é aquele
onde, mesmo se a preempção é permitida, nenhuma das atividades pode ter seu início antecipado sem acarretar atraso para pelo menos uma das demais. O conjunto
dos escalonamentos sem-atraso é um subconjunto do conjunto dos escalonamentos
ativos e apresenta a desvantagem de, quando se considera uma medida regular de
desempenho, nem sempre conter a solução ótima. A propósito, Kolisch et al. (1998)
testaram 298 instâncias de 30 tarefas e, entre estas, somente 175 (59,73%) tinham
escalonamento ótimo no conjunto dos escalonamento sem-atraso ao minimizar o
makespan. A complexidade no tempo do SGS paralelo também é O (J2.K) (cf. Pinson et al., 1994).
Em virtude de o SGS serial explorar o espaço dos escalonamentos ativos, no qual a
solução ótima obrigatoriamente se encontra, todos os algoritmos implementados
para solução do PSP em estudo o tem incorporado como sub-rotina. Mais precisamente, uma variante do SGS serial, que recebe uma sucessão de atividades e as vai
alocando conforme a ordem de comparecimento. Dessa forma a decisão de escolha
– linha 2b no pseudocódigo do esquema serial da figura 5.1 – é predefinida.
5.2
Regras de Prioridades
Existem diversos trabalhos versando sobre regras de prioridades entre os quais podem ser citados Cooper (1976), Alvarez-Valdés & Tamarit (1996), Kolisch (1996) e
Kolisch & Hartmann (1998). Investigação na literatura dão conta de mais de 100 tipos diferentes de regras de prioridade (Kolisch & Hempel, 1996).
81
Regras de prioridades são empregadas pelas heurísticas que se utilizam de ambos
ou de apenas um dos esquemas de geração de escalonamentos no processo de
programação das tarefas, como é o caso das aqui apresentadas adiante. A regra de
prioridade em si é útil como critério de seleção de uma tarefa no conjunto de decisão
Di .
Formalmente, uma regra de prioridade é um mapeamento que atribui a cada atividade j no conjunto Di um valor numérico v(j) e um parâmetro dicotômico extr ∈
{max,min}, definindo se a decisão deve recair sobre a atividade com máximo ou mínimo valor. Um critério de desempate deve ser preestabelecido. O critério trivial é escolher a tarefa de menor índice, mas pode-se proceder arbitrariamente, por via de
uma seleção ao acaso.
As regras de prioridade podem ser classificadas segundo diferentes critérios. Com
respeito ao tipo de informação empregada para calcular v(j), podem-se distinguir as
regras baseadas no tempo, na rede ou no recurso bem como regras de limitantes inferiores e superiores. Estas últimas calculam um valor do limitante (inferior ou superior) da função-objetivo para cada atividade. No que se refere à quantidade de informação adotada, as regras podem ser locais ou globais. Regras locais utilizam informação apenas da tarefa sob consideração, tal como o tempo de processamento, enquanto que as globais se valem de uma gama maior de informação geral. Se o valor
de v(j) permanece constante ao longo do processamento, a regra se classifica como
estática e torna-se dinâmica no caso contrário. Se o critério for o SGS subjacente ao
Notação
Extremo
Série vs.
Est. vs.
Din.
E
E
E
E
D
S
D
LFT
LST
SLK
MTS
min
min
min
max
Paralelo
S,P
S,P
S,P
S,P
RSM
SPT
WCS
min
min
min
P
S,P
P
v(j)
LFTj
LFTj - dj
LFTj - EFTj
|S j |
max(l,j)∈AP{0,ti+dj – (LFTl-dl) E(l,j)}
dj
LFTj - dj - max(l,j)∈AP{E(l,j)}
Tabela 5.1: Regras de prioridade
procedimento, uma regra pode ser indicada apenas para um ou para ambos os ti82
pos, i.e., em série e em paralelo (cf. Schirmer, 1997). A tabela 5.1, extraída de Kolisch & Hartmann (1998), apresenta sete regras de prioridades (com base no tempo e
na rede) mais utilizadas, em vista de desempenho superior, comprovado por alguns
estudos (cf. Schirmer, 1997): LFT tempo mais tarde de conclusão (latest finish time);
LST tempo mais tarde de início (latest start time); SLK folga (slack); MTS total de sucessores (most total sucessors); RSM método do escalonamento de recurso (resource scheduling method); SPT tempo de processamento (shortest processing time);
WCS folga do pior caso (worse case slack). A regra MTS emprega S j , o conjunto de
todos os sucessores, diretos e indiretos, isto é, não necessariamente imediatos, de j.
O conjunto de todos os S j compõe o fecho transitivo do grafo de precedência. As
regras RSM e WCS usam o conjunto AP = {(l,j) ∈ Di x Di | l ≠ j} dos pares de todas as
atividades (l,j) que estão no conjunto de decisão Di. Por fim, a regra WCS emprega
E(l,j), que representa o tempo de início mais cedo, viável em precedência e recurso,
da atividade j se a atividade l é escalonada para ter início no tempo ti.
5.3
Algoritmos do tipo Aleatório Puro
É o mais simples procedimento de amostragem. Consiste em selecionar uma tarefa
entre as candidatas do conjunto de decisão Di utilizando um processo puramente
aleatório. Logicamente, dispensa o cálculo de valores de prioridade para as tarefas
candidatas, que agora são escolhidas ao acaso.
A utilização de métodos aleatórios como geradores de soluções benckmark para estudos comparativos de performance de outros algoritmos é prática comum nas pesquisas de otimização matemática do PSP (Hartmann & Kolisch, 1999). Em geral,
qualquer outro método mais bem elaborado deve superá-los nos resultados. Desafortunadamente, para o caso em tela, a literatura não registra pesquisa pregressa
com a qual se possa comparar o desempenho dos algoritmos ora apresentados,
como aludido no capítulo 4. Nenhum conjunto de teste exclusivo existe disponível
voltado para o PSP com redes seriais e NC (complexidade de rede) unitária, objeto
do corrente estudo, o que torna imperativo elaboração de soluções de referência
com que cotejar os resultados.
83
5.3.1
Algoritmo Aleatório Proposto
A cada iteração, o procedimento concebido e implementado produz uma sucessão
de atividades, viável em precedência, via seleção aleatória das tarefas do conjunto
de decisão Di. Constrói, em seguida, uma lista com os modos de execução atribuído
a cada uma das J tarefas. Ato contínuo, chama a sub-rotina SerialSGS para alocálas levando-se em conta seus modos de execução, no ordenamento listado e em
seu tempo mais cedo, viável em recursos, como apresentado na tabela 5.1. Produz
um escalonamento a cada iteração e registra a melhor entre as soluções computadas. O critério de parada pode ser de dois tipos: impor limite ao número de iterações
ou ao tempo de CPU. Sua estrutura é como se apresenta a seguir.
Para uma dada instância, faça:
Repetir
Construção aleatória de uma sucessão de tarefas;
Montagem aleatória da lista de modos de execução;
SerialSGS.
Até satisfazer condição de parada
Retornar a melhor solução
5.4
GRASP
Método iterativo que busca soluções aproximadas para problemas de otimização
combinatória, a GRASP (Greedy Randomized Adaptive Search Procedure) foi concebida por Feo & Resende (1989). Trata-se de um procedimento de amostragem
aleatória onde cada iteração consiste de duas fases: construção e busca local. Seu
leiaute básico é como vai a seguir:
Para uma dada instância, faça:
Repetir
Construção de uma solução gulosa aleatória;
Busca de um mínimo local nas vizinhanças;
Atualização da solução;
Até satisfazer condição de parada
Retornar a melhor solução
Uma solução viável é gerada iterativamente, elemento a elemento, na fase de construção. Todos os elementos viáveis são antes ordenados segundo uma função gulosa – míope – preestabelecida. A partir daí, uma lista de candidatos é extraída, relaxando o critério guloso – regra de prioridade – e permitindo que elementos que
atendam em alguma medida ao critério componham tal lista restrita (restrict candidate list - RCL) e então possam ser selecionados.
84
Em cada estágio, um elemento da lista de candidatos é eleito para integrar a solução
incompleta e então é excluído da RCL. A escolha se dá aleatoriamente entre os candidatos da lista, quer dizer, não necessariamente o melhor é selecionado, o que confere ao método um caráter probabilístico e permite que a cada iteração uma solução
distinta possa ser retornada.
A RCL é então remontada a cada iteração da fase de construção. Assim, os benefícios relacionados com cada elemento da lista são atualizados de modo a repercutir
as mudanças introduzidas pela seleção do elemento anterior e, em razão disso, o
procedimento se diz adaptativo.
Ao cabo da fase de construção, não obrigatoriamente um ótimo local será encontrado, o que torna oportuna a inclusão de um processo de melhoria para explorar suas
vizinhanças e perseguir uma solução localmente ótima. Introduz-se então um algoritmo de busca local, que funciona de modo iterativo ao sucessivamente substituir a
solução viável corrente por outra das vizinhanças, gerada a partir de perturbação induzida na primeira. Mas apenas retorna esta última se for de menor makespan.
Empiricamente, sabe-se que a eficiência do algoritmo de busca local será função da
qualidade da solução fornecida pela fase de construção. Assim, boas soluções de
partida podem acelerar o processo de busca e preveni-lo contra desempenho exponencial (cf. Feo & Resende, 1994).
5.4.1
Algoritmo GRASP Proposto
A literatura que cobre o método (Resende, 1998) não registra uma GRASP aplicada
a qualquer categoria de PSP, incluindo o caso em questão. Sob este ponto de vista,
portanto, a abordagem é inédita. Nessa seção são detalhados os passos das duas
etapas integrantes do algoritmo GRASP sugerido para solução do PSP em estudo,
isto é, as fases de construção e melhoria.
Fase de construção
Inicialmente, deve-se definir a função gulosa. Adota-se a regra de prioridade min
LFT, visto que estudos precedentes (Kolisch & Hartmann, 1998) autorizam supor
melhor desempenho para o PSP em métodos com base em amostragem aleatória. A
RCL é construída a partir do conjunto de decisão Di , formado por todas as atividade
que, a cada iteração i, já tiveram suas predecessoras na rede devidamente alocadas, ou seja, são viáveis em precedência. Em vez de se fazer meramente a escolha
85
Algoritmo ConstSchedGRASP
//
1
//
2
3
Início
Entrada: J, κ, T ,Pj, LFTj, Mj, ,j=1,...,J+1
Processo
SC0 ={0}, M0 ={1}
Para i = 1,...,J faça:
a
Di = {j ∈ J \ SCi | Pj ⊆ SCi}
b
Limiinf = min { LFTj | j ∈ Di }
c
Limisup = Limiinf + κ( T - Limiinf )
d
sup
RCLi = {j ∈ Di | LFTj ≤ Limi }
e
Selecionar aleatoriamente ji ∈ RCLi
f
SCi+1 = SCi ∪ {ji}
g
Selecione aleatoriamente mi ∈ {1,.., M ji }
h
Mi+1 = Mi ∪ {mi}
fim-para
4 SC = SCJ+1 ∪ {J+1}, M = MJ+1 ∪ {1}
// Resultado
5 SC, M
Figura 5.3: Pseudocódigo da fase de construção da GRASP
gulosa em Di, ou seja, optar pela tarefa de menor LFT do conjunto de decisão, o procedimento constrói a lista restrita e permite que um candidato a integre se seu corsup
respondente LFT for menor ou igual a um limitante superior ( Limi ). Este último se
calcula pela soma do menor LFT entre as tarefas em Di, dito limite inferior ( Limiinf ), e
um dado percentual, estipulado pelo chamado parâmetro de relaxação κ, 0 ≤ κ ≤ 1,
de sua diferença até o horizonte de tempo do projeto T . Em outras palavras, o limisup
inf
tante superior Limi resulta da combinação convexa entre o limitante inferior Limi e
o horizonte de tempo do projeto T . Assim, definindo-se os limitantes inferior e superior a cada iteração i da fase de construção,
Limiinf = min { LFTj | j ∈ Di } e Limisup = Limiinf + κ( T - Limiinf ), tem-se
sup
RCLi = {j ∈ Di | LFTj ≤ Limi }.
Este tipo de limitante da lista de candidatos, imposto por κ, é costumeiramente referido como restrição de valor. Note-se que se κ = 0, a escolha será totalmente gulosa;
por outro lado, se κ = 1, a escolha dar-se-á de modo totalmente aleatório. Como é
86
bem de ver, o parâmetro κ deve ser modulado criteriosamente, de modo a produzir
os melhores resultados para uma dada classe de problemas de otimização. É o que
se faz na subseção 6.2.1. Opcionalmente, poder-se-ia obrigar a RCL a ter um número máximo de componentes, com o que se estabelece a assim denominada restrição
de cardinalidade.
Uma vez definida a RCL em cada iteração i (linha 3d), procede-se a uma escolha
aleatória na qual qualquer tarefa desta lista tem a mesma probabilidade de ser escolhida – linha 3e. Fazendo-se i:=1,...,J , o procedimento, concluída esta etapa, acaba
por montar uma lista contendo uma sucessão SC das J+2 tarefas. Esta última, juntamente com a lista M dos modos de execução associados a cada atividade e elaborada aleatoriamente (linhas 3g e 3h), são enviadas ao SGS serial para que cada tarefa seja alocada em seu tempo mais cedo
Fase de busca local
Conforme já salientado, a fase de construção não obrigatoriamente produz um escalonamento localmente mínimo. Útil se faz assim perseguir uma solução nas vizinhanças que seja de melhor qualidade. O procedimento de melhoria (busca local) é centrado em permutação de pares de tarefas (local shift), tentando produzir escalonamento de menor makespan. O pseudocódigo correspondente é mostrado na tabela
5.4
Algoritmo MelhorSchedGRASP
// Início
1 Entrada: SC, M,Pj, Mj, djm, ,j=1,...,J, m=1,...,Mj
// Processo
2 Para i = 1,...,J-1 faça:
3 k = ji
Se( ji ∉ P ji + 1 ) ∧ ( ∃ mh ∈ { 1,..., M ji + 1 }: d ji + 1 ,mh < d ji + 1 ,mi + 1 ) Então
4
a
Atualizar SC e M : ji = ji+1 ∧ mi+1 = mi
b
Atualizar SC e M : ji+1 = k ∧ mi = mh
fim-se
fim-para
5 Escalonar e computar FTJ+1 com SerialSGS
// Resultado
6 SC, FT, M, FTJ+1 (makespan)
87 melhoria da GRASP
Figura 5.4: Pseudocódigo da fase de
A partir da posição 1 até a posição J-1 da lista corrente, duas tarefas consecutivas
são permutadas em sua ordem e o modo da segunda é redefinido se esta atender
simultaneamente às duas condições seguintes:
•
não for sucessora imediata da primeira atividade no grafo de precedência e;
•
puder ter sua duração diminuída via substituição de seu modo de execução.
A primeira condição previne quanto à violação da restrição de precedência enquanto
a última, uma vez atendida, envolve uma operação de mudança de modo em que a
tarefa é processada, que então é de fato consumada, tentando melhorar a solução
ao diminuir o makespan do projeto.
A permuta opera sempre nas listas já atualizadas, a partir daquelas recebidas da
fase de construção. Após efetuadas as J-1 iterações, a sub-rotina SerialSGS é chamada para alocação de cada tarefa da lista corrente no instante mais cedo, viável
em recursos, observando a ordem em que comparece na nova sucessão S* e o
modo no qual deve ser executada, segundo o M* corrente, e computa o makespan.
do projeto FTJ+1. Dessa forma, um mínimo local é, esperançosamente, encontrado.
Finda esta etapa de melhoria, a GRASP reinicia uma nova etapa de construção, e
assim sucessivamente, até atender o critério de parada.
Conforme a conveniência do ensaio, dois são os critérios possíveis de parada incorporados ao algoritmo GRASP: limite do número de iterações ou do tempo de uso da
CPU. O algoritmo termina por montar um escalonamento do projeto ao menos subótimo, bem definido em seqüenciamento das tarefas e respectivos instantes de conclusão (cf. seção 3.2.8).
Outras modalidades de combinação de duração com ordenamento das tarefas foram
tentadas como forma de busca local e testes comparativos preliminares, que não
são explicitados aqui, sinalizaram desempenho superior do mecanismo adotado e
ora descrito.
5.5
Algoritmos Evolucionários
Denominação mais geral para as abordagens genéticas, algoritmos evolucionários
(ou evolutivos) são meta-heurísticas baseadas no principio da evolução natural. Sua
aplicabilidade universal e destacada performance quando aplicados a uma vasta
gama de problemas de otimização fizeram emergir um notável interesse neste tipo
de estratégia nos últimos anos (Kohlmorgen et al. (1998) e Houdayer, 1999). Têm
88
experimentado largo emprego como meta-estratégia nos domínios, e.g., da otimização continua e discreta, machine learning e teoria dos jogos. Uma boa introdução no
tema, com alentada bibliografia, é propiciada por Goldberg (1989).
5.5.1 Genética, Evolução e Otimização
Hereditariedade é a transferência, dos indivíduos para os seus descendentes, das
informações – representadas pelos genes – responsáveis por suas características. A
genética20 é o estudo da hereditariedade. Genótipo é como comumente se denomina
a constituição genética de um indivíduo, enquanto fenótipo é qualquer característica
metabólica ou morfológica. Diz-se que um caráter é adquirido, quando a causa é essencialmente ambiental e hereditário, se a causa é essencialmente genética. A evolução natural diz respeito à freqüência de genes numa população.
Os princípios da teoria da evolução das espécies21. se descrevem resumidamente do
seguinte modo: um indivíduo ou, mais precisamente, seu fenótipo consiste de características básicas contidas em seu gene, o genótipo, acrescidas de outras mais, adquiridas. Os indivíduos de uma espécie são similares, salvo pelos seus fenótipos e
genótipos. Novos indivíduos surgem por cruzamento de seus “pais”. O genótipo de
um indivíduo é determinado por uma recombinação dos genes dos “pais” e por mutação, isto é, alterações raras e fortuitas de alguns genes.
A seleção natural conduz a um crescente nível de adaptação das espécies ao ambiente, num processo que se perpetua ao longo das gerações, tendendo a preservar
as variações favoráveis e fazer desaparecer as desfavoráveis. Na luta pela sobrevivência, os indivíduos de uma espécie competem por comida e parceiros de acasalamento. Os indivíduos mais bem adaptados de uma população têm maiores chances
de subsistência e assim podem transferir seus genes para os descendentes, enquanto aqueles cujas características são menos apropriadas para enfrentar as condições ambientais tendem a perecer antes que possam se reproduzir. O processo de
adaptação de uma população ao seu ambiente é chamado aprendizado filogenético
em contraste com a adaptação individual, referida como aprendizado ontogenético.
Todo este mecanismo evolutivo inspirou Holland (1995) nas bases para idealização
dos algoritmos genéticos (AG), cuja utilização na otimização matemática tem alcan20
O abade tcheco Gregor Mendel (1822-1884) foi o precursor do estudo da hereditariedade utilizando
o método científico.
21
O naturalista inglês Charles R. Darwin (1809-1882), com seu livro “On the Origin of the Species by
Means of Natural Selection”, legou ao mundo as bases para a moderna teoria da evolução.
89
çado resultados altamente expressivos. Sua terminologia é copiada diretamente da
biologia.
Grosso modo, um AG é baseado em uma codificação específica do problema e os
operadores mutação, cruzamento e seleção22. Antes de tudo uma população inicial é
determinada e o nível de adaptação de cada indivíduo é calculado, refletindo seus
atributos com respeito a um objetivo preestabelecido. Continuando, os novos indivíduos são gerados pelo emprego dos operadores mutação e cruzamento. Finalmente, uma nova população remanesce por uma estratégia de seleção que favorece a
permanência dos indivíduos mais bem adaptados e exclui os demais. Às vezes,
emulando a natureza, este processo se repete em diferentes “ilhas” para várias populações com processos evolutivos independentes.
O operador cruzamento recombina partes de dois indivíduos para formar seus descendentes. Isto sugere uma combinação de genes e as partes constitutivas são supostas responsáveis pela adaptação dos indivíduos “pais” e são referidas como blocos de construção. Do operador mutação pode originar combinação de genes que
antes não ocorreu na população. Em outras palavras, o genótipo resultante de uma
mutação pode não ter sido produzido por cruzamento.
O algoritmo genético clássico tem a seguinte estrutura básica:
Para uma dada instância, faça:
Gerar População Inicial
Avaliar Adaptação dos Indivíduos
Repetir
Cruzamento dos “pais” e geração dos descendentes;
Mutação dos descendentes;
Avaliação de adaptação dos descendentes;
Seleção dos “pais” e formação de nova população.
Até satisfazer condição de parada
Retornar a melhor solução
Até onde se depreende da literatura, são três os algoritmos genéticos propostos até
agora para o MRCPSP: Özdamar (1996), Hartmann (1997a) e Mori & Tseng (1997).
Os dois últimos representam as fontes de cujas idéias o presente trabalho representa uma adaptação. Contudo, para o caso do MRCPSP em estudo, contando exclusi-
22
Há outros operadores usuais, de acordo com cada pesquisador (Hartmann, 1999). Esses três, todavia, são os mais freqüentemente empregados.
90
vamente com recursos renováveis e circunscrito a redes seriais, não há paralelo na
literatura.
5.5.2
Algoritmo Genético Proposto
O seqüenciamento básico de evolução simulado pela abordagem adotada é agora
descrito. Adaptado dos trabalhos de Hartmann (1997a) e Mori & Tseng (1997), o AG
proposto se volta para a solução sub-ótima do MRCPSP alvo da pesquisa corrente.
É, portanto, concebido sob medida para o caso de redes seriais contando unicamente com recursos da categoria renováveis, tal como nas instâncias de teste.
Na estratégia empregada, espaço de busca (o conjunto de genótipos) compreende
as seqüências viáveis com respeito à precedência e todas as combinações de modo
de execução. Um fenótipo (escalonamento) associado a um genótipo é gerado, a exemplo dos demais algoritmos implementados, pelo emprego do esquema de geração em série, que produz escalonamentos ativos. O pseudocódigo do AG implementado é como se mostra na figura 5.5.
A codificação genética, em vez de usar bit, é do tipo direta e baseada em lista (permutação) de atividades. O algoritmo começa por produzir uma população inicial
POP1 de modo puramente aleatório – empregando o algoritmo AP –, equivalente à
primeira geração, que contém um número inteiro par de indivíduos, NIND, e então
avalia seus níveis de adaptação (fitness), o que equivale a calcular o valor das funções-objetivo de cada solução viável, i.é, ao makespan. – linha 3 do pseudocódigo
da fig. 5.x. A população é então aleatoriamente particionada em pares de indivíduos
que formam os NIND/2 casais de “pais” sobre os quais se aplica o operador cruzamento com o que se produzem os novos indivíduos (“filhos”). Isto feito, numa probabilidade pmut , os genótipos dos recém criados indivíduos sofrem a mutação. Após
computar o nível de adaptação de cada um dos novos indivíduos gerados, toda a
prole é incorporada à população, agora de dimensão 2.NIND. O passo que se segue
é aplicar o operador seleção à população corrente de modo a reduzi-la a seu tamanho original NIND – linhas 4a até 4i. Sempre que a sub-rotina SerialSGS é acionada ao longo do processamento, registra-se o escalonamento de menor makespan.
Todo esse processo é ser repetido para um numero preestabelecido de gerações
denotado NGEN – linha 4. Alternativamente, o critério de parada pode ser estabelecido por limite de tempo de CPU ou de indivíduos e respectivos escalonamentos
91
computados. Ao final do processamento – linha 5 –, obtém-se um escalonamento
bem definido em tarefas, tempos e modos (FTJ+1 representa o valor do makespan).
92
Indivíduos e Adaptação
A codificação adotada é do tipo direta com um indivíduo IND representado por um
par composto por uma permutação de atividades e uma designação de modos que
se denota por
I
IND =(SCi, Mi) ≡ (( j1I ,..., j J ), mI).
A seqüência de tarefas SCi = j1I ,..., j JI é suposta ser uma permutação viável com relação às restrições de precedência. A designação de modo Mi é um mapeamento
que atribui a cada atividade j ∈ {1,...,J} um modo mI(j) ∈ {1,...,Mj}.
Cada genótipo relaciona-se com um escalonamento (fenótipo), determinado de
modo único. A princípio, a atividade fictícia 0 de início do projeto é começada no instante zero e, em seguida, as demais atividades são escalonadas em seu tempo mais
I
cedo viável na ordem prescrita pela seqüência j1I ,..., j J , sendo a cada atividade atriI
I
buído seu devido modo. A atividade ji é escalonada no modo mI( ji ), definido alea-
toriamente. Utiliza-se a sub-rotina SerialSGS para a decodificação do genótipo,
com o que o resultado é um escalonamento viável com respeito às restrições de precedência e recursos e, além disso, ativo (cf. seção 3.X). A medida de adaptação de
cada indivíduo equivale ao makespan do escalonamento correspondente e é útil
quando da aplicação do operador seleção. Nesta etapa preliminar assim, é montada
a população inicial (i.é, geração original) de NIND indivíduos, com seqüências e modos definidos aleatoriamente, cujos níveis de adaptação são devidamente computados.
Cruzamento
Os pares selecionados para cruzamento são constituídos dos indivíduos “mãe” M e
“pai” F, que se reproduzem para formar os indivíduos “filha” D e “filho” S. Considerese primeiro a definição da “filha”. Sejam p1 e p2 dois inteiros extraídos ao acaso com
1 ≤ p1,p2 ≤ J. Na seqüência de tarefas de D, as posições i=1,...,p1 são tomadas da
“mãe”, com o que
jiD := jiM .
A seqüência de tarefas das posições i= p1+1,...,J de D é constituída pelas tarefas
restantes e obedecendo o ordenamento com que comparecem em F. Assim sendo,
93
Algoritmo SchedALGEN
// Início
1. Entrada:NIND , NGEN
// Processo
2. POP1 ={ }, MOD1={ }, POP2={ }, MOD2={ }, RNDSET = {1,...,POP}, NITER = 1
3. Para i = 1,..., NIND faça:
a. Gerar SCi, Mi com o algoritmo AP
i
b. SerialSGS(SCi, Mi)computa FTJ + 1 e registra melhor escalonamento
c. POP1 = POP1 ∪ {SCi} , MOD1 = MOD1 ∪ {Mi}
fim-para
4. Enquanto (NITER ≤ NGEN) faça:
a. POP2 = POP1 , MOD2 = MOD1
b. Para i = NIND +1 ,..., 2* NIND, 2 faça:
c.
Random (k , l ∈ RNDSET) ; RNDSET = RNDSET\{k,l}
d.
Cruzamento(SCk, SCl) para gerar SCi , SCi+1 , Mi, Mi+1
e.
SerialSG(SCi, Mi),(SCi+1, Mi+1)
Se (probabilidade) Então:
f.
g.
Mutação(SCi, Mi),(SCi+1, Mi+1)
h.
SerialSGS(SCi, Mi),(SCi+1, Mi+1)
fim-se
i.
POP2 = POP2 ∪ { SCi , SCi+1 }, MOD2 = MOD2 ∪ { Mi , Mi+1 }
fim-para
j. Para i = 1,...2* NIND faça: Seleção( FTJi+ 1 )
k. POP1 = { NIND indivíduos i de menor makespan }
l. MOD1 = { NIND listas dos modos indivíduos de POP1 }
m. NITER = NITER + 1
fim-enquanto
// Resultado
5. SC , FT, M, FTJ+1
Figura 5.5: Pseudocódigo do algoritmo genético proposto.
as tarefas que já tenham sido tomadas da “mãe” M não são consideradas novamente no “pai” F. Desse modo,
jiD := j kF , onde k é o menor índice no qual j kF ∉ { j1D ,..., jiD− 1 }.
Este tipo de operador cruzamento diz-se de ponto unitário.
As atividades nas posições i=1,...,p2 da “filha” D recebem os mesmos modos com
que comparecem na “mãe” M
94
D
D
mD( ji ) := mM ( ji ),
ao passo que os modos das suas tarefas remanescentes, nas posições i=p2+1,...,J,
são atribuídos conforme a designação mF dos modos do “pai”, ou seja,
D
D
mD ( ji ) := mF ( ji ).
O “filho” S dos indivíduos M e F tem uma estrutura de geração analogamente definida. A diferença é que as posições i=1,...,p1 de sua lista é copiada do “pai” F e as demais posições são tomadas da “mãe” M. Similarmente, os modos das tarefas de S,
até p2, são extraídos de F e daí em diante vêm de M.
A par de assegurar que cada atividade seja considerada uma única vez, este mecanismo também garante que as posições relativas nas seqüências de tarefas dos
“pais” sejam preservadas, com o que se produz uma lista de atividades que respeita
as restrições de precedência. Isto pode ser demonstrado pelo seguinte teorema
(Hartmann, 1997a):
Teorema 1 Se aplicado a “pais” cujos seqüenciamentos obedecem às restrições de
precedência, o operador cruzamento de ponto unitário para a codificação genética baseada em permutação produz descendentes de genótipos viáveis em precedência.
Prova
Assuma-se que a seqüência correspondente à “filha” seja inviável em precedência,
D
D
D
quer dizer, existem duas atividades ji e j k com 1 ≤ i < k ≤ J e j k ∈ P
jiD
, conjunto
D
dos predecessores imediatos de ji . Com isto, três casos podem ser examinados:
Caso 1: Ter-se-ia i,k ≤ p1. . Todavia, as posições relativas são mantidas pelo
D
D
operador cruzamento, com o que a atividade ji situa-se antes da atividade j k na
seqüência de tarefas da “mãe” M, o que contraria o pressuposto de viabilidade de M.
D
D
Caso 2: Ter-se-ia i,k > p1. Então a atividade ji situa-se antes da atividade j k
na seqüência de tarefas do “pai” F, contrariando a suposição de viabilidade de F.
D
D
Caso 3: Ter-se-ia i ≤ p1 e k > p1. Com isso, a tarefa ji antecede j k na seqüên-
cia da “mãe” M, igualmente contrariando o pressuposto de viabilidade de M.
♦
Mutação
A exemplo do que ocorre no ambiente natural, a mutação é fato esporádico que introduz alterações genéticas sempre muito discretas ao longo do processo evolutivo.
95
É útil porque torna possível criar seqüências de tarefas (combinações de genes) que
podem não ter sido obtidas pelo operador cruzamento e lograr introduzir modos (genes) que não ocorreram na população corrente. Duas variantes de mutação são testadas.
O operador mutação idealizado guarda forte semelhança com a fase de melhoria da
GRASP já descrita. Aplica-se com probabilidade pmut e induz modificação no genótipo
de cada novo indivíduo. Um inteiro 1 ≤ q < J-1 é extraído aleatoriamente. Todos os
pares de tarefas ji e ji+1, q ≤ i < J são passíveis de mutação, contanto que atendam
simultaneamente a duas condições:
•
Se a tarefa ji+1 não for sucessora imediata de ji e;
•
Se houver um modo de menor duração para a tarefa ji+i.
No caso afirmativo, as tarefas são permutadas e a ji+i. é atribuído o primeiro modo
entre {1,..., M jiI+ 1 } cuja duração seja menor que a imposta pelo modo atual.
Também se tenta (cf. subseção 6.x) uma modalidade de operador mutação aplicada
com probabilidade pmut a cada novo indivíduo. Sugerida por Hartmann (1997a), funciona do modo seguinte: dois números inteiros q1 e q2 são extraídos aleatoriamente,
I
I
com 1 ≤ q1 < J e 1 ≤ q2 ≤ J. As tarefas j q1 e j q1 + 1 são permutadas se isso não violar a
restrição de precedência, mas sem acarretar nenhuma alteração nos modos de processamento das tarefas, que são mantidos. Adicionalmente, atribui-se um novo
I
modo de execução para a atividade da posição q2 , a saber, redefine-se mI( j q2 ), ex-
traindo-se aleatoriamente um número inteiro do intervalo {1,..., M jqI 2 }.
Seleção
A seleção se dá por um simples mecanismo que permite a sobrevivência apenas
dos indivíduos mais bem adaptados. Constrói-se um ranking baseado no valor do
makespan dos 2*NIND indivíduos. O tamanho original da população é restabelecido
ao se manter os NIND indivíduos de melhor nível de adaptação, sendo os demais removidos da população, isto é, morrem. Empates são decididos arbitrariamente. Este
critério mostrou ser o de melhores resultados entre outros possíveis (Hartmann
1997a).
96
5.5.2
Heurística Híbrida Proposta
Graças a seu desempenho marcadamente superior, algoritmos híbridos de busca
são largamente empregados na otimização combinatória (Goldberg, 1989). Caracterizam-se por harmonizar, parcial ou totalmente, duas ou mais técnicas típicas de métodos já consagrados. A idéia básica que norteia heurísticas dessa natureza é tornálas ecléticas, no sentido de tentar agregar as melhores particularidades de seus procedimentos constituintes com o que ensejar soluções igualmente melhores.
De outro lado, é sabido que num método evolucionário a população inicial desempenha um papel mais importante do que meramente fornecer indivíduos para ação dos
operadores genéticos. Com efeito, sua qualidade inicial pode repercutir ao longo de
todo o processo algorítmico. Em outras palavras, o bom desempenho do método
pode depender da “higidez” dos indivíduos pioneiros como um todo. Este raciocínio
motivou a configuração da heurística evolucionária híbrida (HH) que doravante se
descreve.
Opta-se então por tentar conjugar as “virtudes” da GRASP com as do algoritmo genético, isto é, a heurística denomina-se evolucionária híbrida porque incorpora abordagens que distinguem uma GRASP e outras, tipicamente vinculadas a algoritmos
genéticos: a população original é toda gerada pela GRASP detalhada na seção 5.x
e, a partir daí, a heurística assume o comportamento do algoritmo genético tal como
apresentado na seção anterior. Isso significa que o pseudocódigo da HH coincide
exatamente com o do AG da figura 5.5, exceto pela linha 3a: o algoritmo aleatório
puro AP é substituído pela GRASP na formação dos indivíduos (SCi, e respectivos
modos Mi) da população inicial POP1. Como seus detalhes funcionais correspondentes são idênticos nos algoritmos constituintes mencionados e já apresentados, a HH
não é aqui objeto de descrição mais minuciosa.
97
Capítulo 6
Onde se relatam os testes computacionais comparativos das heurísticas propostas
Experimentos Numéricos
A
gora que se tem devidamente modelado o PSP da indústria de petróleo em
estudo, as heurísticas desenvolvidas para resolvê-lo já descritas e montados
os conjuntos de instâncias representativas do problema, são apresentados os resultados dos testes computacionais comparativos efetuados.
Como o interesse é estabelecer menores prazos de encerramento para os projetos,
via alocação dos recursos às tarefas, a função-objetivo se refere sempre ao critério
de performance minimização do makespan. Portanto, o desempenho relativo de uma
heurística é suposto tanto melhor quanto menor o makespan do correspondente escalonamento produzido.
Os algoritmos foram codificados em Object Pascal e compilados com a IDE Delphi III
em ambiente Windows 98. Os experimentos numéricos foram conduzidos num microcomputador Pentium II com clock-pulse de 266 MHz e 64 Mb de RAM.
O capítulo tem o seguinte leiaute: a seção 6.1 descreve o ajuste das meta-heurísticas, visando a estabelecer seu melhor funcionamento; os testes computacionais propriamente ditos são expostos e interpretados na seção 6.2, onde também se discute
a influência dos parâmetros de problemas RF e RS e a eficiência das heurísticas. Por
fim, alguns comentários adicionais são colocados na seção 6.3.
6.2
Configuração das Meta-heurísticas
Testes preliminares são conduzidos objetivando calibrar os valores dos parâmetros
κ, para a GRASP, e POP e Pmut, para as heurísticas evolucionárias. Para estas últimas, também se define a melhor entre duas modalidades possíveis do operador mutação. O conjunto de instâncias de 50 tarefas, J50, foi empregado nos experimentos
com 30s de CPU.
98
6.1.1 Ajuste dos parâmetros
Objetivando a utilização dos métodos GRASP, AG e HH no seu ponto ótimo de funcionamento, ensaiam-se as várias possibilidade dos parâmetros funcionais de modo
a encontrar seus níveis de desempenho maximizado.
GRASP
Como já aludido no capítulo 4, para a GRASP, o parâmetro de relaxação κ, para dadas características de problema, deve sofrer ajuste fino antes de seu emprego efetivo. Tal parâmetro, pertencente ao intervalo real [0,1], estipula o percentual que baliza a lista restrita de candidatos, RCL. Quando κ = 0, a GRASP torna-se completamente míope, ou seja, a escolha da tarefa do conjunto das elegíveis recai sobre
aquela que melhor atende a regra de prioridade e, se não fosse pela fase de busca
GRASP J50 - 30 s
κ
0,0
0,2
0,35
0,5
0,65
0,8
1,0
Média de Makespan
79,50
79,24
78,95
78,77
78,71*
78,76
80,66
Tabela 6.1: Calibração do parâmetro κ.
local, computaria sempre uma mesma solução, não importando o número de iterações; de outro lado, se κ = 1, o método, também na fase de construção, adquire caráter puramente aleatório. O conjunto de teste J50 foi empregado como dado de entrada em testes com critério de parada de 30s de CPU. A tabela 6.1 mostra o resultado de rodadas sucessivas da GRASP com os valores de κ e respectivos valores
médios da função objetivo, i.é, média de makespan dos 360 projetos de J50.
A GRASP calcula a média mínima de makespan de 78,71 dias para κ = 0,65. Portanto, assume-se que este valor é o que deve ser ajustado para testar todos os conjuntos de problemas. Note-se que para κ nulo, o valor 79,50 é pouco satisfatório ao
passo que, para κ igual à unidade, a média de 80,66 dias é a pior para efeito de minimização de makespan dos projetos.
99
Algoritmo Genético (AG)
Em procedimentos meta-heurísticos, o operador mutação pode gerar genótipos que
não ocorreram antes, o que costuma ser útil como forma de melhor explorar o espaço de busca. A mutação é fato raro, que se dá com algum nível de probabilidade,
Pmut, o qual deve ser predefinido. Igualmente, o tamanho da população inicial, POP,
também deve ser conhecido a priori, como dado de entrada. Os efeitos de POP e
Pmut interagem ao longo de todo o processamento, de modo que ambos devem ser
analisados conjuntamente. O procedimento estará em sua melhor forma como função do par (POP, Pmut). A modulação do AG deve, assim, observar essa interdependência. A tabela 6.2 exibe os valores da função-objetivo para as diversas combina-
AG J50 - 30 s
Pop. Inicial
10
Pmut
Makespan médio
0,0
86,67
0,2
80,74
0,4
80,60
0,6
79,99
0,8
80,25
1,0
81,02
20
0,2
79,17
0,4
79,06*
0,6
79,53
0,8
79,67
30
0,2
79,81
0,4
79,75
0,6
80,01
0,8
80,23
40
0,2
81,01
0,4
80,75
0,6
80,94
0,8
80,93
50
0,2
81,70
0,4
81,55
0,6
81,75
0,8
81,57
60
0,2
82,36
0,4
82,19
0,6
82,19
0,8
82,12
Tabela 6.2: Probabilidade de Mutação – Pmut.
100
ções (POP, Pmut). Novamente o conjunto de instâncias J50 foi usado, com 30s de
CPU em cada execução.
A menor média de makespan foi alcançada com os valores 20 para POP e 0,4 para
Pmut. Conjectura-se que valham também para problemas assemelhados, com o que
são adotados doravante para todos os testes das heurísticas evolucionárias (AG e
HH).
Pela análise da tabela 6.2, percebe-se, para uma POP de 10 indivíduos, os correspondentes valores médios de 86,67 e 81,02 para o makespan quando se usam 0,0 e
1,0 para Pmut, respectivamente. São resultados sofríveis – de fato, os piores – quando
comparados com os demais naquela população. Isto dá bem a medida dos efeitos, a
exemplo da evolução natural, da mutação: no primeiro caso, ela nunca acontece; no
segundo, o genótipo sempre está sujeito à mutação. Mas, como já se disse anteriormente, a mutação genética é fato raro na evolução biológica. Digno de nota é que, à
medida que a população inicial POP cresce, a partir de 20 indivíduos, o procedimento computa médias de makespan cada vez maiores.
6.1.2 Definição do Operador Mutação
Na subseção 5.5.2 são descritas duas configurações para o operador mutação: um
primeiro, proposto pelo presente estudo e um segundo, sugerido por Hartmann
(1997a). Agora, ambos os operadores mutação têm cotejados seus resultados para
um mesmo ambiente de PSP. É o que pode ser visto na tabela 6.3 que se segue.
Para POP=20, Pmut = 0,4 e 30s de processamento, a menor média de makespan das
360 instâncias analisadas é obtida com o operador proposto. Como o que se preten-
AG J50 - 30s – POP = 20, Pmut = 0,4
Algoritmo
Proposto
Hartmann 1997
Média de Makespan
79,06
80,80
Tabela 6.3: Teste comparativo entre operadores mutação.
de é minimizar o makespan, este último é adotado como o operador mutação dos
procedimentos evolucionários deste trabalho (AG e HH). Presume-se, com isso, que
tal configuração é também a mais conveniente para uso em instâncias de maior porte de problema análogos, como é o corrente caso.
101
6.2
Experimentos Numéricos Comparativos
Os três conjuntos de instâncias, J50, J100 e J200, são submetidos separadamente
aos algoritmos, agora já devidamente calibrados. Numerosos testes comparativos
são efetuados e seus resultados são interpretados para efeito de definição de desempenho relativo dos algoritmos.
6.2.1 Testes com o conjunto J50
Dos três conjuntos de teste, J50 é o que reúne os problemas de escalonamento relativamente mais fáceis. São na verdade instâncias de médio porte, representando
projetos de 50 tarefas cada uma delas. Todas as 360 instâncias se submetem a
cada uma das heurísticas em 30s de CPU para cada execução.
A tabela 6.4 a seguir mostra os resultados, com os algoritmos e a média de makespan correspondente computada. A HH apresenta o melhor desempenho para makespan, vis-à-vis as demais heurísticas, para 77,07 dias de makespan médio. Por ordem de qualidade de resultados, a seqüência das demais é dada por GRASP, AG,
AP. Recorde-se que o que se persegue é a minimização do makespan de cada um
dos projetos. É de se notar que o AG e a GRASP têm performance bem próximas.
J50 - 30 s
Algoritmo
HH
GRASP
AG
AP
Makespan médio
77,07
78,71
79,06
89,46
Tabela 6.4: Teste comparativo entre as
heurísticas com o conjunto J50.
Numa análise simplificada, i.é, considerando que o prazo de encerramento dos projetos seja função apenas da programação das tarefas, os projetos na prática apresentariam, em média, mais de 12 dias de atraso se obedecessem a um escalonamento ditado pelo AP em vez de pela HH.
6.2.2 Testes com o conjunto J100
Os problemas de escalonamento de dificuldade relativa intermediária estão agrupados no conjunto J100. Mas de fato as instâncias de J100 representam problemas de
grande porte, contando 100 atividades cada um.
102
Como critério de parada para todos os algoritmo, o processamento de cada instância
demandou 120s de CPU. Na tabela 6.5 a seguir, podem ser lidos os resultados.
J100 - 120 s
Algoritmo
HH
GRASP
AG
AP
Makespan médio
80,26
81,79
82,37
97,65
Tabela 6.5: Teste comparativo entre as
heurísticas com o conjunto J100.
Novamente a HH supera as demais em perfomance, com 80,26 de média de makespan. Na seqüência, GRASP, AG, AP. Note-se a grande discrepância entre o valor
médio de 97,65 dias computado pelo AP quando confrontado com as outras.
6.2.3 Testes com o conjunto J200
Essas são as instâncias de solução mais laboriosa. Com efeito, os PSP’s do conjunto J200 exige programação de 200 tarefas e atribuição de seus respectivos modos
de execução. Duas seqüências de testes são conduzidas, as quais se diferenciam
pelo critério de parada. Na primeira seqüência, as quatro heurística têm 300s de
CPU para cálculo do makespan de cada instância, enquanto na segunda seqüência
o critério de parada é o atingimento de 480s em cada rodada. As tabelas 6.6 e 6.7 a
seguir mostram os resultados.
J200 - 300 s
Algoritmo
HH
GRASP
AG
AP
Makespan médio
87,14
87,88
91,11
115,46
Tabela 6.6: Teste comparativo entre as
heurísticas com o conjunto J200 em 300s.
A ordem de superioridade das heurísticas de novo se repete. Novamente, para ambas as baterias de testes, a melhor perfomance é apresentada pela HH com 87,14
103
de makespan em 300s e 86,72 dias em 480s de CPU. O ranking se completa – sem
surpresas, nos dois casos – com GRASP, AG, AP.
Note-se que o acréscimo de 180s de CPU de um experimento para outro fez melhorar muito pouco os resultados. Concedeu-se um tempo 60% maior e o makespan
médio para todas as heurísticas diminuiu apenas 0,8%, em média. Isso vem em decorrência do grande esforço computacional exigido para construção e verificação de
J200 – 480 s
Algoritmo
HH
GRASP
AG
AP
Makespan Médio
86,72
87,76
90,09
113,80
Tabela 6.7: Teste comparativo entre as
heurísticas com o conjunto J200 em 480s.
um escalonamento, como adiante se demonstra. Com isso se pode aquilatar a enorme dificuldade inerente aos problemas combinatórios dessa dimensão.
6.2.4 Eficiência dos Algoritmos
Entre as medidas costumeiras de desempenho de algoritmos, uma das mais representativas é a eficiência. Como forma de medir a eficiência dos algoritmos implementados, opta-se aqui por aferir quantitativa e qualitativamente as soluções heurísticas emanadas como função do tempo de processamento. Isto está de acordo com
o que recomendam Jackson et. al. 1991 (Guidelines for reporting results of computational experiments. Report of the ad hoc committee):a eficiência de um algoritmo
mede, simultaneamente, o esforço computacional requerido para se obter uma solução (e.g., tempo de CPU, número de avaliações e número de iterações) e a sua quaJ200 – 480 s
Algoritmo
AP
AG
GRASP
HH
Desvio
0,234367
0,159491
0,139266
0,135287
Tabela 6.8: Desvio médio das heurísticas
em relação ao limitante inferior CPM.
lidade (e.g., acurácia).
104
As tabelas 6.8 e 6.9 são empregadas para análise da qualidade e quantidade das
soluções, respectivamente. Na tabela 6.8 se apresentam os desvios médios das soluções em relação ao respectivo limitante inferior estabelecido pelo caso trivial, i.é,
sem restrição de recursos, tal como no CPM, enquanto na tabela 6.9 pode ser lido o
número médio de escalonamentos avaliados em cada rodada de um procedimento
em 480s de CPU para o conjunto J200.
Com respeito à eficiência relativa ao AP, destaque para o AG: a população inicial é
J200 – 480 s
Algoritmo
AG
HH
AP
GRASP
# escalonamentos
653,58
432,52
417,91
200,61
Tabela 6.9: Número médio de escalonamentos avaliados pelas heurísticas em 480 s.
toda gerada pelo AP, e o AG é capaz de produzir aproximadamente 50% a mais de
escalonamentos e consegue resultados bem melhores. Eis aí um traço que corrobora as vantagens, no que tange a simplicidade e eficácia, da auto-aprendizagem dos
métodos evolucionários.
A GRASP tem desempenho pior no que concerne à quantidade de soluções. Isso
decorre do grande esforço computacional despendido na montagem da RCL e verificação do escalonamento, na fase de construção, e iterações da fase de busca local.
Não obstante, demonstra aproveitar muito bem este dispêndio, ao direcionar sua
busca para espaços de melhores soluções, em menor quantidade de escalonamentos, p. ex., do que o AG.
O algoritmo AP tem resultados intermediários na quantidade de escalonamentos que
verifica. Contudo, a qualidade da solução é sofrível (cf. tabela 6.8). De qualquer
modo, certamente a resposta é bem melhor do que simplesmente uma sucessão
viável.
A HH parece ser a que melhor consegue conciliar quantitativa e qualitativamente as
soluções encontradas. Sob este ponto de vista, pode ser eleita a de maior eficiência
vis-à-vis as demais heurísticas.
105
Cumpre notar o enorme esforço computacional exigido para atingir uma única solução: em média, consome-se mais de 1s (cf. tabela 6.9). Eis aí uma medida da dimensão incomensurável do PSP em questão.
6.2.5 Efeitos dos Parâmetros de Problema RF e RS
Também, visando a uma maior abrangência e melhor compreensão dos testes realizados, investigam-se os efeitos dos parâmetros de problemas RF e RS nas respostas
das heurísticas (cf. subseção 4.3.1). O fator recurso, RF, dá a medida da porção média dos recursos demandada por tarefa do problema; a potência dos recursos, RS,
reflete sua escassez.
Na figura 6.1 a seguir tem-se o gráfico cartesiano no qual os valores de makespan
são plotados contra as instâncias correspondentes. Pelo exame da figura, percebese grande uniformidade no comportamento dos algoritmos quando tomados em conjunto. Da esquerda para a direita, o RF cresce de 0,25 até 1,0. Nota-se que o desempenho das heurísticas é pouco sensível ao valor do RF , já que o perfil se reproduz em 4 ciclos, com discreta elevação na média do makespan.
Contrariamente, o RS influencia fortemente os resultados. A cada ciclo de 90 instâncias, o RS varia em três níveis: 0,2, 0,4 e 0,6. Há três patamares bem definidos em
cada um dos ciclos, cada qual correspondendo a um grupo de 30 problemas, de
igual RS. O valor do makespan calculado decresce com o incremento da disponibilidade de recursos e cresce com a escassez. Os maiores makespan são aqueles correspondentes aos problemas de RS=0,2, ao passo que, em sendo pouco restrito o
problema, o makespan diminui bastante, como quando RS=0,6.
Não apenas em média, mas sistematicamente, a heurística híbrida apresenta performance que supera as demais. Ratificando isso, a figura 6.2 exibe o que poderia ser
tomado como zum da região do gráfico da figura 6.1 compreendida entre as instâncias J20001 e J20030, o que permite melhor visualização. Percebe-se nitidamente o
desempenho superior da HH e isso se repete para todas as instâncias e em todos os
conjuntos de teste, embora não inteiramente demonstrado aqui.
106
DESEMPENHO DAS HEURÍSTICAS
J200 - 480s
AP
175
AG
GRASP
HH
165
155
145
Makespan
135
125
115
105
95
85
75
65
55
Figura 6.1: Instância vs. makespan comparando todas as heurísticas
107
361
351
341
331
321
311
301
291
281
271
261
251
241
231
221
211
Instância
201
191
181
171
161
151
141
131
121
111
101
91
81
71
61
51
41
31
21
11
1
45
DESEMPENHO DAS HEURÍSTICAS
J200 - 480s
170
160
Makespan
150
140
130
120
110
AP
AG
GRASP
HH
100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Instâncias
Figura 6.2: Resultados com todas as heurísticas do makespan para as 30 primeiras instâncias
108
24
25
26
27
28
29
30
6.3
Considerações Finais
Para os três conjuntos de problemas, J50, J100 e J200, a HH é a de melhor desempenho no cômputo dos escalonamentos de menor makespan. Por conseqüência, a
estratégia de somar as melhores características de dois métodos distintos foi, sem
dúvida, plenamente exitosa. O que difere a HH do AG é exclusivamente o grau de
adaptação dos POP indivíduos que ambas recebem como população inicial. A população inicial da HH, sendo gerada pela GRASP, incorpora indivíduos que representam soluções de melhor qualidade. Esse fato confirma a grande influencia da população inicial na resposta dos métodos evolucionários. Para as outras heurísticas,
pela ordem de qualidade dos resultados, o ranking geral, computados todos os problemas, é GRASP, AG e AP.
É relevante aqui reiterar a substancial diferença entre um seqüenciamento meramente viável e outro, de makespan minimizado, na prática do gerenciamento de projeto. Para sublinhar o raciocínio, seja, como exemplo, a tabela 6.7. A diferença média, entre os encerramentos dos 360 projetos cuja programação foi produzida pelo
procedimento AP e aquelas proporcionadas pela HH é por volta de 27 dias, ou um
atraso médio de 31% nos prazos – ressalte-se que o AP, de fato, faz mais que simplesmente produzir um escalonamento viável, ao optar pela melhor dentre as soluções visitadas). Se imediatamente transposto para a receita adicional que proporcionaria no caso das companhia de petróleo em termos de antecipação de produção,
isso pode significar cifras milionárias. Claro está que há fatores envolvidos que não
estão sendo aqui devidamente ponderados como, entre outros, o caráter estocástico
das durações e intercorrências nas operações. De qualquer sorte, todavia, um escalonamento otimizado sempre vai potencialmente favorecer o acerto na tomada de
decisão na gestão dos tempos de um projeto.
Capítulo 7
Onde o projeto de pesquisa conhece sua fase de encerramento
Conclusões, Recomendações e Futuras Pesquisas
N
este trabalho pretendeu-se de alguma forma contribuir com um estudo de
caso de interesse regional, ao tratar um problema de alocação de recursos críticos às atividades em poços da bacia de Campos. O caso recebe tratamento de
problema de escalonamento de projeto da classe MRCPSP, cuja nomenclatura é
MPS|prec|Cmax e para o qual procedimentos aproximados são propostos. Antes disso, apresenta os fundamentos do gerenciamento de projeto, no qual o caso é situado.
As contribuições deste trabalho podem ser assim sumariadas:
• Estudo de caso de interesse regional;
•
Geração de três conjuntos de instâncias de teste, de médio e grande portes,
disponíveis também para futuras pesquisas na área;
•
Proposição de uma GRASP e uma heurística evolucionária híbrida inéditas
para o MRCPSP;
•
Implementação de códigos computacionais de um total de quatro heurísticas de solução aproximada para o caso em estudo;
•
Definição da heurística mais eficiente entre as quatro estudadas por meio
de experimentos numéricos exaustivos.
7.1
Conclusões
Com respeito à qualidade e robustez das heurísticas propostas, os resultados
empíricos sugerem que a heurística híbrida domina todas as demais, todo o tempo e
em todos os conjuntos de teste. A HH é a que melhor consegue conciliar quantitativa
e qualitativamente as soluções visitadas. Sob este prisma, pode ser eleita a de maior
eficiência, vis-à-vis os demais algoritmos. Isso evidencia as vantagens, no que tange
a simplicidade e eficácia, da auto-aprendizagem dos métodos evolucionários e robustece a idéia de que futuras pesquisas nessa direção são prometedoras.
110
Em que pese sua performance ter sido a pior no que respeita a quantidade de soluções, a GRASP prova ótimo rendimento, ao direcionar sua busca para espaços de
melhores soluções, em menor quantidade de escalonamentos. É seu grande esforço
computacional despendido na montagem da RCL e verificação do escalonamento,
na fase de construção, e iterações da fase de busca local que resulta em menor número de escalonamentos produzidos.
O algoritmo AP tem resultados intermediários na quantidade de escalonamentos que
verifica. Contudo, a qualidade da solução é sofrível De qualquer modo, certamente
a resposta é bem melhor do que simplesmente uma seqüenciamento viável. O algoritmo genético, por sua vez, consegue melhorar extraordinariamente as soluções
quando comparado com o algoritmo AP.
Um teste completo das quatro heurísticas apenas com o conjunto J200 exige 192 h
(oito dias) de CPU. Eis aí uma medida da complexidade e magnitude do MRCPSP
estudado.
Como visto, para os três conjuntos de problemas, J50, J100 e J200, a HH é a de
melhor desempenho no cômputo dos escalonamentos de menor makespan. Por
conseqüência, a estratégia de conjugar as melhores características de dois métodos
distintos foi bem-sucedida. Comprova-se, adicionalmente, a forte influencia da população inicial na resposta dos métodos evolucionários, de vez que a HH difere do AG
apenas pela sua população inicial. Para as heurísticas, pela ordem de qualidade dos
resultados, o ranking geral, computados todos os problemas, é HH, GRASP, AG e
AP.
Também, objetivando melhor compreensão dos testes realizados, investigam-se os
efeitos dos parâmetros de problemas RF e RS nas respostas das heurísticas . O fator
recurso, RF, dá a medida da porção média dos recursos utilizados por atividade do
projeto, ao passo que a potência dos recursos, RS, espelha sua escassez. Verificase que o desempenho das heurísticas é pouco sensível ao valor do RF, enquanto o
contrário se dá com RS, que influencia grandemente os resultados. Um problema torna-se mais difícil à medida que o RS cresce, quer dizer, à medida que mais recursos
ficam indisponíveis.
A partir dos experimentos levados a cabo, pode-se aquilatar a expressiva diferença
entre um seqüenciamento meramente viável e outro, de makespan minimizado, na
prática do gerenciamento de projeto. Desconsiderando fatores outros, o atraso pode
implicar substanciais perdas de receita. No caso de companhia de petróleo, em termos de antecipação de produção, isso pode importar grandes somas. Ademais, um
111
escalonamento otimizado tende a favorecer o acerto na tomada de decisão no que
concerne à gestão dos tempos de um projeto.
7.2
Recomendações
Crescentemente, o Brasil será palco de lançamento de grandes obras, requeridas
para o seu desenvolvimento econômico, represado há anos. Antevê-se mais e mais
exigência de competência e diligência na condução dos projetos. Como uma sociedade sintonizada com seu tempo, no qual cada vez mais se consomem insumos
cognitivos, a necessidade da formalização e disseminação do aprendizado do gerenciamento de projeto desponta no pais. A despeito disso, o ambiente universitário
brasileiro carece do gerenciamento de projeto como disciplina dos cursos regulares
e, inevitavelmente, os projetos acabam por se ressentir disso. O cenário recomenda
que os currículos de cursos tais como os de graduação em Administração e Engenharia de Produção contemplem o gerenciamento de projeto como disciplina.
Por outro lado, embora tenham se tornado imprescindíveis ao moderno gerenciamento de projeto, aplicativos comerciais deixam a desejar. Em que pese a sua boa
evolução nos últimos anos em termos gerais, e também com relação à capacidade
de geração de escalonamentos de melhor qualidade, nesse particular tais software
são bem limitados quando aplicados a problemas que não de pequeno porte. Melhor
dizendo, sua capacidade de geração de escalonamento de boa qualidade ainda está
longe dos resultados obtidos por métodos mais recentes. Além disso, os programas
disponíveis não conseguem capturar todas as singularidades do PSP subjacente a
todo projeto. Como exemplo, a possibilidade de modos alternativos de execução, indispensável para se lidar com o MPS|prec|Cmax, não está prevista nesses programas.
Sugere-se que corporações, onde grandes e complexos projetos sejam uma constante, desenvolvam códigos computacionais complementares – add in – que funcionem combinados com os software comerciais, compartilhando dados, de modo a torná-los customizados e melhor possa atender às necessidades de cada empresa, em
cada projeto, no que tange ao escalonamento.
7.3
Futuras Pesquisas
De modo a viabilizar um trabalho experimental deste tipo, como é natural, algumas
hipóteses simplificadoras foram consideradas, o que delimita sua abrangência. Obje112
tivando ampliar suas conclusões de modo que possam valer para casos ainda mais
realistas, algumas linhas de pesquisas futuras poderiam ser:
•
A duração das atividades antes de ser determinística, é de fato uma variável aleatória (cf. Brucker et. al., 1998a). Mais estudos devem ser levados a efeito para a
modelagem do problema como um PSP estocástico.
•
O modelo seria mais completo se os seus recursos fossem enquadrados na categoria dos parcialmente renováveis (Drexl et al., 1998). Há casos, como os da árvore de natal molhada, ANM, cuja disponibilidade varia no tempo, seja pelo uso,
seja pelo prazo de entrega do fabricante, e são melhor capturados por esta categoria de recursos.
•
O critério de performance dos PSP’s analisados sempre é a minimização do lapso decorrido a partir do início até a conclusão do projeto (makespan). Todavia,
outros critérios podem ser levados em conta como, p. ex., vazão esperada dos
poços e custos globais do projeto. Um problema deste tipo diz-se multicritério (cf.
Slowiński et al., 1994; Deckro & Hebert, 1990; e Cortes, 1998) e deve ser estudado no futuro, com o que melhor subsidiar a tomada de decisão.
•
Adicionalmente, o processamento computacional em paralelo pode ser tentado,
de vez que se trata de problemas que reclamam enorme carga computacional.
Com isso se estaria tirando partido da notável adequação das meta-heurísticas a
este ambiente (Mavridou et al., 1995).
113
Simbologia & Definições
p = 1, ..., P
: projetos
πj (εj)
: release date (due date) da tarefa j
πp (εp)
: release date (due date) do projeto p
cjmt
: fluxo de caixa induzido pela tarefa j no modo m e término em t
cp
: custo incorrido por período se o projeto p se concluir após seu prazo
devido (due date)
FJp(LJp)
: numero da primeira (última) tarefa do projeto p
J
: conjunto das tarefas j, |J|=J+2
J
: número de tarefas reais (i é, não-fictícias)
j = 0 (J+1)
: única fonte (sumidouro) da rede
Pj(Sj)
: conjunto dos predecessores (sucessores) imediatos da tarefa j
At
: conjunto das tarefas ativas (em execução) no tempo t
ESTj (LSTj)
: tempo mais cedo (mais tarde) de início da tarefa j
EFTj (LFTj)
: tempo mais cedo (mais tarde) de conclusão da tarefa j
STj
: tempo de início da tarefa j
FTj
: tempo de conclusão da tarefa j
SC
vetor escalonamento com permutação viável das tarefas j ∈ J
ST
: vetor escalonamento com os tempos de início STj
FT
: vetor escalonamento com os tempos de conclusão FTj
M
T
vetor dos modos de execução mj
: limitante superior do makespan do projeto (horizonte de tempo)
R(N,D)
: conjunto dos recursos renováveis (não-renováveis, duplamente restritos)
r ∈ R(N,D)
: índice do recurso demandado (consumido)
114
Mj
: número de modos pelos quais a tarefa j pode ser executada
m=1, ..., Mj
: modos possíveis de execução da tarefa j
djm
: duração da tarefa j executada no modo m
ρ
k jmr
: uso por período do recurso renovável (duplamente restrito) r exigido
para executar a tarefa j no modo m
k νjmr
: consumo total do recurso não-renovável (duplamente restrito) r para
executar a tarefa j no modo m
K rρ
: disponibilidade por período do recurso renovável (duplamente restrito) r
K νr
: disponibilidade total do recurso não-renovável (duplamente restrito) r
K (modificar) : número total (itens) dos diferentes recursos , K =|R|+|N|+|D|
115
Bibliografia
Agrawal, M.K., Elmaghraby, S.E., Herroelen, W.S., (1996), “A generator of testsets for project activity nets.”, European Journal of Operational Research,
90: 376-382.
Alvares-Valdés, R., Tamarit, J. M., (1993), “The project scheduling polyhedron:
Dimension, facets and lifting theorems”, European Journal of Operational
Research, 67: 204-220.
Alvares-Valdés, R., Tamarit, J. M., (1996), “Heuristic algorithms for resourceconstrained project scheduling: A review and an empirical analysis “, ed.
Slowiński, R. e Weglarz, J., Advances in Project Scheduling, Elsevier,
Amsterdam, pp. 113-134.
Antonisse, J.M., Hee, K.M., Lenstra, J.K., (1988)T., Brucker, P., Knust, S., (1997),
“Resource-constrained project scheduling: an international exercise in
DSS development”, Decision Sciences, 4:249-257.
Assad, A. A., Wasil, E.A., (1986), “ Project management using a microcomputer ”,
Computers & Operations Research, 13(2/3): 231-260.
Baar, T., Brucker, P., Knust, S., (1997), “Tabu-search algorithms for the resourceconstrained project scheduling problem”, Relatório Técnico, Osnabrücker
Schriften zur Mathematik, Fachbereich Mathematik/Informatik, Universität
Osnabrücker, Alemanha, 14p.
Baker, K. R., (1974), “Introduction to Sequencing and Scheduling”, 1a ed., New
New York, John Wiley & Sons, tal p.
Balas, E., (1969), “Machine sequencing via disjunctive graphs: An implicit
enumeration algorithm”, Operations Research, 17: 941-957.
Bandelloni, M., Tucci, M., Rinaldi, R., (1994), “Optimal resource leveling using
non-serial dynamic programming ”, European Journal of Operational
Research, 78: 162-177.
116
Bell, C.E., Han, J., (1991), “A new heuristic solution method in resource
constrained project scheduling ”, Naval Research Logics, 38: 315-331.
Bhargava, (1996), “Decision support on demand: Emerging electronic markets for
decision technologies “. Decision Support Systems, fevereiro 1996.
Bixby, N., Boyed, E. (1996), “Using the CPLEX callable library”, CPLEX
Optimization Inc., Houston,TX.
Blażewicz, J., Lenstra, J. K., Rinnooy, G., (1983), “Scheduling subject to resource
constraints: classification and complexity”, Discrete Applied Mathematics,
5: 11-24.
Blażewicz, (1996), “The job shop scheduling problem: Conventional and new
solution tecniques”, European Journal of Operational Research, 93: 1-33.
Boctor, F. F., (1993), “Heuristics for scheduling projects with resource restrictions
and several resource-duration modes ”, International Journal of Production
Research, 31(11): 2547-2558.
Boctor, F. F., (1996), “A new and efficient heuristic for scheduling projects with
resource restrictions and multiple execution modes”, European Journal of
Operational Research, 90: 349-361.
Boctor, F. F., (199X), “An adaptation of the simulated annealing algorithm for
solving resource-constrained project scheduling problems ”, International
Journal of Production Research, 3x(11): .
Bouleimen, K., Lecocq, H., (1998), “A new efficient simulated annealing algorithm
for the resource-constrained project scheduling problem ”, Relatório
Técnico, Service de Robotique et Automatisation, Université de Liège.
Brucker, P., Drexl, A., Möhring, R., Neumann, K., Pesch, E., (1998a), “ResourceConstrained Project Scheduling: Notation, Classification, Models, and
Methods”, manuskripte aus den Instituten für Betriebswirtschaftslehre der
Universität Kiel, Alemanha, 51p.
Brucker, P., Knust, S., Schoo, A., Thiele, O. (1998b),”A branch and bound
algorithm for the resource constrained project scheduing problem ”,
European Journal of Operational Research, 107: 272-288.
Carruthers, J.A., Battersby, A., (1966), “Advances in critical path methods”,
Operations Research Quarterly, 17(4): 359-380.
Cavalcante, C.C.B., (1998), “Escalonamento com restrição de mao-de-obra: heurísticas combinatórias e limitantes inferiores”,Tese (Mestrado em Ciências
da Computação), Campinas-SP, Unicamp, 119p.
117
Cho, J.H., Kim, Y.D., (1997), “A simulated annealing algorithm for resource
constrained project scheduling “, Journal of the Operational Research
Society, 48: 736-744.
Chong, E.K.P., Z ak , S.H., (1996), “An ntroduction to optimization”, New York,
John Wiley & Sons, 409p.
Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A., (1998), “Combinatorial
optimization”, New York, John Wiley & Sons, 355p.
Cooper, D.F., (1976), “Heuristics for scheduling resource-constrained projects: An
experimental investigation ”, Management Science, 22(11): 1186-1194.
Christofides, N., Alvares-Valdés, R., Tamarit, J. M., (1987), “Project scheduling
with resource constraints: A branch and bound approach”, European
Journal of Operational Research, 29: 262-273.
Chung, T. H., Carroll, H.B., (1995), “Application of fuzzy expert systems for EOR
project risk analysis”, SPE 30741, Annual Technical Conference and
Exhibition, Dallas, Texas.
Cortes J. M.R., (1998), “Uma contribuição para a resolução do problema de alocação multiobjetivo de plataformas de produção de petróleo “,Tese (Mestrado em Engenharia de Produção), Campos dos Goitacazes-RJ, UENF,
88p.
Davis, K. R., Stan, A., Grzybowski, A., (1992), “Resource constrained project
scheduling with motiple objectives: A decision support approach ”,
Computers & Opertions Research, 19(7): 657-669.
Davis, E. W., Heidorn, G.E., (1971), “An algorithm for optimal project scheduling
under multiple resource constraints ”, Management Science, 17: 803-816.
Davis, E. W., (1973), “Project scheduling under resource constraints - historical
review and categorization of procedures”, AIIE Transactions, 5: 297-313.
Davis, E. W., (1975), “Project network summary measures constrained-resource
scheduling ”, AIIE Transactions, 7: 132-142.
Deckro, R.F., Hebert, J.E., (1990) “A multiple objective programming framework
for tradeoffs in project scheduling”, Engineering Costs and Production
Economics, 18: 255-264
Demeulemeester, E., Herroelen, W.S., (1992), “A branch and bound procedure for
the multiple resource-constrained project scheduling problem”, European
Journal of Operational Research, 90: 334-348.
Demeulemeester, E., Dodin, B., Herroelen, W.S., (1993), “A random activity
network generator ”, Operations Research, 41: 972-980.
118
Demeulemeester, E., Herroelen, W.S, (1996), “An efficient optimal solution
procedure for the preemptive resource-constrained project scheduling
problem”, European Journal of Operational Research, 90: 334-348.
Demeulemeester, E., Herroelen, W.S., Elmaghraby, S.E., (1996), “Optimal
procedures for the discrete time/cost trade-off problem in project networks
”, European Journal of Operational Research, 88: 50-68.
Drexl, A., Grünewald, J., (1993), “Nonpreemptve mult-imode resource-constrained
project scheduling “, IIE Transactions, 25(5): 74-81.
Drexl, A., Juretzka, J., Salewiski, F., Schirmer, A., (1998), “New modelling
concepts and their impact on resource-constrained project scheduling”,
Handbook on Recent Advances in Project Scheduling, ed. J. Weglarz,
Kluwer, Amsterdam.
Drummond, H., (1999), “Are we any closer to the end? Escalation and the case of
Taurus”, International Journal of Project Management, 17: 11-16.
Elmaghraby, S. E., (1977), “Activity Networks: Project planning and control by
network models ”, New York, John Wiley & Sons, xxx p.
Farid, F., Manoharan,S., (1996), “Comparative analysis of resource-allocation
capabilities of project management software packages”, Project
Management Journal, 24(2): 35-44.
Feo, T.A., Resende, M.G.C., (1989), “A probabilistic heuristic for a computationally
difficult set covering problem ”, Operations Research Letters, 8: 67-71.
Feo, T.A., Resende, M. G. C., (1994), “Greedy Randomized Adaptive Search
Procedures ”, The University of Texas, Austin, Relatório Técnico.
French, S., (1982), “Sequencing and scheduling: An introduction to the
mathematics of the job-shop ”, New York, John Wiley & Sons, NY.
Gantt, H.L. (1919), “Efficiency and democracy”, Transactions of the American
Society of Mechanical Engineers, EUA, 40: 799-808
Garey, M.R., Johnson, D.S., (1979), “Computer and intractability – A guide to the
theory of NP-completeness ”, W.H. Freeman, San Francisco.
Glover, F. (1989),“Tabu search, Part I”,ORSA Journal on computing, 1(3):190-206.
Glover, F. (1990), “ Tabu search, Part II ”, ORSA Journal on computing, 2(3): 4-32.
Goldberg, D. E., (1989), “Genetic Algorithms in Search, Optimization, and
Machine Learning”, Massachusetts, Addison-Wesley Longman, 412 p.
119
Graham, R.L, Lawler, E.L.,Lenstra, J. K., e Rinnooy Kan, A.H.G. (1979)
“Optimization and approximation in deterministic sequencing and
scheduling theory: a survey ”, Annals of Discrete Mathematics, 5: 287-326.
Günther, O., Müller, R., Schmidt, P., Bhargava, H., Krishnan, R., (1997), “MMM: A
web-based system for sharing statistical computing modules”, Internet
Computing, 1(3): 59-68.
Harding, A. M., (1997), “Experience whith a global optimisation approach to
project scheduling and resource allocation”, SPE 38488, Offshore Europe
Conference, Aberdeen, Scotland.
Hartmann, S., Drexl, A., (1997), “Project scheduling with multiple modes: A
comparison of exact algorithms ”, manuskripte aus den Instituten für
Betriebswirtschaftslehre der Universität Kiel, wp430, Alemanha, 22p.
Hartmann, S. (1997a), “Project scheduling with multiple modes: a genetic
algorithm”, manuskripte aus den Instituten für Betriebswirtschaftslehre der
Universität Kiel, wp435, Alemanha, 21p.
Hartmann, S. (1997b), “A competitive genetic algorithm for resource-constrained
project
scheduling”,
manuskripte
aus
den
Instituten
für
Betriebswirtschaftslehre der Universität Kiel, wp451, Alemanha, 18p.
Hartmann, S., Kolisch, R., (1999), “Experimetal evaluation of state-of-the-art
heuristics for the resource-constrained project scheduling ”, Proceedings
of INFORMS Spring Conference, Cincinatti, Ohio, EUA.
Hartmann, S. (1999), “ Self-adapting genetic algorithm with an application to
project scheduling ”, manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel, Alemanha, 24p.
Heller, U., (1981), “On the shortest overall duration in stochastic project networks”,
Methods of Operations Research, 42: 85-104.
Herroelen, W.S., van Dommelen, P., Demeulemeester, E.L, (1997), “Project
network models with discounted cash flows – A guided tour through recent
developments”, European Journal of Operational Research, 100: 97-121.
Hillier, F. S., Lieberman, G. J., (1995), “Introduction to Operations Research”, New
York, McGraw-Hill, Inc., 6a ed., 998 p.
Holland, J. H. (1995), “Adaptation in natural and artificial systems ”, MIT Press,
Cambridge, MA, 5ª reimpressão, 211p.
Houdayer, J., Martin, O. C., (1999), “Renormalization for discret optimization”,
Loboratoire de Physique Théorique et Modèles Statistiques, Université
Paris-Sud, Relatório Técnico.
120
Icmeli, O., Erenguc, S. S., Zappe, C. J., (1993), “Project scheduling problems: a
survey”, International Journal of Operations and Production Management,
13(11): 80-91
Icmeli, O., Rom, W.O., (1997), “Ensuring quality in resource constrained project
scheduling”, European Journal of Operational Research, 103: 483-496
Icmeli, O., Rom, W.O., (1998), “Analysis of the characteristics of projects in
diverse industries”, Journal of Operations Management” , Technical Note,
16: 43-61
Jackson, R.H.F., Boggs, P.T., Nash, S.G., Powell, S., (1991), “Guidelines for
reporting results of computational experiments. Report of the ad hoc
committee”, Mathematical Programming, North-Holland, 49: 413-425
Johnson, R.V., (1992), “Resource constrained scheduling capabilities of
commercial project management software ”, Project Management Journal,
22(4): 39-43.
Jüngen, F. J., Kowalczyk, W., (1995), “An intelligent interactive project
management support system”, European Journal of Operational Research,
84: 60-81.
Kelley, J.E., (1963), “The critical path method: Resource planning and scheduling”,
Industrial Scheduling, ed. Muth, J.F. e Thompson, G.L, Prentice-Hall, New
Jersey.
Kirkpatrick, S., Gellat Jr., C.D., Vecchi, M.P., (1983), “Optimization by simulated
annealing “, Science, 220: 671-680.
Kohlmorgen, U., Schmeck, H., Haase, K., (1998), “Experiences with fine-grained
parallel genetic algorithm ”, manuskripte aus den Instituten für
Betriebswirtschaftslehre der Universität Kiel, Alemanha, 17p.
Kolisch, R., Sprecher, A., Drexl, A., (1995), “Characterization and generation of a
general class of resource-constrained project scheduling problems”,
Management Science, 41(10): 1693-1703
Kolisch, R., Hempel, K., (1996), “Finite scheduling capabilities of commercial
project management systems”, manuskripte aus den Instituten für
Betriebswirtschaftslehre der Universität Kiel, Alemanha, no. 397, 15p.
Kolisch, R., (1996), “Serial and parallel resource-constrained project scheduling
methods revisited: Theory and computation”, European Journal of
Operational Research, 90: 320-333
Kolisch, R., Sprecher, A., (1996), “PSPLIB – A project scheduling problem library”,
European Journal of Operational Research, 96: 205-216.
121
Kolisch, R., Padman, R. (1997), “An Integrated survey of project scheduling”,
manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität
Kiel, Alemanha, wp463, 34p.
Kolisch, R., Drexl, A. (1996), “Adaptive search for solving hard project scheduling
problems ”, Naval Research Logics, 43: 23-40.
Kolisch, R., Drexl, A. (1997), “Local search for nonpreemptive multi-mode
resource-constrained project scheduling”, IIE Transactions 29: 987-999.
Kolisch, R., Hartmann, S., (1998), “Heuristic algorithms for solving the resourceconstrained project scheduling problem: Classification and computacional
analysis ”, Handbook on Recent Advances in Project Scheduling, ed. J.
Weglarz, Kluwer, Amsterdam.
Kolisch, R., Schwindt, C., Sprecher, A., (1998), “Benchmark instances for project
scheduling problems”, Handbook on Recent Advances in Project
Scheduling, ed. J. Weglarz, Kluwer, Amsterdam.
Langley, P. (1996), “Elements of Machine Learning”, San Francisco, CA, Morgan
Kaufmann, Inc., 419p.
Lee, J.K., Kim, Y.D, (1996), “Search heuristics for resource constrained
scheduling”, Journal of the Operational Research Society, 47: 678-689.
Lenstra, J. K., e Rinnooy Kan, A.H.G. (1979) “Computational complexity of
discrete optimization problems”, Annals of Discrete Mathematics, 4: 121140.
Leon, V.J., Balakrishnan, R., (1995), “Strength and adaptability of problem space
based neighborhoods for resource-constrained scheduling “, OR
Spectrum, 17(2/3): 173-182.
Lewis, J. P. (1997), “Fundamentals of Project Management ”, New York, NY,
Amacom, 117p.
Lewis, J. P. (1998), “Mastering Project Managemen: applying advanced concepts
of Systems Thinking, Control and Evaluation, Resource Allocation”, New
York, NY, McGraw-Hill, 319p.
Lock, D., (1997), “Project Managemen””, Hampshire, England, Gower Publishing
Limited, 522p.
Maroto, C., Tormos, P., (1994), “Project management: an evaluation of software
quality ”, Transactions of Operatinal Research, 1(2): 209-221.
Mausser, H.E., Lawrence, S.R., (19XXcap3), “Exploiting block structure to improve
resource-constrained project schedules ”, Metaheuristics, 1(2): 209-221.
122
Mavridou, T., Pardalos, P. M., Pitsoulis, L., Resende, M. G., (1995), “Parallel
search for combinatorial optimization: genetic algorithms, simulated
annealing, tabu search and GRASP ”, Proceedings of the workshop on
parallel algorithms for irregularly structured problems, Lyon, França.
Mori, M., Tseng, C.C.,(1997), ”A genetic algorithm for multi-mode resourceconstrained project scheduling problem”, European Journal of Operational
Research, 100: 134-141.
Morton, T. E., Pentico, D. W., (1993), “Heuristic Scheduling Systems”, New York,
John Wiley & Sons, 695 p.
Nemhauser, C.L., Wolsey, L.A., (1988), “Integer and Combinatorial Optimization ”,
New York, John Wiley & Sons, 763 p.
Neumann, K., Schwindt, C., (1995), “Projects with minimal and maximal time lags:
construction of activity-on-node networks and aplications”, Universität
Karlsruhe, Relatório Técnico, wior-447, 36p.
Norbis, M., Smith, J. M., (1996), “ An interactive decision support system for the
resource constrained scheduling problem ”, European Journal of
Operational Research, 94: 54-65.
Oğuz, O., Bala, H., (1994), “A comparative study of computational procedures for
the resource constrained project scheduling problem ”, European Journal
of Operational Research, 72: 406-416.
Özdamar, L., Ulusoy, G. (1995), “An iterative local constraint based analysis for
solving the resource-constrained project scheduling problem “, Journal of
Operations Management, 14(3): 193-208.
Özdamar, L., (1996), “A genetic algorithm approach to the general category
project scheduling problem ”, Relatório Técnico, Marmara University,
Istanbul.
Pascoe,T.L., (1966), “Allocation of resources CPM. ”, Revue Française Recherche
Operationelle, 38: 31-38.
Patterson, J. H., Huber, W.D., (1974), “A horizon-varying, zero-one approach to
project scheduling ”, Manegement Science, 20: 990-998.
Patterson, J. H., (1984), “A comparison of exact approachs for solving the multiple
constrained resource, project scheduling problem”, Manegement Science,
30(7): 854-867.
Pinedo, M. (1995), “Scheduling: theory, algorithms, and systems”, New Jersey,
Prentice-Hall, 378 p.
123
Pinson, E., Prins, C., Rullier, F., (1994), “Using tabu search for solving the
resource-constrained project scheduling problem”, Proceedings of the 4º
International Workshop on Project Management and Scheduling, pp.102106.
Pritsker, A., Watters, W., Wolfe, P., (1969), “Multiproject scheduling with limited
resources: A zero-one programming approach”, Management Science, 16:
93 –108.
Project Management Institute, (1996),”Project Management Body of Knowledge”,
Pennsylvania, EUA, 176p.
Pyron, T., “Using Microsoft Project 98 – special edition”, Indiana, QUE
Corporation, 989p.
Resende, M.G.C., (1998), “A bibliografy of GRASP ”, AT&T Labs Research.
Russel, A.H., (1970), “Cash flows in networks”, Management Science, 16(5): 357373.
Salewski, F., Schirmer, A., Drexl, A., (1996), “Project scheduling under resource
and mode identity constraints. Part II: an application to audit-staff
scheduling”, manuskripte aus den Instituten für Betriebswirtschaftslehre
der Universität Kiel, wp388, Alemanha, 24p.
Simpson, W.P., Patterson, J.H, (1996), “A multiple tree-search for the resource
project scheduling problem ”, European Journal of Operational Research,
89: 525-542.
Slowiński, R., SonieWicki, B.,Weglarz, J., (1994), “DSS for multiobjective project
scheduling subject to multiple-category resource constraints”, European
Journal of Operational Research, 79: 220-229.
Schirmer, A., (1996a), “A guide to complexity theory in operations research”,
manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität
Kiel, wp381, Alemanha, 46p.
Schirmer, A., (1996b), “New insights on the complexity of resource-constrained
project scheduling: a case of single-mode scheduling”, manuskripte aus
den Instituten für Betriebswirtschaftslehre der Universität Kiel, wp390,
Alemanha, 17p.
Schirmer, A., (1996c), “New insights on the complexity of resource-constrained
project scheduling: two cases of multi-mode scheduling”, manuskripte aus
den Instituten für Betriebswirtschaftslehre der Universität Kiel, wp391,
Alemanha, 30p.
Schirmer, A., (1997), “Advanced Biased Random Sampling in Serial and Parallel
Scheduling”, manuskripte aus den Instituten für Betriebswirtschaftslehre
der Universität Kiel, Alemanha, 34p.
124
Schirmer, A., Drexl, A., (1997), “Allocation of partially renewable resources –
concept, models and applications”, manuskripte aus den Instituten für
Betriebswirtschaftslehre der Universität Kiel, wp455, Alemanha, 26p.
Schirmer, A., Riesenberg, S., (1997), “Parameterized Heuristics for Project
Scheduling – Biased Random Sampling Methods”, manuskripte aus den
Instituten für Betriebswirtschaftslehre der Universität Kiel, wp456,
Alemanha, 43p.
Schirmer, A., Riesenberg, S., (1998), “Class-base control schemes for
parameterized project scheduling heuristics”, manuskripte aus den
Instituten für Betriebswirtschaftslehre der Universität Kiel, wp471,
Alemanha, 26p.
Schirmer, A., (1998), “Case-based reasoning and improved adaptive search for
project
scheduling”,
manuskripte
aus
den
Instituten
für
Betriebswirtschaftslehre der Universität Kiel, wp472, Alemanha, 27p.
Shaffer, L.R., Ritter, J.B., Meyer, W.L., (1965), “The critical-path method “,
McGralw Hill, Nova Iorque.
Slack, N., Chambers, S., Harland, C., Harrison, A., Johnston, R., (1995), “Administração da Produção”, Editora Atlas S.A., São Paulo, SP, 722p.
Slowiński, R., (1980), “Two approaches to problems of resource allocation among
project activities – A comparative study ”, Journal of the Operational
Research Society, 31(8): 711-723.
Slowiński, R., SonieWicki, B.,Weglarz, J., (1994), “DSS for multiobjective project
scheduling subject to multiple-category resource constraints”, European
Journal of Operational Research, 79: 220-229.
Sprecher, A., Hartmann, S., Drexl, A., (1994), “Project scheduling with discrete
time-resource and resource-resource tradeoffs”, manuskripte aus den
Instituten für Betriebswirtschaftslehre der Universität Kiel, wp357,
Alemanha, 24p.
Sprecher, A., Kolisch, R., Drexl, A., (1995), “Semi-active, active, and non-delay
schedules for the resource-constrained project scheduling problem”,
European Journal of Operational Research, 80: 94-102
Sprecher, A., (1997), “Solving the RCPSP efficiently at modest memory
requirement ”, manuskripte aus den Instituten für Betriebswirtschaftslehre
der Universität Kiel, wp425, Alemanha, 21p.
Sprecher, A., Hartmann, S., Drexl, A., (1997), “An exact algorithm for project
scheduling with multiple modes ”, OR Spektrum, 19: 195-203.
125
Stinson, J.P., Davis, E.W., Khumawala, B.M., (1978), “Multiple resourceconstrained scheduling using branch and bound”, AIIE Transactions,
10:252-259.
Storer, R.H., Wu, S.D., Vaccari, R. (1992), “New search spaces for sequencing
problems with applications to job shop scheduling “, Management
Science, 38: 1495-1509.
Talbot, F.B., Patterson, J.H., (1978), “An efficient integer programming algorithm
with network cuts for solving resource-constrained scheduling problems ”,
Management Science 24: 1163-1174.
Talbot, F.B., (1982), “Resource constrained scheduling with time-resource
tradeoffs: The non-preemptive case”, Management Science 28(10): 11971210.
Tavares, L.V., Ferreira, J.A.A., Coelho, J.S., (1998), “On the optimal management
of project risk”, European Journal of Operational Research, 107: 451-469.
Tsai, Y-W., Gemmill, D. D., (1998), “Using tabu search to schedule activities of
stochastic resource-constrained projects ”, European Journal of
Operational Research, 111: 129-141.
Turner, S. K., Singer, R.V., Pegram, A., Saunders, B., (1998), “Integrated risk
management in oil and gas exploration and production”, SPE 46811,
International Conference on Health, Safety and Enviroment in Oil and Gas
Exploration and Production, Caracas, Venezuela.
Valeriano, D.L, (1998), “Gerência em projetos – pesquisa, desenvolvimento e engenharia”, São Paulo, Makron Books do Brasil, 438 p.
Wall, M.B. (1996), “A genetic algorithm for resouce-constrained scheduling”, Tese
(Doutorado em Engenharia Mecânica), MIT- Massachusetts, EUA, 62p.
Weglarz, J., (1981), “Project scheduling with continuously-divisible, doubly
constrained resources ”,Management Sciences, 27(9): 1040-1053.
de Wit, J., Herroelen, W., (1990), “ An evaluation of microcomputer-based
software packages for project management ”, European Journal of
Operational Research, 49: 102-139.
Zaver, M., (1998), “An integrated approach to project management, Wainwright
West Project”, SPE 49064, Annual Technical Conference and Exhibition,
New Orleans, Lousiana.
126
Anexo
Análise de Complexidade do PSP
Com o propósito de jogar alguma luz sobre complexidade no que se refere aos problemas e algoritmos de solução do PSP tratados nos capítulos precedentes, o tema
é aqui brevemente discutido. A abordagem adotada é antes aquela de maior interesse para a pesquisa operacional.
A teoria da complexidade é focada na tratabilidade computacional inerente aos problemas matemáticos. De há muito já se sabe que existem problemas algorítmicos
cuja solução é impossível. Mesmo dentre problemas que garantidamente são solucionáveis, há casos que podem ser considerados praticamente insolúveis. Decorre daí
que, antes de se perguntar se um problema de fato tem solução, a questão de fundo
é o quão eficientemente um problema pode ser resolvido. É exatamente isso que
constitui o tema central da analise de complexidade.
Numerosos critérios já foram sugeridos para medir a eficiência de algoritmos com
respeito ao cálculo de solução exata mas, em última análise, esta se relaciona ao
tempo computacional. Assim, um algoritmo é considerado tão mais eficiente quanto
mais rapidamente resolve um dado problema. Também, a complexidade de um algoritmo costuma ser expressa em termos de tempo de solução como função do tamanho da instância. Para cada tamanho de instância, conforme é usual, aqui a complexidade baseia-se no pior caso. Coerentemente, a complexidade no tempo de um algoritmo estabelece o tempo requerido, no pior caso, para resolver uma instância daquele tamanho.
Por simplicidade, nenhuma distinção se faz entre o número de operações executadas por um algoritmo para solução de um problema e a duração de seu processa-
127
mento, porque presume-se que cada operação se dá num mesmo espaço de tempo
(unit time measure).
Com base no pior caso, um algoritmo é considerado de tempo polinomial (ou, simplesmente, polinomial) se, e somente se, sua complexidade no tempo puder ser limitada por um polinômio no tamanho da instância; em caso contrário, o algoritmo dizse exponencial. Algoritmos polinomiais são considerados eficientes, ao passo que os
exponenciais não o são, porque aqueles, em geral, são mais rápidos do que estes.
Por extensão, a complexidade de um problema é associada à complexidade do melhor algoritmo possível capaz de resolvê-lo, onde melhor algoritmo possível deve ser
entendido como aquele que apresente a mais baixa complexidade no tempo. Consoante, um problema é dito polinomial se, e somente se, existir um algoritmo polinomial que possa resolvê-lo; no caso contrário, o problema é referido como exponencial.
Decorre daí que, para um dado problema, a complexidade de qualquer algoritmo conhecido que possa resolvê-lo fornece um limitante superior para sua complexidade.
Problemas cuja solução somente se obtém por algoritmos de tempo exponencial são
rotulados como intratáveis, i.é, não eficientemente solucionáveis; de outro lado,
aqueles problemas cuja solução se alcança a partir de um algoritmo polinomial são
ditos tratáveis.
Na prática, entretanto, a distinção entre problemas tratáveis e intratáveis é apenas
de valor restrito, de vez que, para uma vasta gama de problemas, malgrado atilados
estudos de abnegados pesquisadores, se por um lado não se encontrou um algoritmo polinomial para sua solução, por outro lado não se tem uma prova de sua intratabilidade. Daí, hoje em dia, ao se classificar um problema em função de sua tratabilidade, uma distinção se faz entre os polinomiais, da classe P, daqueles ditos NPcompletos, cuja solução não conta com nenhum algoritmo polinomial conhecido.
A classe NP23 reúne os problemas para o quais uma resposta positiva tem um “certificado”, a partir do qual sua veracidade pode ser verificada em tempo polinomial. Por
exemplo, a questão:
Dado um PSP, existe um escalonamento S que seja viável em precedência e recursos?
pertence à classe NP. Se a resposta é “sim”, basta simplesmente apresentar um escalonamento S como certificado e a resposta pode ser confirmada em tempo polino23
NP não significa “não-polinomial”. Leia-se como “tempo polinomial não-determinístico”
128
mial. Note-se que não se faz obrigatório descobrir o certificado em tempo polinomial;
é suficiente que o certificado exista com as propriedades requeridas.
Pode-se demonstrar que P ⊆ NP (Cook et al., 1998). A classe NP é, aparentemente,
muito maior que a P, e mesmo não parece haver muitas razões fazendo crer que
ambas são iguais. Não obstante, ninguém ainda foi capaz de provar que são de fato
diferentes. Por conseguinte, uma questão fundamental se impõe: seria P = NP? Uma
resposta, negativa ou positiva, provavelmente fará emergir enormes efeitos práticos
para a análise de complexidade.
Transformação Polinomial e Prova de Complexidade
Definição 1 um problema de decisão é um par Π=(D,Y) no qual D é um conjunto de
objetos finitos , chamados instâncias (I), e Y ⊆ D é um subconjunto de objetos denominados instâncias-sim.
Se um algoritmo A for capaz de decidir, para cada instância Ik ∈ D, se também Ik ∈ Y,
diz-se que A resolve Π.
Definição 2 Sejam Π=(D,Y) e Π’=(D`,Y`) problemas de decisão. Então Π polinomialmente transforma-se em Π’ se, e somente se, existir uma função f : D → D`; I → I` tal
que:
(1) I ∈ Y se, e somente se I` ∈ Y`, e
(2) f puder ser computada por um algoritmo polinomial determinístico.
A utilidade da transformação (em tempo) polinomial se comprova pelo que se segue.
Empregando-se tal conceito, podem-se definir classes de problemas de decisão que
são de complexidade computacional equivalente. A classe de maior destaque é a
dos problemas NP-completos, os quais se definem como aqueles mais difíceis em
NP. Um problema Π é dito NP-completo se para cada problema Π’ em NP existir
uma transformação polinomial de Π’ para Π. Ou seja, se Π ∈ NP , Π’ é NP-completo
e existe uma redução em tempo polinomial de Π’ para Π, implica que também Π é
NP-completo.
Comumente, para se provar complexidade, costuma-se meramente demonstrar que
o problema em consideração é uma generalização de algum outro cuja complexidade é conhecida. Empregando-se demonstração devida a Kolisch e Drexl (1997), pro129
va-se agora que, para MRCPSP mais restritos, mesmo a questão de existência de
uma solução viável, de per si, já é um problema NP-completo.
Teorema
O problema de viabilidade do MRCPSP é NP-completo para |N| ≥ 2 e Mj
≥ 2, 1 ≤ j ≤ J.
Prova
Claramente, o problema está em NP, uma vez que a viabilidade de qualquer solução
pode ser conferida em tempo polinomial. Para a demonstração, antes de tudo, fazse uma transformação polinomial do MRCPSP para o problema da mochila, o qual
notoriamente é NP-completo (Garey e Johnson, 1979).
O problema da mochila (knapsack problem – KSP) pode ser declarado do seguinte
modo: dados um conjunto finito U com elementos u, 1 ≤ u ≤ |U|, um tamanho s(u) ∈
Z+ e um valor v(u) para cada u ∈ U , um tamanho B ∈ Z+ e um tamanho D ∈ Z+, existe um subconjunto U’ ⊆ U tal que valem as relações
∑
u∈ U
s(u) ≤ B e
∑
u∈ U '
v( u ) ≥ D ?
A idéia geral por trás da transformação é mapear cada elemento de U em uma atividade real (não-fictícia) com dois modos de execução. Se uma atividade é processada no modo m=1 o u correspondente é elemento do subconjunto U’ ; contrariamente,
se m=2, o u correspondente não é membro de U’. Então, J = |U|+1, Mj=2, 1 ≤ j ≤ J e
Mj = 1, j ∈ {0,J+1}. As duas restrições da mochila são representadas por duas restrições de recursos não-renováveis, i.é, |N| = 2. Paralelamente, as restrições referentes
aos recursos renováveis não têm que ser levadas em conta, quer dizer, R = ↓.
A primeira restrição da mochila pode ser considerada diretamente. Daí, com respeito
ao recurso r=1, a disponibilidade é K1=B e, para cada atividade 1 ≤ j ≤ J, o consumo
de recurso do primeiro modo vale kj11 = s(u), enquanto o consumo de recurso no segundo modo é igual a zero, kj21 = 0.
A segunda restrição da mochila deve ser reescrita como se segue para ser considerada. Multiplica-se a restrição por “-1” o que produz
∑
u∈ U '
− v( u ) ≤ -D. Isto feito, adicio-
na-se max {v(z) | z ∈ U} para cada somatório do primeiro membro e |U|.max {v(z) | z ∈
U} para o segundo membro de modo a se obter somente valores não-negativos.
Pode-se agora proceder conforme feito com a primeiro restrição: para o recurso r=2,
o consumo para cada atividade 1 ≤ j ≤ J é kj12 = max {v(z) | z ∈ U} – v(u), quando pro130
cessada no primeiro modo e kj22 = max {v(z) | z ∈ U}, se no segundo modo. A disponibilidade de recurso é K2 = |U|. max {v(z) | z ∈ U} - D .
Todos o outros parâmetros do problema de escalonamento recebem zero, i.e, djm = 0
para todo 1 ≤ j ≤ J, m=1,...,Mj e Pj = ↓ para j=1,...,J+1. Conseqüentemente, cada instância do problema da mochila pode ser polinomialmente transformada em uma instância do MRCPSP. Uma solução para este último polinomialmente se converte em
uma solução do problema da mochila: se o primeiro modo for designado para a atividade j, 1 ≤ j ≤ J, i.e, mj=1, o correspondente u está em U’. Isso prova que o problema
de viabilidade do MRCPSP, para |N| ≥ 2 e Mj ≥ 2, 1 ≤ j ≤ J , é NP-completo.
♦
Merece registro o esforço de Schirmer (1996b e 1996c), que argumenta com evidências que a complexidade de um problema pode depender da formulação empregada
para traduzir o modelo. O autor examina a prática padrão de se representar os problemas de escalonamento de projeto restritos em recursos – a saber, modelos de
otimização utilizando variáveis binárias para se representar escalonamentos. Como
Pritsker, Watters e Wolfe (1969) foram os primeiros a utilizar este conceito para escalonamento, os modelos derivados – e.g., aquele formulado por (6)–(12) da tabela
3.3 – são denominados modelos PWW.
Tanto para o RCPSP como para o MRCPSP, Schirmer (op. cit.), prova que, em sua
viab .
viab .
versão de viabilidade, em seu modelo PWW, i.e., o RCPSP PWW e o MRCPSP PWW
não podem ser verificados em tempo polinomial, i.e., são exponenciais. Obviamente,
qualquer solução para uma instância do RCPSPPWW ou do MRCPSPPWW também o é
para seu o correspondente problema de viabilidade. Sucede que o problema de viabilidade não pode ser de mais fácil solução do que sua versão exata, donde se conclui que tanto o RCPSPPWW quanto MRCPSPPWW são exponenciais.
Por definição, o conceito NP-completo aplica-se a problemas em NP e, portanto, tãosomente a problemas de decisão. Todavia, esta restrição não impede que o conceito
seja ampliado para os problemas de busca (cf. Schirmer 1996a), como é o caso da
otimização nos domínios da pesquisa operacional. Analogamente, a conjectura de
intratabilidade pode ser estendida imediatamente dos problemas (de decisão) de viabilidade, NP-completos, para os problemas de otimização, que então são classificados como NP-difícieis. Foi demonstrado por Blażewicz et al. (1983) que o RCPSP,
131
como generalização do problema de job shop, JSP, pertence à classe dos problemas de otimização NP-difícieis.
Deve ser enfatizado que, apesar de, como se viu, comprovadamente intratável, não
se exclui a possibilidade de que algumas ou mesmo a maioria das instâncias do
PSP possam ser resolvidas em tempo polinomial. Uma vez que a definição de complexidade considerada tem em conta o pior caso, antes significa que nem todas as
suas instâncias são passíveis de solução em tempo polinomial.
132