Pesquisa Operacional 2
Semana 05 - Aula 01
Prof. Anibal Tavares de Azevedo
Tema da Semana
Sequenciamento de Tarefas - Teoria
Semana 05
Sequenciamento de Tarefas
Aplicações
Semana 05
Princípios para a modelagem
2 corpos não ocupam o mesmo espaço ao
mesmo tempo
Semana 05
Instrumentos para a modelagem
Relembrando a simulação da Semana 02
Espaço & Tempo em um simulação
Semana 05
Gráfico de Gantt - Simulação simplificada
Espaço & Tempo em um plano cartesiano
Espaço
Tempo
Semana 05
Gráfico de Gantt - Simulação simplificada
Apenas um produto no sistema
Espaço
Tempo
Semana 05
Gráfico de Gantt - Simulação simplificada
Um produto na fila outro no atendimento
Espaço
Tempo
Semana 05
Componentes do problema
Linha do tempo
Máquina
Tarefa 1
Tarefa 2
Semana 05
Componentes do problema
Processamento da Tarefa 1
Máquina
Tarefa 1
Tarefa 2
Espaço
Tempo
p1
Semana 05
Componentes do problema
Instante de entrega C1
Máquina
Tarefa 1
Tarefa 2
Espaço
Tempo
p1
C1
Instante
Entrega
Semana 05
Componentes do problema
Data de entrega d1
Máquina
Tarefa 1
Tarefa 2
Espaço
Tempo
p1
C1
d1
Instante
Entrega
Data de
Entrega
Semana 05
Componentes do problema
Avanço da tarefa E1
Máquina
Tarefa 1
Tarefa 2
Espaço
Tempo
p1
C1
d1
Instante
Entrega
Data de
Entrega
Avanço
Tarefa
E1 = Max{d1-C1, 0}
Semana 05
Componentes do problema
Atraso da tarefa T2
Máquina
Tarefa 1
Tarefa 2
Espaço
Tempo
p1
C2
d2
Instante
Entrega
Data de
Entrega
Atraso
Tarefa
T2 = Max{C1-d1, 0}
p2
Semana 05
Componentes do problema
Lateness L2
Máquina
Tarefa 1
Tarefa 2
Espaço
Tempo
p1
C2
d2
Instante
Entrega
Data de
Entrega
Atraso
Tarefa
L2 = Lateness = C2-d2
p2
Semana 05
Variáveis do problema
A tarefa i sucede a tarefa j: xij = 1
Máquina
Tarefa 1
Tarefa 2
Espaço
Tempo
p1
p2
X12 = 1
X12 = 1
Sequenciamento - Modelo 1
Minimizar soma de instante de entrega
Restrições tarefa anterior e posterior
Qual a próxima tarefa j?
Qual a tarefa i anterior?
Sequenciamento - Modelo 1
Minimizar soma de instante de entrega
Cuidado com a tarefa fictícia!
Qual a próxima tarefa j?
Qual a tarefa i anterior?
Tarefa fictícia 0 inicial e final
Sequenciamento - Modelo 1
Minimizar soma de instante de entrega
Restrição para cálculo de tempo de entrega
Qual a próxima tarefa j?
Qual a tarefa i anterior?
Cálculo de
instante de entrega!
Tarefa fictícia 0 inicial e final
Sequenciamento - Modelo 1
Minimizar soma de instante de entrega
Modelo Completo!
Qual a próxima tarefa j?
Qual a tarefa i anterior?
Cálculo de
instante de entrega!
Minimizar soma instante entrega
Tarefa fictícia 0 inicial e final
Sequenciamento - Modelo 2
Minimizar atraso máximo
Restrições de cálculo do atraso máximo
Atraso máximo e da tarefa i
Sequenciamento - Modelo 2
Minimizar atraso máximo
Função objetivo Tmax
Atraso máximo e da tarefa i
Minimizar atraso máximo
| Instante Entrega (Ci) | Atraso (Ti) | Avanço (Ei) | Lateness (Li) |
Soma | | | | |
Min-Max | | | | |
Número | | | | |
Sequenciamento - Modelos
Várias funções objetivo
Afetam quais restrições considerar
Makespan
| Instante Entrega (Ci) | Atraso (Ti) | Avanço (Ei) | Lateness (Li) |
Soma | | | | |
Min-Max | | | | |
Número | | | | |
Sequenciamento - Modelos
Várias funções objetivo
Afetam quais restrições considerar
Makespan
Sequenciamento - Heurísticas
Regras para sequenciar as tarefas
Sequenciar e avaliar as funções objetivos
Tarefa | Processamento Pi | Instante Término | Soma Ci |
1 | 3 | | |
2 | 6 | | |
3 | 4 | | |
Sequenciamento - Heurísticas
Regras para sequenciar as tarefas
Sequenciar e avaliar as funções objetivos
Espaço
Tempo
p1 = 3
p2 = 6
p3 = 4
Ordem|ΣC=25|Tmax=3
p1 = 3
p2 = 6
p3 = 4
p1 = 3
p2 = 6
p3 = 4
SPT|ΣC=23
EDD|Tmax=0
Data de entrega: 13, 6, 10
Sequenciamento - Setup
Dependente da sequência ou não
Usar matriz para dependente
Independente da Sequência
Pode agrupar!
Sequenciamento - Setup
Dependente da sequência ou não
Usar matriz para dependente
Independente da Sequência
Dependente da Sequência
Pode agrupar!
Ordem importa!
Sequenciamento - Setup
Dependente da sequência ou não
Usar matriz para dependente
Tarefa | 1 | 2 | 3 |
1 | 0 | 1 | 3 |
2 | 2 | 0 | 2 |
3 | 1 | 3 | 0 |
Dependente da Sequência
Ordem importa!
Sequenciamento - Setup
Dependente da sequência ou não
Usar matriz para dependente
Tarefa | 1 | 2 | 3 |
1 | 0 | 1 | 3 |
2 | 2 | 0 | 2 |
3 | 1 | 3 | 0 |
p12 = 1
Sequenciamento - Setup
Dependente da sequência ou não
Usar matriz para dependente
Tarefa | 1 | 2 | 3 |
1 | 0 | 1 | 3 |
2 | 2 | 0 | 2 |
3 | 1 | 3 | 0 |
p12 = 1
p21 = 2
Múltiplas máquinas
Várias formulações possíveis
Idênticas | Uniformes | Não-relacionadas
Próxima aula…
Práticas com Google Colab