UMA META-HEURÍSTICA BASEADA EM BUSCA EM VIZINHANÇA VARIÁVEL … · 2016-11-11 · Para solucionar problemas de programação, assim como o JSP, as técnicas da Pesquisa Operacional

UMA META-HEURÍSTICA BASEADA EM

BUSCA EM VIZINHANÇA VARIÁVEL

PARA O PROBLEMA DE JOB SHOP

Janaina Maria da Silva (UFU )

[email protected]

JORGE VON ATZINGEN DOS REIS (UFU )

[email protected]

O planejamento e controle da produção (PCP) em uma empresa tem

como objetivo reduzir os custos relacionados a produção. Um das

tarefas do PCP é determinar a melhor sequência de produção,

problema conhecido na literatura como Job Shop Probleem (JSP). A

determinação do sequenciamento é uma tarefa complexa devido às

diversas restrições que necessitam ser consideradas. Este trabalho tem

como objetivo principal criar uma sequência de produção para uma

linha de produção de modo a maximizar o lucro. A avaliação dos

resultados é dada pela comparação entre os valores das soluções

iniciais e finais após a aplicação da meta-heurística VNS - Variable

Neighborhood Search, que utiliza estruturas de vizinhança para buscar

soluções otimizadas. Os dados utilizados foram gerados

aleatoriamente baseados nos dados da literatura.

Palavras-chave: VNS, meta-heurística, Job Shop Problem

XXXVI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCÃO Contribuições da Engenharia de Produção para Melhores Práticas de Gestão e Modernização do Brasil

João Pessoa/PB, Brasil, de 03 a 06 de outubro de 2016.


João_Pessoa/PB, Brasil, de 03 a 06 de outubro de 2016. .

2

1. Introdução

Tubino (2009) define como Planejamento e Controle da Produção (PCP) a atividade

responsável por organizar os dados e as tomadas de decisões considerando todos os fatores do

processo produtivo. O PCP precisa definir a melhor maneira de coordenar e aplicar os

recursos da empresa de modo a atender os planos estabelecidos nos níveis estratégico, tático e

operacional.

Algumas das atividades mais importantes do PCP são a previsão da demanda, o planejamento

estratégico, o planejamento-mestre, a programação da produção e o acompanhamento e

controle da produção (TUBINO, 2009).

Dentro da programação da produção, um dos principais problemas é a alocação dos recursos

para assegurar a data de conclusão dos projetos. Esse é um problema de sequenciamento da

produção, conhecido na literatura como Job Shop Problem ou Job Scheduling Problem (JSP).

É parte importante do Planejamento e Controle da Produção, devido às empresas necessitarem

de um plano eficiente afim de elevar sua produtividade utilizando recursos restritos, como

máquina e rotinas de trabalho. Muitas empresas aplicam multas e restrições em caso de

atrasos, logo, o planejamento eficiente é fator determinante para uma empresa (TUBINO,

2009).

As tarefas de um processo produtivo são independentes entre si, o que significa que cada uma

possui seu próprio fluxo nas máquinas. Comum a todos os processamentos é que cada

máquina pode processar uma tarefa por vez e cada tarefa só pode ser processada por uma

máquina por vez. O tempo de processamento de todas as tarefas é conhecido como makespan

(Cmax) e objetivo de solucionar um JSP é tornar este tempo o menor possível (JAIN &

MEERAN, 1998).

Para solucionar problemas de programação, assim como o JSP, as técnicas da Pesquisa

Operacional (PO) devem ser utilizadas. A PO é formada por um aglomerado de técnicas de

solução para os diversos tipos de problemas, a determinação da solução é baseada na

complexidade do problema (TAHA, 2008).

Algumas das técnicas da PO são a programação linear, a programação inteira, a programação

dinâmica, otimização em redes, a programação não linear e as heurísticas e meta-heurísticas.

As heurísticas e meta-heurísticas diferentemente das outras técnicas podem não apresentar



3

uma solução ótima, mas sim uma solução boa ou melhorada, dado que elas são utilizadas na

solução de problemas que possuem modelos matemáticos muito complexos, como o caso do

JSP (TAHA, 2008).

Meta-heurísticas são utilizadas quando algoritmos não são capazes de encontrar a solução

