8/19/2019 3 - Apresentacao Oficina Corte 2015
1/70
IMECC - UNICAMP
Métodos de Soma Ponderada e ε−Restrito no
Problema do Corte Unidimensional Bi-objetivo
Angelo Aliano
Antonio Moretti
UNICAMP
11 de junho de 2015
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 1 / 35
8/19/2019 3 - Apresentacao Oficina Corte 2015
2/70
IMECC - UNICAMP
Sumário
1 Definição e motivação
2 Modelo matemático
3 Métodos de soluçãoε−RestritoSoma Ponderada
4
Resultados preliminares
5 Conclusões preliminares
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 2 / 35
8/19/2019 3 - Apresentacao Oficina Corte 2015
3/70
IMECC - UNICAMP
Definição e motivação
Definição do problema e motivação
1 O PCUI é um dos problemas mais estudados dentro da
otimização combinatória, devido a sua vasta aplicabilidade em
indústrias que cortam diversos materiais
2 Problema mono-objetivo: cortar, de um rolo mestre maior, itensmenores de modo a atender à demanda e minimizar o
desperdı́cio ou o número de peças cortadas
3 Este problema é N P -difı́cil
4 Além disso, sua formulação envolve um número muito grande devariáveis inteiras, mesmo para pequenas instâncias
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 3 / 35
8/19/2019 3 - Apresentacao Oficina Corte 2015
4/70
IMECC - UNICAMP
Definição e motivação
Definição do problema e motivação
1 O PCUI é um dos problemas mais estudados dentro da
otimização combinatória, devido a sua vasta aplicabilidade em
indústrias que cortam diversos materiais
2 Problema mono-objetivo: cortar, de um rolo mestre maior, itensmenores de modo a atender à demanda e minimizar o
desperdı́cio ou o número de peças cortadas
3 Este problema é N P -difı́cil
4 Além disso, sua formulação envolve um número muito grande devariáveis inteiras, mesmo para pequenas instâncias
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 3 / 35
8/19/2019 3 - Apresentacao Oficina Corte 2015
5/70
IMECC - UNICAMP
Definição e motivação
Definição do problema e motivação
1 O PCUI é um dos problemas mais estudados dentro da
otimização combinatória, devido a sua vasta aplicabilidade em
indústrias que cortam diversos materiais
2 Problema mono-objetivo: cortar, de um rolo mestre maior, itensmenores de modo a atender à demanda e minimizar o
desperdı́cio ou o número de peças cortadas
3 Este problema é N P -difı́cil
4 Além disso, sua formulação envolve um número muito grande devariáveis inteiras, mesmo para pequenas instâncias
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 3 / 35
8/19/2019 3 - Apresentacao Oficina Corte 2015
6/70
IMECC - UNICAMP
Definição e motivação
Definição do problema e motivação
1 O PCUI é um dos problemas mais estudados dentro da
otimização combinatória, devido a sua vasta aplicabilidade em
indústrias que cortam diversos materiais
2 Problema mono-objetivo: cortar, de um rolo mestre maior, itensmenores de modo a atender à demanda e minimizar o
desperdı́cio ou o número de peças cortadas
3 Este problema é N P -difı́cil
4 Além disso, sua formulação envolve um número muito grande devariáveis inteiras, mesmo para pequenas instâncias
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 3 / 35
8/19/2019 3 - Apresentacao Oficina Corte 2015
7/70
IMECC - UNICAMP
Definição e motivação
Definição do problema e motivação
Abordagem bi-objetiva:
1 Considerar outro objetivo a ser concomitantemente minimizado: o
setup2 Esse objetivo é conflitante com o primeiro, i.e., sua minimização
acarreta a piora do outro, e vice-e-versa
3 Ambos possuem igual importância para o problema
4
A quest˜ao
´e estabelecer um trade off entre esses objetivos
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 4 / 35
D fi i ˜ i ˜
8/19/2019 3 - Apresentacao Oficina Corte 2015
8/70
IMECC - UNICAMP
Definição e motivação
Definição do problema e motivação
Abordagem bi-objetiva:
1 Considerar outro objetivo a ser concomitantemente minimizado: o
setup2 Esse objetivo é conflitante com o primeiro, i.e., sua minimização
acarreta a piora do outro, e vice-e-versa
3 Ambos possuem igual importância para o problema
4
A quest˜ao
´e estabelecer um trade off entre esses objetivos
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 4 / 35
D fi i ˜ ti ˜
8/19/2019 3 - Apresentacao Oficina Corte 2015
9/70
IMECC - UNICAMP
Definiçao e motivaçao
Definição do problema e motivação
Abordagem bi-objetiva:
1 Considerar outro objetivo a ser concomitantemente minimizado: o
setup2 Esse objetivo é conflitante com o primeiro, i.e., sua minimização
acarreta a piora do outro, e vice-e-versa
3 Ambos possuem igual importância para o problema
4 A questão é estabelecer um trade off entre esses objetivos
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 4 / 35
Definicão e motivacão
8/19/2019 3 - Apresentacao Oficina Corte 2015
10/70
IMECC - UNICAMP
Definiçao e motivaçao
Definição do problema e motivação
Abordagem bi-objetiva:
1 Considerar outro objetivo a ser concomitantemente minimizado: o
setup2 Esse objetivo é conflitante com o primeiro, i.e., sua minimização
acarreta a piora do outro, e vice-e-versa
3 Ambos possuem igual importância para o problema
4 A questão é estabelecer um trade off entre esses objetivos
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 4 / 35
Definicão e motivacão
8/19/2019 3 - Apresentacao Oficina Corte 2015
11/70
IMECC - UNICAMP
Definiçao e motivaçao
Definição do problema e motivação
L
j = 2
j = 1
i = 1
i = 1
i = 2
i = 3
i = 1
i = 1
i = 3
i = 4
i = 2
i = 3
a1 = (3, 1, 1, 0)T
a2 = (1, 1, 2, 1)T
rolo mestre
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 5 / 35
Modelo matemático
8/19/2019 3 - Apresentacao Oficina Corte 2015
12/70
IMECC - UNICAMP
Modelo matematico
Modelo matemático
Sejam os seguintes parâmetros
b : número de rolos mestres disponı́vel
Lk : largura do rolo mestre k = 1, ..., b
m : número de itens demandados
l i
8/19/2019 3 - Apresentacao Oficina Corte 2015
13/70
IMECC - UNICAMP
Modelo matematico
Modelo matemático
Definição: padrão de corte factı́vel
Um padrão de corte factı́vel a jk ∈ Nm é factı́vel se satisfaz as
seguintes condições:
m
i =1
l i ·
a ij ≤
Lk ,
(1)
m i =1
l i · a ij ≥ Lk − ∆, (2)
m i =1
a ij ≤ F , (3)
onde ∆ = min1≤i ≤m
{l i } e F o no de facas máximo permitido por padrão
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 7 / 35
Modelo matemático
8/19/2019 3 - Apresentacao Oficina Corte 2015
14/70
IMECC - UNICAMP
Modelo matematico
Modelo matemático
Variáveis
x jk : frequência do padrão de corte j retirado da bobina mestre k , j = 1, ..., p e k = 1, ..., b
y jk =
1, se x jk > 00, caso contrário
para j = 1, ..., p e k = 1, ..., b
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 8 / 35
Modelo matemático
8/19/2019 3 - Apresentacao Oficina Corte 2015
15/70
IMECC - UNICAMP
Modelo matemático
O modelo inteiro para o PCUIB é apresentado a seguir:
Minimize z 1 =b
k =1
p
j =1
x jk
Minimize z 2 =
b
k =1
p
j =1
y jk
sujeito a
b
k =1
p
j =1
a ijk · x jk ≥ d i , i = 1, ...,m ,
x jk ≤ N · y jk , j = 1, ...,p , k = 1, ..., b ,
x jk ≥ y jk , j = 1, ...,p , k = 1, ..., b ,y jk ∈ B, x jk ∈ N, j = 1, ...,p , k = 1, ..., b ,
(4)
onde N é um limitante superior para x jk
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 9 / 35
Modelo matemático
8/19/2019 3 - Apresentacao Oficina Corte 2015
16/70
IMECC - UNICAMP
Modelo matemático
O modelo anterior têm vários fatores complicadores:
1 Se a jk não for fornecido a priori , o problema é não-linear
2
Se a jk é fornecido, não há garantia de se obter a fronteira dePareto ótima global
3 Sua versão linear (fornecendo os padrões a jk ) possui uma
relaxação linear muito fraca
4 Bi-dimensionalidade da função objetivo
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 10 / 35
Modelo matemático
8/19/2019 3 - Apresentacao Oficina Corte 2015
17/70
IMECC - UNICAMP
Modelo matemático
O modelo anterior têm vários fatores complicadores:
1 Se a jk não for fornecido a priori , o problema é não-linear
2
Se a jk é fornecido, não há garantia de se obter a fronteira dePareto ótima global
3 Sua versão linear (fornecendo os padrões a jk ) possui uma
relaxação linear muito fraca
4 Bi-dimensionalidade da função objetivo
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 10 / 35
Modelo matemático
8/19/2019 3 - Apresentacao Oficina Corte 2015
18/70
IMECC - UNICAMP
Modelo matemático
O modelo anterior têm vários fatores complicadores:
1 Se a jk não for fornecido a priori , o problema é não-linear
2
Se a jk é fornecido, não há garantia de se obter a fronteira dePareto ótima global
3 Sua versão linear (fornecendo os padrões a jk ) possui uma
relaxação linear muito fraca
4 Bi-dimensionalidade da função objetivo
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 10 / 35
Modelo matemático
8/19/2019 3 - Apresentacao Oficina Corte 2015
19/70
IMECC - UNICAMP
Modelo matemático
O modelo anterior têm vários fatores complicadores:
1 Se a jk não for fornecido a priori , o problema é não-linear
2
Se a jk é fornecido, não há garantia de se obter a fronteira dePareto ótima global
3 Sua versão linear (fornecendo os padrões a jk ) possui uma
relaxação linear muito fraca
4 Bi-dimensionalidade da função objetivo
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 10 / 35
Métodos de solução
8/19/2019 3 - Apresentacao Oficina Corte 2015
20/70
IMECC - UNICAMP
Definição do problema e motivação
1 Fornecer os p padrões de Gilmore-Gomory para a formulação (4)
2 Obtemos, assim, uma versão linear para o mesmo3 Duas abordagens distintas foram utilizadas e comparadas:
Utilizar x jk inteiro: obtenção de uma fronteira de Pareto Z ∗
Relaxar as condições de integralidade destas. Sucessivamentefazer o arredondamento de cada solução eficiente, obtendo-seuma fronteira heurı́stica Z̄
4 Utilizar e comparar como técnicas de escalarização Soma
Ponderada (SP) e ε−Restrito (ε−R) em cada abordagem
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 11 / 35
Métodos de solução
8/19/2019 3 - Apresentacao Oficina Corte 2015
21/70
IMECC - UNICAMP
Definição do problema e motivação
1 Fornecer os p padrões de Gilmore-Gomory para a formulação (4)
2 Obtemos, assim, uma versão linear para o mesmo3 Duas abordagens distintas foram utilizadas e comparadas:
Utilizar x jk inteiro: obtenção de uma fronteira de Pareto Z ∗
Relaxar as condições de integralidade destas. Sucessivamentefazer o arredondamento de cada solução eficiente, obtendo-seuma fronteira heurı́stica Z̄
4 Utilizar e comparar como técnicas de escalarização Soma
Ponderada (SP) e ε−Restrito (ε−R) em cada abordagem
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 11 / 35
Métodos de solução
8/19/2019 3 - Apresentacao Oficina Corte 2015
22/70
IMECC - UNICAMP
Definição do problema e motivação
1 Fornecer os p padrões de Gilmore-Gomory para a formulação (4)
2 Obtemos, assim, uma versão linear para o mesmo3 Duas abordagens distintas foram utilizadas e comparadas:
Utilizar x jk inteiro: obtenção de uma fronteira de Pareto Z ∗
Relaxar as condições de integralidade destas. Sucessivamentefazer o arredondamento de cada solução eficiente, obtendo-seuma fronteira heurı́stica Z̄
4 Utilizar e comparar como técnicas de escalarização Soma
Ponderada (SP) e ε−Restrito (ε−R) em cada abordagem
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 11 / 35
Métodos de solução
8/19/2019 3 - Apresentacao Oficina Corte 2015
23/70
IMECC - UNICAMP
Definição do problema e motivação
1 Fornecer os p padrões de Gilmore-Gomory para a formulação (4)
2 Obtemos, assim, uma versão linear para o mesmo3 Duas abordagens distintas foram utilizadas e comparadas:
Utilizar x jk inteiro: obtenção de uma fronteira de Pareto Z ∗
Relaxar as condições de integralidade destas. Sucessivamentefazer o arredondamento de cada solução eficiente, obtendo-seuma fronteira heurı́stica Z̄
4 Utilizar e comparar como técnicas de escalarização Soma
Ponderada (SP) e ε−Restrito (ε−R) em cada abordagem
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 11 / 35
Métodos de solução
8/19/2019 3 - Apresentacao Oficina Corte 2015
24/70
IMECC - UNICAMP
Definição do problema e motivação
1 Fornecer os p padrões de Gilmore-Gomory para a formulação (4)
2 Obtemos, assim, uma versão linear para o mesmo3 Duas abordagens distintas foram utilizadas e comparadas:
Utilizar x jk inteiro: obtenção de uma fronteira de Pareto Z ∗
Relaxar as condições de integralidade destas. Sucessivamentefazer o arredondamento de cada solução eficiente, obtendo-seuma fronteira heurı́stica Z̄
4 Utilizar e comparar como técnicas de escalarização Soma
Ponderada (SP) e ε−Restrito (ε−R) em cada abordagem
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 11 / 35
Métodos de solução
8/19/2019 3 - Apresentacao Oficina Corte 2015
25/70
IMECC - UNICAMP
Definição do problema e motivação
1 Fornecer os p padrões de Gilmore-Gomory para a formulação (4)
2 Obtemos, assim, uma versão linear para o mesmo3 Duas abordagens distintas foram utilizadas e comparadas:
Utilizar x jk inteiro: obtenção de uma fronteira de Pareto Z ∗
Relaxar as condições de integralidade destas. Sucessivamentefazer o arredondamento de cada solução eficiente, obtendo-seuma fronteira heurı́stica Z̄
4 Utilizar e comparar como técnicas de escalarização Soma
Ponderada (SP) e ε−Restrito (ε−R) em cada abordagem
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 11 / 35
Métodos de solução ε−Restrito
8/19/2019 3 - Apresentacao Oficina Corte 2015
26/70
IMECC - UNICAMP
Método do ε−Restrito
1 Adotamos como função objetivo z 1 para o problema escalar P ε e
z 2 como restrição, pois a amplitude de variação desta função é
muito menor se comparada com z 12 Então P ε com a imposição de um setup de até ε é definido a
seguir, onde ρ > 0
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 12 / 35
Métodos de solução ε−Restrito
8/19/2019 3 - Apresentacao Oficina Corte 2015
27/70
IMECC - UNICAMP
Método do ε−Restrito
1 Adotamos como função objetivo z 1 para o problema escalar P ε e
z 2 como restrição, pois a amplitude de variação desta função é
muito menor se comparada com z 12 Então P ε com a imposição de um setup de até ε é definido a
seguir, onde ρ > 0
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 12 / 35
Métodos de solução ε−Restrito
8/19/2019 3 - Apresentacao Oficina Corte 2015
28/70
IMECC - UNICAMP
Método do ε−Restrito
P ε
Minimize z ε =b
k =1
p
j =1
x jk + ρ ·b
k =1
p
j =1
y jk
sujeito a
b
k =1
p
j =1
a ∗ijk ·
x jk ≥
d i , i
= 1, ...,m ,
x jk ≤ N · y jk , j = 1, ...,p , k = 1, ...,b ,x jk ≥ y jk , j = 1, ...,p , k = 1, ...,b ,
p
j =1
b
j =1
y jk ≤ ε,
y jk ∈ B, x jk ∈ Z+, j = 1, ...,p , k = 1, ...,b .
onde a ∗ jk são fornecidos pelo método de GG. Agora vamos definir um intervalo para ε
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 13 / 35
Métodos de solução ε−Restrito
8/19/2019 3 - Apresentacao Oficina Corte 2015
29/70
IMECC - UNICAMP
Método do ε−Restrito
É razoável considerar os valores inteiros de ε variando no intervalo I = [z −2 , z
+2 ], onde z
−2
é obtido resolvendo-se
P −ε
Minimize z ε =b
k =1
p
j =1
y jk + ρ ·b
k =1
p
j =1
x jk
sujeito a
b
k =1
p
j =1
a ∗ijk · x jk ≥ d i , i = 1, ...,m ,
x jk ≤ N · y jk , j = 1, ...,p , k = 1, ...,b ,x jk ≥ y jk , j = 1, ...,p , k = 1, ...,b ,y
jk ∈ B, x
jk ∈ Z
+, j
= 1, ...,p , k
= 1, ...,b ,
e calculando-se o setup da solução resultante.
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 14 / 35
Métodos de solução ε−Restrito
8/19/2019 3 - Apresentacao Oficina Corte 2015
30/70
IMECC - UNICAMP
Método do ε−Restrito
É razoável considerar os valores inteiros de ε variando no intervalo I = [z −2 , z
+2 ], onde z
−2
é obtido resolvendo-se
P −ε
Minimize z ε =b
k =1
p
j =1
y jk + ρ ·b
k =1
p
j =1
x jk
sujeito a
b
k =1
p
j =1
a ∗ijk · x jk ≥ d i , i = 1, ...,m ,
x jk ≤ N · y jk , j = 1, ...,p , k = 1, ...,b ,x jk ≥ y jk , j = 1, ...,p , k = 1, ...,b ,y
jk ∈ B, x
jk ∈ Z
+, j = 1, ...,p , k = 1, ...,b ,
e calculando-se o setup da solução resultante.
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 14 / 35
Métodos de solução ε−Restrito
8/19/2019 3 - Apresentacao Oficina Corte 2015
31/70
IMECC - UNICAMP
Método do ε−Restrito
Analogamente, z +2 é obtido resolvendo-se
P +ε
Minimize z ε =b
k =1
p
j =1
x jk + ρ ·b
k =1
p
j =1
y jk
sujeito ab
k =1
p
j =1
a ∗ijk · x jk ≥ d i , i = 1, ...,m ,
x jk ≤ N · y jk , j = 1, ...,p , k = 1, ..., b ,x jk ≥ y jk , j = 1, ...,p , k = 1, ..., b ,y jk ∈ B, x jk ∈ Z+, j = 1, ...,p , k = 1, ..., b ,
e calculando-se o setup da solução resultante
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 15 / 35
Métodos de solução ε−Restrito
8/19/2019 3 - Apresentacao Oficina Corte 2015
32/70
IMECC - UNICAMP
Método do ε−Restrito
Analogamente, z +2 é obtido resolvendo-se
P +ε
Minimize z ε =b
k =1
p
j =1
x jk + ρ ·b
k =1
p
j =1
y jk
sujeito ab
k =1
p
j =1
a ∗ijk · x jk ≥ d i , i = 1, ...,m ,
x jk ≤ N · y jk , j = 1, ...,p , k = 1, ..., b ,x jk ≥ y jk , j = 1, ...,p , k = 1, ..., b ,y jk ∈ B, x jk ∈ Z+, j = 1, ...,p , k = 1, ..., b ,
e calculando-se o setup da solução resultante
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 15 / 35
Métodos de solução ε−Restrito
´
8/19/2019 3 - Apresentacao Oficina Corte 2015
33/70
IMECC - UNICAMP
Método do ε−Restrito
Algorithm 1 ε− Restrito para o Problema do Corte Bi-objetivo1: Entrada: dados do problema do corte e ∆2: X ∗ = {x 1, x 2}3: Z ∗ = {(z −1 , z
+2 )
T , (z +1 , z −2 )
T }4: ε = z −2 + ∆5: while ε ≤ z +2 − ∆ do6: Resolva o problema P ε7: Seja x ε a solução ótima de PR ε8: X ∗ = X ∗ ∪ {x ε}9: Z ∗ = Z ∗ ∪ {((z ε1 , z
ε2 )
T }10: ε
← ε + ∆
11: end while12: Saı́da: X ∗ e Z ∗
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 16 / 35
Métodos de solução Soma Ponderada
M ´ d d S P d d
8/19/2019 3 - Apresentacao Oficina Corte 2015
34/70
IMECC - UNICAMP
Método da Soma Ponderada
Primeiramente, utilizando-se os pontos lexicográficos, normaliza-se osobjetivos e considera-se o problema ponderado (P w ) no pesow =]0, 1[ a seguir:
P w
Minimize z w = w · β 1 ·b
k =1
p
j =1
x jk +
+(1 − w ) · β 2 ·b
k =1
p
j =1
y jk
sujeito a
b
k =1
p
j =1
a ∗ijk · x jk ≥ d i , i = 1, ...,m ,
x jk ≤ N · y jk , j = 1, ...,p , k = 1, ..., b ,x jk ≥ y jk , j = 1, ...,p , k = 1, ..., b ,y jk ∈ B, x jk ∈ Z+, j = 1, ...,p , k = 1, ..., b ,
onde β 1 e β 2 são constantes que normalizam z 1 e z 2
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 17 / 35
Métodos de solução Soma Ponderada
M ´ t d d S P d d
8/19/2019 3 - Apresentacao Oficina Corte 2015
35/70
IMECC - UNICAMP
Método da Soma Ponderada
Primeiramente, utilizando-se os pontos lexicográficos, normaliza-se osobjetivos e considera-se o problema ponderado (P w ) no pesow =]0, 1[ a seguir:
P w
Minimize z w = w · β 1 ·b
k =1
p
j =1
x jk +
+(1 − w ) · β 2 ·b
k =1
p
j =1
y jk
sujeito a
b
k =1
p
j =1
a ∗ijk · x jk ≥ d i , i = 1, ...,m ,
x jk ≤ N · y jk , j = 1, ...,p , k = 1, ..., b ,x jk ≥ y jk , j = 1, ...,p , k = 1, ..., b ,y jk ∈ B, x jk ∈ Z+, j = 1, ...,p , k = 1, ..., b ,
onde β 1 e β 2 são constantes que normalizam z 1 e z 2
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 17 / 35
Métodos de solução Soma Ponderada
M ´ t d d S P d d
8/19/2019 3 - Apresentacao Oficina Corte 2015
36/70
IMECC - UNICAMP
Metodo da Soma Ponderada
Algorithm 2 Soma Ponderada para o Problema do Corte Bi-objetivo1: Entrada: dados do problema do corte ∆2: X̃ = {x 1, x 2}3: Z̃ = {(z −1 , z
+2 )
T , (z +1 , z −2 )
T }4: Normalize os objetivos z 1 e z 2
5: w = ∆6: while w ≤ 1 − ∆ do7: Resolva o problema P w 8: Seja x w a solução ótima de (P w )
9: X̃ = X̃ ∪ {x w }10: Z̃ = Z̃ ∪ {(z w 1 , z
w 2 )
T }
11: w ← w + ∆12: end while
13: Saı́da: X̃ e Z̃
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 18 / 35
Métodos de solução Soma Ponderada
Ab d d d d t
8/19/2019 3 - Apresentacao Oficina Corte 2015
37/70
IMECC - UNICAMP
Abordagem de arredondamento
Idéia: obter uma fronteira de Pareto heurı́stica, Z̄ ≈ Z ∗, demaneira mais acelerada
Nesta segunda abordagem, em vez de resolver os sub-problemas P εe P w considerando-se x jk inteiro, relaxamos esta condição e
posteriormente arredondamos cada solução eficiente utilizando-se a
heurı́stica melhorativa a seguir
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 19 / 35
Métodos de solução Soma Ponderada
Abordagem de arredondamento
8/19/2019 3 - Apresentacao Oficina Corte 2015
38/70
IMECC - UNICAMP
Abordagem de arredondamento
Idéia: obter uma fronteira de Pareto heurı́stica, Z̄ ≈ Z ∗, demaneira mais acelerada
Nesta segunda abordagem, em vez de resolver os sub-problemas P εe P w considerando-se x jk inteiro, relaxamos esta condição e
posteriormente arredondamos cada solução eficiente utilizando-se a
heurı́stica melhorativa a seguir
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 19 / 35
Métodos de solução Soma Ponderada
Abordagem de arredondamento
8/19/2019 3 - Apresentacao Oficina Corte 2015
39/70
IMECC - UNICAMP
Abordagem de arredondamento
Idéia: obter uma fronteira de Pareto heurı́stica, Z̄ ≈ Z ∗, demaneira mais acelerada
Nesta segunda abordagem, em vez de resolver os sub-problemas P εe P w considerando-se x jk inteiro, relaxamos esta condição e
posteriormente arredondamos cada solução eficiente utilizando-se a
heurı́stica melhorativa a seguir
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 19 / 35
Métodos de solução Soma Ponderada
Arredondamento com melhoramento gradual
8/19/2019 3 - Apresentacao Oficina Corte 2015
40/70
IMECC - UNICAMP
Arredondamento com melhoramento gradual
Algorithm 3 Arredondamento com melhoramento gradual
1: Entrada: x̃ , A∗, d e v j = {i : A∗ij > 0} para todo j = 1, ..., m
2: x̄ ← x̃ 3: r = A∗x̄ − d 4: while r ≥ 0 do5: for j = 1, ...,m do
6: if x j > 0 then7: x̄ j ← x̄ j − 18: r j = r j − A
∗ j para todo j ∈ v j
9: if r j
8/19/2019 3 - Apresentacao Oficina Corte 2015
41/70
IMECC - UNICAMP
Problemas testes
Simulações realizadas num core i3 Quad com 4GB de memória,
usando o CPLEX 12.6 para resolver os sub-problemas
1
Nestes experimentos foram geradas 18 classes2 Cada classe, 40 problemas testes
3 Para problema e para cada método, foram obtidas duas fronteiras
de Pareto e as comparamos entre si
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 21 / 35
Resultados preliminares
Problemas testes
8/19/2019 3 - Apresentacao Oficina Corte 2015
42/70
IMECC - UNICAMP
Problemas testes
As 18 classes contemplam combinações entre itens pequenos,
médios e grandes, quantidade de itens e bobinas mestres
Os valores para l i foram gerados entre [v 1L̄, v 2L̄], ondeLk = [300, 2000] foi aleatoriamente gerado e L̄ é a média de Lk
Além disso, a demanda d i = [100, 2000] aleatoriamente gerada
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 22 / 35
Resultados preliminares
Problemas teste
8/19/2019 3 - Apresentacao Oficina Corte 2015
43/70
IMECC - UNICAMP
Problemas teste
As classes estão dispostas a seguir
Table: Classes para o PCUIB
Classe m Tipo do item b
1 20 P 12 20 P 33 20 P 5
4 20 M 15 20 M 36 20 M 57 20 G 18 20 G 39 20 G 5
10 40 P 111 40 P 312 40 P 5
13 40 M 114 40 M 315 40 M 516 40 G 117 40 G 318 40 G 5
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 23 / 35
Resultados preliminares
Resultados preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
44/70
IMECC - UNICAMP
Resultados preliminares
Calculamos, tanto para Z ∗, quanto para Z :
t ε−R e t SP denotam os tempos computacionais (em segundos)
demandados
|Z ε−R | e |Z SP | o número de soluções não-dominadasencontradas por cada método
A∗ε−R e A
∗SP as áreas delimitadas pelas fronteiras de Pareto
(×10−4)
αSP
e αε−R proporção de soluções não-dominadas não
coincidentes entre as duas fronteiras
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 24 / 35
Resultados preliminares
Resultados preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
45/70
IMECC - UNICAMP
Resultados preliminares
Calculamos, tanto para Z ∗, quanto para Z :
t ε−R e t SP denotam os tempos computacionais (em segundos)
demandados
|Z ε−R | e |Z SP | o número de soluções não-dominadasencontradas por cada método
A∗ε−R e A
∗SP as áreas delimitadas pelas fronteiras de Pareto
(×10−4)
αSP e αε−R proporção de soluções não-dominadas nãocoincidentes entre as duas fronteiras
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 24 / 35
Resultados preliminares
Resultados preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
46/70
IMECC - UNICAMP
Resultados preliminares
Calculamos, tanto para Z ∗, quanto para Z :
t ε−R e t SP denotam os tempos computacionais (em segundos)
demandados
|Z ε−R | e |Z SP | o número de soluções não-dominadasencontradas por cada método
A∗ε−R e A
∗SP as áreas delimitadas pelas fronteiras de Pareto
(×10−4)
αSP e αε−R proporção de soluções não-dominadas nãocoincidentes entre as duas fronteiras
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 24 / 35
Resultados preliminares
Resultados preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
47/70
IMECC - UNICAMP
Resultados preliminares
Calculamos, tanto para Z ∗, quanto para Z :
t ε−R e t SP denotam os tempos computacionais (em segundos)
demandados
|Z ε−R | e |Z SP | o número de soluções não-dominadasencontradas por cada método
A∗ε−R e A
∗SP as áreas delimitadas pelas fronteiras de Pareto
(×10−4)
αSP e αε−R proporção de soluções não-dominadas nãocoincidentes entre as duas fronteiras
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 24 / 35
Resultados preliminares
Resultados preliminares para Z∗
8/19/2019 3 - Apresentacao Oficina Corte 2015
48/70
IMECC - UNICAMP
Resultados preliminares para Z
Table: Resultados computacionais médios do ε−R e SP no PCUIM para afronteira Z ∗
Classe t ∗ε−R t
∗
SP |Z ∗
ε−R | |Z ∗
SP | A∗
ε−R A∗
SP
1 0,92 0,82 10,70 6,80 1,21 0,802 1,04 0,84 10,30 6,20 1,08 0,593 1,13 1,00 10,70 6,60 1,45 0,884 0,32 0,27 6,70 4,45 0,33 0,185 0,55 0,50 8,05 5,50 0,47 0,30
6 1,08 0,53 7,70 5,15 0,47 0,247 0,15 0,16 5,10 3,35 0,06 0,088 0,34 0,32 7,75 5,50 0,13 0,249 0,33 0,30 6,80 4,60 0,34 0,15
Média 0,59 0,52 8,21 5,35 0,63 0,3910 6,46 3,83 18,30 10,15 7,15 4,3411 7,25 3,36 18,80 9,65 7,89 4,2512 9,24 4,07 17,95 9,55 6,70 3,6813 4,50 2,57 14,80 7,75 3,29 1,74
14 6,28 3,28 16,85 8,65 4,41 2,4615 7,73 3,97 15,70 8,60 3,68 2,1416 0,91 0,70 11,75 7,05 1,58 0,9117 0,76 0,63 11,95 7,60 1,68 1,0718 3,18 2,15 15,40 8,40 3,02 1,68
Média 5,14 2,73 15,72 8,60 4,38 2,48
Média Geral 1,97 1,15 9,48 5,81 1,70 0,98
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 25 / 35
Resultados preliminares
Resultados preliminares para Z̄
8/19/2019 3 - Apresentacao Oficina Corte 2015
49/70
IMECC - UNICAMP
p p
Table: Resultados computacionais médios do ε−R e SP no PCUIM para afronteira Z̄
Classe ¯t ε−R
¯t SP | ¯Z ε−R | ¯|Z SP |
¯Aε−R
¯ASP 1 0,91 0,86 10,60 6,91 1,20 0,792 0,65 0,60 10,30 6,53 1,08 0,633 0,85 0,83 10,30 6,67 1,43 0,894 0,24 0,25 6,62 4,61 0,33 0,185 0,33 0,35 7,81 5,53 0,46 0,30
6 0,40 0,41 7,73 5,02 0,41 0,237 0,13 0,16 5,13 3,50 0,13 0,088 0,26 0,27 7,72 5,31 0,34 0,239 0,24 0,23 6,64 4,42 0,23 0,14
Média 0,45 0,44 8,12 5,42 0,62 0,39
10 5,59 3,22 18,01 10,11 7,03 4,2611 5,83 3,34 18,32 9,92 7,76 4,3712 6,43 3,40 17,24 9,83 6,57 3,7513 3,00 2,73 14,56 9,75 3,27 1,74
14 3,82 3,05 16,52 7,72 4,38 2,4615 4,43 3,49 15,21 8,70 3,61 2,1216 1,16 0,92 11,80 7,23 1,58 0,9317 0,90 0,72 11,92 7,64 1,67 1,0518 2,49 2,02 15,23 8,32 3,00 1,65
Média 3,74 2,54 15,42 8,6 4,32 2,47Média Geral 1,44 1,05 9,31 5,82 1,68 0,97
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 26 / 35
Resultados preliminares
Resultados preliminares para α
8/19/2019 3 - Apresentacao Oficina Corte 2015
50/70
IMECC - UNICAMP
p p
Table: Resultados computacionais médios para αClasse α
ε−R αSP 1 0,05 0,162 0,09 0,173 0,07 0,184 0,06 0,125 0,03 0,136 0,06 0,09
7 0,00 0,068 0,07 0,099 0,13 0,15
Média 0,09 0,1310 0,21 0,3011 0,15 0,2112 0,20 0,2713 0,15 0,1914 0,17 0,25
15 0,18 0,2016 0,04 0,0617 0,03 0,1218 0,17 0,2
Média 0,16 0,18
Média Geral 0,08 0,13
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 27 / 35
Resultados preliminares
Exemplo tı́pico de uma fronteira
8/19/2019 3 - Apresentacao Oficina Corte 2015
51/70
IMECC - UNICAMP
p p
1,000 1,200 1,400 1,600 1,80050
60
70
80
90
z 1
z 2
Z̃
Z ∗
Z̄
Figure: Ilustração das possı́veis fronteiras de Pareto para um problema-teste
com m = 100 itens
Para encontrar a fronteira Z ∗ foram necessários 93 segundos, ao passo que
para obter a fronteira Z̃ e fazer seu arredondamento foram necessários
apenas 37 segundos, isto é, quase 1/3 do tempo computacional
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 28 / 35
Resultados preliminares
Exemplo tı́pico de uma fronteira
8/19/2019 3 - Apresentacao Oficina Corte 2015
52/70
IMECC - UNICAMP
p p
1,000 1,200 1,400 1,600 1,80050
60
70
80
90
z 1
z 2
Z̃
Z ∗
Z̄
Figure: Ilustração das possı́veis fronteiras de Pareto para um problema-teste
com m = 100 itens
Para encontrar a fronteira Z ∗ foram necessários 93 segundos, ao passo que
para obter a fronteira Z̃ e fazer seu arredondamento foram necessários
apenas 37 segundos, isto é, quase 1/3 do tempo computacional
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 28 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
53/70
IMECC - UNICAMP
Algumas conclusões deste estudo:Vantagem de se utilizar o modelo parcialmente relaxado
Por um lado, perde-se 1,8% s (no ε−R) e 0,01% (na SP) dassoluções eficientes
A área média de Z̄ foi de 98,8% da área da fronteira ocupada porZ ∗
Por outro lado, economizou-se 27% do tempo computacional.
Essa diferença fica ainda maior para problemas com mais itens
Larga vantagem do ε−
R em relação à SP: esta conseguiu apenas
61,2% das soluções eficientes usando-se 58% do tempo
computacional
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 29 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
54/70
IMECC - UNICAMP
Algumas conclusões deste estudo:Vantagem de se utilizar o modelo parcialmente relaxado
Por um lado, perde-se 1,8% s (no ε−R) e 0,01% (na SP) dassoluções eficientes
A área média de Z̄ foi de 98,8% da área da fronteira ocupada porZ ∗
Por outro lado, economizou-se 27% do tempo computacional.
Essa diferença fica ainda maior para problemas com mais itens
Larga vantagem do ε−
R em relação à SP: esta conseguiu apenas
61,2% das soluções eficientes usando-se 58% do tempo
computacional
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 29 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
55/70
IMECC - UNICAMP
Algumas conclusões deste estudo:Vantagem de se utilizar o modelo parcialmente relaxado
Por um lado, perde-se 1,8% s (no ε−R) e 0,01% (na SP) dassoluções eficientes
A área média de Z̄ foi de 98,8% da área da fronteira ocupada porZ ∗
Por outro lado, economizou-se 27% do tempo computacional.
Essa diferença fica ainda maior para problemas com mais itens
Larga vantagem do ε−
R em relação à SP: esta conseguiu apenas
61,2% das soluções eficientes usando-se 58% do tempo
computacional
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 29 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
56/70
IMECC - UNICAMP
Algumas conclusões deste estudo:Vantagem de se utilizar o modelo parcialmente relaxado
Por um lado, perde-se 1,8% s (no ε−R) e 0,01% (na SP) dassoluções eficientes
A área média de Z̄ foi de 98,8% da área da fronteira ocupada porZ ∗
Por outro lado, economizou-se 27% do tempo computacional.
Essa diferença fica ainda maior para problemas com mais itens
Larga vantagem do ε−R em relação à SP: esta conseguiu apenas61,2% das soluções eficientes usando-se 58% do tempo
computacional
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 29 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
57/70
IMECC - UNICAMP
Algumas conclusões deste estudo:Vantagem de se utilizar o modelo parcialmente relaxado
Por um lado, perde-se 1,8% s (no ε−R) e 0,01% (na SP) dassoluções eficientes
A área média de Z̄ foi de 98,8% da área da fronteira ocupada porZ ∗
Por outro lado, economizou-se 27% do tempo computacional.
Essa diferença fica ainda maior para problemas com mais itens
Larga vantagem do ε−R em relação à SP: esta conseguiu apenas61,2% das soluções eficientes usando-se 58% do tempo
computacional
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 29 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
58/70
IMECC - UNICAMP
Algumas conclusões deste estudo:Vantagem de se utilizar o modelo parcialmente relaxado
Por um lado, perde-se 1,8% s (no ε−R) e 0,01% (na SP) dassoluções eficientes
A área média de Z̄ foi de 98,8% da área da fronteira ocupada porZ ∗
Por outro lado, economizou-se 27% do tempo computacional.
Essa diferença fica ainda maior para problemas com mais itens
Larga vantagem do ε−R em relação à SP: esta conseguiu apenas61,2% das soluções eficientes usando-se 58% do tempo
computacional
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 29 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
59/70
IMECC - UNICAMP
Direções imediatas de pesquisa:
Implementação de outras técnicas de escalarização: NISE,
Tchebycheff, Benson, etc...
Uso de outras heurı́sticas de arredondamento
Uso de um modelo não-linear (com uma possı́vel linearização)que implicitamente fornece os padrões de corte
Consideração de mais objetivos
Levar em conta o PCUIM com datas de entregas e considerar
múltiplos perı́odosAplicação em problemas de cortes bi-dimensionais
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 30 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
60/70
IMECC - UNICAMP
Direções imediatas de pesquisa:
Implementação de outras técnicas de escalarização: NISE,
Tchebycheff, Benson, etc...
Uso de outras heurı́sticas de arredondamento
Uso de um modelo não-linear (com uma possı́vel linearização)que implicitamente fornece os padrões de corte
Consideração de mais objetivos
Levar em conta o PCUIM com datas de entregas e considerar
múltiplos perı́odosAplicação em problemas de cortes bi-dimensionais
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 30 / 35
Conclus˜oes preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
61/70
IMECC - UNICAMP
Direções imediatas de pesquisa:Implementação de outras técnicas de escalarização: NISE,
Tchebycheff, Benson, etc...
Uso de outras heurı́sticas de arredondamento
Uso de um modelo não-linear (com uma possı́vel linearização)que implicitamente fornece os padrões de corte
Consideração de mais objetivos
Levar em conta o PCUIM com datas de entregas e considerar
múltiplos perı́odosAplicação em problemas de cortes bi-dimensionais
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 30 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
62/70
IMECC - UNICAMP
Direções imediatas de pesquisa:Implementação de outras técnicas de escalarização: NISE,
Tchebycheff, Benson, etc...
Uso de outras heurı́sticas de arredondamento
Uso de um modelo não-linear (com uma possı́vel linearização)que implicitamente fornece os padrões de corte
Consideração de mais objetivos
Levar em conta o PCUIM com datas de entregas e considerar
múltiplos perı́odosAplicação em problemas de cortes bi-dimensionais
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 30 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
63/70
IMECC - UNICAMP
Direções imediatas de pesquisa:Implementação de outras técnicas de escalarização: NISE,
Tchebycheff, Benson, etc...
Uso de outras heurı́sticas de arredondamento
Uso de um modelo não-linear (com uma possı́vel linearização)que implicitamente fornece os padrões de corte
Consideração de mais objetivos
Levar em conta o PCUIM com datas de entregas e considerar
múltiplos perı́odosAplicação em problemas de cortes bi-dimensionais
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 30 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
64/70
IMECC - UNICAMP
Direções imediatas de pesquisa:Implementação de outras técnicas de escalarização: NISE,
Tchebycheff, Benson, etc...
Uso de outras heurı́sticas de arredondamento
Uso de um modelo não-linear (com uma possı́vel linearização)que implicitamente fornece os padrões de corte
Consideração de mais objetivos
Levar em conta o PCUIM com datas de entregas e considerar
múltiplos perı́odosAplicação em problemas de cortes bi-dimensionais
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 30 / 35
Conclusões preliminares
Conclusões preliminares
8/19/2019 3 - Apresentacao Oficina Corte 2015
65/70
IMECC - UNICAMP
Direções imediatas de pesquisa:Implementação de outras técnicas de escalarização: NISE,
Tchebycheff, Benson, etc...
Uso de outras heurı́sticas de arredondamento
Uso de um modelo não-linear (com uma possı́vel linearização)que implicitamente fornece os padrões de corte
Consideração de mais objetivos
Levar em conta o PCUIM com datas de entregas e considerar
múltiplos perı́odosAplicação em problemas de cortes bi-dimensionais
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 30 / 35
Conclusões preliminares
Modelo linearizado
O d l li i d ´ t d i
8/19/2019 3 - Apresentacao Oficina Corte 2015
66/70
IMECC - UNICAMP
O modelo linearizado e apresentado a seguir:
Minimize z 1 =b
k =1
p
j =1
κ
h =1
2h −1 · α jkh
Minimize z 2 =b
k =1
p
j =1
y jk
sujeito a
b
k =1
p
j =1
κ
h =1
2h −1
· r ijkh ≥ d i , i ∈ I ,
r ijkh ≤ M · α jkh , i ∈ I , j ∈ P , k ∈ K , h ∈ H ,
r ijkh ≤
a ijk , i
∈ I , j
∈ P , k
∈ K , h
∈ H ,
a ijk − M · (1 − α jkh ) ≤ r ijkh , i ∈ I , j ∈ P , k ∈ K , h ∈ H ,m
i =1
i · a ijk ≤ Lk , j ∈ P , k ∈ K ,
m
i =1
i · a ijk ≥ Lk − ∆, j ∈ P , k ∈ K ,
m
i =1
a ijk ≤ q , j ∈ P , k ∈ K ,
κ
h =1
2h −1 · α jkh ≤ N · y jk , j ∈ P , k ∈ K ,
κ
h =1
2h −1 · α jkh ≥ y jk , j ∈ P , k ∈ K ,
α jkh , y jk ∈ B, a ijk ∈ N, r ijkh ∈ R+, i ∈ I , j ∈ P , k ∈ K , h ∈ H ,
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 31 / 35
Conclusões preliminares
Agradecimentos
8/19/2019 3 - Apresentacao Oficina Corte 2015
67/70
IMECC - UNICAMP
Queremos agradecer à
pelo apoio técnico e financeiro, sob o processo 2013/06035-0
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 32 / 35
Conclusões preliminares
References
8/19/2019 3 - Apresentacao Oficina Corte 2015
68/70
IMECC - UNICAMP
P. C. Gilmore and R. E Gomory. A Linear Programming Approachto the Cutting-Stock Problem. Oper Res, 9:848-859, 1961.
G. Wascher and T. Gau. Heuristic for the Integer One-dimensional
Cutting Stock Problem: a Computational Study. OR Spektrum,
18:131-144, 1996.K. C. Poldi and M. N. Arenales. Heuristicas para o Problema do
Corte Unidimensional Inteiro. Pesquisa Operacional, 26:473-492,
2006.
R. R. Golfeto, A. C. Moretti, and L. L. N. Sales. A GraspMetaheuristic for the Ordered Cutting Stock Problem. Revista
Chilena de Ingenieria (En linea), 16:421-427, 2008.
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 33 / 35
Conclusões preliminares
References
8/19/2019 3 - Apresentacao Oficina Corte 2015
69/70
IMECC - UNICAMP
F. Vanderbeck. An Exact Algorithm for ip Column Generation.
Operations Research Letters, 19:151-159, 1996.
S. Kirkpatrick & D. C. Gellat & M. P. Vecchi. Optimization by
Simulated Annealing. Science, 220:671-680, 1983.
J. M. V. Carvalho. Exact Solution of Bin-packing Problems Using
Column Generation and Branch-and-bound. Annals of Operations
Research, 86:629-659, 1999.
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 34 / 35
Conclusões preliminares
Métodos de Soma Ponderada e ε−Restrito no
8/19/2019 3 - Apresentacao Oficina Corte 2015
70/70
IMECC - UNICAMP
Metodos de Soma Ponderada e ε−Restrito noProblema do Corte Unidimensional Bi-objetivo
Angelo Aliano
Antonio Moretti
UNICAMP
11 de junho de 2015
Angelo Aliano Antonio Moretti (UNICAMP) SP e ε−Restrito no PCUIB 11 de junho de 2015 35 / 35