Heuristic Algorithm for 2D Cutting Stock Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-01-03

AUTHORS

Georgi Evtimov , Stefka Fidanova

ABSTRACT

Every day optimization problems arise in our life and industry. Many of them require huge amount of calculations and need special type of algorithms to be solved. An important industrial problem is cutting stock problem (CSP). Cutting with less possible waste is significant in some industries. The aim of this work is to cut 2D items from rectangular stock, minimizing the waste. Even the simplified version of the problem, when the items are rectangular is NP hard. When the number of items increases, the computational time increases exponentially. It is impossible to find the optimal solution for a reasonable time. Only for very small problems the exact algorithms and traditional numerical methods can be applied. We propose a stochastic algorithm which solves the problem, when the items are irregular polygons. More... »

PAGES

350-357

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-73441-5_37

DOI

http://dx.doi.org/10.1007/978-3-319-73441-5_37

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1100171480


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Information and Communication Technologies, Bulgarian Academy of Sciences, Acad. G. Bonchev Str., bl. 25A, 1113, Sofia, Bulgaria", 
          "id": "http://www.grid.ac/institutes/grid.424988.b", 
          "name": [
            "Institute of Information and Communication Technologies, Bulgarian Academy of Sciences, Acad. G. Bonchev Str., bl. 25A, 1113, Sofia, Bulgaria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Evtimov", 
        "givenName": "Georgi", 
        "id": "sg:person.07366160356.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07366160356.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Information and Communication Technologies, Bulgarian Academy of Sciences, Acad. G. Bonchev Str., bl. 25A, 1113, Sofia, Bulgaria", 
          "id": "http://www.grid.ac/institutes/grid.424988.b", 
          "name": [
            "Institute of Information and Communication Technologies, Bulgarian Academy of Sciences, Acad. G. Bonchev Str., bl. 25A, 1113, Sofia, Bulgaria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fidanova", 
        "givenName": "Stefka", 
        "id": "sg:person.011173106320.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011173106320.18"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-01-03", 
    "datePublishedReg": "2018-01-03", 
    "description": "Every day optimization problems arise in our life and industry. Many of them require huge amount of calculations and need special type of algorithms to be solved. An important industrial problem is cutting stock problem (CSP). Cutting with less possible waste is significant in some industries. The aim of this work is to cut 2D items from rectangular stock, minimizing the waste. Even the simplified version of the problem, when the items are rectangular is NP hard. When the number of items increases, the computational time increases exponentially. It is impossible to find the optimal solution for a reasonable time. Only for very small problems the exact algorithms and traditional numerical methods can be applied. We propose a stochastic algorithm which solves the problem, when the items are irregular polygons.", 
    "editor": [
      {
        "familyName": "Lirkov", 
        "givenName": "Ivan", 
        "type": "Person"
      }, 
      {
        "familyName": "Margenov", 
        "givenName": "Svetozar", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-73441-5_37", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-73440-8", 
        "978-3-319-73441-5"
      ], 
      "name": "Large-Scale Scientific Computing", 
      "type": "Book"
    }, 
    "keywords": [
      "traditional numerical methods", 
      "stock problem", 
      "heuristic algorithm", 
      "huge amount", 
      "exact algorithm", 
      "stochastic algorithm", 
      "computational time", 
      "reasonable time", 
      "small problems", 
      "optimization problem", 
      "important industrial problem", 
      "optimal solution", 
      "numerical method", 
      "algorithm", 
      "cutting stock problem", 
      "industrial problems", 
      "rectangular stocks", 
      "possible waste", 
      "items increases", 
      "simplified version", 
      "irregular polygons", 
      "special type", 
      "problem", 
      "NPs", 
      "items", 
      "industry", 
      "polygons", 
      "calculations", 
      "solution", 
      "version", 
      "time", 
      "work", 
      "method", 
      "number", 
      "amount", 
      "types", 
      "life", 
      "aim", 
      "stocks", 
      "waste", 
      "increase"
    ], 
    "name": "Heuristic Algorithm for 2D Cutting Stock Problem", 
    "pagination": "350-357", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1100171480"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-73441-5_37"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-73441-5_37", 
      "https://app.dimensions.ai/details/publication/pub.1100171480"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_23.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-73441-5_37"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-73441-5_37'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-73441-5_37'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-73441-5_37'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-73441-5_37'


 

This table displays all metadata directly associated to this object as RDF triples.

121 TRIPLES      23 PREDICATES      68 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-73441-5_37 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 anzsrc-for:08
4 anzsrc-for:0802
5 schema:author Nd92ee27117864effac07a99703827f09
6 schema:datePublished 2018-01-03
7 schema:datePublishedReg 2018-01-03
8 schema:description Every day optimization problems arise in our life and industry. Many of them require huge amount of calculations and need special type of algorithms to be solved. An important industrial problem is cutting stock problem (CSP). Cutting with less possible waste is significant in some industries. The aim of this work is to cut 2D items from rectangular stock, minimizing the waste. Even the simplified version of the problem, when the items are rectangular is NP hard. When the number of items increases, the computational time increases exponentially. It is impossible to find the optimal solution for a reasonable time. Only for very small problems the exact algorithms and traditional numerical methods can be applied. We propose a stochastic algorithm which solves the problem, when the items are irregular polygons.
9 schema:editor Nbf29c96dfc904c16a0e59b31a8089113
10 schema:genre chapter
11 schema:inLanguage en
12 schema:isAccessibleForFree false
13 schema:isPartOf N9900ba29ae2f45dd83031c1f2f631f71
14 schema:keywords NPs
15 aim
16 algorithm
17 amount
18 calculations
19 computational time
20 cutting stock problem
21 exact algorithm
22 heuristic algorithm
23 huge amount
24 important industrial problem
25 increase
26 industrial problems
27 industry
28 irregular polygons
29 items
30 items increases
31 life
32 method
33 number
34 numerical method
35 optimal solution
36 optimization problem
37 polygons
38 possible waste
39 problem
40 reasonable time
41 rectangular stocks
42 simplified version
43 small problems
44 solution
45 special type
46 stochastic algorithm
47 stock problem
48 stocks
49 time
50 traditional numerical methods
51 types
52 version
53 waste
54 work
55 schema:name Heuristic Algorithm for 2D Cutting Stock Problem
56 schema:pagination 350-357
57 schema:productId N309f0c52fa9c4281b2151ff3548c68ca
58 Na995b5c7995941b6aebf979aa7ca12f8
59 schema:publisher N8d0d8de739414bad86716688907bf2a8
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100171480
61 https://doi.org/10.1007/978-3-319-73441-5_37
62 schema:sdDatePublished 2022-05-10T10:42
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N31dd317e1d7640048bb95d9fe9007907
65 schema:url https://doi.org/10.1007/978-3-319-73441-5_37
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N0c0655d9d5154827be1bf40e64317326 rdf:first Ne1d2ed7950524fc1831f08dd45c26424
70 rdf:rest rdf:nil
71 N309f0c52fa9c4281b2151ff3548c68ca schema:name dimensions_id
72 schema:value pub.1100171480
73 rdf:type schema:PropertyValue
74 N31dd317e1d7640048bb95d9fe9007907 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N8d0d8de739414bad86716688907bf2a8 schema:name Springer Nature
77 rdf:type schema:Organisation
78 N9900ba29ae2f45dd83031c1f2f631f71 schema:isbn 978-3-319-73440-8
79 978-3-319-73441-5
80 schema:name Large-Scale Scientific Computing
81 rdf:type schema:Book
82 Na995b5c7995941b6aebf979aa7ca12f8 schema:name doi
83 schema:value 10.1007/978-3-319-73441-5_37
84 rdf:type schema:PropertyValue
85 Nbf29c96dfc904c16a0e59b31a8089113 rdf:first Ne8cf7062c36a40328bff66c9c5a7af33
86 rdf:rest N0c0655d9d5154827be1bf40e64317326
87 Nd92ee27117864effac07a99703827f09 rdf:first sg:person.07366160356.00
88 rdf:rest Nf30acc3adf8c4df6b1d9f46febf3a4eb
89 Ne1d2ed7950524fc1831f08dd45c26424 schema:familyName Margenov
90 schema:givenName Svetozar
91 rdf:type schema:Person
92 Ne8cf7062c36a40328bff66c9c5a7af33 schema:familyName Lirkov
93 schema:givenName Ivan
94 rdf:type schema:Person
95 Nf30acc3adf8c4df6b1d9f46febf3a4eb rdf:first sg:person.011173106320.18
96 rdf:rest rdf:nil
97 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
98 schema:name Mathematical Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
101 schema:name Numerical and Computational Mathematics
102 rdf:type schema:DefinedTerm
103 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
104 schema:name Information and Computing Sciences
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
107 schema:name Computation Theory and Mathematics
108 rdf:type schema:DefinedTerm
109 sg:person.011173106320.18 schema:affiliation grid-institutes:grid.424988.b
110 schema:familyName Fidanova
111 schema:givenName Stefka
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011173106320.18
113 rdf:type schema:Person
114 sg:person.07366160356.00 schema:affiliation grid-institutes:grid.424988.b
115 schema:familyName Evtimov
116 schema:givenName Georgi
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07366160356.00
118 rdf:type schema:Person
119 grid-institutes:grid.424988.b schema:alternateName Institute of Information and Communication Technologies, Bulgarian Academy of Sciences, Acad. G. Bonchev Str., bl. 25A, 1113, Sofia, Bulgaria
120 schema:name Institute of Information and Communication Technologies, Bulgarian Academy of Sciences, Acad. G. Bonchev Str., bl. 25A, 1113, Sofia, Bulgaria
121 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...