Application Program Development

About Description Cutting Stock Problem Circle Optimization Problem
Cutting Rectangles Cutting Triangles Cutting Circles Contact Us

  Packing problems   are optimization problems that are concerned with searching a  good arrangement
  of multiple items   in   a   2d regions.  The usual objective   of the allocation is to maximise the material
  utilization   and to minimize the wasted area.   This  is of  particular interest to industries involved with
  mass-production   as  small improvements in   the layout   can result   in   savings   of   material   and a
  considerable reduction   in production costs.   The goal in the cutting stock problem is to determine the
  optimal   plan   to cut   a 2 dimensional sheet   to satisfy   a   set of customers demands.   Cutting stock
  problems may involve a variety  of objectives,   minimizing trim loss, minimizing the number of cutting
  lines,   maximizing profit,   and so on.   In   order   to  solve the cutting stock problem,  we use a cutting
  pattern optimizer and mathematical programming.   In general,  the cutting stock problem is reduce to
  an integer programming application.   Because of its complexity, solutions to the 2 dimensional cutting
  stock problem have often been generated using genetic algorithms. This is due, in part, to the fact that
  the 2 dimensional cutting stock problem may also be reduced to a bin-packing problem. The rectangular
  cutting stock problem is to determine how to cut a number of rectangular pieces out of a given stock of
  rectangular sheets. Most variants of the nesting problem is the problem of packing shapes within some
  regions without overlap.  The cutting stock problem asks for a minimization of the area of a rectangular
  region.   In   the cutting industry a multitude   of   additional constraints are very often necessary.   The
  shapes   or   regions   can   have   different quality zones or even holes. The nesting problem occurs in a
  number   of   industries   and it seems to have many names.   In the clothing industry it is called marker
  making,   while the metal industry call it simply nesting.     In  a theoretical context the problem is most
  often  called   the   two-dimensional irregular   cutting stock problem.   The   2 dimensional cutting stock
  problem   is a   classic combinatorial optimization problem in which a number of parts of various lengths
  must  be   cut from an   inventory   of  2d material.   The two-dimensional cutting stock problem may be
  applied   in   a   number of  industries,   glass,   shoe-leather cutting,   furniture,   machine-building,  etc.
  The   problem   is as   follows   :   a   set   of   rectangular pieces is to be placed on a given area of a stock
  material   with   minimum  of trim-loss.   The cutting pattern has no overlaps of the pieces and meets all
  technological requirements.    The stock cutting problem has gained a lot of attention in many industrial
  sectors.     Stock Cutting Problems  is  essential  in   many  industries.     These problems   are  treated in
  different fields.  The reduction of scrap may not only affects cost of materials used but may also reduce
  the costs of handling and labor.   A great number of problems are essentially based on the same logical
  structure of the Cutting and Packing problems. The stock cutting problem is an example of a large scale
  optimization   problem.   This   means   that   this   problem requires   a   computing effort that increases
  exponentially   with   the problem size.     Since   the stock cutting problem is an efficient approximation
  algorithms,   namely,   algorithms that   do not produce optimal but rather   close-to-optimal   solutions,
  Cutting  and  packing problems are encountered in many industries.     The   wood-,   glass-   and   paper
  industry  are   mainly   concerned with the cutting of regular figures,   whereas in the textile and leather
  industry irregular, arbitrary items are to be packed.

  In   this  kind of  applications  all  cuts  have  to  be  accomplished  from one edge of the rectangle to the
  opposite  one.   The  cut has   to  be  of  a  guillotine  type.   For  such  applications  the  problem  can  be
  formulated  as  a mathematical optimization program and the optimal solution can be found in terms of
  material yield  and production costs.  The quality of a cutting pattern is determined by the cutting ratio,
  which  is  defined  as  the  ratio  between  the  total  area  of  the  placed pieces and the total area of the
  stock-material.   Single  pass  packing strategies involve taking the pieces in order and placing them on
  the  sheet  according to  a  given  placement policy.   This  may  be  repeated  several times for different
  orderings   or   different   placements  and  the  best  solution  chosen.   The  process  will  continue  until
  shifting-down,   shifting-left   or   rotation is no longer possible.  In other words, the algorithm continues
  pushing  pieces  downwards  and  leftwards  until  the  pieces  reach  stable  positions.   Cutting  out  the
  material  in  the  most  effective  way  result  in  reducing  its  stock  holding  which  can make additional
  savings  through  improved  cash  flow.   Although   the  normal motivation  for  effective stock cutting is
  financial, companies  may  have  other  objectives  in  implementing  efficient stock cutting procedures.
  For example,  there  may  be  a  requirement  to  meet certain orders within a given time. In the nesting
  problem it  is  necessary to place a number of parts into a larger sheet.   In doing so, the parts must not
  overlap and they must stay within the sheet.  The usual objective is to minimize the waste of the larger
  sheet.  The  algorithms  makes  use  of  the  search  procedures  when  deciding  where pieces should be
  placed.  The  location  of  the  next  piece  is  calculated  using  the  search  procedures.   Once  the  best
  placement has been found the piece is added to the optimization list and the next piece is  placed.   The
  packing problem consists of packing a collection of pieces onto a rectangular sheet while minimizing the
  unused space.  The  packing process  has  to  ensure that there is no overlap between the pieces. There
  are  thousands  of  different  ways  in  which  just  a  few different pieces can be cut out of a stock sheet.
  Most patterns would be extremely wasteful, and many would be difficult to cut.  The Genetic algorithms
  are search  and optimization procedures,   where  the  search is guided towards improvement using the
  searching  of  the best item.   This  is achieved by extracting the most desirable items from a temporary
  solution list and combining them to form the next solution list.  The quality of each solution is evaluated
  and the best items are selected for the reproduction process.   Continuation of this process will result in
  optimal or near optimal solutions.