ótima em tempo razoável, ou seja, a obtenção de uma solução ótima é extremamente difícil

em um tempo computacional aceitável. O JSP é um problema de otimização combinatorial

classificado como NP-hard, o que significa que não há um algoritmo capaz de encontrar a

melhor solução em tempo polinomial, o que requer o uso de uma meta-heurística (MELO;

RONCONI, 2012).

A meta-heurística escolhida neste trabalho para solucionar o JSP é a Variable Neighborhood

Search (VNS ou Busca em Vizinhança Variável). O VNS tem como princípio criar conjuntos

de soluções e combiná-las entre si para chegar a melhor solução possível. Age explorando as

soluções vizinhas à solução corrente através de trocas sistemáticas de estruturas de

vizinhança, e focaliza a busca no entorno (vizinhança) de uma nova solução, a qual é

alcançada somente quando um movimento de melhora é identificado (MLADENOVIC &

HANSEN, 1997).

O objetivo deste trabalho é desenvolver o JSP a partir de uma instância teórica e buscar a

solução utilizando a meta-heurística VNS através de um modelo computacional. A partir dos

resultados, identificar as melhoras e como estas são significativas para a realidade.

2. Referencial teórico

Segundo Tubino (2009) a programação da produção é dividida em três grupos, sendo eles: a

administração de estoques, o sequenciamento e a emissão e liberação de ordens. O foco deste

trabalho é a fase de sequenciamento, na qual gera-se um programa de produção que combina

a fabricação e montagem dos produtos com qualidade e baixo custo.

2.1. Job Shop Problem

O Job Shop Problem é um problema de sequenciamento no qual há uma quantidade n de

tarefas que devem ser processadas em um número m de máquinas. Em cada tarefa i existe

uma sequência de m de operações (Oi1, Oi2, Oi3, ..., Oim). O princípio do JSP é que cada tarefa

deve ser processada sem interrupções, nas máquinas previamente definidas e por um tempo

pré-determinado (GAO, SUN & GEN, 2007).



4

A Figura 1 apresenta o modelo matemático para o JSP, no qual Pik é o tempo de

processamento da tarefa i na máquina k; maqi é a máquina que processa a i-ésima tarefa; M é

um número suficientemente grande; Cik é o instante de término do processamento da tarefa i

na máquina k; e por fim xijk é a variável binária que assume valor 1 caso aquela tarefa, naquela

máquina esteja sendo realizada, e 0 caso contrário.

Figura 1 – Modelo matemático do Job Shop Problem

min∑i= 1

n

C i m

C i ,maq1⩾ pi , maq1

∀ i= 1,... , n

C i , maqk+1⩾C i ,maqk

+ pi , maqk+1∀ i= 1,. .. , n ∀ k= 1,... , m− 1

C jk⩾C ik + p jk− M (1− x ijk) i≠ j ∀ i , j= 1,. .. , n ∀ k= 1,... , m

C ik⩾C jk+ pik− M xijk i≠ j ∀ i , j= 1,... , n ∀ k= 1,. .. , m

C ik⩾0 ∀ i= 1,. .. , n ∀ k= 1,... , m

x ijk∈ [0,1] ∀ i , j= 1,. .. , n ∀ k= 1,... ,m Fonte: Adaptado de Arenales et al. (2007)

2.2. Variable Neighborhood Search

O VNS é uma meta-heurística flexível e refinada. Flexível por ser adaptável à diversos tipos

de problemas e refinada por ter sido adaptada de outras meta-heurísticas, ILS e a VND.

ILS (Iterated Local Search) é um procedimento para otimização de soluções baseados na

busca local. A solução local sofre perturbações afim de encontrar uma nova solução melhor

que a inicial, ou seja, há uma variação dos pontos para a nova busca local (GLOVER &

KOCHENBERG, 2003).

VND (Variable Neighborhood Descent) tem como propósito também a busca local, porém

auxiliado por métodos determinísticos. Nesta meta-heurística, a cada iteração ocorre uma

ampliação do espaço da busca local, afim de encontrar uma melhor solução (MLADENOVIC

& HANSEN, 1997).

Mladenovic e Hansen (1997), propuseram a meta-heurística VNS a fim de demonstrar que era

possível um método de solução simples e eficiente através de mudanças sistemáticas de

