home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10868 < prev    next >
Encoding:
Internet Message Format  |  1992-09-02  |  2.0 KB
  1. Path: sparky!uunet!pmafire!news.dell.com!swrinde!cs.utexas.edu!sun-barr!ames!haven.umd.edu!darwin.sura.net!dtix!mimsy!afterlife!adm!amsaa-cleo!matt
  2. From: matt@amsaa-cleo.brl.mil (Matt Rosenblatt)
  3. Newsgroups: sci.math
  4. Subject: Minimizing waste when cutting fabric.
  5. Summary: Algorithm or computer program wanted.
  6. Keywords: Waste; Fabric
  7. Message-ID: <8832@amsaa-cleo.brl.mil>
  8. Date: 2 Sep 92 15:35:02 GMT
  9. Organization: U.S. ARMY MATERIEL SYSTEMS ANALYSIS ACTIVITY (AMSAA), APG, MD.
  10. Lines: 31
  11.  
  12. Suppose I am an upholsterer who buys fabric in rolls.  Each roll is
  13. 54 inches wide, and I can assume it is infinitely long:
  14.  
  15.                                Y
  16.             -------------------------------------------
  17.            |                                          /
  18.            |                                         /
  19.         X  |                                        |   . . .
  20.            |                                         \
  21.            |                                         /
  22.             -----------------------------------------
  23.  
  24. Suppose I need to cut  n  pieces  P_i,  where  P_i  is to be a 
  25. rectangle  x_i  inches wide in the  X  direction, and  y_i  inches 
  26. long in the  Y  direction.  (Because of the pattern in the fabric,
  27. a rectangle  x" wide by  y"  long is not equivalent to a rectangle
  28. y"  wide by  x"  long.)  I can start at the beginning of the roll,
  29. cutting a few rectangles whose combined width  w  does not exceed 
  30. 54".  When I can no longer fit any more rectangles at the beginning, 
  31. I can start cutting rectangles out of the as-yet-unused material.
  32. Once I start doing this, a strip of fabric  (54" - w) wide will
  33. have to be wasted.  I want to cut the  n  pieces in such a way
  34. as to minimize this waste.
  35.  
  36. This must be a basic version of a much more general problem where
  37. the pieces to be cut can take all sorts of shapes.  Surely there
  38. have been algorithms designed for the more general case.  What kind
  39. of algorithms are they, and where can I find them?
  40.  
  41.                     -- Matt Rosenblatt
  42.                     (matt@amsaa-cleo.brl.mil)
  43.