Anar al contingut

Cort en guillotina

De L'Enciclopèdia, la wikipedia en valencià
Un tall en guillotina: un full tallat en rectànguls més chicotets que es poden dividir intactes de forma optimisada per mig de la série correcta de corts bisecantes d'un extrem a un atre
Un tall impossible en guillotina: estos rectànguls "no poden" separar-se únicament a pur de corts bisecantes a lo llarc del pla

El tall en guillotina és el procés de produir formes rectangulars chicotetes de dimensions fixes a partir d'un full rectangular gran determinada, utilisant únicament corts de guillotina. Un tall en guillotina (també cridat tall de vora a vora) és una llínea bisectriz recta que va des d'una vora d'un rectàngul existent fins a la vora oposta, de manera similar a lo que fa una guillotina per a paper.

El tall en guillotina és particularment comuna en l'indústria del vidre. Les làmines de vidre es marquen en llínees horisontals i verticals i despuix es trenquen segons estes llínees per a obtindre panels més menuts.[1] El procediment també és útil per a tallar plaques d'acer, tallar làmines de fusta per a fabricar mobles, i per a tallar el cartó amprat en la fabricació de caixes.[2]

Existixen varis problema d'optimisació relacionats en el tall en guillotina, tals com maximizar l'àrea total de les peces produïdes o el seu valor total; o també minimisar la cantitat de desperdicis (parts no utilisades) del full gran, o el número total de fulls. S'han estudiat en geometria discreta, investigació d'operacions i ingenieria industrial.[3]

Un problema relacionat pero diferent és la partició en guillotina. En este problema, les dimensions dels rectànguls chicotets no estan fixades de bestreta. El desafiu sorgix del fet de que el full original pugues no ser rectangular, sino que pot ser qualsevol polígon rectilíneo. En particular, podria contindre forats (que representen defectes en la matèria primera). L'objectiu d'optimisació sol ser minimisar el número de rectànguls chicotets o minimisar la llongitut total dels corts.

Terminologia i suposts

Els següents térmens i notacions s'utilisen a sovint en la lliteratura sobre tall en guillotina.

El rectàngul gran, també cridat full comú, és el full rectangular en bruto que es deu tallar. Es caracterisa per la seua ample W0 i alt H0, que són les entrades principals del problema.

  • Els rectànguls menuts, també cridats elements, són les eixides requerides del tall. Es caracterisen per la seua ample wi i alt hi i per i en 1,...,m, a on m és el número de rectànguls. A sovint es permet tindre varis rectànguls de les mateixes dimensions; en este cas, el parell de dimensions (wi,hi) sol denominar-se tipo.
  • Un patró de tall, a sovint cridat simplement patró, és una disposició de chicotets rectànguls en el full de material. Pot donar-se com una seqüència de punts (xi,ii), per a i en 1,...,m, a on (xi,ii' ') és la coordenada inferior esquerra del rectàngul i. En tal patró, el rectàngul i ocupa un segment horisontal (xi, xi+wi) i un segment vertical (ii, ii +hi).

Una construcció es referix a generar un nou rectàngul unint dos rectànguls més menuts. Per la restricció de la guillotina, solament hi ha dos tipos de construccions: en una construcció horisontal, el rectàngul combinat té un ample wi+wj i una altura màxima(hi, hj); en una construcció vertical, el rectàngul combinat té un ample màxim(wi,wj) i una altura hi+hj. Cada patró es pot representar com una seqüència recursiva de construccions, que correspon a molts patrons diferents, que tenen una estructura combinatòria equivalent. El conjunt de tots els patrons corresponents a la mateixa construcció recursiva es denomina "classe de tall de guillotina".[4]

Alguns problemes accepten entrades adicionals, com s'explica a continuació. L'objectiu és tallar del rectàngul en bruto alguns rectànguls més chicotets que tinguen les dimensions desijades. A sovint es fan les següents suposicions:[2]

Tots els corts tenen ample zero. Açò no supon molta pèrdua de generalitat, ya que si cada tall té un ample fix de d>0, llavors el problema es pot reduir a la variant d'ample zero simplement agregant d a wi i hi per a i en 0,...,m. Les dimensions de destí no es poden rotar, és dir, w-by-h no és el mateix tipo que h-by-w. Açò tampoc supon una pèrdua de generalitat significativa, ya que la variant en la que els rectànguls es poden rotar es pot reduir a la variant no rotativa agregant explícitament els patrons rotados.

Comprovació d'un patró donat

