Pesquisa Operacional 2
Semana 05 - Aula 02
Prof. Anibal Tavares de Azevedo
Tema da Semana
Sequenciamento de Tarefas - Python
Semana 05
Gráfico de Gantt - Simulação simplificada
Espaço & Tempo em um plano cartesiano
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
Dados para o Modelo 1
Minimizar soma de instante de entrega
Link:
https://colab.research.google.com/drive/13Q__YcBltpUq1GZqbz3UWokufkL2ToIR?usp=sharing
Dados para o Modelo 1
Minimizar soma de instante de entrega
Link:
https://colab.research.google.com/drive/13Q__YcBltpUq1GZqbz3UWokufkL2ToIR?usp=sharing
Dados para o Modelo 1 - CMAX
Minimizar Máximo instante Entrega - Cmax
Link:
https://colab.research.google.com/drive/13Q__YcBltpUq1GZqbz3UWokufkL2ToIR?usp=sharing
Dados para o Modelo 1 - CMAX
Minimizar Máximo instante Entrega - Cmax
Link:
https://colab.research.google.com/drive/13Q__YcBltpUq1GZqbz3UWokufkL2ToIR?usp=sharing
Dados para o Modelo 1 - CMAX
Minimizar Máximo instante Entrega - Cmax
Link:
https://colab.research.google.com/drive/13Q__YcBltpUq1GZqbz3UWokufkL2ToIR?usp=sharing
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
Dados para o Modelo 2
Minimizar atraso máximo Tmax
Link:
https://colab.research.google.com/drive/13Q__YcBltpUq1GZqbz3UWokufkL2ToIR?usp=sharing
Dados para o Modelo 2
Minimizar atraso máximo Tmax
Link:
https://colab.research.google.com/drive/13Q__YcBltpUq1GZqbz3UWokufkL2ToIR?usp=sharing
Dados para o Modelo 2
Minimizar atraso máximo Tmax
Link:
https://colab.research.google.com/drive/13Q__YcBltpUq1GZqbz3UWokufkL2ToIR?usp=sharing
Dados para o Modelo 2 - # T
Minimizar # tarefas atrasadas
Link:
https://colab.research.google.com/drive/13Q__YcBltpUq1GZqbz3UWokufkL2ToIR?usp=sharing
| 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
Aplicações reais
Uso de regras para solução
Alocação empilhadeiras em CD
https://proceedings.sbmac.org.br/sbmac/article/view/2030
Aplicações reais
Uso de Simulação + Otimização
Operação de Layer picker
https://www.youtube.com/watch?v=GTQBKSmDukY&feature=youtu.be
Próxima Semana…
Problemas de Corte e Empacotamento