Motivated by operational issues in real-world glass manufacturing, this thesis addresses a problem of laying out and sequencing the orders so as to minimize wasted glass, called scrap. This optimization problem combines aspects of traditional cutting problems and traditional scheduling and sequencing problems. In so far as we know, the combination of cutting and scheduling has not been modeled, or solved. We propose a two-phase approach: snap construction and constructing cutting and offload schedules. Regarding the second phase problem, we introduce FGSP (float glass scheduling problem), and provide its solution structure, called coveys. We analyze simple sub-models of FGSP considering the main elements: time, unit, and width. For each model, we provide either a polynomial time algorithm or a proof of NP-completeness. Since FGSP is NP-complete, we propose a heuristic algorithm, Longest Unit First (LUF), and analyze the worst case performance of the algorithm in terms of the quality of solutions; the worst case performance bound is {1+(m-1)/m}+{1/3-1/(3m)} where m is the number of machines. It is 5/3 when m=2. For the real-world problem, we propose two different methods for snap construction, and we apply two main approaches to solve cutting and offloading schedules: an MIP approach and a heuristic approach. Our solution approach produces manufacturing yields greater than 99%; current practice is about 95%. This is a significant improvement and these high-yield solutions can save millions of dollars.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/39637 |
| Date | 20 December 2010 |
| Creators | Na, Byungsoo |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.002 seconds