En el problema de verificació de patrons, hi ha un patró de tall donat com una seqüència de punts (xi,ii), per a i en 1,...,m, a on (xi,ii) és la coordenada inferior esquerra del rectàngul i (hi ha un únic rectàngul de cada dimensió objectiu). L'objectiu és decidir si este patró es pot implementar utilisant únicament corts de guillotina i, de ser aixina, trobar una seqüència per a dits corts.


Una condició necessària òbvia és que no se superponguen dos rectànguls d'entrada en abdós dimensions. Ben Messaoud, Chengbin i Espinouse[5] varen fixar una condició més forta, que és al mateix temps necessària i suficient. Els rectànguls d'entrada estan ordenats d'esquerra a dreta, de modo que x1 = ... = xm. Existix una permutació p sobre els índexs tal que, en esta permutació, els rectànguls quedarien ordenats d'avall cap a dalt, és dir, ip(1) = ... = ip(m). Daus quatre índexs i1 = i2 i j1 = j2, el conjunt I(i1,i2,j1,j2) conté els índexs de tots els rectànguls el cantó inferior dels quals esquerra està en el rectàngul [xi1,xi2] X [ip(j1),ip(j2)]. Un patró de cort és un patró de guillotina si i solament si, per a totes les cuaternas d'índexs i1 = i2 i j1 = j2, a lo manco es complix una de les següents condicions per a I(i1,i2,j1,j2):

  1. I(i1,i2,j1,j2) conté com a màxim un element
  2. L'unió dels segments horisontals (xi, xi+wi), sobre totes les i en I(i1,i2 ,j1,j2), es compon d'a lo manco dos intervals disjuntos
  3. L'unió dels segments verticals (ii, ii+hi), sobre totes les i en I(i1,i2 ,j1,j2), es compon d'a lo manco dos intervals disjuntos.

La condició 2 implica que els rectànguls en I(i1,i2,j1,j2) poden separar-se per mig d'un tall vertical (que va entre els dos intervals horisontals). La condició 3 implica que els rectànguls en I(i1,i2,j1,j2) es poden separar per mig d'un tall horisontal. Totes les condicions juntes impliquen que, si qualsevol conjunt de rectànguls adjacents conté més d'un element, llavors poden separar-se per mig d'algun tall en guillotina.

Esta condició es pot verificar per mig del següent algoritme:

  • En cada iteración, dividixca's un patró determinat, que continga a lo manco dos rectànguls, en dos subpatrones separats usant un tall de guillotina i repetixca's en cada subpatrón.
  • Detinga's quan tots els subpatrones continguen un rectàngul (en el cas del qual la resposta és "sí") o no siguen possibles més corts de guillotina (en el cas de la qual la resposta siga "no").

Trobar un tall en guillotina per a un patró determinat es realisa de la següent manera:

  • Determinar els intervals horisontals m i ordenar-los d'esquerra a dreta; determinar els intervals verticals m i ordenar-los d'avall cap a dalt. Açò requerix un temps de càlcul d'O(m log m).
  • Fusionar intervals horisontals superposts i fusionar intervals verticals superposts. Açò requerix un temps O(m).
  • Si, despuix de la fusió, queden a lo manco dos intervals horisontals separats, llavors és possible un tall en guillotina vertical; si hi ha a lo manco dos intervals verticals separats, llavors és possible un tall horisontal; de lo contrari no serà possible realisar cap tall.

L'ordenació dels passos es realisa una volta i el pas de fusió es realisa m-1 voltes. Per lo tant, el temps d'eixecució de tot l'algoritme és O(m2).


Quan l'algoritme torna "sí", també produïx una seqüència de corts de guillotina; quan torna "no", també produïx subconjunts específics de rectànguls que no poden separar-se per mig de corts en guillotina.

La condició necessària i suficient es pot utilisar per a presentar el problema de tall de tires en guillotina com programa llineal sancer mixt.[5]<span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: sec.5  El seu model té 3n4/4 variables binàries i 2n4 restriccions, i no es considera útil en la pràctica.

Trobar un patró de tall òptim

Estes són variants dels problemes bidimensionales de talle de material, empaquetat en contenidors i empaquetat de rectànguls, a on els corts estan obligats a ser corts en guillotina.[6]

  • En el problema de tall en guillotina bàsic ("no ponderat"), el resultat requerit és una seqüència de corts que produïxen peces de les dimensions objectiu, de manera que s'maximizar l'àrea total de les peces produïdes (equivalentemente, que es minimisen els rebujos del procés).

