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

DOI10.1111/ITOR.12206MaRDI QIDQ5374525zbMATH OpenOpenAlexFDO

Authors Marcus Ritt, Alysson M. Costa

Publication date 14 September 2018

Published in International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.0934

zbMATH Keywords

assembly line balancinginteger linear programmingprecedence constraintsstation limitsvalid inequalities

Mathematics Subject Classification ID

Integer programming (90C10) Applications of mathematical programming (90C90)

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.

Recommendations

• An linear programming based lower bound for the simple assembly line balancing problem
• An improved mathematical program to solve the simple assembly line balancing problem
• Integer programming models for the design and balancing of flexible assembly systems
• An Integer Programming Algorithm with Network Cuts for Solving the Assembly Line Balancing Problem
• A method for mixed-model assembly line balancing problem
• State-of-the-art exact and heuristic solution procedures for simple assembly line balancing
• Model and heuristics for the assembly line worker integration and balancing problem
• The type E simple assembly line balancing problem: a mixed integer linear programming formulation
• Cost-oriented assembly line balancing: model formulations, solution difficulty, upper and lower bounds

Cited in

(16)

• Shortest-route formulation of mixed-model assembly line balancing problem
• Solving the accessibility windows assembly line problem level 1 and variant 1 (AWALBP-L1-1) with precedence constraints
• Benders' decomposition for the balancing of assembly lines with stochastic demand
• Assembly line balancing: what happened in the last fifteen years?
• The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problem
• Cost-oriented assembly line balancing: model formulations, solution difficulty, upper and lower bounds
• An improved mathematical program to solve the simple assembly line balancing problem
• Analysis of the simple assembly line balancing problem complexity
• In-line kitting for part feeding of assembly lines: workload balancing and storage assignment to reduce the workers' walking effort
• Modelling and a hybrid genetic algorithm for the equity-oriented worker assignment problem in seru production systems
• A multi‐objective hybrid evolutionary search algorithm for parallel production line balancing problem including disassembly and assembly tasks
• New mathematical and constraint programming models for U-type assembly line balancing problems with assignment restrictions
• A new upper bound based on Dantzig-Wolfe decomposition to maximize the stability radius of a simple assembly line under uncertainty
• Domain-independent dynamic programming
• On the MILP model for the U-shaped assembly line balancing problems
• Solving logic-based benders decomposition master problems with constraint programming and domain-independent dynamic programming

This page was built for publication: Improved integer programming models for simple assembly line balancing and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5374525)