Graduate Thesis Or Dissertation

 

A linear programming and sampling approach to the cutting-order problem Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/db78tg15k

Descriptions

Attribute NameValues
Creator
Abstract
  • In the context of forest products, a cutting order is a list of dimension parts along with demanded quantities. The cutting-order problem is to minimize the total cost of filling the cutting order from a given lumber grade (or grades). Lumber of a given grade is supplied to the production line in a random sequence, and each board is cut in a way that maximizes the total value of dimension parts produced, based on a value (or price) specified for each dimension part. Hence, the problem boils down to specifying suitable dimension-part prices for each board to be cut. The method we propose is adapted from Gilmore and Gomory's linear programming approach to the cutting stock problem. The main differences are the use of a random sample to construct the linear program and the use of prices rather than cutting patterns to specify a solution. The primary result of this thesis is that the expected cost of filling an order under the proposed method is approximately equal to the minimum possible expected cost, in the sense that the ratio (expected cost divided by the minimum expected cost) approaches one as the size of the order (e.g., in board feet) and the size of the random sample grow large. A secondary result is a lower bound on the minimum possible expected cost. The actual minimum is usually impractical to calculate, but the lower bound can be used in computer simulations to provide an absolute standard against which to compare costs. It applies only to independent sequences, whereas the convergence property above applies to a large class of dependent sequences, called alpha-mixing sequences. Experimental results (in the form of computer simulations) suggest that the proposed method is capable of attaining nearly minimal expected costs in moderately large orders. The main drawbacks are that the method is computationally expensive and of questionable value in smaller orders.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome, 8-bit Grayscale) using ScandAll PRO 1.8.1 on a Fi-6770A in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-08-21T21:33:10Z (GMT) No. of bitstreams: 1 HamiltonEvanD2001.pdf: 3093818 bytes, checksum: 4b5a87054652de144b2c27010c3bf3f4 (MD5)
  • description.provenance : Made available in DSpace on 2012-08-21T21:33:10Z (GMT). No. of bitstreams: 1 HamiltonEvanD2001.pdf: 3093818 bytes, checksum: 4b5a87054652de144b2c27010c3bf3f4 (MD5) Previous issue date: 2000-11-15
  • description.provenance : Submitted by Kaylee Patterson (kdpscanner@gmail.com) on 2012-08-21T20:32:53Z No. of bitstreams: 1 HamiltonEvanD2001.pdf: 3093818 bytes, checksum: 4b5a87054652de144b2c27010c3bf3f4 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-08-21T21:27:38Z (GMT) No. of bitstreams: 1 HamiltonEvanD2001.pdf: 3093818 bytes, checksum: 4b5a87054652de144b2c27010c3bf3f4 (MD5)

Relationships

Parents:

This work has no parents.

Items