nach oben

Journal of Combinatorial Optimization

Erschienen in:

18.02.2021

Modified Greedy Heuristic for the one-dimensional cutting stock problem

verfasst von: Gonçalo R. L. Cerqueira, Sérgio S. Aguiar, Marlos Marques

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

One can get an integer solution for the one-dimensional cutting stock problem by means of the constructive or residual heuristic. In this work we propose a change in the Constructive Greedy Heuristic that consists in building a cutting pattern by sorting in descending order the items of pair or odd length, priority being given to those which appear more frequently in the problem, cut from objects in stock with pair or odd length respectively, with the aim of minimizing the quantity of cut objects. Computing tests that were carried out showed the efficiency of the proposed heuristic when compared with other methods in the literature that generate an integer solution for the problem and will be presented at the end of this work.

Vorheriger Artikel An improved mechanism for selfish bin packing

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Barnhart C, Johnson EL, Nenhauser GL, Vance PH (1994) Solving binary cutting stock problems by colum generation and branch and bound. Comput Optim Appl 3:111–130MathSciNetCrossRef

Bazaraa MS, Jarvis JJ, Sherali HD (1990) Linear programming and network flows, 2nd edn. Wiley, New YorkMATH

Belov G, Scheithauer G (2002) Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths. Eur J Oper Res 141:295–312 MathSciNetCrossRef

Cerqueira GRL, Yanasse HH (2009) A pattern reduction procedure in a one-dimensional cutting stock problem by grouping items according to their demands. J Comput Interdiscip Sci 2:159–164

Cherri AC, Arenales MN, Yanasse HH (2009) The one-dimensional cutting stock problem with usable leftover: a heuristic approach. Eur J Oper Res 196:897–908MathSciNetCrossRef

Cui Y, Yang Y, Yu P (2008) A heuristic for the one-dimensional cutting stock problem with pattern reduction. Eng Manuf 222:677–685CrossRef

Cui Y (2005) A cutting stock problem and its solution in the manufacturing industry of large electric generators. Comput Oper Res 32:1709–1721CrossRef

Farley AA (1990) The cutting stock problem in the canvas industry. Eur J Oper Res 44:247–255CrossRef

Foerster H, Wascher G (1999) Pattern reduction in one-dimensional cutting stock problems. Int J Prod Res 38:1657–676CrossRef

Gau T, Wascher G (1995) Cutgen1: a problem generator for one-dimensional cutting stock problem. Eur J Oper Res 84:572–579CrossRef

Gilmore P, Gomory R (1961) A linear programming approach to the cutting stock problem. Oper Res 9:849–859MathSciNetCrossRef

Gilmore P, Gomory R (1963) A linear programming approach to the cutting stock problem-part II. Oper Res 6:863–888CrossRef

Hinxman AI (1980) The trim-loss and assortment problems: a survey. Eur J Oper Res 5:8–18MathSciNetCrossRef

Johnson MP, Rennick C, Zak E (1997) Skiving addition to the cutting stock problem in the paper industry. Soc Ind Appl Math 39:472–483MathSciNetMATH

Marcotte O (1985) The cutting stock problem and integer rounding. Math Program 33:82–92MathSciNetCrossRef

Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New YorkMATH

McDiarmid C (1999) Pattern minimisation in cutting stock problems. Discrete Appl Math 98:121–130MathSciNetCrossRef

Ongkunaruk P (2005) Asymptotic worst-case analyses for the open bin packing problem. Faculty of the Virginia Polytechnic Institute

Pisinger D (1993) Algorithms for knapsack problems. Thesis-DIKU, University of Copenhagen, Copenhagen

Poldi KC, Arenales MN (2009) Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths. Comput Oper Res 36:2074–2081CrossRef

Scheithauer G, Terno J (1995) The modified integer round-up property of the one-dimensional cutting stock problem. Eur J Oper Res 84:562–571CrossRef

Stadtler H (1990) A one-dimensional cutting stock problem in the aluminium industry and its solution. Eur J Oper Res 44:209–223CrossRef

Wascher G (1990) An lp-based approach to cutting stock problems with multiple objectives. Eur J Oper Res 44:175–184MathSciNetCrossRef

Wascher G, Gau T (1996) Heuristics for the integer one-dimensional cutting stock problem: a computational study. OR Spektrum 18:131–144CrossRef

Yanasse HH, Poldi KC, Cerqueira GRL (2011) Modified KOMBI to reduce the different patterns in cutting stock problems. International Federation of Operational Research Societies Melbourne, Australia

Yanasse HH, Limeira MS (2006) A hybrid heuristic to reduce the number of different patterns in cutting stock problems. Comput Oper Res 33:2744–2756CrossRef

Titel: Modified Greedy Heuristic for the one-dimensional cutting stock problem
verfasst von: Gonçalo R. L. Cerqueira
Sérgio S. Aguiar
Marlos Marques
Publikationsdatum: 18.02.2021
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2021
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-021-00695-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2021

Conflict-free connection of trees

Batch scheduling of nonidentical job sizes with minsum criteria

The spectral radius and domination number in linear uniform hypergraphs

A dynamic approach to detecting, eliminating and fixing memory leaks

Preface: special issue on the annual international conference on combinatorial optimization and applications (COCOA)

A spectral partitioning algorithm for maximum directed cut problem

Premium Partner