Redução de desperdícios de corte em empresas Têxtil-Lar

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Redução de desperdícios de corte em empresas Têxtil-Lar Ricardo Nuno Pinto Salazar de Almeida Mestrado Integrado em Engenharia Electrotécnica e de Computadores Orientador: Elsa Marília da Costa Silva Co-orientador: Maria Antónia da Silva Lopes de Carravilla 30 de Abril de 2014 c Ricardo Nuno Pinto Salazar de Almeida, 2014 ii Resumo Ao longo das últimas décadas tem sido intensivo o estudo acerca de problemas na área de Cutting and Packing, ou C&P, problemas estes que se podem encontrar num variado leque de indústrias. Este estudo levou à criação de métodos para obtenção de resultados ideias, algoritmos de otimização. No entanto, devido à grande complexidade que este tipo de problemas poderá ter, estes resultados necessitam por vezes de um tempo de processamento demasiado alto, sendo estes irrealistas para uma aplicação prática. Desta forma surge a oportunidade para o desenvolvimento de heurísticas, criadas com o objetivo de obter um resultado eficiente e próximo do ideal com um tempo de processamento adequado à realidade prática. No seguimento da dissertação desenvolvida por Bernardo Cerqueira [1] surge a possibilidade do desenvolvimento de heurísticas que permitam encontrar soluções para os processos de corte da empresa Textilar - Indústrias Têxteis S.A., uma empresa de produção de artigos da categoria têxtil-lar. Esta dissertação terá como objetivo não só o desenvolvimento de uma heurística de otimização para o processo de corte da empresa Textilar mas também a implementação da mesma numa aplicação informática. Para isso, em primeiro lugar será feita uma abordagem que nos permita perceber qual o tipo de problema com que nos encontramos. Essa análise será feita utilizando tipologias desenvolvidas para problemas do tipo C&P ao longo dos últimos anos, nomeadamente a desenvolvida em 2007. Numa segunda parte do documento será apresentada a heurística desenvolvida, que terá como base algumas já desenvolvidas para problemas similares. Utilizando algumas instâncias fornecidas pela empresa Textilar, a heurística será testada e os seus resultados demonstrados e discutidos. Numa análise final será efetuado um balanço da eficiência da heurística assim como propostas de melhoramento da mesma. iii iv Abstract Along the past few decades, studies in the area of Cutting and Packing have been extensive, as a result of the vast number of applications throughout industries. This study led to the creation of methods in order to obtain ideal results, optimization algorithms. However, this results, due to the great complexity this type of problems may have, needed a long processing time making them unrealistic for practical applications. This way an opportunity for the development of heuristics emerges, whose objective is not to find the ideal solution but one that can be calculated in an adequate processing time, while still presenting some efficient results. As a result of the dissertation developed by Bernardo Cerqueira [1] emerges the possibility for the development of heuristics that permit an optimization of cutting processes in Textilar - Indústrias Têxteis S.A. industry, a company whose goal is the production of products in the home textile category. The purpose of this dissertation is not only the development of an optimization heuristic for the cutting process of Textilar, but also the implementation of an informatics application. In order to do that, first an approach that lets us realize the kind of problem we have must be done. This analisis will be made using typologies developed for the C&P problems. Then the heuristic will be presented, having some techniques used in other heuristics as a base for it. Using some instances supplied by Textilar, the heuristic will be testes and its results presented and discussed. In a final analysis, an assessment will be made as will some propositions for future work. v vi Agradecimentos À Professora Elsa Silva, por toda a sua paciência e compreensão que foram essenciais a manter a motivação durante o desenvolvimento do trabalho. Por toda a disponibilidade que sempre demonstrou em ajudar e garantir que tinha todo o apoio necessário.. À Professora Maria Antónia Carravilla, cuja confiança e honestidade foram os motores para o ínicio deste projeto e cuja compreensão me ajudou a levantar nos momentos mais complicados. A todos os meus amigos que me ajudaram a tornar na pessoa que sou hoje, por todas as memórias e momentos que levo comigo para a vida. A todos os laços que o tempo nunca poderá quebrar. Que este passo não signifique um adeus mas apenas um até já. Ao Pai, Mãe e irmão, por todo o apoio dado ao longo da minha vida e por todos os ensinamentos que me deram os valores necessários para cingir na vida. Aos meus Padrinhos, por garantirem a continuidade da minha educação nos momentos mais difíceis e por todo o apoio incondicional que me deram ao longo da vida. Ricardo Almeida vii xiv LISTA DE FIGURAS Lista de Tabelas 2.1 Dados acerca dos parâmetros do problema . . . . . . . . . . . . . . . . . . . . . 8 4.1 Dadosdepedidodefabrico............................. 23 4.2 Comparaçãodeáreas................................ 23 4.3 Tabela de prioridades inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.4 Tabela de prioridades intermédia . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.5 Tabela de prioridades Final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.6 Resultados finais para 2 estágios + trimming . . . . . . . . . . . . . . . . . . . . 29 4.7 Resultados finais para 3 estágios sem trimming . . . . . . . . . . . . . . . . . . 32 4.8 Resultados finais para 3 estágios + trimming . . . . . . . . . . . . . . . . . . . . 35 5.1 Instânciasanalisadas ................................ 38 5.2 Resultados das instâncias para 2 estágios com trimming . . . . . . . . . . . . . . 39 5.3 Resultados das instâncias para 3 estágios sem trimming . . . . . . . . . . . . . . 39 5.4 Resultados das instâncias para 3 estágios com trimming . . . . . . . . . . . . . . 40 5.5 Resultados das instâncias para 2 estágios com trimming . . . . . . . . . . . . . . 41 5.6 Resultados das instâncias para 3 estágios com e sem trimming . . . . . . . . . . 42 xv xvi LISTA DE TABELAS Abreviaturas e Símbolos PF Pedido de Fabrico C&P Cutting & Packing FFDH First Fit Decreasing Height NFDH Next Fit Decreasing Height BFDH Best Fit Decreasing Height HFF Hybrid First Fit HNF Hybrid Next Fit HBF Hybrid Best Fit xvii Capítulo 1 Introdução 1.1 Enquadramento A Textilar é uma empresa vertical que engloba diferentes etapas produtivas da indústria têxtil desde a tecelagem até à expedição do produto acabado embalado. A roupa de cama representa a quase totalidade da produção da empresa. O Departamento Comercial recebe as encomendas e define, em conjunto com o cliente, o produto acabado pretendido. Essa definição inclui, para além da especificação dos materiais e acessórios para confeção, a definição dos materiais e acessórios para embalagem. A intervenção do Departamento Comercial termina com a aceitação da encomenda por parte do cliente. O processo é seguidamente remetido para o Departamento de Produção, cabendo a este a gestão das encomendas a produzir e respetivas datas de entrada em produção gerando Pedidos de Fabrico (PF). Um PF inclui toda a informação necessária aos vários setores da empresa para satisfação da encomenda, desde as características do rolo de tecido a produzir/utilizar passando pelas dimensões e quantidades dos componentes que constituem os confecionados a produzir e por fim também os materiais para as embalagens. A primeira fase de produção na empresa é a da tecelagem, produzindo-se a tela com as características necessárias para satisfação da encomenda. De seguida, realizam-se as fases de acabamento de tinturaria e/ou estampagem, a que finalmente se segue a fase de corte dos rolos de tecido. Os produtos são então confecionados e embalados. Entre cada uma destas fases existe stock que poderá ser utilizado numa fase de produção subsequente, conforme definido pelo planeamento de produção. O stock intermédio pode ser alimentado pelo produto acabado de uma fase a montante ou por produto adquirido a um fornecedor externo (e.g. os rolos de tecido importados do Paquistão, que são tingidos ou estampados na Textilar). Cada confecionado é produzido a partir de um tecido com determinadas características de tecelagem, tinturaria e estampagem. Para garantir um bom fluxo de produção e evitar custos de set-up excessivos, são definidos, para cada uma das fases do processo, mínimos de produção a cumprir. Por exemplo, na fase da tecelagem cada largura de cada referência de tecelagem terá uma quantidade mínima de produção (em metros), o mesmo acontecendo a cada cor na tinturaria ou a 1 2Introdução cada desenho na estampagem. Note-se que a mesma cor pode ser aplicada a diferentes referências de tecelagem e o mesmo estampado pode ser aplicado a diferentes cores de base. Esta flexibilidade torna o problema de planeamento dessa sequência de fases particularmente complexo. Também na fase de corte se pretende garantir um comprimento mínimo de tecido a que seja aplicado o mesmo padrão de corte, de forma a balancear o desperdício com a produtividade do corte. As dificuldades sentidas no planeamento da produção da Textilar, em particular na definição das características dos rolos de tecido a produzir ou adquirir e dos padrões de corte neles aplicados para produção dos confecionados, que são base do negócio da empresa, representam um problema continuado e de enorme importância. É notório que todas essas restrições e graus de liberdade tornam muito complicado o processo de planeamento de produção. Entre decidir quais as melhores larguras de rolo de tecido a produzir, de entre um conjunto de larguras standard predefinidas, que possam resultar nos planos de corte com menos desperdício, decidir que rolos usar de stock ou então que rolos adquirir junto de um fornecedor externo, ou até qual o plano de corte que melhor se adequa a uma dada largura de tela, torna-se difícil chegar, de uma forma manual, à melhor solução de entre um número extraordinariamente grande de combinações possíveis. É desta forma que se abre espaço a uma aplicação informática que, utilizando modelos de otimização matemática avançados, auxilie este planeamento e apoie o processo de decisão dos planos de corte. Uma primeira abordagem ao problema da empresa foi proposta na dissertação [1], que para além da definição do problema em estudo propõe também um modelo matemático que permite a resolução integrada do problema tendo em consideração todo o planeamento da produção e os respetivos custos. O modelo matemático proposto assenta no conhecimento de um conjunto alargado de padrões de corte (disposição geométrica das peças no tecido), nesta dissertação serão criados padrões de corte que poderiam ser utilizados pelo modelo matemático proposto por [1]. 1.2 Objetivos Nesta dissertação apenas será estudado o problema da secção de corte. Para isso serão desenvolvidos e implementados algoritmos heurísticos, que terão como foco a geração de padrões de corte que respeitem as restrições do processo e permitam a minimização de desperdícios. Por padrão de corte entende-se a disposição das peças a serem produzidas no tecido de forma a ser efetuado o corte (este processo será explicado com mais detalhe no capítulo 2). De forma a cumprir este objetivo será necessário: 1. Efetuar uma análise do problema; 2. Efetuar um levantamento bibliográfico de problemas semelhantes na literatura; 3. Criar uma abordagem para resolução de um problema de geração de padrões de corte; 4. Implementar o algoritmo definido utilizando o software Microsoft Visual Studio 2013 em linguagem C++; 1.3 Estrutura do Documento 3 5. Efetuar testes e melhorias contínuas ao algoritmo já desenvolvido; 6. Utilizar ferramentas gráficas (gnuplot) de forma a visualizar o resultado obtido; 1.3 Estrutura do Documento Este documento será constituído por 6 capítulos. Neste primeiro, introdução, é apresentado o enquadramento do problema, objetivos da dissertação e estrutura do documento. No Capítulo 2, Definição e Descrição do problema, haverá uma descrição que permite uma melhor compreensão do problema em estudo, assim como definição dos parâmetros utilizados. No Capítulo 3, Revisão de Literatura, serão apresentados os resultados da pesquisa efetuada acerca de problemas semelhantes na literatura. No Capítulo 4, Heurística proposta, a heurística desenvolvida será apresentada, tendo em consideração os resultados obtidos do capítulo 2 e 3. No Capítulo 5, Resultados, haverá uma apresentação dos resultados obtidos com a heurística desenvolvida de forma a poder obter conclusões, que serão apresentadas no Capítulo 6 juntamente com propostas para trabalhos futuros. 4Introdução Capítulo 2 Descrição do problema O problema que se pretende resolver ao longo do desenvolvimento desta dissertação é um problema de corte, conhecido na literatura como cutting stock problem, neste caso do tipo 2 dimensões e de dimensão aberta. É de dimensão aberta pois o comprimento dos padrões de corte é variável, podendo ser adaptado de forma a minimizar desperdícios. Neste tipo de problema, o cliente envia um pedido de fabrico (PF) constítuido pelas peças que pretende. Essas peças, conhecidas na literatura como itens pequenos, têm um comprimento li, uma largura wie uma quantidade a ser produzida qi. O objetivo do problema prende-se na produção de todas as peças utilizando o mínimo tecido possível. De forma a produzir as peças, o tecido é desenrolado e dobrado em camadas sobre uma mesa. A esta disposição dá-se o nome de mesada. Uma mesada, como se pode ver na figura 2.1 [1], têm um comprimento L, uma largura W, e uma altura H. É importante referir a existência de tecido na dobra entre folhas. Este tecido, denominado enfesto, é normalmente considerado desperdício e não é utilizado na confecção de peças visto ter um comprimento pouco preciso. No entanto, caso o cliente o aprove, esse tecido poderá ser utilizado na confecção de peças, como irá ser explicado mais adiante. Figura 2.1: Disposição do tecido na mesa de corte Importa também referir que numa mesada todas as folhas deverão ter o mesmo padrão de corte, visto que o corte é efetuado a todas as folhas em simultâneo. Um padrão de corte, de comprimento 5 12 Revisão da Literatura 3.1 Antiga estruturação dos problemas do tipo C&P Os problemas de cutting epacking apesar de serem diferentes em alguns aspetos, partilham certos conceitos sendo por isso referidos como um tipo de problema e não diferenciados completamente. O conceito mais básico deste tipo de problemas é a definição do que é o input, ou entrada, eoutput, ou saída. Definem-se então dois conjuntos de elementos: •Conjunto de objetos grandes (entrada, oferta); •Conjunto de itens pequenos (saída, procura). O objetivo do problema é portanto distribuir o conjunto de itens pequenos, com número de elementos que varia de 1 a n, pelo conjunto de objetos grandes, que poderá variar também de 1 a n. A nível de posicionamento podem ser retiradas portanto algumas restrições: •Os itens pequenos não poderão ser colocados de forma sobreposta nos objetos grandes; •Os itens pequenos terão de ficar na sua totalidade dentro das margens dos objetos grandes. Estas restrições dependem da dimensão do problema, que poderá ser uni ou multi dimensional. Outro factor de categorização é também o objetivo da solução. A utilização parcial ou total do conjunto de objetos grandes e itens pequenos, respetivamente, permite a diferenciação de dois tipos de solução: minimização de objetos largos utilizados ou maximização de itens pequenos. Estas soluções partilham no entanto um conjunto de sub-problemas que são necessários resolver de forma a atingir a solução final óptima: •Selecção de objetos grandes; •Selecção de itens pequenos; •Problema de agrupamento relativamente a itens pequenos; •Problema de alocação relativamente aos grupos de itens pequenos nos objetos grandes; •Problema de layout relativamente ao arranjo dos itens pequenos seleccionados em cada um dos objetos grandes considerando a condição geométrica; A tipologia apresentada em [3] utiliza como critérios, para além dos já apresentados, a classificação tanto dos objetos grandes como dos itens pequenos. Para os objetos grandes são consideradas três classes diferentes: objeto único, objetos idênticos, objetos distintos. Para os itens pequenos são consideradas quatro classes: poucos items de diferentes tipos, muitos items de diferentes tipos, muitos items de relativamente poucos tipos, items congruentes. Seguidamente encontra-se portanto a categorização final apresentada por Dyckhoff. 3.2 Desenvolvimento de uma nova tipologia 13 1. Dimensionalidade (1) Uni-Dimensional (2) Bi-Dimensional (3) Tri-Dimensional (N) N-Dimensional (N>3) 2. Tipo de solução (B) Utilizar todos os objetos para alocar alguns itens (V) Alocar todos os itens em alguns objetos 3. Classificação dos objetos grandes (O) Objeto único (I) Objetos idênticos (D) Objetos distintos 4. Classificação dos itens pequenos (F) Poucos itens de diferentes tipos (M) Muitos itens de diferentes tipos (R) Muitos itens de relativamente poucos tipos (C) Itens congruentes (iguais em forma e tamanho) Apesar desta categorização ter representado um passo na uniformização de problemas do tipo C&P, o código utilizado pelas categorias não era auto-explicativo, visto que derivava de uma língua que não era o inglês (alemão), o que provocou alguma dificuldade na aceitação por parte da comunidade científica. Para além disso, em alguns tipos de problemas, como é o caso do Vehicle Loading Problem, a classificação do problema era ambíguo. Neste exemplo, o problema tanto foi codificado como sendo 1/V/I/F como sendo 1/V/I/M [3]. Para um exemplo standard como este, uma classificação uniforme e coerente seria desejada. Outros exemplos de incoerência de conceitos podem ser encontrados em [2]. 3.2 Desenvolvimento de uma nova tipologia A tipologia desenvolvida por Gerhard Wäscher, Heike Haußner e Holger Schumann baseia-se num esquema em árvore onde o problema começa como um Pure C&P Problem Type e acaba em Refined Problem Type. Este esquema vai utilizando os parâmetros referidos na tipologia anterior para a definição do problema. Isto permite explicar onde problemas que utilizam parâmetros inesperados se separam dos problemas standard. Estes problemas com parâmetros incertos são chamados de Problem Variants. Um problema do tipo Pure C&P Problem Type juntamente com os 14 Revisão da Literatura parâmetros de objetivo do problema (maximização da saída ou minimização das entradas) e tipos de itens pequenos formam os chamados Basic Problem Types. Estes, por sua vez, juntamente com o parâmetro tipos de objetos grandes formam os chamados Intermediate Problem Types. Finalmente, juntando a dimensionalidade e forma dos itens pequenos obtemos os Refined Problem Types. Em todos estes parâmetros existem suposições acerca dos resultados possíveis. Caso algum problema utilize dados fora de comum, estes serão considerados como variações do problema visto não haver definição existente acerca dos mesmos. Isto torna o esquema explicado mais global e aceitável pela comunidade científica, problema esse existente na tipologia de Dyckhoff. Nas seguintes subsecções serão explicados mais pormenorizadamente os parâmetros e as suposições tomadas para cada um deles. 3.2.1 Dimensionalidade Quanto à dimensionalidade, os problemas distinguem-se entre uni-, bi- e tridimensionais. Qualquer problema com dimensionalidades acima dessas é considerado uma variante nesta tipologia. 3.2.2 Objetivo do problema Assim como na tipologia de Dyckhoff, o objetivo do problema poderá ser maximização das saídas ou minimização das entradas. No caso de maximização de saídas, um conjunto de itens pequenos tem de ser alocado num dado conjunto de objetos grandes. Este conjunto de objetos grandes não é suficiente para alojar todos os itens pequenos e o objetivo deverá ser portanto tentar utilizar o máximo de itens pequenos. No caso de minimização de entradas, todos os itens pequenos deverão ser alocados nos objetos grandes, sendo a solução óptima aquela que utilize objetos grandes de menor valor. Este valor poderá ser calculado através de preço do objeto grande, medidas deste, quantidade de objetos utilizados, etc. 3.2.3 Tipos de items pequenos Em relação aos tipos de itens pequenos, foram considerados três casos: itens idênticos, classificação heterogénea fraca e classificação heterogénea forte. Itens idênticos refere-se à utilização de itens com a mesma forma e tamanho. No caso de maximização do output como objetivo do problema, pode-se considerar a procura dos itens infinita. Na classificação heterogénea fraca o grupo de itens pequenos é constituído por poucas classes de itens diferentes (em tamanho). Normalmente a procura deste tipo de itens é relativamente grande e pode, ou não, ser limitada por um limite superior de procura. Na classificação heterogénea forte o grupo de itens pequenos é constituído por muitas classes de itens normalmente de procura baixa. Neste caso os itens são muitas vezes considerados como individuais com procura igual a um. 3.3 Enquadramento do problema 15 3.2.4 Tipos de objetos grandes Em relação a objetos grandes são apresentados os seguintes casos: Objeto Único Neste caso o conjunto de objetos grandes singe-se apenas a um elemento. Este poderá ter as suas dimensões fixas ou poderá ter uma ou mais dimensões variável. Vários objetos Em relação a problemas estudados da literatura, não pareceu necessário ao autor considerar objetos de dimensão fixa para este caso. De forma análoga aos itens pequenos, para este caso existe distinção entre objetos iguais, classificação heterogénea fraca e classificação heterogénea forte. Desta forma obtemos uma extensão à tipologia de Dyckhoff, que apenas considerava objetos grandes como idênticos ou de formas diferentes. Para além disso a tipologia também supõe que todos os objetos grandes, para duas e três dimensões, são rectangulares, estando os problemas em que estes têm formas diferentes na secção de variantes de problema. 3.2.5 Forma dos itens pequenos No caso de problemas de duas e três dimensões, para a definição de problemas refinados, existe a distinção entre itens pequenos regulares (com formas rectangulares, circulares, cilíndricas, esféricas, etc) e irregulares. De acordo com o que é normalmente considerado na literatura, assume-se que os itens pequenos sendo rectangulares são dispostos ortogonalmente. Problemas que permitem disposição não ortogonal ou misturas entre objetos regulares e não regulares são considerados variantes de problema. 3.3 Enquadramento do problema Após uma análise da tipologia, torna-se possível efetuar o enquadramento do problema em estudo. Os objetos grandes são os rolos de tecido que são caracterizados por uma largura e um comprimento indeterminado, os itens pequenos são as peças rectangulares (fronhas, lençois, capas para edredão) com procuras conhecidas. Pretende-se que todas as peças sejam cortadas dos rolos de tecido de modo que o desperdício seja mínimo. De acordo com a tipologia de [2] trata-se de um problema do tipo Open Dimension Problem, uma vez que se pretende a minimização das entradas (desperdício), os objetos grandes têm dimensão variável e os itens pequenos são pouco heterogéneos. O comprimento da mesa utilizada para o processo de corte será usado para limitar o comprimento possível de um padrão de corte. Sendo assim, os objetos grandes passam a ter dimensão fixa (rectângulos) e, segundo a tipologia, o problema passa a ser caracterizado como Cutting Stock Problem. Diferentes comprimentos podem ser considerados para o padrão de corte, e 16 Revisão da Literatura portanto pode-se dizer que são considerados vários objetos grandes sendo o problema classificado como Multiple Stock Size Cutting Stock Problem. Como análise final ficam as características que definem o nosso problema, Multiple Stock Size Cutting Stock Problem: •Input Minimisation •Weakly heterogeneous assortment •Multiple large objects •2-dimensional Neste problema é portanto necessário efetuar o corte de um conjunto de itens rectangulares, cada um com uma procura alta, dispostos ortogonalmente num conjunto de objetos grandes. A heurística a desenvolver tem como objetivo minimizar o número de objetos grandes necessário para a alocação de todos os itens. Nas secções seguintes serão analisados os métodos utilizados para a resolução deste tipo de problemas. 3.4 Solução através de geração de colunas O trabalho de Gilmore e Gomory[4] foi pioneiro na utilização da técnica de geração de colunas para a resolução de problemas de corte. O método de geração de colunas funciona através da divisão do problema num problema mestre e um subproblema. O problema mestre utiliza apenas um sub conjunto de variáveis a considerar. O subproblema por sua vez é criado com o objetivo de identificar uma nova variável. O objetivo do subproblema é encontrar uma variável com custo reduzido negativo. Se tal não for possível a solução do problema mestre é a solução óptima do modelo linear. No caso dos problemas de corte, cada variável de decisão representa um padrão de corte e, sendo assim, o subproblema constrói padrões de corte atrativos, isto é, que permitam melhorar o valor da função objetivo do problema mestre. 3.5 Heurísticas para resolução do problema Nesta secção serão expostas algumas heurísticas existentes na literatura. Algumas das heurísticas descritas neste capítulo, apesar de não terem sido desenvolvidas para o nosso problema em específico, poderão ser utilizadas para Multiple Stock Cutting Stock Problems. Estas heurísticas são todas baseadas em level packing, que pressupõe uma divisão dos objetos grandes em várias partes que serão chamadas de níveis. Esta secção do documento estará dividida em duas subsecções: uma destinada a heurísticas de 2 estágios outra destinada a heurísticas de 3 estágios. Como já foi referido no capítulo 2, número de estágios refere-se ao número de direções diferentes em 3.5 Heurísticas para resolução do problema 17 que a máquina se terá de posicionar para efetuar um corte (ex: corte horizontal seguido de um corte vertical e com outro corte horizontal refere-se a um corte 3 estágios). 3.5.1 Heurísticas para 2 estágios As heurísticas descritas neste capítulo são compostas por duas fases. Numa primeira fase os itens são organizados por níveis numa tira de larguraWcom comprimento infinito. O comprimento de cada nível será definido pelo primeiro item a entrar nesse nível. As peças serão dispostas por comprimentos decrescente. Numa segunda fase, os níveis serão reorganizados de forma a caberem nos objetos grandes de largura We comprimento Lsegundo a regra definida pela heurística [5]. 3.5.1.1 Hybrid First Fit (HFF) Na primeira fase, as peças seguem o algoritmo FFDH (First Fit Decreasing Height). Este algoritmo empacota a peça seguinte no primeiro nível onde ela possa ser alocada. Caso nenhum nível possa acomodar a peça, um novo nível será criado. A segunda fase irá adotar o mesmo tipo de algoritmo, FFDH. Neste caso, os níveis serão inseridos no primeiro padrão de corte que tenha um comprimento residual superior ao comprimento dos níveis. 3.5.1.2 Hybrid Next Fit (HNF Esta heuristica é, comparativamente com a anterior, menos eficiente. Isso acontece porque, tanto na primeira fase como na segunda, segue o algoritmo NFDH (Next Fit Decreasing Height). Nesse algoritmo uma peça é inserida no último nível criado. Caso isso não seja possível é criado um nível novo, ignorando sempre os níveis anteriores. Isso faz com que uma peça que poderia ser inserida nos primeiros níveis não o seja, sendo por isso menos eficiente. 3.5.1.3 Hybrid Best Fit (HBF) Nesta heurística, tanto na primeira como na segunda fase, será seguido o algoritmo BFDH (Best Fit Decreasing Height. Esse algoritmo empacota as peças no nível em que depois de a acomodar fique com largura residual menor. Numa segunda fase, os níveis serão inseridos no primeiro objeto grande que o possa acomodar ficando com comprimento residual menor. 3.5.2 Heurística para 3 estágios Nesta subsecção será apenas referida uma heurística restrita para 3 estágios [6]. Heurísticas restritas são heurísticas onde o comprimento do nível é definido por uma peça única, e não por um conjunto de peças. Nesta heurística é criado um nível com a primeira peça i, segundo a ordenação definida. Neste nível serão inseridas todas as peças jque contenham comprimento menor ou igual a i, que por sua 18 Revisão da Literatura vez é o comprimento do nível, e cuja largura seja menor que a largura residual do nível. Assim que tiverem sido verificadas todas as peças j, é criado um novo nível com a peça seguinte, e assim sucessivamente até que não possam ser criados mais níveis no padrão de corte. Nesse momento, o padrão de corte é fechado e criado um novo padrão de corte caso ainda haja peças por inserir. 3.6 Conclusão Após uma análise das heurísticas tornou-se claro que o caminho certo a tomar seria o de uma heurística baseada em level packing, organização por níveis. Este tipo de organização permite um controlo sobre o número de estágios da heurística. É importante mais uma vez referir que nenhuma das heurísticas estudadas considerava rotação de peças ou utilização de enfestos pelo que deverão ser desenvolvidas funcionalidades que consigam tirar o melhor partido destas características. Capítulo 4 Heurística Proposta Neste capítulo trata-se da definição da heurística, tendo como meta reduzir os desperdícios no processo de corte na Textilar. Na secção 4.1 será definida e descrita a heurística criada. Posteriormente será apresentado um exemplo de forma a demonstrar o funcionamento da mesma. Por fim, na secção 4.3 serão apresentados os resultados obtidos para o exemplo de teste utilizando a heurística desenvolvida. 4.1 Definição e descrição da Heurística Após uma análise acerca das heurísticas construtivas existentes na literatura acerca de Multiple Stock Size Cutting Stock Problems tomou-se a decisão de criar uma heurística baseada em level packing ou organização por níveis, já explicada no Capítulo 3, como representado na figura 4.1. Este tipo de heurísticas divide o padrão de corte em várias secções, às quais se chamam níveis, sendo o primeiro corte efetuado no sentido das mesmas. Esses mesmos níveis são depois divididos em várias stacks de items, onde poderá haver uma ou mais peças dependendo do número de estágios definido. A orientação dos níveis utilizada nesta heurística é vertical, sendo esse portanto o sentido do primeiro corte. Esta decisão foi tomada devido às medidas da mesa, com comprimento muito superior à largura, obtendo assim um padrão com vários níveis de poucas stacks. Esta orientação não deverá no entanto ser tomada como ideal, pois os resultados relativamente à orientação horizontal poderão variar de instância para instância. Após estar definida a forma como se organizam as peças, é necessário definir como as ordenar. Nas heurísticas estudadas no capítulo 3, é utilizado o comprimento das peças como unidade de comparação aquando da ordenação das peças. No entanto os casos estudados utilizavam itens pequenos heterogéneos, enquanto que neste caso de estudo os itens pequenos são de um baixo número de tipos diferentes tendo cada uma deles uma procura alta. Outro factor que difere das heurísticas estudadas é a possibilidade de rotação das peças, o que aumenta a importância de ambas as medidas (comprimento e largura) aquando da ordenação dos itens. 19 20 Heurística Proposta Figura 4.1: Organização de um padrão de corte por níveis Tendo em consideração todas estas diferenças, foi criada como unidade de ordenação das peças um novo parâmetro denominado prioridade, que inclui tanto as medidas da peça (largura e comprimento) como o número de unidades que é necessário produzir. A fórmula para cálculo deste novo parâmetro pode ser vista na equação 4.1. Pi=li∗wi∗qi(4.1) A heurística começa por ordenar as peças por prioridade, decidindo assim qual a peça seguinte a inserir no padrão de corte. Sempre que uma nova peça é inserida no padrão de corte, a prioridade da mesma é atualizada de forma a refazer os cálculos e definir qual a peça seguinte a ser inserida. De forma a melhorar a eficiência da heurística, esta inclui uma funcionalidade em que sempre que uma nova peça é inserida no padrão de corte, esta verifique se existe alguma peça que falte alocar que preencha o restante do nível. A esta funcionalidade deu-se o nome de check combos, que será mencionada mais adiante. Após o padrão de corte estar preenchido, este é fechado, faltando apenas definir o número de vezes que este vai ser reproduzido. De forma a evitar sobreprodução, ficou definido que o número de folhas de um padrão seria igual ao necessário até estar completa a produção de pelo menos uma das peças inserida nesse mesmo padrão. Caso sejam utilizados enfestos no padrão de corte, também é garantido que o número de folhas em utilização é par. O comprimento é também ajustado neste momento consoante o que ficou livre. Desta forma foi desenvolvido um código simplificado com as funcionalidades descritas. O código é baseado em ciclos. Enquanto faltarem ser produzidas peças, o código irá criar um padrão de corte. Nesta situação uma variável que define se as peças já foram testadas está a FALSE para todas aquelas que ainda não foram produzidas. Neste momento o programa entra num ciclo que irá testar se a peça pode ser inserida no padrão de corte, quer seja numa stack, num nível ou criando 4.1 Definição e descrição da Heurística 21 um novo nível se ainda houver comprimento suficiente. Caso não seja possível inserir a peça no padrão, a variável que define se esta já foi testada é posta a TRUE. Assim que forem testadas todas as peças o padrão é encerrado, o seu comprimento ajustado e um ficheiro com a informação sobre esta criado (com quantidade de peças inseridas). A variável peça testada é então posta a FALSE para peças que ainda não tenham sido completamente produzidas e outro padrão é aberto caso ainda haja necessidade. O código, numa versão simplificada, pode ser analisado no algoritmo 1. 28 Heurística Proposta Figura 4.6: Padrão de corte teste - Final Para finalizar falta apenas decidir o número de vezes que o padrão vai ser reproduzido. Cada padrão será reproduzido o número de vezes necessário de forma a que uma das peças contida no mesmo tenha a sua produção finalizada. Para além disso, visto que neste caso os enfestos são utilizados para produção de peças, o número de folhas tem de ser par. Obtém-se então como valor final 2 folhas deste padrão (completando-se assim a produção da peça do tipo 2). Tabela 4.5: Tabela de prioridades Final Largura (cm) Comprimento (cm) Quantidade em falta Prioridade Testada Peça3 260 240 10 624000 TRUE Peça1 180 290 8 417600 TRUE Peça4 50 65 61 198250 TRUE Peça2 240 220 0 0 TRUE 4.3 Resultados do exemplo teste A aplicação desenvolvida após guardar os dados acerca da alocação de peças do PF exporta ficheiros, do tipo .txt, com o código a inserir num software que nos permite visualizar o resultado dos diferentes padrões de corte, gnuplot. Nesta subsecção são apresentados os resultados obtidos para o PF de teste, que se encontra na tabela 4.1, para diferentes estágios: 2 estágios + trimming (4.3.1), 3 estágios (4.3.2) e 3 estágios + trimming(4.3.3). Devido ao tamanho da tabela, o nome das peças (Peça1, Peça2, Peça3, Peça4) foi abreviado (P1, P2, P3 e P4). 4.3 Resultados do exemplo teste 29 4.3.1 2 estágios + trimming Como esperado, os resultados para 2 estágios apresentaram resultados piores que para um número superior de estágios, não podendo alocar todas as peças do tipo 4 (50*65) nos padrões criados para alocação de outras peças de tamanho superior, tendo sido necessário criar um padrão de corte só para a produção das restantes peças. De resto, nota-se que os padrões foram bem preenchidos Na tabela 4.6 podem ser consultados os resultados finais para este número de estágios e nas figuras 4.7,4.8,4.9 e4.10 os respetivos padrões representados. Tabela 4.6: Resultados finais para 2 estágios + trimming Largura (cm) Comprimento (cm) P1 P2 P3 P4 Folhas Área total (cm) Padrão 1 400 960 3,5 3,0 0,0 0,5 2 768 000 Padrão 2 400 960 0,0 0,0 3,5 13,0 4 1 536 000 Padrão 3 400 990 5,5 0,0 0,0 5,5 2 792 000 Padrão 4 400 50 0,0 0,0 0,0 6,0 1 20 000 Área total utilizada 3 116 000 Área total necessária (somatório de todas as peças) 1 951 300 Eficiência 63% Figura 4.7: Resultados teste para 2 estágios + trimming: Padrão No1 30 Heurística Proposta Figura 4.8: Resultados teste para 2 estágios + trimming: Padrão No2 Figura 4.9: Resultados teste para 2 estágios + trimming: Padrão No3 4.3 Resultados do exemplo teste 31 Figura 4.10: Resultados teste para 2 estágios + trimming: Padrão No4 32 Heurística Proposta 4.3.2 3 estágios Ao poder utilizar 3 estágios já se verificou uma melhoria significativa em relação aos resultados com 2 estágios, tanto em número de folhas utilizadas como de eficiência da heurística. No entanto, devido à alta produção exigida da peça número 3, continuou a ser necessário um quarto padrão de corte que baixa significativamente a eficiência do resultado. Na tabela 4.7 podem ser consultados os resultados dos padrões, e nas figuras 4.11,4.12,4.13 e4.14 as respetivas representações. Tabela 4.7: Resultados finais para 3 estágios sem trimming Largura (cm) Comprimento (cm) P1 P2 P3 P4 Folhas Área total (cm) Padrão 1 400 960 3,5 3,0 0,0 1,5 2 768 000 Padrão 2 400 960 0,0 0,0 3,5 41,0 2 768 000 Padrão 3 400 990 5,5 0,0 0,0 0,0 2 792 000 Padrão 4 400 780 0,0 0,0 3,0 0,0 1 312 000 Área total utilizada 2 640 000 Área total necessária (somatório de todas as peças) 1 951 300 Eficiência 74% Figura 4.11: Resultados teste para 3 estágios sem trimming: Padrão No1 4.3 Resultados do exemplo teste 33 Figura 4.12: Resultados teste para 3 estágios sem trimming: Padrão No2 Figura 4.13: Resultados teste para 3 estágios sem trimming: Padrão No3 34 Heurística Proposta Figura 4.14: Resultados teste para 3 estágios sem trimming: Padrão No4 4.4 Conclusões 35 4.3.3 3 estágios + trimming A utilização de trimming com 3 estágios, no caso de teste utilizado, não provocou nenhuma melhoria em termos de eficiência da heurística, visto que apenas permitiu inserção de mais peças do tipo 4 (50*65) no 1opadrão, como se pode ver na figura 4.15. Todos os outros padrões mantiveram-se constantes. Os resultados finais do padrão podem ser consultados na tabela 4.8. Tabela 4.8: Resultados finais para 3 estágios + trimming Largura (cm) Comprimento (cm) P1 P2 P3 P4 Folhas Área total (cm) Padrão 1 400 960 3,5 3,0 0,0 4,5 2 768 000 Padrão 2 400 960 0,0 0,0 3,5 41,0 2 768 000 Padrão 3 400 990 5,5 0,0 0,0 0,0 2 792 000 Padrão 4 400 780 0,0 0,0 3,0 0,0 1 312 000 Área total utilizada 2 640 000 Área total necessária (somatório de todas as peças) 1 951 300 Eficiência 74% Figura 4.15: Resultados teste para 3 estágios + trimming: Padrão No1 4.4 Conclusões Os resultados obtidos para este exemplo de teste demonstraram que a utilização de um número superior de estágios provoca um aumento da eficiência da heurística, tal como esperado. No caso 36 Heurística Proposta do trimming, apesar de não haver um aumento da eficiência neste exemplo, existem casos para os quais se poderá verificar uma melhoria. O exemplo de teste, no entanto, não é suficiente para a análise da heurística, pois este foi criado usando um pedido de fabrico aleatório podendo nem sequer corresponder à realidade da empresa. Deverão portanto ser efetuados mais testes de forma a estudar e aprimorar a heurística criada. Capítulo 5 Resultados Neste capítulo são apresentados os resultados obtidos com a heurística desenvolvida. Na secção 5.1 é apresentada uma caracterização das instâncias analisadas e na secção 5.2 podem ser vistos os resultados obtidos assim como a discussão dos mesmos. 5.1 Caracterização das instâncias Para obtenção de resultados foram analisadas 15 instâncias, fornecidas de pedidos reais efetuados à empresa Têxtilar. Cada instância contém informação acerca das medidas das diferentes peças (em cm), quantidades a serem produzidas, possibilidade de rotação e utilização de enfestos, referências das peças e rolos e larguras dos rolos (em cm). O comprimento máximo da mesa é de 1500cm pelo que esse foi o valor base utilizado para criação de padrões de corte. Na tabela 5.1 são apresentados os dados que caracterizam cada uma das instâncias, assim como os valores mínimos e máximos para as medidas das peças e larguras dos rolos. Espera-se que as instâncias que contenham peças de dimensão mais reduzida consigam obter uma percentagem de desperdício menor pois as peças mais pequenas poderão preencher os espaços deixados pelas peças de maior dimensão. Nas instâncias em que as peças têm dimensões mínimas maiores os desperdícios deverão ser também maiores, visto que não há peças para preencher os espaços de dimensão menor. Quanto às peças de maiores dimensões não há nenhuma conclusão a ser retirada pois estas terão, em príncipio, uma maior prioridade sendo por isso a base dos padrões de corte e não as que irão efetuar o preenchimento dos espaços livres. Estas conclusões estão no entanto sujeitas a outros fatores (tais como quantidade de produção de peças de maior dimensão, quantidade de larguras disponíveis para análise e número de peças a serem produzidas) não devendo por isso funcionar como medida de análise para a eficiência da heurística. A eficiência deverá ser feita comparando os diferentes números de estágios e possibilidade de rotação e inserção de meias-peças para as mesmas instâncias. 37 44 Conclusão e trabalhos futuros Anexo A Anexos A.1 Descrição das funções do código simplificado A.1.1 criar pecas Esta função tem como objetivo a obtenção dos dados acerca do PF contidos num ficheiro txt. Nesse ficheiro podem ser extraídas informações acerca de dimensões, quantidade a produzir, possibilidade de rotação e possibilidade de utilização de enfestos das diferentes peças. A.1.2 atualizar prioridades Esta função tem como objetivo reordenar o array de peças consoante a sua prioridade. A.1.3 seleccionar peca Esta função tem como objetivo seleccionar a seguinte peça a ser produzida. Essa será equivalente à peça com maior prioridade que ainda tenha unidades a serem produzidas e não tenha sido ainda testada neste padrão de corte. A.1.4 ha pecas por testar Esta função retorna um valor binário que indica se ainda há peças que ainda não foram testadas neste padrão de corte e ainda tenham unidades a serem produzidas. A.1.5 possivel inserir em stack Esta função retorna um valor binário que indica se a peça pode ser inserida em alguma stack já criada pertencente a este padrão de corte. 45 46 Anexos A.1.6 possivel inserir em nivel peca inteira Esta função retorna um valor booleano que indica se a peça pode ser inserida em algum nível já criado, criando uma nova stack nesse nível e inserindo a peça na mesma. Essa verificação é feita apenas em níveis contendo a peça completa, não contando o nível que utiliza enfestos. A.1.7 possivel inserir em nivel meia peca Esta função faz a mesma verificação que a função anterior mas no nível que utilizem os enfestos da mesada. A.1.8 possivel criar nivel Esta função retorna um booleano que indica se é possível criar um nível novo com o comprimento igual ao da peça (ou largura caso seja possível rodar a mesma). Se for possível, irá ser criado um nível novo com uma stack nova na qual será inserida a peça. A.1.9 possivel criar nivel meia peca Esta função faz a mesma verificação que a anterior mas para o nível que utiliza os enfestos da mesada. Só pode haver um nível deste tipo por padrão de corte. A.1.10 verificar posicao Esta função tem como objetivo verificar se a peça pode ser inserida na sua posição natural ou se é necessário rodar a mesma. Caso possa ser inserida de ambas as maneiras, a heurística toma como valor default a posição natural da peça, a menos que na outra posição exista um possível combo (explicado na função seguinte). A.1.11 verificar combos Esta função tem como objetivo verificar se existe, juntamente com a peça a ser inserida, outra peça que complete o restante do nível garantindo a utilização de toda a largura do nível. A.1.12 fechar padrao Esta função tem como objetivo encerrar o padrão de corte, funcionalidade que existe por razões de logística da aplicação. A.1.13 ajustar comprimento do padrao Esta função tem como objetivo ajustar o comprimento do padrão de corte reduzindo a quantidade de tecido desperdiçado. A.1 Descrição das funções do código simplificado 47 A.1.14 criar ficheiro do padrao Esta função tem como objetivo a criação dos ficheiros .txt com o código a ser copiado para o gnuplot, onde poderá ser visualizado o resultado final do padrão de corte. A.1.15 reset pecas testadas Esta função tem como objetivo mudar os valores de peça testada para false, visto que o padrão de corte irá mudar. Esta mudança não acontece para as peças que já não necessitem de ser produzidas. A.1.16 fechar niveis e stacks Esta função tem um objetivo idêntico à função "close bin"sendo esta utilizada para encerrar os níveis e stacks presentes no padrão de corte atual, por motivos logísticos da aplicação. A.1.17 criar ficheiros de info Esta função tem como objetivo exportar um .txt onde pode ser consultado quantas folhas devem ser produzidas de cada padrão de corte criado. 48 Anexos Referências [1] Bernardo Cerqueira. KAIZEN NA INDÚSTRIA TÊXTIL : Uma abordagem ao aumento de produtividade e redução de desperdício. 2013. [2] Gerhard Wäscher, Heike Hauß ner, e Holger Schumann. An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3):1109–1130, 2007. [3] Harald Dyckhoff. A typology of cutting and packing problems. European Journal of Operational Research, 44(2):145–159, 1990. [4] R E Gomory e P C Gilmore. Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research, 13(1):94–120, 1965. [5] Andrea Lodi. Algorithms for Two-Dimensional Bin Packing and Assignment Problems. Universita degli Studi di Bologna, 1999. [6] Jakob Puchinger e Günther R. Raidl. Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research, 183(3):1304–1327, Dezembro 2007. 49