بهینه سازی خط تولید شیشه شناور خودکار

Flat glass is approximately a $20 billion/year industry worldwide, with almost all flat glass products being manufactured on float glass lines. New technologies are allowing float glass manufacturers to increase the level of automation in their plants, but the question of how to effectively use the automation has given rise to a new and difficult class of optimization problems. These optimization problems combine aspects of traditional cutting problems and traditional scheduling and sequencing problems. In this paper we consider a float line with a fully automated offloading process using robots to pick up glass plates from the float line. The continuous nature of the process causes some glass to be wasted if it is cut but cannot be picked up in time. Such wasted glass is called cycle time scrap. Even if any glass cut could easily be offloaded, the laying out of the customers' orders on to the ribbon can incur waste known as layout scrap. We define and model a problem of optimizing the cutting sequence and the layout of the glass being cut so that the total amount lost to cycle time scrap and layout scrap is small. We develop heuristic solution methods using construction and local search algorithms for this problem. We validate the proposed approach using real data from a major float glass manufacturer and show that it produces manufacturing yields greater than 99%.

Flat glass manufacturing is a continuous process whereby a ribbon of molten glass is produced in a furnace and then cooled on a bath of molten tin to ensure flatness. The continuous glass ribbon is then carried on rollers through an annealing lehr, machine-cut according to customer size requirements, and offloaded for distribution. The equipment in this process, beginning with the furnace and ending with the offloading equipment, constitutes a float line (see Fig. 1). Assuming that any glass cut could easily be offloaded, the problem of fitting all of the customers' orders into the smallest-possible piece of ribbon is very similar to traditional 2-dimensional cutting problems. In this case, the only way glass is wasted (other than breakage) is in the process of laying out orders on the ribbon. This wasted glass, or scrap, is known as layout scrap. This paper considers a float line in a glass plant that has recently fully automated their previously manual offloading process by using machines to pick up glass plates from the float line. There are clear safety and cost advantages to performing offloading with robots rather than humans, but the automation is more restricted in the amount of glass it can offload per unit time. As a result, some additional glass might be wasted if it is cut but cannot be picked up in time to clear the line for the next glass produced. This additional scrap is known as cycle time scrap because it is caused by the cycle time (minimum time between pickups) of the picking machines. Of course, cycle time scrap could be eliminated by purchasing more automated equipment, but each machine costs millions of dollars. It is preferable to optimize the sequence and layout of the glass being cut so that the total amount lost to cycle time scrap and layout scrap is small. Although the literature addresses some individual aspects of the float glass problem, we are unaware of any model in the literature that deals with the full complexity of the problem. The float glass problem resembles a guillotine version of the two-dimensional cutting-stock problem (2D CSP) studied by Gilmore and Gomory, 1961 and Gilmore and Gomory, 1963 and the trim-loss problems surveyed by Hinxman (1980). However, the 2D CSP and the trim-loss problems address only layout scrap. The float glass problem has the added complexity of cycle time scrap. Some cases of the trim-loss problems surveyed by Dyckhoff et al. (1985) consider sequencing. Dyson and Gregory (1974) propose two-stage methods for the trim-loss problem in the flat glass industry. The first stage generates a set of cutting patterns and the second stage optimizes the sequencing of the set of cutting patterns so that the number of discontinuities is minimized. Madsen (1980) studied the cutting problem with an additional sequencing constraint that some glass pieces should be cut within a certain time interval. Their sequencing issue is different from that of our float glass problem, where sequencing is caused by the relation between the cutting and offloading operations. Another related problem is two-stage hybrid flow shop (HFS) scheduling with no intermediate storage and identical parallel machines in the second stage. The cutting and offloading operations in the float glass problem make up the two stages of a flow shop, and minimizing cycle time scrap is equivalent to scheduling to minimize processing time. Sriskandarajah (1993) studies worst case performance analysis for no-wait (or blocking) flowshops with parallel machines. However, HFS scheduling does not address layout scrap. Moreover, the operational restriction such as machine dedication, which will be explained in the next section, makes the float glass problem harder. See Linn and Zhang (1999) for general HFS scheduling, and see Gupta and Tunc (1991) for the HFS with parallel machines at the second stage. Also, see Pinedo (2008) for the flow shop with limited intermediate storage. Other related literature concerns cyclic scheduling. When a set of orders is produced in a no-wait flowshop and each order has multiple units, the same schedule is repeated over and over again. This repeated pattern is called a cyclic schedule in operations research (see McCormick et al., 1989 or Pinedo, 2008) and a campaign in chemical processes (see Birewar and Grossmann, 1989a and Birewar and Grossmann, 1989b). The float glass problem also yields cyclic schedules, but because of the machine dedication and machine cycle time properties, which will be explained in the next section, the type of cycles that appear in the float glass problem has a different structure than those considered previously. With regard to real-world applications of flat glass cutting, Arbib and Fabrizio (2007) proposed a heuristic algorithm to minimize trim loss in float glass manufacturing for the automotive market. The cutting phase is the same as our's in that vertical and horizontal cutting is made. However, after cutting, glass is stacked in a buffer and the unloading process is very different than our's. In our float glass problem, unloading (offloading) occurs directly on a conveyor line rather than a separate buffer. Therefore, offloading and cutting should be simultaneously considered. Another real-world glass cutting problem studied by Puchinger et al. (2004) considers an additional cutting constraint that customer orders are grouped according to the destination of delivery. Dash et al. (2007) study the problem of producing rectangular plates for a steel company to minimize scrap, but do not consider the sequencing issue. Thus, none of these earlier works adequately captures the full complexity of the float glass problem. Na et al. (to appear) introduce FGSP (float glass scheduling problem) in which cycle time scrap is considered but layout scrap is not. They show that the problem is NP-hard, and identify when each of the problem's components are polynomially solvable and when they induce hardness. In addition, they propose a simple heuristic algorithm, provide its worst-case performance bounds, and demonstrate that the bounds are tight. When the number of machines is two, the worst-case performance is 5/35/3. Na (2011) shows that the float glass problem is NP-hard in general, and introduces a mixed-integer programming (MIP) formulation. However, because of the MIP's size and difficulty, state-of-the art commercial solvers are unable to find good solutions within a reasonable amount of time. Therefore, we present a heuristic solution approach to solve the float glass problem. We will empirically show that the proposed heuristic solution approach produces nearly optimal solutions for a collection of randomly generated and real-world test problems. In the Problem Description section, we introduce the relevant characteristics of a float line, and describe the sequencing and layout optimization problem. In the Solution Approach section, we present heuristic algorithms to solve the problem. The performance of the proposed algorithms is demonstrated in the Computational Results section. We conduct sensitivity analysis on the number of offloading machines in the Sensitivity Analysis section.

Motivated by operational issues in real-world glass manufacturing, this paper addressed a problem of laying out and sequencing orders so as to minimize wasted glass, called scrap. There are two different types of scrap, layout scrap and cycle time scrap, and a number of operational restrictions are imposed by the manufacturer because of the limitations of the glass-making process and the equipment involved. We proposed a two-phase approach: snap construction and constructing cutting and offload schedules. The heuristic solution methods which we proposed improve manufacturing yields from 95% (the current practice) to greater than 99%. According to the United States census bureau, the costs of materials for the flat glass manufacturing industry in the U.S. was $1609 million in 2007 (United States Census Bureau, 2013). Therefore, a 4% increase in manufacturing yields can contribute a savings of about $64 million in the flat glass manufacturing industry of the U.S. and much more globally. Moreover, our sensitivity analysis helps to give managerial insights regarding issues such as the optimal number of offloading machines.