Improved integer programming models for simple assembly line balancing and related problems

2011/11/03 by Marcus Ritt, Ritt, Marcus, Alysson M. Costa +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO

paper · pdf · doi:10.48550/arxiv.1111.0934

17 pages

arxiv created 2015/08/10 · arxiv updated 2015/08/11

Abstract

We propose a stronger formulation of the precedence constraints and the station limits for the simple assembly line balancing problem. The linear relaxation of the improved integer program theoretically dominates all previous formulations using impulse variables, and produces solutions of significantly better quality in practice. The improved formulation can be used to strengthen related problems with similar restrictions. We demonstrate their effectiveness on the U-shaped assembly line balancing problem and on the bin packing problem with precedence constraints.

Related

• Solving Assembly Line Balancing Problems by Combining IP and CP
• Domain-Independent Dynamic Programming and Constraint Programming Approaches for Assembly Line Balancing Problems with Setups
• Assembly line balancing with task division
• A branch, price and remember algorithm for the U shaped assembly line balancing problem
• A Receding Horizon Control For General Assembly Line Balancing Problems