vizinhança combinando-as com uma busca local. O nome Variable Neighborhood Search

explica-se pelo fato de, ao contrário de outras buscas locais que seguem uma trajetória única,



5

este método avalia uma vizinhança que pode ser maior ou menor dependendo da precisão a

ser almejada da solução.

As estruturas de vizinhança de uma solução são as modificações que podem ser feitas na

solução atual, de tal forma a gerar uma nova solução distinta e melhorada. Para se determinar

se a solução vizinha é uma melhora de uma anterior é utilizada a função de avaliação, que tem

como objetivo quantificar cada solução e selecionar as de valores superiores. (REIS &

CUNHA, 2010).

A princípio o método VNS necessita de uma solução inicial e uma vizinhança Nk (s), na qual k

é um número natural maior que 1 e menor que o valor determinado como critério de parada,

que pode ser algo como o tempo máximo de processamento ou o número máximo de

iterações, e s é o conjunto de soluções (MLADENOVIC & HANSEN, 1997).

Um vizinho s’ é submetido a uma busca local o que resulta em uma solução s’’, esta solução é

então comparada com a atual solução, chamada de solução corrente. Dentre as duas soluções

a menor é descartada e a maior assume a posição de solução corrente (MLADENOVIC &

HANSEN, 1997). O pseudocódigo que representa esse processo encontra-se na Figura 2

abaixo.

Figura 2 – Pseudocódigo Variable Neighborhood Search

Fonte: Adaptado de Reis & Cunha (2010)

3. Metodologia



6

Para a realização do trabalho foi desenvolvido um código em linguagem C++ para encontrar

a solução para o problema de sequenciamento. Os dados do problema foram retirados da

literatura.

3.1. Dados de entrada

Os dados de entrada necessários para a realização do código em C++ foram adaptados a partir

dos problemas existentes no site da OR-Library -

http://people.brunel.ac.uk/~mastjjb/jeb/info.html. Foram eles: capacidade das máquinas,

tempos de setup, demandas, custos, margens de lucro, tamanhos e cores dos produtos. Os

valores foram dispostos em um arquivo do tipo texto utilizado como fonte de entrada do

programa.

3.2. Heurística Construtiva

A solução inicial é o ponto de partida para a meta-heurística do VNS, e a mesma foi obtida

através de uma heurística construtiva de modo que atendesse as restrições de viabilidade, tal

como, o produto só pode ser manufaturado se a máquina tiver capacidade disponível, caso

haja embalagem para o produto e se houver demanda para o mesmo. A Figura 3 apresenta o

pseudocódigo da heurística construtiva.

Figura 3 – Pseudocódigo da Heurística Construtiva



7

Fonte: Autoria Própria

3.3. Estruturas de vizinhança

A estrutura de vizinhança é o local onde se encontram substituições viáveis e que serão

utilizadas pelo VNS afim de encontrar novas soluções. Essa estrutura é composta por

combinações de trocas possíveis de serem realizadas, como por exemplo, a substituição da

fabricação de um produto preto de 2000 cm3 por oito produtos da mesma cor de tamanho 250

cm3 ou até mesmo dois produtos da mesma cor de tamanho 1000 cm

3, ou simplesmente a

substituição das cores. Na estrutura de vizinhança encontram-se diversas substituições

equivalentes que serão avaliadas pela função objetivo na intenção de melhorar a solução. A

imagem abaixo ilustra algumas das estruturas de vizinhança.

Figura 4 – Ilustração das Estruturas de Vizinhança



8


3.4. Função Objetivo

A Função Objetivo (FO) é a função responsável por avaliar as soluções e verificar quais

apresentam os melhores resultados, tornando-as momentaneamente como solução corrente. A

FO para este caso específico foi formulada considerando o lucro adquirido com a produção e

venda do produto, descontando o prejuízo causado com o não atendimento da demanda. A

Tabela 1 apresenta as margens de lucro de cada produto e a Figura 5 apresenta a Função

Objetivo.

Tabela 1 – Valores dos benefícios para todos os produtos

Tamanho

Cores

Preto Laranja Verde Vermelho Roxo

250 cm3 0,75 0,57 0,54 0,57 0,54

600 cm3 0,81 0,65 0,62 0,65 0,62

1000 cm3 1,27 1,13 0,99 1,13 0,99

