IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v202y2010i3p747-755.html
   My bibliography  Save this article

Optimizing glass coating lines: MIP model and valid inequalities

Author

Listed:
  • Gicquel, C.
  • Miégeville, N.
  • Minoux, M.
  • Dallery, Y.

Abstract

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.

Suggested Citation

  • Gicquel, C. & Miégeville, N. & Minoux, M. & Dallery, Y., 2010. "Optimizing glass coating lines: MIP model and valid inequalities," European Journal of Operational Research, Elsevier, vol. 202(3), pages 747-755, May.
    • Handle: RePEc:eee:ejores:v:202:y:2010:i:3:p:747-755
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00493-7
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Boysen, Nils & Fliedner, Malte, 2008. "A versatile algorithm for assembly line balancing," European Journal of Operational Research, Elsevier, vol. 184(1), pages 39-56, January.
    2. Kalvenes, Joakim & Kennington, Jeffery & Olinick, Eli, 2005. "Hierarchical cellular network design with channel allocation," European Journal of Operational Research, Elsevier, vol. 160(1), pages 3-18, January.
    3. Boysen, Nils & Fliedner, Malte & Scholl, Armin, 2007. "A classification of assembly line balancing problems," European Journal of Operational Research, Elsevier, vol. 183(2), pages 674-693, December.
    4. Anulark Pinnoi & Wilbert E. Wilhelm, 1998. "Assembly System Design: A Branch and Cut Approach," Management Science, INFORMS, vol. 44(1), pages 103-118, January.
    5. Zeghal, F.M. & Minoux, M., 2006. "Modeling and solving a Crew Assignment Problem in air transportation," European Journal of Operational Research, Elsevier, vol. 175(1), pages 187-209, November.
    6. Becker, Christian & Scholl, Armin, 2006. "A survey on problems and methods in generalized assembly line balancing," European Journal of Operational Research, Elsevier, vol. 168(3), pages 694-715, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Scholl, Armin & Fliedner, Malte & Boysen, Nils, 2010. "Absalom: Balancing assembly lines with assignment restrictions," European Journal of Operational Research, Elsevier, vol. 200(3), pages 688-701, February.
    2. Boysen, Nils & Schulze, Philipp & Scholl, Armin, 2022. "Assembly line balancing: What happened in the last fifteen years?," European Journal of Operational Research, Elsevier, vol. 301(3), pages 797-814.
    3. Sternatz, Johannes, 2014. "Enhanced multi-Hoffmann heuristic for efficiently solving real-world assembly line balancing problems in automotive industry," European Journal of Operational Research, Elsevier, vol. 235(3), pages 740-754.
    4. Walter, Rico & Schulze, Philipp & Scholl, Armin, 2021. "SALSA: Combining branch-and-bound with dynamic programming to smoothen workloads in simple assembly line balancing," European Journal of Operational Research, Elsevier, vol. 295(3), pages 857-873.
    5. Moreira, Mayron César O. & Costa, Alysson M., 2013. "Hybrid heuristics for planning job rotation schedules in assembly lines with heterogeneous workers," International Journal of Production Economics, Elsevier, vol. 141(2), pages 552-560.
    6. García-Villoria, Alberto & Corominas, Albert & Nadal, Adrià & Pastor, Rafael, 2018. "Solving the accessibility windows assembly line problem level 1 and variant 1 (AWALBP-L1-1) with precedence constraints," European Journal of Operational Research, Elsevier, vol. 271(3), pages 882-895.
    7. Borba, Leonardo & Ritt, Marcus & Miralles, Cristóbal, 2018. "Exact and heuristic methods for solving the Robotic Assembly Line Balancing Problem," European Journal of Operational Research, Elsevier, vol. 270(1), pages 146-156.
    8. Corominas, Albert & Pastor, Rafael & Plans, Joan, 2008. "Balancing assembly line with skilled and unskilled workers," Omega, Elsevier, vol. 36(6), pages 1126-1132, December.
    9. Chica, Manuel & Bautista, Joaquín & Cordón, Óscar & Damas, Sergio, 2016. "A multiobjective model and evolutionary algorithms for robust time and space assembly line balancing under uncertain demand," Omega, Elsevier, vol. 58(C), pages 55-68.
    10. Boysen, Nils & Fliedner, Malte, 2008. "A versatile algorithm for assembly line balancing," European Journal of Operational Research, Elsevier, vol. 184(1), pages 39-56, January.
    11. Hamta, Nima & Fatemi Ghomi, S.M.T. & Jolai, F. & Akbarpour Shirazi, M., 2013. "A hybrid PSO algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect," International Journal of Production Economics, Elsevier, vol. 141(1), pages 99-111.
    12. Marcus Ritt & Alysson M. Costa & Cristóbal Miralles, 2016. "The assembly line worker assignment and balancing problem with stochastic worker availability," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 907-922, February.
    13. Armin Scholl & Nils Boysen & Malte Fliedner, 2009. "Optimally solving the alternative subgraphs assembly line balancing problem," Annals of Operations Research, Springer, vol. 172(1), pages 243-258, November.
    14. Özcan, Ugur, 2010. "Balancing stochastic two-sided assembly lines: A chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm," European Journal of Operational Research, Elsevier, vol. 205(1), pages 81-97, August.
    15. Bautista, Joaquín & Pereira, Jordi, 2011. "Procedures for the Time and Space constrained Assembly Line Balancing Problem," European Journal of Operational Research, Elsevier, vol. 212(3), pages 473-481, August.
    16. Wen-Chyuan Chiang & Timothy L. Urban & Chunyong Luo, 2016. "Balancing stochastic two-sided assembly lines," International Journal of Production Research, Taylor & Francis Journals, vol. 54(20), pages 6232-6250, October.
    17. Arnd Huchzermeier & Tobias Mönch, 2023. "Mixed‐model assembly lines with variable takt and open stations," Production and Operations Management, Production and Operations Management Society, vol. 32(3), pages 704-722, March.
    18. Ibrahim Kucukkoc & Kadir Buyukozkan & Sule Itir Satoglu & David Z. Zhang, 2019. "A mathematical model and artificial bee colony algorithm for the lexicographic bottleneck mixed-model assembly line balancing problem," Journal of Intelligent Manufacturing, Springer, vol. 30(8), pages 2913-2925, December.
    19. M. H. Alavidoost & M. H. Fazel Zarandi & Mosahar Tarimoradi & Yaser Nemati, 2017. "Modified genetic algorithm for simple straight and U-shaped assembly line balancing with fuzzy processing times," Journal of Intelligent Manufacturing, Springer, vol. 28(2), pages 313-336, February.
    20. Tiacci, Lorenzo, 2015. "Simultaneous balancing and buffer allocation decisions for the design of mixed-model assembly lines with parallel workstations and stochastic task times," International Journal of Production Economics, Elsevier, vol. 162(C), pages 201-215.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:202:y:2010:i:3:p:747-755. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.