Experiments in Flat Glass Cutting Optimization

                         Joseph D. Touch

                     University of Scranton
                       Scranton, PA 18510
                           April 1985

                    Advisor:  Dr. J. Beidler

		      Translated May, 1999.

          The  flat glass cutting problem is in the class of 
     NP-Complete problems, thus making an exhaustive search, 
     of every pane in every position,  impossible.  Instead, 
     an approximate solution is formed,  using a combination 
     of software techniques,  involving preprocessing of the 
     lists  to be cut as well as various feedback  processes 
     within the cutting algorithms.   Due to practical  con-
     siderations, the methods used are further restricted to 
     operation  on a small personal computer,  using an hour 
     or less of processing time, so previously posited solu-
     tions  are  not applicable.   This experiment  will  be 
     limited to polynomial - timed solutions,  and  operates 
     on large (up to 500 panes) data sets.   Current results 
     yield  a daily average efficiency of up to 89%,  excel-
     lent  when compared to the industry yearly  average  of 


ASCII Text of the entire thesis, with line breaks, but without
diagrams and charts, is available.

Structured and formatted versions are available as
component files:

Thesis						HTML	PS.GZ	PDF


A: Timing analysis and proof of NP nature	HTML	PS.GZ	PDF
B stock data sets used				HTML	PS.GZ	PDF
C sample clustergraphs and pattern outputs	HTML	PS.GZ	PDF
D raw statistical data				HTML	PS.GZ	PDF
E data correlations				HTML	PS.GZ	PDF
F CPU time vs. number of panes graphs		HTML	PS.GZ	PDF
G efficiency vs. number of panes graphs		HTML	PS.GZ	PDF

Last modified: Tue May 18 16:22:06 1999
This page written and maintained by Joe Touch touch@isi.edu