2000 cm3 1,77 1,44 1,32 1,44 1,32


Figura 5 – Pseudocódigo da Função Objetivo



9


3.5. Quicksort

O Quicksort é um algoritmo de ordenação utilizado para rearranjar vetores em ordem

crescente ou decrescente (FARIAS, 2012). O Quicksort foi o método escolhido para organizar

os resultados de forma a apresenta-los na ordem decrescente.

O método de funcionamento do algoritmo é simples, um valor dentro no vetor é selecionado,

o chamado pivô, a partir dele é iniciado o método de separação. Caso a ordem crescente seja

escolhida, os valores, menores que o pivô, serão considerados pequenos, e os maiores como

grandes, e consequentemente ficarão a esquerda e a direita do pivô, respectivamente. Caso a

ordem decrescente seja a escolhida a disposição será oposta (FARIAS, 2012).

4. Resultados Obtidos

As tabelas a seguir mostram os valores obtidos pelo programa desenvolvido.

Tabela 2 – Resultados para os produtos da cor preto

Preto

Valor da FO inicial R$ 6.268,00

Valor da FO final R$ 8.608,00

Tamanho Demanda Quantidade Produzida

250 cm3 2.179 4.056

600 cm3 2.656 1.330

1000 cm3 2.493 0

2000 cm3 8.292 7.278




10

Tabela 3 – Resultados para os produtos da cor laranja

Laranja




250 cm3 684 1.400

600 cm3 4.388 4.210

1000 cm3 1.754 1.750

2000 cm3 3.577 2.702


Tabela 4 – Resultados para os produtos da cor verde

Verde

Valor da FO inicial -R$ 723,00



250 cm3 2.708 962

600 cm3 5.384 4.784

1000 cm3 2.419 2.659

2000 cm3 1.673 1.675


Tabela 5 – Resultados para os produtos da cor vermelho

Vermelho




250 cm3 1.979 600

600 cm3 1.933 0

1000 cm3 1.415 708

2000 cm3 2.736 2.586




11

Tabela 6 – Resultados para os produtos da cor roxo

Roxo




250 cm3 3.348 127

600 cm3 5.037 4.962

1000 cm3 2.166 2.196

2000 cm3 1.207 1.215


As Tabelas de 2 a 6 indicam as quantidades que devem ser produzidas de todos os produtos. É

possível observar pelos valores das quantidades produzidas que não é simples identificar a

lógica utilizada na determinação dos resultados, como por exemplo, produzir mais dos

produtos que apresentam maior benefício, ou produzir a mesma quantidade dos produtos que

tenham semelhança, o que representa como é difícil determinar o sequenciamento de

produção manualmente.

Os valores das soluções obtidas antes e depois da aplicação da meta-heurística VNS indicam

como é benéfico programar o sequenciamento utilizando um método de solução auxiliar,

como algoritmos e meta-heurística, para problemas de grande dimensão. O lucro total

calculado antes da aplicação do VNS foi de R$ 10.870,00, enquanto que o calculado após foi

de R$ 19.234,00, o que representa uma melhora de 76,95% de retorno monetário.

As quantidades produzidas inferiores as demandas são justificadas pelo fato de que a condição

do problema, ou seja, a Função Objetivo, era maximizar o lucro e não atender ao máximo das

demandas, porém a perda de não atender à alguma demanda foi contabilizada no cálculo da

Função Objetivo. O aumento monetário significativo, de quase 77%, mostra que o modelo

atingiu sua condição e maximizou o lucro.

É importante ressaltar que o resultado apresentado por este modelo, assim como em outros

casos, deve ser analisado pelo tomador de decisão. Não há necessidade de se produzir mais de

100% da demanda para este caso, porque neste modelo não há estoque, porém, o valor em



12

excesso aparece porque o mesmo foi desenvolvido sem considerar interrupção da máquina

por meio externo, somente caso a capacidade fosse atendida, logo alguns valores das

quantidades produzidas são superiores a demanda.

Em situações na qual o produto não tem um ciclo de vida muito curto, e o produto final seja

de fácil armazenamento, a produção até a capacidade máxima pode ser vantajosa, entretanto é

tarefa do tomador de decisão analisar os custos relacionados ao armazenamento.

5. Conclusão

