capÍtulo 1 conceitos sobre planeamento e escalonamento
TRANSCRIPT
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 1 Planning and Scheduling, FEUP/PRODEI /MIEIC 1
Métodos de Planeamento e Escalonamento
Eugénio Oliveira
CAPÍTULO 1
Conceitos sobre Planeamento e Escalonamento
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 2 Planning and Scheduling, FEUP/PRODEI /MIEIC 2
Métodos de Planeamento e Escalonamento
Planeamento e Escalonamento : Processo de “tomada de decisão” quanto à selecção e (sequenciação)/ordenação de atividades e ao uso otimizado de recursos limitados para as realizar em ambientes de produção (incluindo serviços)
Processos de Planeamento e Escalonamento baseiam-se em técnicas e métodos: matemáticos heurísticos
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 3 Planning and Scheduling, FEUP/PRODEI /MIEIC 3
Métodos de Planeamento e Escalonamento
Planeamento e Escalonamento : São importantes em grandes projetos/realizações que consistem na execução de várias tarefas involvendo Restrições (mútuas ou não)
Um dos Objetivos é sempre minimizar o tempo de finalização da última tarefa “Makespan”
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 4 Planning and Scheduling, FEUP/PRODEI /MIEIC 4
Métodos de Planeamento e Escalonamento
Nos Modelos de Linhas de produção (Job Shop) e dispondo de Sistemas Flexíveis de Produção (FMS) pretende-se maximizar o “throughput” (produtividade , produção em função dos fatores de produção: tempo, matéria prima, pessoal...) FMS são sistemas de produção altamente automatizados como por exemplo na Indústria Automóvel
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 5 Planning and Scheduling, FEUP/PRODEI /MIEIC 5
Métodos de Planeamento e Escalonamento
Exemplo de aplicação: Conceção, instalação e teste de um grande sistema computacional Tarefas: identificação dos requisitos selecção do hardware desenvolvimento/adaptação do software teste e depuração de erros recrutamento e treino de operadores Objetivos: Instalação no tempo mínimo respeitar a ordenação das tarefas
Planeamento e Controlo de Projetos e Processos
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 6 Planning and Scheduling, FEUP/PRODEI /MIEIC 6
Métodos de Planeamento e Escalonamento
Exemplo de aplicação: Sistema de Produção de Circuitos Integrados Tarefas: produção de “bolachas” de silício teste das “bolachas” de silício corte dos Circuitos Integrados montagem do Circuitos Integrados Teste de qualidade Objetivos: Produção da maior quantidade possível de CIs com o máximo de qualidade
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 7 Planning and Scheduling, FEUP/PRODEI /MIEIC 7
Métodos de Planeamento e Escalonamento
Planeamento encontra, a um nível de maior abstração e agregação as restrições a observar posteriormente pela fase de Escalonamento e a tomada de decisão a um nível mais detalhado
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 8 Planning and Scheduling, FEUP/PRODEI /MIEIC 8
Métodos de Planeamento e Escalonamento
Exemplo: planeamento e escalonamento numa cadeia de fornecimento. Tarefas: material ou bens são movimentados de uma empresa para outra (numa rede de empresas). Objetivos: minimizar os custos totais (produção, transporte e inventário).
Ex: Fábrica de papel está incluida numa rede de empresas desde o fornecimento da madeira, a celulose, tratamento, armazenamento até à venda aos consumidores finais Mais valor vai sendo adicionado em cada passo da cadeia
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 9 Planning and Scheduling, FEUP/PRODEI /MIEIC 9
Métodos de Planeamento e Escalonamento
xx
Modelos de Cadeia de Fornecimento (Supply-Chain)
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 10 Planning and Scheduling, FEUP/PRODEI /MIEIC 10
Métodos de Planeamento e Escalonamento
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 11 Planning and Scheduling, FEUP/PRODEI /MIEIC 11
Métodos de Planeamento e Escalonamento
Antecipar/influenciar Comportamento de consumidores Maximizando lucros
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 12 Planning and Scheduling, FEUP/PRODEI /MIEIC 12
Métodos de Planeamento e Escalonamento
Caracteristicas das Atividades (processamento)
Restrições: de precedência de recursos (máquinas...) elegíveis da força de trabalho (equipas, nº de trabalhadores…) de manuseamento de materiais (robôs,…)
Restrições: de custos de sequência dos tempos de “set up”, manutenção,… de espaço de armazenamento e tempos de espera de prioridades (interromper tarefas devido a outras) de meios de transportes
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 13 Planning and Scheduling, FEUP/PRODEI /MIEIC 13
Métodos de Planeamento e Escalonamento
Medidas de Desempenho e Objetivos:
Minimizar o “Makespan” equivale (ajuda) a maximizar o “Throughput”
Throughput: dependente de passos (ou recursos) críticos (engarrafamentos)
Makespan: Cmax = max (C1, C2,…, Cn) onde Ci é o tempo da finalização da realização da tarefa Ti
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 14 Planning and Scheduling, FEUP/PRODEI /MIEIC 14
Métodos de Planeamento e Escalonamento
Medidas de Desempenho e Objetivos:
Desvio temporal (Lateness): Lj = Cj – dj Onde dj é o tempo devido para finalizar a tarefa j Desvio máximo: max (L1,…Ln)
Atraso (“Tardiness”): Função objetivo Tj = max(Cj-dj, 0)
“Tardiness” ponderada: Somatório de Wj*Tj (1 a n)
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 15 Planning and Scheduling, FEUP/PRODEI /MIEIC 15
Métodos de Planeamento e Escalonamento
Medidas de Desempenho e Objetivos:
Os Objetivos normalmente combinam tempos e utilização de recursos (custos) Minimizar os Custos totais, relacionados com: makespan setup atraso (tardiness) pessoal
Tentar encontrar tempo ideal de início das actividades
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 16 Planning and Scheduling, FEUP/PRODEI /MIEIC 16
Métodos de Planeamento e Escalonamento
Representações de planos de atividades:
Precedências: 1 - 4 2 - 5 3 - 6, 7 4 - 6, 7 5 - 6 6 -2 7 -2
Tarefas no eixo dos tempos
Diagrama em Rede
Diagrama de Gantt
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 17 Planning and Scheduling, FEUP/PRODEI /MIEIC 17
Métodos de Planeamento e Escalonamento
Método do Passo (ou caminho) Crítico (CPM)
Programar as atividades numa escala temporal Tempos de processamento de tarefas j Pj são conhecidos Independência de recursos Número suficiente de máquinas em paralelo N tarefas com restrições de precedência
Objetivo: minimizar o makespan Há tarefas cujo início pode ser adiado (slack job) e outras que são “tarefas críticas” O conjunto das tarefas que formam um caminho de maior comprimento entre o nó início e nó fim formam o passo crítico e as suas tarefas são Críticas (qualquer atraso, produz atraso do fim do projeto)
Planeamento e Controlo de Projetos e Processos
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 18 Planning and Scheduling, FEUP/PRODEI /MIEIC 18
Métodos de Planeamento e Escalonamento
Método do Passo (ou caminho) Crítico (CPM)
Vantagens: •Visão gráfica (Rede) do desenrolar do projeto/ processo • Prevê o tempo necessário para concluir o projeto/processo • Explicita as atividades críticas a cuidar no plano
Planeamento e Controlo de Projectos e Processos
Fases: • Especificar as atividades individuais • Determinar a ordenação (sequência) dessas atividades • Criar o diagrama em Rede • Estimar o tempo necessário a cada atividade • Identificar o passo crítico • Revêr o diagrama durante a execução
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 19 Planning and Scheduling, FEUP/PRODEI /MIEIC 19
Métodos de Planeamento e Escalonamento
Método do Passo Crítico (CPM)
Procedimento direto (forward procedure) Começando a análise em t=0 calcula o tempo mais cedo possível para iniciar cada tarefa O instante em que se completa a última tarefa = makespan
Procedimento inverso (backward procedure) Começando em t= makespan calcula o tempo máximo em que as tarefas Se podem iniciar. Encontra o passo crítico
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 20 Planning and Scheduling, FEUP/PRODEI /MIEIC 20
Métodos de Planeamento e Escalonamento
Método do Passo Crítico (CPM)
Notação: _pj tempo de processamento da tarefa j _S'j instante mais cedo de início da tarefa j _C'j tempo mais cedo de finalização da tarefa j _S"j instante mais tardio de início da tarefa j _C"j tempo mais tardio de finalização da tarefa j _C'j = S'j + pj _{todas k j} tarefas predecessoras da tarefa j _{j todas k } tarefas sucessoras da tarefa j
C’’
S’
Slack
Pj C’
S’’
Nome da Tarefa j
Descrição da Tarefa Nos diagramas
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 21 Planning and Scheduling, FEUP/PRODEI /MIEIC 21
Métodos de Planeamento e Escalonamento
Método do Passo Crítico (CPM)
Procedimento Directo: Passo 1: t = 0 Fazer S’j=0 e C’j= pj. Para todas j sem predecessores
Passo 2: Calcular para cada uma das outras tarefas j S’j= max C’k {todos kj} C’j= S’j + pj
Passo 3: O makespan óptimo é: C’max= max(C´1,..,C´n)
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 22 Planning and Scheduling, FEUP/PRODEI /MIEIC 22
Métodos de Planeamento e Escalonamento
Método do Passo Crítico (CPM)
Procedimento Inverso: Passo 1: t = Cmax Fazer C’’j= Cmax e S’’j= Cmax - Pj. Para todas j sem sucessores
Passo 2: Calcular para cada tarefa j C’’j = min S’’k (j todos k ) S’’j = C’’j - Pj Passo 3: Verificar se: min(S’’1,..,S’’n)=0
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 23 Planning and Scheduling, FEUP/PRODEI /MIEIC 23
Métodos de Planeamento e Escalonamento
Método do Passo Crítico (CPM)
Se ambos estes tempos são iguais, a tarefa pertence ao Passo Crítico (não tem margem para variar o seu início) Se são diferentes, a tarefa é “slack job” (tarefa ”relaxada”)
Comentários: O procedimento Directo dá o tempo para iniciar cada tarefa o mais cedo possível O procedimento Inverso dá o tempo mais tardio possível de início de cada tarefa
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 24 Planning and Scheduling, FEUP/PRODEI /MIEIC 24
Métodos de Planeamento e Escalonamento
Método do Passo Crítico (CPM)
Exemplo: Tarefas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Pj 5 6 9 12 7 12 10 6 10 9 7 8 7 5
Precedências: O diagrama em rede pode ser Substituído pelo diagrama de Gantt
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 25 Planning and Scheduling, FEUP/PRODEI /MIEIC 25
Métodos de Planeamento e Escalonamento
Método do Passo Crítico (CPM)
Procedimento Directo:
Cmax = 56
Tarefas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Pj 5 6 9 12 7 12 10 6 10 9 7 8 7 5
Tarefas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 C’j 5 11 14 23 21 26 33 32 36 42 43 51 50 56
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 26 Planning and Scheduling, FEUP/PRODEI /MIEIC 26
Métodos de Planeamento e Escalonamento
Método do Passo Crítico (CPM)
Procedimento Inverso:
Tarefas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 C’j 5 11 14 23 21 26 33 32 36 42 43 51 50 56
Tarefas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Pj 5 6 9 12 7 12 10 6 10 9 7 8 7 5
Cmax = 56
36
Tarefas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 C’j 5 11 14 23 21 26 33 32 36 42 43 51 50 56
Tarefas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 C’’j 5 12 14 24 30 26 34 36 36 43 43 51 51 56 26
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 27 Planning and Scheduling, FEUP/PRODEI /MIEIC 27
Métodos de Planeamento e Escalonamento
Método do Passo Crítico (CPM)
Passo Crítico:
Cmax = 56
Tarefas 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 28 Planning and Scheduling, FEUP/PRODEI /MIEIC 28
Métodos de Planeamento e Escalonamento
Técnica de Avaliação e Revisão do Programa /Projeto (PERT)
Tempos de Processamento não deterministicos. Representados por variáveis com aleatoriedade probabilistica Tempos de processamento são médios Mj e com uma variância (sj)2.
Determina o makespan pja = tempo optimista de processamento da tarefa j pjm = tempo mais provável de processamento da tarefa j em condições normais pjb = tempo pessimista de processamento da tarefa j
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 29 Planning and Scheduling, FEUP/PRODEI /MIEIC 29
Métodos de Planeamento e Escalonamento
Técnica de Avaliação e Revisão do Programa/Projeto (PERT)
Cálculo do Makespan esperado: tempo de processamento Médio (esperado) de cada tarefa j: M^
j=(pja+4pjm+pjb)/6
aplicar CPM com tempos de processamento esperados seja Jcp um passo crítico médio
Estimativa do makespan esperado: E^(Cmax)= S j M
^j
(j pertence ao passo crítico médio)
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 30 Planning and Scheduling, FEUP/PRODEI /MIEIC 30
Métodos de Planeamento e Escalonamento
Técnica de Avaliação e Revisão do Programa/Projeto (PERT)
Tempos de processamento de tarefas. Restrições de precedências iguais às já consideradas
Se μ = E(X) é o valor esperado (média) da variável aleatória X, então a variância é Var(X)= E ( (X-m)2 ) Isto é, é o valor esperado do quadrado do desvio de X da sua própria média. Em linguagem comum isto pode ser expresso como "A média do quadrado da distância de cada ponto até a média". É assim a "média do quadrado dos desvios". A variância da variável aleatória "X" é geralmente designada porVar(X) ou simplesmente σ2. Neste caso σ2= (optimista-pessimista/6)2
Cálculo dos valores médios e variâncias:
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 31 Planning and Scheduling, FEUP/PRODEI /MIEIC 31
Métodos de Planeamento e Escalonamento
Técnica de Avaliação e Revisão do Programa/Projeto (PERT)
Ex dos cálculos da Var(j): Tarefa1: Var(T1)= [(4-6)/6]2=(1/3)2
Tarefa2: Var(T2)= [(4-8)/6]2 =(2/3) 2 TarefaT6: Var(T6)=[(12-12)/6] 2 = 0
Eugénio Oliveira FEUP/2014
MPE/ProDEI/MIEIC Eugénio Oliveira Planning and Scheduling, FEUP/PRODEI /MIEIC 32 Planning and Scheduling, FEUP/PRODEI /MIEIC 32
Métodos de Planeamento e Escalonamento
Técnica de Avaliação e Revisão do Programa/Projeto (PERT)
As precedências eram as mesmas e o Passo Crítico igual: 1 3 6 9 11 12 14 Makespan estimado: E^(Cmax)= S m^j =56 (J pertencente a Jcp)
Estimativa da Variância do Makespan:V^(Cmax)= S sj 2 = 2.66 (J pertencente a Jcp)
Potenciais problemas com o PERT: Subestima a duração do projeto. Ignora os passos não críticos Baseado em probabilidades