×

Optimizing glass coating lines: MIP model and valid inequalities. (English) Zbl 1176.90415

Summary: Glass coating is a specific transformation aiming at improving glass performance. The work presented in this paper deals with the determination of the optimal configuration of the production lines used to perform this operation. We propose a first MIP formulation of the problem and then discuss several types of valid inequalities for improving it. The main idea is to exploit explicit or implicit binary exclusion constraints to derive stronger valid inequalities: the maximal clique constraints. Efficient (polynomial time) separation algorithms exploiting special structure of the problem are described, giving rise to a cutting-plane generation procedure for strengthening the initial formulation. The computational study carried out shows that, with the enhanced formulation, good solutions can be obtained within reasonable computation times using currently available integer programming software.

MSC:

90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

CPLEX

References:

[1] Arnaud, A., Industrial production of coated glass: Future trends for expanding needs, Journal of Non-crystalline Solids, 218, 12-18 (1997)
[2] Becker, C.; Scholl, A., A survey on problems and methods in generalized assembly line balancing, European Journal of Operational Research, 168, 694-715 (2006) · Zbl 1083.90013
[3] Boysen, N.; Fliedner, M., A versatile algorithm for assembly line balancing, European Journal of Operational Research, 184, 39-56 (2008) · Zbl 1152.90412
[4] Boysen, N.; Fliedner, M.; Scholl, A., A classification of assembly line balancing problems, European Journal of Operational Research, 183, 674-693 (2007) · Zbl 1179.90103
[5] Bukchin, J.; Tzur, M., Design of flexible assembly line to minimize equipment cost, IIE Transactions, 32, 585-598 (2000)
[6] Goycoolea, M.; Murray, A.; Barohona, F.; Epstein, R.; Weintraub, A., Harvest scheduling subject to maximum area restrictions: Exploring exact approaches, Operations Research, 53, 3, 490-500 (2005) · Zbl 1165.91444
[7] ILOG, 2002. ILOG CPLEX 8.0: User’s Manual. ILOG, Gentilly, France.; ILOG, 2002. ILOG CPLEX 8.0: User’s Manual. ILOG, Gentilly, France.
[8] Kalvenes, J.; Kennington, J.; Olinick, E., Hierarchical cellular network design with channel allocation, European Journal of Operational Research, 160, 3-18 (2005) · Zbl 1067.90016
[9] Maier, D., The complexity of some problems on subsequences and supersequences, Journal of the Association for Computing Machinery, 25, 2, 322-336 (1978) · Zbl 0371.68018
[10] Miegeville, N., 2005. Supply Chain Optimization in the process industry. Methods and case study of the glass industry. Ph.D. Thesis, Ecole Centrale de Paris, Paris, France.; Miegeville, N., 2005. Supply Chain Optimization in the process industry. Methods and case study of the glass industry. Ph.D. Thesis, Ecole Centrale de Paris, Paris, France.
[11] Nemhauser, G.; Wolsey, L., Integer and Combinatorial Optimization (1988), John Wiley and Sons: John Wiley and Sons USA · Zbl 0652.90067
[12] Pinnoi, A.; Wilhelm, W., Assembly system design: A branch and cut approach, Management Science, 44, 1, 103-118 (1998) · Zbl 0989.90049
[13] Suzuki, K., State of the art in large area vacuum coatings on glass, Thin solid films, 351, 8-14 (1999)
[14] Zeghal, F.; Minoux, M., Modeling and solving a crew assignment problem in air transportation, European Journal of Operational Research, 175, 187-209 (2006) · Zbl 1137.90596
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.