{"id":37108,"date":"2019-10-31T22:15:47","date_gmt":"2019-10-31T19:15:47","guid":{"rendered":"https:\/\/prohoster.info\/blog\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1\/"},"modified":"2019-10-31T22:15:47","modified_gmt":"2019-10-31T19:15:47","slug":"diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1","status":"publish","type":"post","link":"https:\/\/prohoster.info\/pt\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1","title":{"rendered":"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/89e9927c86cd36ee5b4ab37b5c0753c9.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nNeste artigo, vamos explicar como resolvemos o problema da falta de espa\u00e7os vagos no armaz\u00e9m e o desenvolvimento de um algoritmo de otimiza\u00e7\u00e3o discreta para resolver essa tarefa. Vamos falar sobre como \"constru\u00edmos\" o modelo matem\u00e1tico do problema de otimiza\u00e7\u00e3o e sobre as dificuldades inesperadas que encontramos ao processar os dados de entrada para o algoritmo.<\/p>\n<p>Se voc\u00ea est\u00e1 interessado nas aplica\u00e7\u00f5es da matem\u00e1tica nos neg\u00f3cios e n\u00e3o tem medo de transforma\u00e7\u00f5es de f\u00f3rmulas a n\u00edvel de 5\u00aa s\u00e9rie, sinta-se \u00e0 vontade para continuar!<\/p>\n<p>Este artigo ser\u00e1 \u00fatil para aqueles que implementam <i>sistemas WMS, trabalham na ind\u00fastria de log\u00edstica de armaz\u00e9m ou produ\u00e7\u00e3o, al\u00e9m de programadores que se interessam pelas aplica\u00e7\u00f5es da matem\u00e1tica nos neg\u00f3cios e otimiza\u00e7\u00e3o de processos na empresa.<\/i>-sistemas, atua na \u00e1rea de log\u00edstica de armaz\u00e9ns ou produ\u00e7\u00e3o, assim como para programadores interessados em aplica\u00e7\u00f5es matem\u00e1ticas nos neg\u00f3cios e na otimiza\u00e7\u00e3o de processos na empresa.<\/p>\n<p><noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h4>Parte introdut\u00f3ria<\/h4>\n<p>\nEsta publica\u00e7\u00e3o d\u00e1 continuidade a uma s\u00e9rie de artigos onde compartilhamos nossa experi\u00eancia bem-sucedida na implementa\u00e7\u00e3o de algoritmos de otimiza\u00e7\u00e3o nos processos de armaz\u00e9m. <\/p>\n<p>Em <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/463289\/\">artigo anterior<\/a><\/noindex> descreve as especificidades do armaz\u00e9m onde implementamos <i>sistemas WMS, trabalham na ind\u00fastria de log\u00edstica de armaz\u00e9m ou produ\u00e7\u00e3o, al\u00e9m de programadores que se interessam pelas aplica\u00e7\u00f5es da matem\u00e1tica nos neg\u00f3cios e otimiza\u00e7\u00e3o de processos na empresa.<\/i>o sistema, e tamb\u00e9m conta por que precis\u00e1vamos resolver o problema de clusteriza\u00e7\u00e3o de lotes de produtos remanescentes durante a implementa\u00e7\u00e3o <i>sistemas WMS, trabalham na ind\u00fastria de log\u00edstica de armaz\u00e9m ou produ\u00e7\u00e3o, al\u00e9m de programadores que se interessam pelas aplica\u00e7\u00f5es da matem\u00e1tica nos neg\u00f3cios e otimiza\u00e7\u00e3o de processos na empresa.<\/i>do sistema, e como realocamos esse processo.<\/p>\n<p>Quando terminamos de escrever o artigo sobre algoritmos de otimiza\u00e7\u00e3o, ele ficou muito extenso, ent\u00e3o decidimos dividir o material acumulado em duas partes:<\/p>\n<ul>\n<li>Na primeira parte (este artigo), falaremos sobre como \"constru\u00edmos\" o modelo matem\u00e1tico da tarefa e as grandes dificuldades que encontramos inesperadamente ao processar e transformar os dados de entrada para o algoritmo.<\/li>\n<li>Na segunda parte, examinaremos detalhadamente a implementa\u00e7\u00e3o do algoritmo na linguagem <i>C++<\/i>, realizaremos um experimento computacional e resumiremos a experi\u00eancia que obtivemos durante a implementa\u00e7\u00e3o dessas \"tecnologias inteligentes\" nos processos de neg\u00f3cios do cliente.<\/li>\n<\/ul>\n<p>\nComo ler o artigo. Se voc\u00ea leu o artigo anterior, pode ir direto para a se\u00e7\u00e3o \"Revis\u00e3o das solu\u00e7\u00f5es existentes\"; caso contr\u00e1rio, a descri\u00e7\u00e3o do problema a ser resolvido est\u00e1 no spoiler abaixo.<\/p>\n<p><b class=\"spoiler_title\">Descri\u00e7\u00e3o do problema a ser resolvido no armaz\u00e9m do cliente<\/b><\/p>\n<h4>O ponto cr\u00edtico nos processos<\/h4>\n<p>\nEm 2018, realizamos um projeto de implementa\u00e7\u00e3o do <i>sistemas WMS, trabalham na ind\u00fastria de log\u00edstica de armaz\u00e9m ou produ\u00e7\u00e3o, al\u00e9m de programadores que se interessam pelas aplica\u00e7\u00f5es da matem\u00e1tica nos neg\u00f3cios e otimiza\u00e7\u00e3o de processos na empresa.<\/i>sistema no armaz\u00e9m \"Casa Comercial LD\" na cidade de Chelyabinsk. Implantamos o produto \"1C-Log\u00edstica: Gest\u00e3o de Armaz\u00e9m 3\" em 20 esta\u00e7\u00f5es de trabalho: operadores <i>sistemas WMS, trabalham na ind\u00fastria de log\u00edstica de armaz\u00e9m ou produ\u00e7\u00e3o, al\u00e9m de programadores que se interessam pelas aplica\u00e7\u00f5es da matem\u00e1tica nos neg\u00f3cios e otimiza\u00e7\u00e3o de processos na empresa.<\/i>, armazenistas, motoristas de empilhadeiras. O armaz\u00e9m tem uma \u00e1rea m\u00e9dia de cerca de 4 mil m\u00b2, com 5000 c\u00e9lulas e 4500 SKUs. No armaz\u00e9m, s\u00e3o armazenadas v\u00e1lvulas de esfera de fabrica\u00e7\u00e3o pr\u00f3pria em diversos tamanhos, de 1 kg a 400 kg. Os estoques s\u00e3o mantidos por lotes, uma vez que \u00e9 necess\u00e1rio selecionar os produtos pelo FIFO.<\/p>\n<p>Durante o projeto dos esquemas de automa\u00e7\u00e3o dos processos de armazenagem, nos deparamos com o problema existente do armazenamento ineficiente dos estoques. A especificidade do armazenamento e empilhamento das v\u00e1lvulas \u00e9 tal que em uma c\u00e9lula de armazenamento unit\u00e1rio pode estar somente a nomenclatura de um lote (veja a figura 1). Os produtos chegam ao armaz\u00e9m diariamente e cada entrega \u00e9 um lote separado. Assim, ao final de um m\u00eas de opera\u00e7\u00e3o do armaz\u00e9m, s\u00e3o criados 30 lotes distintos, sendo que cada um deve ser armazenado em uma c\u00e9lula separada. Os itens s\u00e3o frequentemente retirados n\u00e3o em paletes inteiros, mas unidade por unidade, e como resultado, na \u00e1rea de sele\u00e7\u00e3o unit\u00e1ria, muitas c\u00e9lulas apresentam a seguinte situa\u00e7\u00e3o: em uma c\u00e9lula com volume superior a 1m3, est\u00e3o armazenadas v\u00e1rias v\u00e1lvulas que ocupam menos de 5-10% do volume da c\u00e9lula. <\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a7c03f2302c3be02c00c670453353f16.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Figura 1. Foto de v\u00e1rias unidades em uma c\u00e9lula<\/i><\/p>\n<p>H\u00e1 um claro uso n\u00e3o otimizado da capacidade do armaz\u00e9m. Para ilustrar a gravidade da situa\u00e7\u00e3o, posso fornecer n\u00fameros: em m\u00e9dia, existem de 100 a 300 dessas c\u00e9lulas com volume superior a 1m3 contendo \"restos m\u00ednimos\" em diferentes per\u00edodos de opera\u00e7\u00e3o do armaz\u00e9m. Como o armaz\u00e9m \u00e9 relativamente pequeno, durante as temporadas de carga, esse fator se torna um \"gargalo\" que atrasa significativamente os processos de recebimento e expedi\u00e7\u00e3o.<\/p>\n<h4>Ideia para resolver o problema<\/h4>\n<p>\nA ideia surgiu: reunir os lotes com datas mais pr\u00f3ximas em um \u00fanico lote e armazenar esses restos com um lote unificado compactamente juntos em uma c\u00e9lula, ou em v\u00e1rias, se houver falta de espa\u00e7o em uma para acomodar toda a quantidade de restos. Um exemplo dessa \"compacta\u00e7\u00e3o\" \u00e9 ilustrado na figura 2.<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/792f114a7afa6272a6d152a784650681.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Figura 2. Diagrama de compacta\u00e7\u00e3o de restos nas c\u00e9lulas<\/i><\/p>\n<p>Isso permite reduzir significativamente o espa\u00e7o de armazenamento utilizado, que ser\u00e1 destinado a novos produtos. Em situa\u00e7\u00f5es de sobrecarga das capacidades de armazenamento, essa medida \u00e9 extremamente necess\u00e1ria, pois, caso contr\u00e1rio, pode simplesmente n\u00e3o haver espa\u00e7o livre para a coloca\u00e7\u00e3o de novos produtos, o que levar\u00e1 a um impasse nos processos de armazenamento e alimenta\u00e7\u00e3o e, consequentemente, a um bloqueio na aceita\u00e7\u00e3o e expedi\u00e7\u00e3o. Antes da implementa\u00e7\u00e3o do sistema WMS, essa opera\u00e7\u00e3o era realizada manualmente, o que era ineficiente, j\u00e1 que o processo de busca por estoques adequados nas c\u00e9lulas era bastante demorado. Agora, com a implementa\u00e7\u00e3o do sistema WMS, decidimos automatizar, acelerar e tornar o processo mais inteligente.<\/p>\n<p>O processo de resolu\u00e7\u00e3o dessa tarefa \u00e9 dividido em 2 etapas: <\/p>\n<ul>\n<li>na primeira etapa, encontramos grupos de partidas pr\u00f3ximos em data para compacta\u00e7\u00e3o (essa tarefa \u00e9 dedicada <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/463289\/\">artigo anterior<\/a><\/noindex>);<\/li>\n<li>na segunda etapa, calculamos o arranjo mais compacto poss\u00edvel dos estoques de produtos nas c\u00e9lulas para cada grupo de partidas. <\/li>\n<\/ul>\n<p>\nNeste artigo, focaremos na segunda etapa do algoritmo.<\/p>\n<h4>An\u00e1lise das solu\u00e7\u00f5es existentes<\/h4>\n<p>\nAntes de passar \u00e0 descri\u00e7\u00e3o dos algoritmos que desenvolvemos, \u00e9 importante fazer uma breve an\u00e1lise dos sistemas que j\u00e1 existem no mercado <i>sistemas WMS, trabalham na ind\u00fastria de log\u00edstica de armaz\u00e9m ou produ\u00e7\u00e3o, al\u00e9m de programadores que se interessam pelas aplica\u00e7\u00f5es da matem\u00e1tica nos neg\u00f3cios e otimiza\u00e7\u00e3o de processos na empresa.<\/i>, nos quais esse tipo de funcionalidade de compress\u00e3o ideal foi implementado.<\/p>\n<p>Em primeiro lugar, \u00e9 necess\u00e1rio destacar o produto '1C: Enterprise 8. WMS Log\u00edstica. Gest\u00e3o de Armaz\u00e9m 4', que pertence e \u00e9 distribu\u00eddo pela empresa 1C e est\u00e1 relacionado \u00e0 quarta gera\u00e7\u00e3o <i>sistemas WMS, trabalham na ind\u00fastria de log\u00edstica de armaz\u00e9m ou produ\u00e7\u00e3o, al\u00e9m de programadores que se interessam pelas aplica\u00e7\u00f5es da matem\u00e1tica nos neg\u00f3cios e otimiza\u00e7\u00e3o de processos na empresa.<\/i>- sistemas, desenvolvidos pela empresa AXELOT. Este sistema possui a funcionalidade de compress\u00e3o, que visa unir estoques dispersos de produtos em uma \u00fanica c\u00e9lula comum. Vale ressaltar que a funcionalidade de compress\u00e3o nesse sistema inclui tamb\u00e9m outras capacidades, como a corre\u00e7\u00e3o do posicionamento dos produtos nas c\u00e9lulas de acordo com suas classes ABC, mas n\u00e3o abordaremos esses pontos. <\/p>\n<p>Ao analisar o c\u00f3digo do sistema \"1C: Empresa 8. WMS Log\u00edstica. Gest\u00e3o de Armaz\u00e9m 4\" (que nesta parte da funcionalidade \u00e9 aberto), pode-se concluir o seguinte. O algoritmo de compress\u00e3o de res\u00edduos implementa uma l\u00f3gica linear bastante primitiva e n\u00e3o h\u00e1 como falar de uma compress\u00e3o \"otimizada\". Evidentemente, ele n\u00e3o prev\u00ea a clusteriza\u00e7\u00e3o de lotes. V\u00e1rios clientes que tiveram esse sistema implementado reclamaram dos resultados do planejamento de compress\u00e3o. Por exemplo, frequentemente na pr\u00e1tica, ao realizar a compress\u00e3o, surgia a situa\u00e7\u00e3o em que 100 unidades de estoque de um determinado item eram planejadas para serem movidas para outro local onde havia 1 unidade, embora o ideal em termos de economia de tempo fosse fazer o contr\u00e1rio.<\/p>\n<p>Da mesma forma, a funcionalidade de compress\u00e3o de res\u00edduos de produtos nas posi\u00e7\u00f5es \u00e9 anunciada em muitos sistemas estrangeiros, <i>sistemas WMS, trabalham na ind\u00fastria de log\u00edstica de armaz\u00e9m ou produ\u00e7\u00e3o, al\u00e9m de programadores que se interessam pelas aplica\u00e7\u00f5es da matem\u00e1tica nos neg\u00f3cios e otimiza\u00e7\u00e3o de processos na empresa.<\/i>-mas, infelizmente, n\u00e3o temos nem avalia\u00e7\u00f5es reais sobre a efic\u00e1cia do funcionamento dos algoritmos (isso \u00e9 um segredo comercial), nem uma ideia da profundidade de sua l\u00f3gica (software propriet\u00e1rio com c\u00f3digo fechado), portanto, n\u00e3o podemos julgar.<\/p>\n<h4>Busca de um modelo matem\u00e1tico para o problema<\/h4>\n<p>\nPara projetar algoritmos de qualidade para a resolu\u00e7\u00e3o do problema, \u00e9 necess\u00e1rio primeiro formular esse problema de maneira clara e matem\u00e1tica, o que faremos.<\/p>\n<p>Existem muitas posi\u00e7\u00f5es <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/bfff1fb95dd0c633ada02b9398778eab.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, nas quais est\u00e3o os res\u00edduos de um determinado produto. Daqui em diante, chamaremos essas posi\u00e7\u00f5es de posi\u00e7\u00f5es-doadoras. Denotemos <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/50ef693482cd4cb27410b30b0bc107b1.jpeg\" style=\"display:block;margin: 0 auto;\" \/> o volume do produto que est\u00e1 na posi\u00e7\u00e3o <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/dc7faf1656fb12c8e467fe3a5b8977fa.jpeg\" style=\"display:block;margin: 0 auto;\" \/>$.<\/p>\n<p>\u00c9 importante mencionar que, no procedimento de compress\u00e3o, pode participar apenas um produto de um \u00fanico lote, ou de v\u00e1rios lotes, previamente agrupados em um cluster (leia-se <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/463289\/\">artigo anterior<\/a><\/noindex>), o que \u00e9 devido \u00e0 particularidade de armazenamento e arruma\u00e7\u00e3o dos produtos. Para produtos diferentes ou diferentes clusters de lotes, deve ser iniciada uma sua pr\u00f3pria e separada procedimento de compress\u00e3o.<\/p>\n<p>Existem muitas posi\u00e7\u00f5es <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b9aafca691626263d8ecc2faed8dfcfe.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, nos quais os res\u00edduos das posi\u00e7\u00f5es-doadoras podem ser potencialmente colocados. Chamaremos essas posi\u00e7\u00f5es de posi\u00e7\u00f5es-conteiner. Podem ser tanto posi\u00e7\u00f5es livres no armaz\u00e9m quanto posi\u00e7\u00f5es-doadoras de um conjunto <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/25731bc72091e2284e76c434d2abdcfd.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Sempre um conjunto <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d407f97344131a3056b1eab1d3dd7dcd.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u00e9 um subconjunto <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/581806d446f3d8c91927045249698e71.jpeg\" style=\"display:block;margin: 0 auto;\" \/>.<\/p>\n<p>Para cada posi\u00e7\u00e3o <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b084d5852a1e4f00d2498640534d66e9.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do conjunto <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/236efb40a21865f78240c8e14303cc2e.jpeg\" style=\"display:block;margin: 0 auto;\" \/> foram estabelecidas restri\u00e7\u00f5es de capacidade <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/fe253cfe5f2aa39bc8e064674fb206f8.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, medidos em dm\u00b3. Um dm\u00b3 representa um cubo com lados de 10 cm. A produ\u00e7\u00e3o armazenada no armaz\u00e9m \u00e9 suficientemente grande, portanto, neste caso, essa discretiza\u00e7\u00e3o \u00e9 mais do que adequada. <\/p>\n<p>Dada uma matriz das menores dist\u00e2ncias <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/48c133b0affa17f6a2367a02241d5f17.jpeg\" style=\"display:block;margin: 0 auto;\" \/> em metros entre cada par de c\u00e9lulas <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/8fd860e331a8e42dd258857bdf580c05.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, onde <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/feb9a48c6e9e4ccd8e9fa1db5565e96e.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d9a48a8a22ea984d0769373c5620c99a.jpeg\" style=\"display:block;margin: 0 auto;\" \/> pertencem a conjuntos <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e2dd20fda8a8b0b5ea2173c14f04fe00.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/0dabafdb55ac6b8495f6d5f657d6c01d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> respectivamente. <\/p>\n<p>Denotemos <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/2994defad9bb0a44741f31a85273abf2.jpeg\" style=\"display:block;margin: 0 auto;\" \/> os 'custos' de movimenta\u00e7\u00e3o de produtos da c\u00e9lula<img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a2e54425ec786d3a88290dda47f4b9cb.jpeg\" style=\"display:block;margin: 0 auto;\" \/> para a c\u00e9lula <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/bf4a9f1a1f396a9b7b6244cf8c77ecc8.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Denotemos <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/6f4c10386fc638f6ca37e0ccdcf4ccb4.jpeg\" style=\"display:block;margin: 0 auto;\" \/> os 'custos' de selecionar um cont\u00eainer <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/613d619ea5951551427f0cd45c7f79bf.jpeg\" style=\"display:block;margin: 0 auto;\" \/> para mover os restos de outras c\u00e9lulas. Como e em quais unidades de medida os valores ser\u00e3o calculados <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/22130f203fde6271e33cba0db14d6a80.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d75c50be3ee4f8e02a9523f2d2109f0d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> veremos adiante (veja a se\u00e7\u00e3o prepara\u00e7\u00e3o dos dados de entrada), por enquanto, \u00e9 suficiente dizer que tais grandezas ser\u00e3o diretamente proporcionais \u00e0s quantidades <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/5e4e80f122ac1fe43f94de2726c0d3b7.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1b6a9d41ba4ad68d5a5fbae883b80596.jpeg\" style=\"display:block;margin: 0 auto;\" \/> respectivamente.<\/p>\n<p>Denotemos atrav\u00e9s de <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1ebfe4179740aff474a78d11a004aaa7.jpeg\" style=\"display:block;margin: 0 auto;\" \/> uma vari\u00e1vel que assume o valor 1, se os restos da c\u00e9lula <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/48f9789788c38746ba4ac0c947e0a4ca.jpeg\" style=\"display:block;margin: 0 auto;\" \/> s\u00e3o movidos para o cont\u00eainer <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/58ce0b4c9bfb946c00bffdc0c50a05d6.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, e 0 caso contr\u00e1rio. Denotemos atrav\u00e9s de <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/642d5627193c55922be5274826b75cb4.jpeg\" style=\"display:block;margin: 0 auto;\" \/> uma vari\u00e1vel que assume o valor 1, se o cont\u00eainer <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/6939c9f4daf2ecd531d9c2518c03401d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> cont\u00e9m restos do produto, e 0 caso contr\u00e1rio.<\/p>\n<p><b>A tarefa \u00e9 formulada da seguinte maneira<\/b>: \u00e9 necess\u00e1rio encontrar um conjunto de cont\u00eaineres <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d6065db66f210083181dabb39f0e9e16.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e assim 'anexar' as c\u00e9lulas doadoras aos cont\u00eaineres, de modo a minimizar a fun\u00e7\u00e3o<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/68d7f0271f9761fff2c762e0fe6f5207.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>sob restri\u00e7\u00f5es<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d57b8752aa4a8140e239dfa7fdc9ec36.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Assim, durante o c\u00e1lculo da solu\u00e7\u00e3o do problema, buscamos: <\/p>\n<ul>\n<li>em primeiro lugar, economizar espa\u00e7o de armazenamento; <\/li>\n<li>em segundo lugar, economizar o tempo dos estoquistas. <\/li>\n<\/ul>\n<p>\nA \u00faltima restri\u00e7\u00e3o significa que n\u00e3o podemos mover produtos para um cont\u00eainer que n\u00e3o foi escolhido, e, consequentemente, n\u00e3o 'incorremos em custos' pela sua escolha. Essa restri\u00e7\u00e3o tamb\u00e9m significa que o volume de produtos movidos das c\u00e9lulas para o cont\u00eainer n\u00e3o deve exceder a capacidade do cont\u00eainer. Consideraremos a solu\u00e7\u00e3o do problema como um conjunto de cont\u00eaineres <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/db0f987f2d388ad1394d21404e183c93.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e m\u00e9todos de anexa\u00e7\u00e3o das c\u00e9lulas doadoras aos cont\u00eaineres.<\/p>\n<p>Essa formula\u00e7\u00e3o do problema de otimiza\u00e7\u00e3o n\u00e3o \u00e9 nova e foi estudada por muitos matem\u00e1ticos desde o in\u00edcio dos anos 80 do s\u00e9culo passado. Na literatura estrangeira, existem 2 problemas de otimiza\u00e7\u00e3o com um modelo matem\u00e1tico apropriado: <noindex><a rel=\"nofollow\" href=\"http:\/\/www.math.nsc.ru\/AP\/benchmarks\/CFLP\/cflp.html\">Single-Source Capacitated Facility Location Problem<\/a><\/noindex> e <noindex><a rel=\"nofollow\" href=\"https:\/\/waset.org\/publications\/10002290\/a-survey-of-discrete-facility-location-problems\">Multi-Source Capacitated Facility Location Problem<\/a><\/noindex> (sobre as diferen\u00e7as das tarefas, falaremos mais adiante). Vale ressaltar que, na literatura matem\u00e1tica, a formula\u00e7\u00e3o dessas duas tarefas de otimiza\u00e7\u00e3o \u00e9 feita em termos de localiza\u00e7\u00e3o de empresas no territ\u00f3rio, da\u00ed o nome 'Localiza\u00e7\u00e3o de Instala\u00e7\u00f5es'. Em grande parte, isso \u00e9 uma quest\u00e3o de tradi\u00e7\u00e3o, pois a necessidade de resolver tais problemas combinat\u00f3rios surgiu da \u00e1rea de log\u00edstica, principalmente da ind\u00fastria militar nos anos 50 do s\u00e9culo passado. Em termos de localiza\u00e7\u00e3o de empresas, esses problemas s\u00e3o formulados assim: <\/p>\n<ul>\n<li>H\u00e1 um conjunto finito de cidades onde \u00e9 potencialmente poss\u00edvel localizar empresas de produ\u00e7\u00e3o (daqui em diante chamadas de cidades-producers). Para cada cidade-producer, s\u00e3o especificados os custos de abertura de uma empresa nela, assim como a limita\u00e7\u00e3o em rela\u00e7\u00e3o \u00e0 capacidade de produ\u00e7\u00e3o da empresa que ser\u00e1 aberta.<\/li>\n<li>H\u00e1 um conjunto finito de cidades onde, de fato, est\u00e3o os clientes (daqui em diante chamadas de cidades-clientes). Para cada cidade-cliente, \u00e9 especificado o volume de demanda pelo produto. Para simplificar, vamos considerar que o produto que \u00e9 produzido pelas empresas e consumido pelos clientes \u00e9 o mesmo.<\/li>\n<li>Para cada par de cidade-producer e cidade-cliente, \u00e9 especificado o valor dos custos de transporte para entregar o volume necess\u00e1rio de produto do produtor para o cliente.<\/li>\n<\/ul>\n<p>\n\u00c9 necess\u00e1rio encontrar em quais cidades abrir empresas e como vincular os clientes a essas empresas, de modo que:<\/p>\n<ul>\n<li>Os custos totais de abertura das empresas e os custos de transporte sejam m\u00ednimos;<\/li>\n<li>O volume de demanda dos clientes vinculados a alguma empresa aberta n\u00e3o ex\u00e9dia a capacidade de produ\u00e7\u00e3o dessa empresa.<\/li>\n<\/ul>\n<p>\nAgora vale a pena mencionar a \u00fanica diferen\u00e7a entre essas duas tarefas cl\u00e1ssicas:<\/p>\n<ul>\n<li>Single-Source Capacitated Facility Location Problem \u2013 o cliente \u00e9 atendido apenas por uma \u00fanica empresa aberta;<\/li>\n<li>Multi-Source Capacitated Facility Location Problem \u2013 o cliente pode ser atendido por v\u00e1rias empresas abertas ao mesmo tempo.<\/li>\n<\/ul>\n<p>\nEssa distin\u00e7\u00e3o entre as duas tarefas, \u00e0 primeira vista, parece insignificante, mas, na verdade, leva a uma estrutura combinat\u00f3ria completamente diferente dessas tarefas e, como consequ\u00eancia, a algoritmos de solu\u00e7\u00e3o tamb\u00e9m completamente diferentes. A diferen\u00e7a entre as tarefas \u00e9 demonstrada na figura abaixo.<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/77962906c7de2fced174d4a2b7785cc2.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Fig.3. a) Multi-Source Capacitated Facility Location Problem<\/i><\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/0242437e488a1aea0f00ce9ede02886d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Fig.3. b) Single-Source Capacitated Facility Location Problem<\/i><\/p>\n<p>Ambas as tarefas <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b16678811fceca32d18c94e71cfaa603.jpeg\" style=\"display:block;margin: 0 auto;\" \/>-s\u00e3o dif\u00edceis, ou seja, n\u00e3o existe um algoritmo exato que resolva tal problema em tempo polinomial em rela\u00e7\u00e3o ao tamanho dos dados de entrada. Em termos mais simples, todos os algoritmos exatos para resolver o problema funcionar\u00e3o em tempo exponencial, embora possam ser mais r\u00e1pidos do que uma busca exaustiva. Dado que o problema <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/09f42b4b905d9bdc3f00f21098f84ad7.jpeg\" style=\"display:block;margin: 0 auto;\" \/>-\u00e9 dif\u00edcil, vamos considerar apenas heur\u00edsticas aproximadas, ou seja, algoritmos que calcular\u00e3o solu\u00e7\u00f5es que s\u00e3o consistentemente muito pr\u00f3ximas das \u00f3timas e que funcionar\u00e3o de forma suficientemente r\u00e1pida. Se houver interesse em tais problemas, voc\u00ea pode encontrar uma boa vis\u00e3o geral em russo aqui.<\/p>\n<p>Se traduzirmos isso para a terminologia do nosso problema de compress\u00e3o \u00f3tima de produtos em c\u00e9lulas, temos:<\/p>\n<ul>\n<li>cidades-clientes \u2013 s\u00e3o c\u00e9lulas-doadoras <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e6db70dbb85d1c7249f4c30e97e2942e.jpeg\" style=\"display:block;margin: 0 auto;\" \/> com os estoques remanescentes, <\/li>\n<li>cidades-produtoras \u2013 s\u00e3o c\u00e9lulas-conteineres <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/5ef31fe0483d2bc9a0c18b5dc25e9867.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, nas quais se prop\u00f5e colocar os restos de outras c\u00e9lulas,<\/li>\n<li>custos de transporte \u2013 custos de tempo <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/afac567e9057a46de6e0f3d29df9315a.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do operador de armaz\u00e9m para mover o volume de produto da c\u00e9lula-doadora <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/829df82255e40cb99024d7c8dd408d41.jpeg\" style=\"display:block;margin: 0 auto;\" \/> para a c\u00e9lula-conteiner <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b87c9d9260adb26ce623dbe80b4f22c2.jpeg\" style=\"display:block;margin: 0 auto;\" \/>; <\/li>\n<li>custos de abertura de empresa \u2013 custos de escolha do container <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/db4d21fc2067a23b5af5bb01c412323a.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, iguais ao volume da c\u00e9lula-conteiner <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b631a01a65f1ffd3348cbcaeeab11f0d.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, multiplicado por um certo coeficiente de economia de volumes livres (o valor do coeficiente \u00e9 sempre &gt; 1) (ver se\u00e7\u00e3o prepara\u00e7\u00e3o dos dados de entrada).<\/li>\n<\/ul>\n<p>\nDepois que a analogia com os cl\u00e1ssicos problemas de entrega foi tra\u00e7ada, \u00e9 importante responder a uma pergunta crucial, que condiciona a escolha da arquitetura do algoritmo de solu\u00e7\u00e3o: a movimenta\u00e7\u00e3o de restos da c\u00e9lula-doadora \u00e9 poss\u00edvel em apenas um \u00fanico cont\u00eainer (Single-Source) ou \u00e9 poss\u00edvel a movimenta\u00e7\u00e3o de restos para v\u00e1rias c\u00e9lulas-conteineres (Multi-Source)?<\/p>\n<p>Vale a pena notar que, na pr\u00e1tica, ambas as formula\u00e7\u00f5es do problema s\u00e3o v\u00e1lidas. Vamos apresentar todos os \"pr\u00f3s\" e \"contras\" para cada uma dessas formula\u00e7\u00f5es abaixo:<\/p>\n<table>\n<tr>\n<th>Op\u00e7\u00e3o do problema<\/th>\n<th>Pr\u00f3s da op\u00e7\u00e3o<\/th>\n<th>Contras da op\u00e7\u00e3o<\/th>\n<\/tr>\n<tr>\n<td>Single-Source<\/td>\n<td>Opera\u00e7\u00f5es de movimenta\u00e7\u00e3o de produtos calculadas por esta op\u00e7\u00e3o do problema:<\/p>\n<ul>\n<li>exigem menos controle por parte do operador de armaz\u00e9m (pegou TUDO de uma c\u00e9lula, colocou TUDO em outra c\u00e9lula-conteiner), o que elimina os riscos: de erros ao contar o n\u00famero de produtos ao executar as opera\u00e7\u00f5es \"Colocar na c\u00e9lula\"; erros na entrada da quantidade contada no TSD;<\/li>\n<li>N\u00e3o \u00e9 necess\u00e1rio tempo para recalcular a quantidade de produtos ao realizar opera\u00e7\u00f5es de \"Colocar na c\u00e9lula\" e inserir dados no TSD.<\/li>\n<\/ul>\n<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Multi-Source<\/td>\n<td>As compressores calculadas para esta variante de tarefa s\u00e3o geralmente mais compactas em 10-15% em compara\u00e7\u00e3o com as compressores calculadas para a variante \"Single-Source\". Mas tamb\u00e9m notamos que quanto menor a quantidade de estoques nas c\u00e9lulas doadoras, menor \u00e9 essa diferen\u00e7a de compacta\u00e7\u00e3o.<\/td>\n<td>Opera\u00e7\u00f5es de movimenta\u00e7\u00e3o de produtos calculadas por esta op\u00e7\u00e3o do problema:<\/p>\n<ul>\n<li>exigem maior controle por parte do estoquista (\u00e9 necess\u00e1rio recalcular a quantidade de produtos movidos para cada uma das c\u00e9lulas-cont\u00eaineres planejadas), o que elimina o risco de erro ao recalcular a quantidade de produtos e inserir dados no TSD ao realizar opera\u00e7\u00f5es de \"Colocar na c\u00e9lula\".<\/li>\n<li>\u00c9 necess\u00e1rio tempo para recalcular a quantidade de produtos ao realizar opera\u00e7\u00f5es de \"Colocar na c\u00e9lula\".<\/li>\n<li>\u00c9 necess\u00e1rio tempo para \"despesas gerais\" (parar, ir at\u00e9 o palete, escanear o c\u00f3digo de barras da c\u00e9lula-conteiner) ao realizar opera\u00e7\u00f5es de \"Colocar na c\u00e9lula\".<\/li>\n<li>\u00c0s vezes, o algoritmo pode \"dividir\" a quantidade de um palete quase completo entre um grande n\u00famero de c\u00e9lulas-conteineres, onde j\u00e1 h\u00e1 produtos adequados, o que, do ponto de vista do cliente, era inaceit\u00e1vel.<\/li>\n<\/ul>\n<\/td>\n<\/tr>\n<\/table>\n<p><i>Tabela 1. Pr\u00f3s e contras das variantes Single-Source e Multi-Source.<\/i><\/p>\n<p>Uma vez que a quantidade de pr\u00f3s da variante Single-Source \u00e9 maior, al\u00e9m do fato de que quanto menor a quantidade de restos nas c\u00e9lulas doadoras, menor \u00e9 a diferen\u00e7a na compacta\u00e7\u00e3o entre as duas variantes de tarefa, nossa escolha recaiu sobre a variante Single-Source.<\/p>\n<p>Vale a pena mencionar que a solu\u00e7\u00e3o da variante Multi-Source tamb\u00e9m \u00e9 v\u00e1lida. Existem muitos algoritmos eficazes para sua solu\u00e7\u00e3o, a maioria dos quais se resume a resolver uma s\u00e9rie de problemas de transporte. H\u00e1 tamb\u00e9m algoritmos n\u00e3o apenas eficazes, mas elegantes, como<noindex><a rel=\"nofollow\" href=\"http:\/\/www.mathnet.ru\/php\/archive.phtml?wshow=paper&amp;jrnid=da&amp;paperid=791&amp;option_lang=rus\"> aqui.<\/a><\/noindex><\/p>\n<h4>Prepara\u00e7\u00e3o dos dados de entrada<\/h4>\n<p>\nAntes de come\u00e7armos a an\u00e1lise e o desenvolvimento do algoritmo para resolver a tarefa, \u00e9 necess\u00e1rio decidir quais dados e de que forma iremos fornec\u00ea-los como entrada. N\u00e3o h\u00e1 problemas com os volumes de estoques de produtos nas c\u00e9lulas-doadoras e a capacidade das c\u00e9lulas-conteineres, uma vez que isso \u00e9 trivial - esses valores ser\u00e3o medidos em m3, mas os custos de uso da c\u00e9lula-conteiner e a matriz de custos de movimenta\u00e7\u00e3o s\u00e3o mais complicados!<\/p>\n<p>Primeiro, vamos considerar o c\u00e1lculo <b>custo de movimenta\u00e7\u00e3o de mercadorias<\/b> da c\u00e9lula-doadora para a c\u00e9lula-conteiner. Primeiro, \u00e9 necess\u00e1rio decidir em quais unidades de medida iremos calcular os custos de movimenta\u00e7\u00e3o. As duas op\u00e7\u00f5es mais \u00f3bvias s\u00e3o metros e segundos. Contar os custos de movimenta\u00e7\u00e3o em \"metros limpos\" \u00e9 sem sentido. Vamos mostrar isso com um exemplo. Suponha que a c\u00e9lula <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/990a5fae8988ddf41395483263de2bcc.jpeg\" style=\"display:block;margin: 0 auto;\" \/> est\u00e1 situada no primeiro n\u00edvel, a c\u00e9lula <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/9d17b98e807444f431d01f2e77fc96f7.jpeg\" style=\"display:block;margin: 0 auto;\" \/> est\u00e1 a 30 metros de dist\u00e2ncia e est\u00e1 localizada no segundo n\u00edvel:<\/p>\n<ul>\n<li>Mover de <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/3188fd9853d5cda2834a5083539ac11d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> em <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e212a0be19ea687b1017c3aacec3df19.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u00e9 mais caro do que mover de <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d65e60dec37fb3b83c83ca1c566f1ee9.jpeg\" style=\"display:block;margin: 0 auto;\" \/> em <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/4168198a4c90bdd3dd4b7f0c904b06e0.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, pois descer do segundo n\u00edvel (1,5-2 metros do ch\u00e3o) \u00e9 mais f\u00e1cil do que subir para o segundo, mesmo que a dist\u00e2ncia percorrida seja a mesma;<\/li>\n<li>Mover 1 unidade de mercadoria da c\u00e9lula <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/039864ccd0a2bd14a99a83494f056fa3.jpeg\" style=\"display:block;margin: 0 auto;\" \/> em <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/9f9bc7a256119b110f47760b145e174b.jpeg\" style=\"display:block;margin: 0 auto;\" \/> ser\u00e1 mais f\u00e1cil do que mover 10 unidades da mesma mercadoria, embora a dist\u00e2ncia percorrida seja a mesma.<\/li>\n<\/ul>\n<p>\nOs custos de movimenta\u00e7\u00e3o devem ser melhor considerados em segundos, pois isso permite levar em conta tanto a diferen\u00e7a nos n\u00edveis quanto a diferen\u00e7a na quantidade de mercadorias movidas. Para contabilizar os custos de movimenta\u00e7\u00e3o em segundos, devemos dividir a opera\u00e7\u00e3o de movimenta\u00e7\u00e3o em componentes elementares e medir o tempo gasto em cada uma dessas componentes.<\/p>\n<p>Suponha que da c\u00e9lula <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/538c4304e37f340a5a5a8e47e0ee2865.jpeg\" style=\"display:block;margin: 0 auto;\" \/> movem-se <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/6c7e32728f4771726f8ef9b2d78111d6.jpeg\" style=\"display:block;margin: 0 auto;\" \/> unidades de mercadoria para o recipiente <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/fc2ad051b500eae5884404f4b9419841.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Suponha que <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/6733192a31618a03e51e8e3133cb96ee.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u00e9 a velocidade m\u00e9dia de movimenta\u00e7\u00e3o do trabalhador no armaz\u00e9m, medida em m\/s. Suponha que <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/97f7e9c65c2196fa586f957618d1c8a2.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/bbe48d987f180e2f9ccec6e090e6f942.jpeg\" style=\"display:block;margin: 0 auto;\" \/> s\u00e3o as velocidades m\u00e9dias para a execu\u00e7\u00e3o das opera\u00e7\u00f5es de pegar e colocar, respectivamente, para um volume de mercadoria igual a 4 dm3 (volume m\u00e9dio que o funcion\u00e1rio pega de uma s\u00f3 vez ao realizar as opera\u00e7\u00f5es no armaz\u00e9m). Suponha que <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/267d74648f49d5a2d063b1377c6d2fe6.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/fefdd606d5a81ba4e2ce57b107dfe1e6.jpeg\" style=\"display:block;margin: 0 auto;\" \/> s\u00e3o as alturas das c\u00e9lulas das quais as opera\u00e7\u00f5es de pegar e colocar s\u00e3o realizadas, respectivamente. Por exemplo, a altura m\u00e9dia do primeiro n\u00edvel (ch\u00e3o) \u00e9 de 1 m, o segundo n\u00edvel 2 m e assim por diante. Ent\u00e3o, a f\u00f3rmula para calcular o tempo total para realizar a opera\u00e7\u00e3o de movimenta\u00e7\u00e3o <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a48ae3c2e9dc8f2c3108cb2be1f96c40.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u00e9 a seguinte:<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/55afb96b1141bb5656351bdaeba31ae4.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Na Tabela 2, est\u00e3o estat\u00edsticas sobre o tempo de execu\u00e7\u00e3o de cada opera\u00e7\u00e3o elementar, coletadas pelos funcion\u00e1rios do armaz\u00e9m, considerando a especificidade das mercadorias armazenadas.<\/p>\n<table>\n<tr>\n<th>Nome da opera\u00e7\u00e3o<\/th>\n<th>S\u00edmbolo<\/th>\n<th>Valor m\u00e9dio<\/th>\n<\/tr>\n<tr>\n<td>Velocidade m\u00e9dia de movimenta\u00e7\u00e3o do trabalhador no armaz\u00e9m<\/td>\n<td><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/dadbfb13d2b84b95ab2c5d653a21668b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/td>\n<td>1,5 m\/s<\/td>\n<\/tr>\n<tr>\n<td>Velocidade m\u00e9dia para a execu\u00e7\u00e3o de uma opera\u00e7\u00e3o de colocar (para um volume de mercadoria 4 dm3)<\/td>\n<td><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/aa619b43a70a7cf646ad35d5c8883329.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/td>\n<td>2,4 seg<\/td>\n<\/tr>\n<\/table>\n<p><i>Tabela 2. Tempo m\u00e9dio para a execu\u00e7\u00e3o das opera\u00e7\u00f5es de armaz\u00e9m<\/i><\/p>\n<p>Com a forma de c\u00e1lculo dos custos de movimenta\u00e7\u00e3o definida, agora precisamos entender como calcular <b>os custos para a escolha da c\u00e9lula-conteiner<\/b>Aqui tudo \u00e9 muito mais complicado do que os custos de movimenta\u00e7\u00e3o, pois: <\/p>\n<ul>\n<li>em primeiro lugar, os custos devem estar diretamente relacionados ao volume da c\u00e9lula - o mesmo volume de itens a serem movidos de c\u00e9lulas doadoras \u00e9 melhor colocado em um cont\u00eainer menor do que em um grande, desde que esse volume se encaixe totalmente em ambos os cont\u00eaineres. Assim, minimizando os custos totais na escolha dos cont\u00eaineres, buscamos economizar a capacidade de armaz\u00e9m \"deficit\u00e1ria\" na \u00e1rea de sele\u00e7\u00e3o, para realizar as opera\u00e7\u00f5es subsequentes de coloca\u00e7\u00e3o dos produtos nas c\u00e9lulas. Na figura 4 s\u00e3o demonstradas as op\u00e7\u00f5es de movimenta\u00e7\u00e3o de itens em cont\u00eaineres grandes e pequenos e as consequ\u00eancias dessas op\u00e7\u00f5es de movimenta\u00e7\u00e3o durante a execu\u00e7\u00e3o das opera\u00e7\u00f5es de armaz\u00e9m subsequentes.<\/li>\n<li>Em segundo lugar, como precisamos minimizar os custos totais na solu\u00e7\u00e3o do problema original, que \u00e9 a soma tanto dos custos de movimenta\u00e7\u00e3o quanto dos custos de escolha dos cont\u00eaineres, os volumes das c\u00e9lulas em metros c\u00fabicos precisam de alguma forma estar alinhados com segundos, o que n\u00e3o \u00e9 trivial.<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/2c906f9e80b32fcb111fcba7000ea2ba.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Fig. 4. Op\u00e7\u00f5es de movimenta\u00e7\u00e3o de itens para cont\u00eaineres de diferentes capacidades.<\/i><\/p>\n<p>Na figura 4, a quantidade de itens que j\u00e1 n\u00e3o cabe mais no cont\u00eainer na segunda etapa da coloca\u00e7\u00e3o dos produtos \u00e9 mostrada em vermelho. <\/p>\n<p>Os seguintes requisitos para as solu\u00e7\u00f5es computacionais da tarefa ajudar\u00e3o a correlacionar metros c\u00fabicos de custos na escolha do cont\u00eainer com segundos de custos de movimenta\u00e7\u00e3o:<\/p>\n<ul>\n<li>\u00c9 necess\u00e1rio que os itens da c\u00e9lula doadora sejam movidos para a c\u00e9lula cont\u00eainer em todos os casos, se isso reduzir o n\u00famero total de c\u00e9lulas-cont\u00eainer onde o produto est\u00e1 localizado.<\/li>\n<li>\u00c9 necess\u00e1rio manter um equil\u00edbrio entre os volumes dos cont\u00eaineres e os custos de tempo de movimenta\u00e7\u00e3o: por exemplo, se na nova op\u00e7\u00e3o de solu\u00e7\u00e3o do problema em compara\u00e7\u00e3o com a op\u00e7\u00e3o anterior houver um grande ganho de volume, enquanto a perda de tempo for pequena, deve-se escolher a nova op\u00e7\u00e3o.<\/li>\n<\/ul>\n<p>\nCome\u00e7aremos pelo \u00faltimo requisito. Para concretizar a palavra amb\u00edgua \"equil\u00edbrio\", fizemos uma pesquisa com os funcion\u00e1rios do armaz\u00e9m a fim de descobrir o seguinte. Suponha que haja uma c\u00e9lula cont\u00eainer de volume <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/2b831b12448ccaee33c528ac622b7ee3.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, para a qual est\u00e1 programada a movimenta\u00e7\u00e3o dos itens das c\u00e9lulas doadoras, e o tempo total dessa movimenta\u00e7\u00e3o \u00e9 igual a <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/8050f4b02464164d334048bda86b3923.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Suponha que existem v\u00e1rias op\u00e7\u00f5es alternativas para alocar a mesma quantidade de produtos das mesmas c\u00e9lulas doadoras em outros cont\u00eaineres, onde cada aloca\u00e7\u00e3o possui suas pr\u00f3prias avalia\u00e7\u00f5es. <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/76f11cd5ab85f9092c8f458d01ac347b.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, onde <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/9e735d8a9c4cff3c69fd926eac8c85aa.jpeg\" style=\"display:block;margin: 0 auto;\" \/>&lt;<img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d963e193a263a1505467c19e874f0aab.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/ff5d990cf5a1752d7bb45da9fd58cd7a.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, onde <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/485f34b3e720011c38740712cdb8edd9.jpeg\" style=\"display:block;margin: 0 auto;\" \/>&gt;<img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/c66b20d93fd1791e9f186f707b1517bb.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. <\/p>\n<p>A quest\u00e3o que se coloca \u00e9: qual \u00e9 o ganho m\u00ednimo em volume <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/86861ad2236d827efdc683d759d4c120.jpeg\" style=\"display:block;margin: 0 auto;\" \/> aceit\u00e1vel, dado um valor de perda de tempo. <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/3d49171042fd83244c054dfd84e5c6bb.jpeg\" style=\"display:block;margin: 0 auto;\" \/>? \u041f\u043e\u044f\u0441\u043d\u0438\u043c \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435. \u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043f\u043e\u043b\u0430\u0433\u0430\u043b\u043e\u0441\u044c \u0440\u0430\u0437\u043c\u0435\u0449\u0430\u0442\u044c \u0432 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440 \u043e\u0431\u044a\u0435\u043c\u0430 1000 \u0434\u043c3 (1 \u043c3) \u0438 \u0432\u0440\u0435\u043c\u044f \u043d\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u043e 70 \u0441\u0435\u043a\u0443\u043d\u0434. \u0415\u0441\u0442\u044c \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0430\u0437\u043c\u0435\u0449\u0435\u043d\u0438\u044f \u043e\u0441\u0442\u0430\u0442\u043a\u043e\u0432 \u0432 \u0434\u0440\u0443\u0433\u043e\u0439 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440 \u043e\u0431\u044a\u0435\u043c\u0430 500 \u0434\u043c3 \u0438 \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c 130 \u0441\u0435\u043a\u0443\u043d\u0434. \u0412\u043e\u043f\u0440\u043e\u0441: \u0433\u043e\u0442\u043e\u0432\u044b \u043b\u0438 \u043c\u044b \u0442\u0440\u0430\u0442\u0438\u0442\u044c \u0435\u0449\u0435 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 60 \u0441\u0435\u043a\u0443\u043d\u0434 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043a\u043b\u0430\u0434\u043e\u0432\u0449\u0438\u043a\u0430 \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0441\u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0442\u044c 500 \u0434\u043c3 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0433\u043e \u043e\u0431\u044a\u0435\u043c\u0430? \u041f\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430\u043c \u043e\u043f\u0440\u043e\u0441\u0430 \u0441\u043e\u0442\u0440\u0443\u0434\u043d\u0438\u043a\u043e\u0432 \u0441\u043a\u043b\u0430\u0434\u0430 \u0431\u044b\u043b\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0430.<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/283289c63fe1232e95b73d1dffdaa030.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Fig. 5. Diagrama da rela\u00e7\u00e3o entre a economia m\u00ednima de volume aceit\u00e1vel e o aumento da diferen\u00e7a no tempo de execu\u00e7\u00e3o da opera\u00e7\u00e3o.<\/i><\/p>\n<p>Ou seja, se os custos adicionais de tempo totalizam 40 segundos, estamos dispostos a gast\u00e1-los apenas quando o ganho em volume for de pelo menos 500 dm\u00b3. Apesar de haver uma leve n\u00e3o linearidade na rela\u00e7\u00e3o, para simplificar os c\u00e1lculos subsequentes, vamos assumir que a rela\u00e7\u00e3o entre as quantidades \u00e9 linear e \u00e9 descrita pela desigualdade.<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/666802648033d918a1119e58963feffe.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Na figura abaixo, consideraremos as seguintes formas de alocar produtos em cont\u00eaineres.<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a1cb3a5bce4c369f63b3ebeebb738911.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Fig. 6. Op\u00e7\u00e3o (a): 2 cont\u00eaineres, volume total de 400 dm\u00b3, tempo total de 150 seg.<\/i><br \/>\n<img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a13f35b0e2a188e9a8cbf27bcfbf0292.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Fig. 6. Op\u00e7\u00e3o (b): 2 cont\u00eaineres, volume total de 600 dm\u00b3, tempo total de 190 seg.<\/i><br \/>\n<img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/35699c8bd00546c9828dbe50d4b53c46.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Fig. 6. Op\u00e7\u00e3o (c): 1 cont\u00eainer, volume total de 400 dm\u00b3, tempo total de 200 seg.<\/i><\/p>\n<p>A op\u00e7\u00e3o (a) de escolha dos cont\u00eaineres \u00e9 mais prefer\u00edvel do que a op\u00e7\u00e3o inicial, pois a desigualdade se mant\u00e9m: (800-400)\/10 &gt;= 150-120, o que resulta em 40 &gt;= 30. A op\u00e7\u00e3o (b) \u00e9 menos prefer\u00edvel do que a op\u00e7\u00e3o inicial, pois a desigualdade n\u00e3o se mant\u00e9m: (800-600)\/10 &gt;= 190-150, resultando em 20 &gt;= 40. Mas a op\u00e7\u00e3o (c) n\u00e3o se encaixa nessa l\u00f3gica! Vamos examinar essa op\u00e7\u00e3o mais de perto. Por um lado, a desigualdade (800-400)\/10 &gt;= 200-120 se aplica, portanto, a desigualdade 40 &gt;= 80 n\u00e3o se mant\u00e9m, o que indica que o ganho em volume n\u00e3o vale a grande perda de tempo. <\/p>\n<p>Mas, por outro lado, nessa op\u00e7\u00e3o (c) n\u00e3o apenas reduzimos o volume total ocupado, mas tamb\u00e9m diminu\u00edmos o n\u00famero de c\u00e9lulas ocupadas, o que \u00e9 o primeiro de dois requisitos importantes para as solu\u00e7\u00f5es computacionais dos problemas citados acima. Obviamente, para que esse requisito comece a ser atendido, \u00e9 necess\u00e1rio adicionar uma constante positiva ao lado esquerdo da desigualdade. <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/61d6b2cb21474a2f4512d6a130a15a0a.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, sendo que essa constante deve ser adicionada apenas quando o n\u00famero de cont\u00eaineres diminui. Lembremos que <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d80d33679896035041d0ca9a78e8177a.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2014 \u00e9 uma vari\u00e1vel igual a 1 quando o cont\u00eainer <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a83cd6273e544b63099939e6845740fb.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u00e9 escolhido, e 0 quando n\u00e3o \u00e9. <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/bc94d9e952782e630125a6e8919ba5ad.jpeg\" style=\"display:block;margin: 0 auto;\" \/> n\u00e3o selecionado. Vamos denote, <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1e3fb5d7013e60f67c56a56899630852.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 m\u00faltiplos cont\u00eaineres na solu\u00e7\u00e3o original e <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/26ac9732af37e865cea1bb10a343175c.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 m\u00faltiplos cont\u00eaineres na nova solu\u00e7\u00e3o. De maneira geral, a nova desigualdade ser\u00e1:<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1237914e5fdafcc6013203e2624009d0.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Transformando a desigualdade acima, obtemos <\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/80b039f9ef44301c3b624ada42c28db8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>A partir disso, temos a f\u00f3rmula para calcular o custo total <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/cb5bce584fee0156b23adbab83f66b33.jpeg\" style=\"display:block;margin: 0 auto;\" \/> de alguma variante da solu\u00e7\u00e3o do problema:<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/34f382d40368a980674914916c65b4ec.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p><b>Mas agora surge a quest\u00e3o<\/b>: qual valor deve ter essa constante <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e4754f88bcddfba85b3c785512bee697.jpeg\" style=\"display:block;margin: 0 auto;\" \/>? \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043c, \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u043b\u043e\u0441\u044c \u043f\u0435\u0440\u0432\u043e\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0435 \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044f\u043c \u0437\u0430\u0434\u0430\u0447\u0438. \u041c\u043e\u0436\u043d\u043e \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0432\u0437\u044f\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b \u0440\u0430\u0432\u043d\u043e\u0435 103 \u0438\u043b\u0438 106, \u043d\u043e \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c \u0431\u044b \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0445 \u00abmagic numbers\u00bb. \u0415\u0441\u043b\u0438 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u043a\u0443 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0441\u043a\u043b\u0430\u0434\u0441\u043a\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u043f\u043e\u043b\u043d\u0435 \u043e\u0431\u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0445 \u043e\u0446\u0435\u043d\u043e\u043a \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b \u0442\u0430\u043a\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b.<\/p>\n<p>Seja <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/50deefe99bf1d5f948a49591904a8bfe.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 a dist\u00e2ncia m\u00e1xima entre as c\u00e9lulas do armaz\u00e9m de uma zona ABC, que \u00e9, neste caso, igual a 100 m. Seja <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/466892dd75279d08b4835a42e62444d4.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 o volume m\u00e1ximo de uma c\u00e9lula-conteiner no armaz\u00e9m, que \u00e9, neste caso, igual a 1000 dm3.<\/p>\n<p><b>O primeiro m\u00e9todo para calcular a magnitude<\/b> <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/29b94b534da709020cbef206cb0d7dac.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Vamos considerar a situa\u00e7\u00e3o em que h\u00e1 2 cont\u00eaineres no primeiro andar, nos quais j\u00e1 est\u00e1 fisicamente localizado o produto, ou seja, eles pr\u00f3prios s\u00e3o c\u00e9lulas-doadoras, e os custos de mover o produto para essas mesmas c\u00e9lulas, naturalmente, s\u00e3o iguais a 0. Precisamos encontrar tal valor para a constante <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/5cf81db57dd2a18cc0ec29bb7ca3da62.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, para o qual seria sempre vantajoso mover os restos do cont\u00eainer 1 para o cont\u00eainer 2. Substituindo os valores <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/20bbd09e167edc3eb1ed49d8078ecf19.jpeg\" style=\"display:block;margin: 0 auto;\" \/> e <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/605017af48e7b3ca4a323642db4227cd.jpeg\" style=\"display:block;margin: 0 auto;\" \/> na desigualdade mencionada acima, obtemos:<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/2794955b8f9f3d64ffe4e2b449547555.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>o que implica<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/292a6e80c646c7eed80e888c8805990c.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Substituindo os valores do tempo m\u00e9dio de execu\u00e7\u00e3o das opera\u00e7\u00f5es elementares na f\u00f3rmula acima, obtemos<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1f56bf1f98c1a3bbd65a4cea99da7efb.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p><b>O segundo m\u00e9todo para calcular a magnitude<\/b> <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/78e3dff7183b15136d9e03f4a5724479.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Vamos considerar a situa\u00e7\u00e3o em que existem <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/02daff1eff70a2963ab8eaa067f15584.jpeg\" style=\"display:block;margin: 0 auto;\" \/> c\u00e9lulas-doadoras de onde se planeja mover o produto para o cont\u00eainer 1. Definimos <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/df20c3f27815f2060aae20d260210893.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 a dist\u00e2ncia da c\u00e9lula-doadora <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a29ace66656cf1680c9e00258a9ff597.jpeg\" style=\"display:block;margin: 0 auto;\" \/> at\u00e9 o cont\u00eainer 1. Tamb\u00e9m existe o cont\u00eainer 2, que j\u00e1 cont\u00e9m produtos e cujo volume permite acomodar os restos de todas <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e25f0828e7d794f8d804528395f6dc7e.jpeg\" style=\"display:block;margin: 0 auto;\" \/> as c\u00e9lulas. Para simplificar, vamos supor que o volume do produto movido das c\u00e9lulas-doadoras para os cont\u00eaineres \u00e9 igual a <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/35c3392a83fc3b7eef928ddb5e93961a.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. \u00c9 necess\u00e1rio encontrar tal valor para a constante <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/c9bc10aade46cc3c63628c0ba100b364.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, para que a aloca\u00e7\u00e3o de todos os restos das <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e610d9981da2857a541f028a217f2306.jpeg\" style=\"display:block;margin: 0 auto;\" \/> c\u00e9lulas no cont\u00eainer 2 seja sempre mais vantajosa do que a aloca\u00e7\u00e3o em diferentes cont\u00eaineres:<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/27f4f99a920799fba9725f30a04c8ebc.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Transformando a desigualdade, obtemos<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/56abddb4fc3e54eeb1fe466c68e5d8d7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Para \"intensificar\" o valor da magnitude <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d77359ea816f9d45a8910cb26649f717.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, tomamos que <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/9edf13fb4e34b5da26957e451300046f.jpeg\" style=\"display:block;margin: 0 auto;\" \/> = 0. O n\u00famero m\u00e9dio de c\u00e9lulas que normalmente participam do procedimento de compacta\u00e7\u00e3o de restos no armaz\u00e9m \u00e9 igual a 10. Substituindo os valores conhecidos das magnitudes, temos o seguinte valor da constante<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/40323791fd8cd2be3f29a2becf78e175.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Pegamos o maior valor calculado para cada variante, esse ser\u00e1 o valor da magnitude <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/fd018460792c79b8a7953c06b839711d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> para os par\u00e2metros dados do armaz\u00e9m. Agora, para completar, escrevamos a f\u00f3rmula para calcular os custos totais <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d4cb2c81bcc788380f1f0c1123b0eeda.jpeg\" style=\"display:block;margin: 0 auto;\" \/> para alguma solu\u00e7\u00e3o aceit\u00e1vel <img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/052e710199e9417aaea94b16dbed47d3.jpeg\" style=\"display:block;margin: 0 auto;\" \/>:<\/p>\n<p><img decoding=\"async\" alt=\"Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1)\" src=\"\/wp-content\/uploads\/2019\/08\/8dd672c7b91639fe1872ef50dca7a220.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Agora, ap\u00f3s todos <b>os esfor\u00e7os tit\u00e2nicos<\/b> para a transforma\u00e7\u00e3o dos dados de entrada, podemos afirmar que todos os dados foram transformados para a forma necess\u00e1ria e est\u00e3o prontos para uso no algoritmo de otimiza\u00e7\u00e3o.<\/p>\n<h4>Conclus\u00e3o<\/h4>\n<p>\nComo a pr\u00e1tica mostra, a complexidade e a import\u00e2ncia da etapa de prepara\u00e7\u00e3o e transforma\u00e7\u00e3o dos dados de entrada para o algoritmo muitas vezes s\u00e3o subestimadas. Neste artigo, dedicamos muita aten\u00e7\u00e3o a essa etapa para mostrar que apenas dados de entrada preparados de maneira competente e de alta qualidade podem tornar as decis\u00f5es calculadas pelo algoritmo verdadeiramente valiosas para o cliente. Sim, houve muitas dedu\u00e7\u00f5es de f\u00f3rmulas, mas n\u00f3s o avisamos antes do corte \ud83d\ude42<\/p>\n<p>No pr\u00f3ximo artigo, finalmente chegaremos ao que era o objetivo das duas publica\u00e7\u00f5es anteriores \u2013 o algoritmo de otimiza\u00e7\u00e3o discreta.<\/p>\n<p><i>O artigo foi preparado por<br \/>\nRoman Shanguin, programador do departamento de projetos,<br \/>\nempresa Primeiro Bit, cidade de Chelyabinsk<\/i><br \/>\n<br \/>Fonte: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/463481\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0435\u043c, \u043a\u0430\u043a \u0440\u0435\u0448\u0430\u043b\u0438 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u043d\u0435\u0445\u0432\u0430\u0442\u043a\u0438 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0445 \u044f\u0447\u0435\u0435\u043a \u043d\u0430 \u0441\u043a\u043b\u0430\u0434\u0435 \u0438 \u043e \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0442\u0430\u043a\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438. \u0420\u0430\u0441\u0441\u043a\u0430\u0436\u0435\u043c \u043e \u0442\u043e\u043c, \u043a\u0430\u043a \u043c\u044b \u00ab\u0441\u0442\u0440\u043e\u0438\u043b\u0438\u00bb \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u0438 \u043e \u0442\u043e\u043c \u0441 \u043a\u0430\u043a\u0438\u043c\u0438 \u0442\u0440\u0443\u0434\u043d\u043e\u0441\u0442\u044f\u043c\u0438 \u043c\u044b \u043d\u0435\u043e\u0436\u0438\u0434\u0430\u043d\u043d\u043e \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u0438\u0441\u044c \u043f\u0440\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438 \u0432 \u0431\u0438\u0437\u043d\u0435\u0441\u0435 \u0438 [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":27819,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[702],"tags":[],"class_list":["post-37108","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.3 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/pt\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1\" \/>\n\t\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.3\" \/>\n\t\t<meta property=\"og:locale\" content=\"pt_PT\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47\u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u0430\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 \u0434\u043b\u044f WMS: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0436\u0430\u0442\u0438\u044f \u0442\u043e\u0432\u0430\u0440\u043e\u0432 \u0432 \u044f\u0447\u0435\u0439\u043a\u0430\u0445 (\u0447\u0430\u0441\u0442\u044c 1) | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/pt\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T19:15:47+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2019-10-31T19:15:47+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Matem\u00e1tica discreta para WMS: algoritmo de compacta\u00e7\u00e3o de produtos em c\u00e9lulas (parte 1) | ProHoster","description":"No artigo, n\u00f3s.","canonical_url":"https:\/\/prohoster.info\/pt\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pt_PT","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u0430\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 \u0434\u043b\u044f WMS: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0436\u0430\u0442\u0438\u044f \u0442\u043e\u0432\u0430\u0440\u043e\u0432 \u0432 \u044f\u0447\u0435\u0439\u043a\u0430\u0445 (\u0447\u0430\u0441\u0442\u044c 1) | ProHoster","og:description":"\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b.","og:url":"https:\/\/prohoster.info\/pt\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:15:47+00:00","article:modified_time":"2019-10-31T19:15:47+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"37108","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-22 06:08:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 01:33:24","updated":"2026-01-22 06:08:19","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts\/37108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/comments?post=37108"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts\/37108\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media\/27819"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media?parent=37108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/categories?post=37108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/tags?post=37108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}