×

Mathematical modeling and optimal blank generation in glass manufacturing. (English) Zbl 1442.90207

Summary: This paper discusses the stock size selection problem [M. L. Chambers and R. G. Dyson, “The cutting stock problem in the flat glass industry-selection of stock sizes”, Oper. Res. Quart. 27, No. 4, 949–957 (1976; doi:10.1057/jors.1976.187)], which is of relevance in the float glass industry. Given a fixed integer \(N\), generally between 2 and 6 (but potentially larger), we find the \(N\) best sizes for intermediate stock from which to cut a roster of orders. An objective function is formulated with the purpose of minimizing wastage, and the problem is phrased as a combinatorial optimization problem involving the selection of columns of a cost matrix. Some bounds and heuristics are developed, and two exact algorithms (depth-first search and branch-and-bound) are applied to the problem, as well as one approximate algorithm (NOMAD). It is found that wastage reduces dramatically as \(N\) increases, but this trend becomes less pronounced for larger values of \(N\) (beyond 6 or 7). For typical values of \(N\), branch-and-bound is able to find the exact solution within a reasonable amount of time.

MSC:

90C90 Applications of mathematical programming
90C27 Combinatorial optimization
90C56 Derivative-free methods and methods using generalized derivatives
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

NOMAD; OrthoMADS
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem, Operations Research, 9, 6, 849-859 (1961) · Zbl 0096.35501
[2] Gilmore, P. C.; Gomory, R. E., Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 1, 94-120 (1965) · Zbl 0128.39601
[3] Sweeney, P.; Paternoster, E., Cutting and packing problems: a categorized, application-orientated research bibliography, Journal of the Operational Research Society, 43, 7, 691-706 (1992)
[4] Hifi, M., An improvement of Viswanathan and Bagchi’s exact algorithm for constrained two-dimensional cutting stock, Computers & Operations Research, 24, 8, 727-736 (1997) · Zbl 0914.90225
[5] Burke, E. K.; Kendall, G.; Whitwell, G., A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52, 4, 655-671 (2004) · Zbl 1165.90690
[6] Chambers, M. L.; Dyson, R. G., The cutting stock problem in the flat glass industry-selection of stock sizes, Operational Research Quarterly, 27, 4, 949-957 (1976)
[7] Reese, J., Solution methods for the p-median problem: an annotated bibliography, Networks, 48, 3, 125-142 (2006) · Zbl 1133.90357
[8] Mladenović, N.; Brimberg, J.; Hansen, P.; Moreno-Pérez, J. A., The p-median problem: a survey of metaheuristic approaches, European Journal of Operational Research, 179, 3, 927-939 (2007) · Zbl 1163.90610
[9] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), McGraw-Hill
[10] Land, A. H.; Doig, A. G., An automatic method of solving discrete programming problems, Econometrica: Journal of the Econometric Society, 28, 497-520 (1960) · Zbl 0101.37004
[11] Abramson, M. A.; Audet, C.; Dennis,, J. E.; Le Digabel, S., OrthoMADS: a deterministic MADS instance with orthogonal directions, SIAM Journal on Optimization, 20, 2, 948-966 (2009) · Zbl 1189.90202
[12] Audet, C.; Dennis,, J. E., Mesh adaptive direct search algorithms for constrained optimization, SIAM Journal on Optimization, 17, 1, 188-217 (2006) · Zbl 1112.90078
[13] Audet, C.; Dennis,, J. E., A progressive barrier for derivative-free nonlinear programming, SIAM Journal on Optimization, 20, 1, 445-472 (2009) · Zbl 1187.90266
[14] Audet, C.; Le Digabel, S.; Tribes, C., NOMAD user guide, G-2009-37 (2009), Les cahiers du GERAD · Zbl 1187.90266
[15] Le Digabel, S., Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm, ACM Transactions on Mathematical Software, 37, 4, 1-15 (2011) · Zbl 1365.65172
[16] Abramson, M. A.; Audet, C.; Couture, G.; Dennis, J. E.; Le Digabel, S.; Tribes, C., The NOMAD project
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.