Experiments in Flat Glass Cutting Optimization

                         Joseph D. Touch

                     University of Scranton
                       Scranton, PA 18510
                           April 1985

                    Advisor:  Dr. J. Beidler

		      Translated May, 1999.

     ABSTRACT:
          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 
     85%.

*****************************************************************

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

Appendices:

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