Este estudo indica como a meta-heurística VNS é útil na resolução de problemas de grande

dimensão, como o caso do JSP. O modelo desenvolvido apresentou resultado satisfatório,

visto que atendeu a maior restrição, a de maximizar o lucro, fato observado nos valores das

funções objetivos e principalmente na porcentagem otimizada do lucro total, que representa

um aumento de 76,95%.

O JSP foi escolhido por se tratar de um dos problemas mais comuns dentro no planejamento e

controle da produção e de difícil solução, dado que o mesmo pode não apresentar solução

ótima a partir de algoritmos simples.

A meta-heurística VNS foi a opção escolhida por se tratar de uma meta-heurística mais

refinada e flexível, o que permite que os resultados encontrados sejam confiáveis e o modelo

passível de adaptações, afim de solucionar outros problemas.

Os resultados apresentados mostram a melhora significativa nas soluções após a aplicação da

meta-heurística. A mesma conseguiu encontrar os valores a serem a produzidos de modo que

o lucro obtido fosse otimizado.

Os resultados apresentados também contribuem para a avaliação de outras atividades presente

nas empresas, como a questão de produzir mais que a demanda afim de estocar o produto, ou

avaliar se pelas quantidades produzidas a empresa está atingindo sua capacidade máxima e

haja necessidade de flexibilizar o serviço, abrindo uma nova janela de trabalho para os

responsáveis pelo planejamento e controle de produção.

Este trabalho contribui para a realidade atual por se tratar de um modelo genérico para um

problema comum, ou seja, o modelo desenvolvido é passível de ser ajustado para solucionar



13

os problemas das empresas ou melhorar seus processos. É necessário modificar a formatação

dos dados de entrada e criar estruturas de vizinhanças compatíveis com o problema, com as

tarefas e com a produção.

REFERÊNCIAS

ARENALES, Marcos, ARMENTANO, Vinícius, MORABITO, Reinaldo, YANASSE, Horacio. Pesquisa

operacional para cursos de engenharia. Campus Elsevier, Rio de Janeiro, 2007.

FARIAS, Fábio Henrique, SILVA, Fabiano Barbosa Mendes da, NETO, José Belmiro. Quicksort e Quicksort

Aleatorizado: Um estudo comparativo. Anais do Congresso de Matemática Aplicada e Computacional,

CMAC Nordeste 2012.

GAO, Jie, SUN, Linyan, GEN, Mitsuo. A hybrid genetic and variable neighborhood descent algorithm for

flexible job shop scheduling problems. Computer & Operations Research 2007.

GLOVER, Fred, KOCHENBERGER, Gary A. Handbook of metaheuristics. International Series in Operations

Research & Management Series, Kluwer’s International Series, Stanford University, 2003.

JAIN, A S, MEERAN, S. Deterministic job-shop scheduling: past, present and future. Departament of Applied

Physics and Eletronic and Mechanical Engineering, University of Dundee, Dundee, Scotland, UK, DD1 4HN.

1998.

MELO, Everton Luiz de, RONCONI, Débora Pretti. Heurísticas construtivas para a minimização do atraso

total no ambiente job shop flexível. Simpósio Brasileiro de Pesquisa Operacional. Setembro, 2012.

MLADENOVIC, N, HANSEN, P. Variable neighborhood search. Computers and Operations Research, 24,

1097-1100. 1997.

REIS, Jorge Von Atzingen dos, CUNHA, Claudio Barbieri da. Uma heurística baseada em VNS para o

problema bidimensional de binpacking com frota heterogênea. In: XVI PANAM, Lisboa, Portugal. Julho,

2010.

TAHA, Hamdy A. Pesquisa operacional: uma visão geral / Hamdy A. Taha ; tradução Arlete Simille Marques;

revisão técnica Rodrigo Arnaldo Scarpel. – São Paulo: Pearson Prentice Hall, 2008.

TUBINO, Dalvio Ferrari. Planejamento e controle da produção: teoria e prática / Dalvio Ferrari Tubino. - 2.

ed. – São Paulo: Atlas, 2009.

Documents

UMA META-HEURÍSTICA BASEADA EM BUSCA EM VIZINHANÇA VARIÁVEL … · 2016-11-11 · Para solucionar problemas de programação, assim como o JSP, as técnicas da Pesquisa Operacional