En la variant ponderada, per a cada dimensió objectiu i, també hi ha un valor vi. L'objectiu és llavors maximizar el valor total de les peces produïdes. La variant no ponderada (minimisació de residus) es pot reduir a la variant ponderada fent que el valor de cada dimensió objectiu siga igual a la seua àrea (vi = hi * wi).

  • En la variant restringida, per a cada dimensió objectiu i, hi ha un llímit superior bi en el número de peces que es poden produir d'eixe tipo.
  • En la variant doblement restringida, per a cada dimensió objectiu i hi ha un llímit inferior ai i un llímit superior bi en el número de peces produïdes.

La variant binaria és una variant restringida en la que cada dimensió de destí deu aparéixer com a màxim una volta (és dir, el llímit superior és 1). Este cas està associat en un problema de decisió, a on l'objectiu és decidir si és possible produir un sol element de cada dimensió objectiu per mig de corts de guillotina.[4] En el problema del tall de tires en guillotina, el rectàngul gran té una altura infinita (pero un ample fix), i l'objectiu és tallar un sol rectàngul de cada tipo, de modo que el material total utilisat (equivalentemente, l'altura total) es minimise. És una variant del Problema d'empaquetat en tires bidimensional. En el problema de minimisació de material, hi ha un número infinit de fulls de material de les mateixes dimensions i l'objectiu és tallar tots els rectànguls objectiu necessaris utilisant el menor número possible de fulls.[5] És una variant del problema d'empaquetat en contenidors bidimensional.[7] El tall en guillotina en k etapes és una variant restringida del tall en guillotina, en la que el tall es realisa com a màxim en k etapes: en la primera etapa, solament es realisen corts horisontals; en la segona etapa solament es realisen corts verticals; etcétera.

  • En la variant de 2 etapes, una atra distinció és si totes les tires resultants de la primera etapa es tallen en els mateixos llocs (cridats "1 grup") o en dos llocs diferents (cridats "2 grups") o en possiblement diferents ubicacions (cridades "lliures").[8]
  • 1-tall en guillotina simple és una variant restringida del tall de guillotina en la que cada tall separa un sol rectàngul.
  • Un 2-tall en guillotina simple és un patró d'1 simples, de modo que cada part és en sí mateixa un patró de p 1-corts simples: els patrons de cort simples es poden definir de forma recursiva.

Algoritmes d'optimisació

El cas especial en el que solament hi ha un tipo (és dir, tots els rectànguls objectiu són idèntics i estan en la mateixa orientació) es denomina problema de "càrrega de palet en guillotina". Tarnowski, Terno i Scheithauer[9] varen idear un algoritme de temps polinomial per a resoldre-ho.

No obstant, quan hi ha dos o més tipos, tots els problemes d'optimisació relacionats en el tall en guillotina són NP-hard. Per la seua importància pràctica, s'han ideat varis algoritmes exactes i algoritmes d'aproximació.

  • Clautiaux, Jouglet i Moukrim[4] varen propondre un algoritme exacte per al problema de decisió. El seu algoritme utilisa una representació compacta de classes de patrons de tall en guillotina, utilisant un grafo dirigit al que criden "grafo de guillotina". Cada arc en este grafo està coloreat en un de dos colors: "horisontal" o "vertical". Cada cicle dirigit monocromàtic en este grafo correspon a una construcció. En contraure repetidament cicles monocromàtics, es pot recuperar una seqüència de construcció recursiva que representa una classe de patró de cort. Cada grafo de guillotina conté entre m i 2m-2 arcs. Un tipo especial de grafos de guillotina cridats "grafos de guillotina normals" tenen l'interessant propietat de contindre un camí hamiltoniano únic. La classificació dels vèrtiços segons este circuit convertix al grafo en un "grafo de guillotina normal ben ordenat". Existix una correspondència un a un entre dits grafos i les classes de patrons de cort. Llavors, resolen el problema d'optimisació utilisant programació en restriccions en l'espai de grafos de guillotina normals ben ordenats.
  • Russo, Boccia, Sforza i Sterle[8] revisen més de 90 artículs que tracten sobre el tall en guillotina restringit sense etapes (en llímits superiors de cantitat), tant ponderats com no ponderats. Hi ha dos enfocaments principals per a solucions exactes: "programació dinàmica" i "busca en arbre" (ramificació i vinculació). Els enfocaments de busca en arbre es classifiquen ademés com "d'avall cap a dalt" (començant en rectànguls individuals i usant "compilació" per a construir el full complet) o "de dalt cap a avall". En tots els enfocaments, és important trobar bons llímits superior i inferior per a retallar l'espai de busca de manera eficient. Estos llímits a sovint provenen de solucions a variants relacionades, com per eixemple variants sense restriccions, per etapes i sense guillotina.
  • Abou Msabah, Slimane i Ahmed Riadh Bava-Ali. "Una nova heurística de colocació de guillotina combinada en un algoritme genètic millorat per al problema del material de cort ortogonal". Conferència Internacional IEEE 2011 sobre Ingenieria Industrial i Gestió d'Ingenieria. IEEE, 2011.
  • Abou-Msabah, Slimane, Ahmed-Riadh Bava-Ali i Basma Sager. "Un algoritme genètic d'estabilitat controlada en la nova heurística de colocació de guillotina BLF2G per al problema del material de cort ortogonal". Revista Internacional d'Informàtica Cognitiva i Inteligència Natural (IJCINI) 13, no. 4 (2019): 91-111.

Desenrolls

  • McHale and Shah[16] va escriure un programa Prolog que conté un algoritme anytime: genera solucions aproximadament òptimes en un periodo de temps determinat i despuix les millora si l'usuari permet més temps. El programa va ser utilisat per un productor de paper especial i ha reduït el temps necessari per al disseny dels fulls i, al mateix temps, ha reduït el desperdici.

Separació en guillotina

La separació en guillotina és un problema relacionat en el que l'entrada és una colecció de n formes convexas separades per parells en el pla, i l'objectiu és separar-los usant una seqüència de corts de guillotina. Òbviament, pot ser que no siga possible separar-les totes. Jorge Urrutia Galícia va plantejar la qüestió de si és possible separar una fracció constant d'ells,[17] és dir, si existix una constant c tal que, en qualsevol colecció de tamany n, hi ha un subconjunt de tamany cn que és separable en guillotina.

Pach i Tardos[18] varen demostrar que:

  • Si tots els objectes són de tamany similar, llavors es pot separar una fracció constant d'ells. Formalment, si tots els objectes contenen un círcul de ràdio r i estan continguts en un círcul de ràdio R, llavors hi ha un conjunt separable de tamany πr2128R2n≈140.7(R/r)2n. Demostració: construir una cuadrícula en un tamany de cela de 8R per 8R. Moure la cuadrícula uniformemente a l'encert. Cada objecte és intersecado per una llínea horisontal en provabilitat d'1/4 i també per una llínea vertical en provabilitat d'1/4, per lo que el número esperat d'objectes intersecados és n/2. Per lo tant, existixen llínees de cuadrícula que intersecan com a màxim n/2 objectes. Ya que l'àrea de cada cela de la cuadrícula és (8R)2 i l'àrea de cada objecte és a lo manco πr2, cada cela conté com a màxim (8R)2πr2 objectes. Elegir un sol objecte de cada cela i separar-ho dels demés objectes en la mateixa cela. El número total d'objectes separats d'esta manera és a lo manco n2/(8R)2πr2=πr2128R2n. Un argument similar per al cas de quadrats unitaris dona 127n.

Si els objectes són segments de llínea recta, llavors, en alguns casos, solament es poden separar com a màxim O(nlog32)≈O(n0.63) d'ells. En particular, per a cada sancer positiu k, existix una família d'intervals disjuntos 3k tal que com a màxim 2k d'ells poden separar-se. En qualsevol colecció de n objectes convexos, es poden separar a lo manco Ω(n1/3). En qualsevol colecció de n segments de llínea recta, es poden separar a lo manco Ω(n1/2). Conjeturan que el pijor dels casos es pot alcançar per mig de segments de llínea. En qualsevol colecció de n rectànguls paralels als eixos, es poden separar a lo manco n/(2log⁡n). Conjeturan que Ω(n) es poden separar. Esta conjectura encara està oberta. En qualsevol colecció de R-objectes grossos (el disc que conté més chicotet és com a màxim R voltes el disc contingut més gran), es poden guardar a lo manco n/(cRlog⁡n) objectes, a on cR és una constant que depén solament de R.

  • Una teorema anàloga també és vàlit en dimensions superiors: el número d'objectes separables és n/c(R,d)(log⁡n)d.

Totes estes subfamílies separables es poden construir en el temps O(nlog⁡n). Si els objectes són polígons en N costats en total, llavors les llínees de separació es poden calcular en el temps O(N+nlog⁡n). Abed, Chalermsook, Correja, Karrenbauer, Pérez-Lantero, Soto i Wiese[19] varen demostrar que:

  • En qualsevol colecció de n quadrats unitaris paralels als eixos, a lo manco n/2 es poden separar, i hi ha casos en els que com a màxim n/2 es poden separar.
  • En qualsevol colecció de n quadrats paralels als eixos, es poden separar a lo manco n/81.
  • En qualsevol colecció de n quadrats paralels a eixos en pesos, es pot separar a lo manco 4/729 del pes total.
  • En qualsevol colecció de n gavetes d-dimensionals en pesos d'eixos paralels, es pot separar 1/2O(d) del pes total.
  • Respecte a la conjectura de que és possible separar el rectàngul d'eixos paralels Ω(n), si ben no la resolen, mostren que, si és correcta, llavors implica un algoritme d'aproximació O(1) al problema del conjunt disjunto màxim de rectànguls d'eixos paralels en el temps O(n5).

Khan i Pittu[20] varen demostrar:

  • En n rectànguls paralels als eixos, si solament es permeten o(log⁡log⁡n) etapes, llavors no és possible separar els Ω(n) rectànguls.
  • Quan els rectànguls estan ponderats, si solament es permeten o(log⁡n/log⁡log⁡n) etapes, llavors no és possible separar Ω(n) del pes.
  • Existix un algoritme simple de 2 etapes que separa n/(1+log2n) rectànguls. L'algoritme dividix els rectànguls en 1+log2n subconjunts (cridats "nivells") i elegix el nivell en el major número de rectànguls. Cada nivell pot estar separat per dos corts en guillotina.[20]<span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: Thm.14  Un algoritme millorat pot separar n/log3(n+2) rectànguls.
  • En qualsevol colecció de rectànguls grossos, es poden separar en Ω(n).
  • En qualsevol colecció de n quadrats paralels als eixos, es poden separar a lo manco n/40.
  • En qualsevol colecció de n quadrats paralels als eixos en pesos, es pot separar a lo manco una fracció 1/80 del pes total.

Vore també

Més variants

Algunes variants del problema inclouen:

  • Cort en guillotina en tres dimensions.[21][22]
  • Cort en guillotina quan el rectàngul en bruto pot tindre defectes, pero els rectànguls produïts deuen estar lliures de defectes.[23]

Referències

  1. ↑ Tlilane, Lydia; Viaud, Quentin (2018-05-18). «Challenge ROADEF / EURO 2018 Cutting Optimization Problem Description». Challenge ROADEF/EURO. ROADEF. Consultat el 2019-06-13.
  2. ↑ 2,0 2,1 2,2 2,3 Beasley, J. E.(1985-04-01).«Algorithms for Unconstrained Two-Dimensional Guillotine Cutting».Journal of the Operational Research Society.36(4): 297–306.ISSN 0160-5682.doi:10.1057/jors.1985.51.
  3. ↑ Gerhard Wäscher, Heike Haußner, Holger Schumann, An improved typology of cutting and packing problems, European Journal of Operational Research 183 (2007) 1109–1130, [1]
  4. ↑ 4,0 4,1 4,2 Clautiaux, François; Jouglet, Antoine; Moukrim, Aziz(2011-10-17).«A New Graph-Theoretical Model for the Guillotine-Cutting Problem».INFORMS Journal on Computing.25(1): 72–86.ISSN 1091-9856.doi:10.1287/ijoc.1110.0478.
  5. ↑ 5,0 5,1 5,2 Ben Messaoud, Said; Chu, Chengbin; Espinouse, Marie-Laure(2008-11-16).«Characterization and modelling of guillotine constraints».European Journal of Operational Research.191(1): 112–126.ISSN 0377-2217.doi:10.1016/j.ejor.2007.08.029.(en en)
  6. ↑ 6,0 6,1 M. Hifi, R. M’Hallah and T. Saadi, Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting estoc problem. Computational Optimization and Applications, Volume 42, Number 2 (2009), 303-326, doi:10.1007/s10589-007-9081-5
  7. ↑ Carlier, Jacques; Clautiaux, François; Moukrim, Aziz(2007-08-01).«New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation».Computers & Operations Research.34(8): 2223–2250.ISSN 0305-0548.doi:10.1016/j.cor.2005.08.012.(en en)
  8. ↑ 8,0 8,1 Russo, Mauro; Boccia, Maurizio; Sforza, Antonio; Sterle, Claudio(2020).«Constrained two-dimensional guillotine cutting problem: upper-bound review and categorization».International Transactions in Operational Research.27(2): 794–834.ISSN 1475-3995.doi:10.1111/itor.12687.(en en)
  9. ↑ Tarnowski, A. G.; Terno, J.; Scheithauer, G.(1994-11-01).«A Polynomial Clave Algorithm For The Guillotine Pallet Loading Problem».INFOR: Information Systems and Operational Research.32(4): 275–287.ISSN 0315-5986.doi:10.1080/03155986.1994.11732257.
  10. ↑ Gilmore, P. C.; Gomory, R. E.(1965-02-01).«Multistage Cutting Estoc Problems of Two and More Dimensions».Operations Research.13(1): 94–120.ISSN 0030-364X.doi:10.1287/opre.13.1.94.
  11. ↑ Gilmore, P. C.; Gomory, R. E.(1966-12-01).«The Theory and Computation of Knapsack Functions».Operations Research.14(6): 1045–1074.ISSN 0030-364X.doi:10.1287/opre.14.6.1045.
  12. ↑ 12,0 12,1 Herz, J. C.(September 1972).«Recursive Computational Procedure for Two-dimensional Estoc Cutting».IBM Journal of Research and Development.16(5): 462–469.ISSN 0018-8646.doi:10.1147/rd.165.0462.
  13. ↑ Christofides, Nicos; Whitlock, Charres(1977-02-01).«An Algorithm for Two-Dimensional Cutting Problems».Operations Research.25(1): 30–44.ISSN 0030-364X.doi:10.1287/opre.25.1.30.
  14. ↑ O. B. G. Masden (1980), IMSOR working paper, Technical university of Denmark, Lyngby
  15. ↑ Wang, P. Y.(1983-06-01).«Two Algorithms for Constrained Two-Dimensional Cutting Estoc Problems».Operations Research.31(3): 573–586.ISSN 0030-364X.doi:10.1287/opre.31.3.573.
  16. ↑ Michael L. McHale, Roshan P. Shah Cutting the Guillotine Down to Size. PC AI magazine, Volume 13, Number 1 Jan/Feb 99. http://www.amzi.com/articles/papercutter.htm
  17. ↑ Problem presented at ACCOTA '96, Combinatorial and Computational Aspects of Optimization Topology and Algebra, Taxco, Mexico 1996
  18. ↑ Pach, J.; Tardos, G.(2000).«Cutting Glass».Discrete and Computational Geometry.24(2–3): 481–496.ISSN 0179-5376.doi:10.1007/s004540010050.(en en)
  19. ↑ Abed, Fidaa; Chalermsook, Parinya; Correja, José; Karrenbauer, Andreas (2015). On Guillotine Cutting Sequences, pp. 1–19. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1. ISBN 978-3-939897-89-7.
  20. ↑ 20,0 20,1 Khan, Arindam; Pittu, Madhusudhan Reddy(2020).«On Guillotine Separability of Squares and Rectangles».Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020).Schloss Dagstuhl–Leibniz-Zentrum für Informatik.Dagstuhl, Germany:176: 47:1–47:22.doi:10.4230/LIPIcs.APPROX/RANDOM.2020.47.
  21. ↑ Martin, Mateus; Oliveira, José Fernando; Silva, Elsa; Morabito, Reinaldo(2020-11-08).«Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm».Expert Systems with Applications.168: 114257.ISSN 0957-4174.doi:10.1016/j.eswa.2020.114257.(en en)
  22. ↑ Baazaoui, M.; Hanafi, S.; Kamoun, H. (2014-11-01). «A Mathematical formulation and a lower bound for the three-dimensional multiple-bin-size bin packing problem (MBSBPP): A Tunisian industrial case», 2014 International Conference on Control, Decision and Information Technologies (CoDIT), pp. 219–224. doi:10.1109/CoDIT.2014.6996896. ISBN 978-1-4799-6773-5.
  23. ↑ Martin, Mateus; Hokama, Pedro H. D. B.; Morabito, Reinaldo; Munari, Pedro(2020-05-02).«The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm».International Journal of Production Research.58(9): 2712–2729.ISSN 0020-7543.doi:10.1080/00207543.2019.1630773.

Bibliografia

  • Abou Msabah, Slimane, and Ahmed Riadh Bava-Ali. "A new guillotine placement heuristic combined with an improved genetic algorithm for the orthogonal cutting-estoc problem." 2011 IEEE International Conference on Industrial Engineering and Engineering Management. IEEE, 2011.


Referències