A heuristic and a branch-and-bound algorithm for the assembly line worker assignment and balancing problem

DOI10.1016/J.COR.2013.12.002MaRDI QIDQ336970zbMATH OpenOpenAlexFDO

Authors Leonardo Borba, Marcus Ritt

Publication date 10 November 2016

Published in Computers \& Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

assembly line balancingMIPbranch-and-boundbeam searchheterogeneous workers

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10) Production models (90B30)

Abstract: In traditional assembly lines, it is reasonable to assume that task execution times are the same for each worker. However, in sheltered work centres for disabled this assumption is not valid: some workers may execute some tasks considerably slower or even be incapable of executing them. Worker heterogeneity leads to a problem called the assembly line worker assignment and balancing problem (ALWABP). For a fixed number of workers the problem is to maximize the production rate of an assembly line by assigning workers to stations and tasks to workers, while satisfying precedence constraints between the tasks. This paper introduces new heuristic and exact methods to solve this problem. We present a new MIP model, propose a novel heuristic algorithm based on beam search, as well as a task-oriented branch-and-bound procedure which uses new reduction rules and lower bounds for solving the problem. Extensive computational tests on a large set of instances show that these methods are effective and improve over existing ones.

Recommendations

• A branch-and-bound algorithm for assembly line worker assignment and balancing problems
• A competitive branch-and-bound algorithm for the simple assembly line balancing problem
• Model and heuristics for the assembly line worker integration and balancing problem
• An efficient branch and bound algorithm for assembly line balancing problems with parallel multi-manned workstations
• An efficient heuristic method for the simple assembly line balancing problem
• A dynamic programming based heuristic for the assembly line balancing problem
• An enumerative heuristic and reduction methods for the assembly line balancing problem
• Bounds for Assembly Line Balancing Heuristics
• A heuristic algorithm for two-sided assembly line balancing

Cites work

• A branch, bound, and remember algorithm for the simple assembly line balancing problem
• A branch-and-bound algorithm for assembly line worker assignment and balancing problems
• A classification of assembly line balancing problems
• A survey on problems and methods in generalized assembly line balancing
• Amortized efficiency of a path retrieval data structure
• An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type-II
• An linear programming based lower bound for the simple assembly line balancing problem
• Branch and bound procedures for solving the assembly line worker assignment and balancing problem: Application to sheltered work centres for disabled
• Duality-Based Algorithms for Scheduling Unrelated Parallel Machines
• Exact and approximation algorithms for makespan minimization on unrelated parallel machines
• On solving the assembly line worker assignment and balancing problem via beam search
• State-of-the-art exact and heuristic solution procedures for simple assembly line balancing
• Stochastic assembly line balancing using beam search
• Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing
• The stochastic U-line balancing problem: a heuristic procedure

Cited in

(31)

• Multi-manned assembly line balancing problem with dependent task times: a heuristic based on solving a partition problem with constraints
• Branch and bound procedures for solving the assembly line worker assignment and balancing problem: Application to sheltered work centres for disabled
• A new MILP model for the accessibility windows assembly line balancing problem level 2 (AWALBP-L2)
• Flow shop scheduling with heterogeneous workers
• An heuristic algorithm for the production line layout problem
• A systematic approach for an application of personnel selection in assembly line balancing problem
• Traveling worker assembly line (re)balancing problem: model, reduction techniques, and real case studies
• A branch-and-bound algorithm for assembly line worker assignment and balancing problems
• Enhanced branch-bound-remember and iterative beam search algorithms for type II assembly line balancing problem
• Exact and heuristic methods for a workload allocation problem with chain precedence constraints
• Exact and heuristic methods for solving the robotic assembly line balancing problem
• Developing optimization \& robust models for a mixed-model assembly line balancing problem with semi-automated operations
• Optimal workforce assignment to operations of a paced assembly line
• The multi-objective assembly line worker integration and balancing problem of type-2
• The robust (minmax regret) assembly line worker assignment and balancing problem
• A Branch and Cut Approach for Workload Smoothing on Assembly Lines
• A memetic algorithm for the cost-oriented robotic assembly line balancing problem
• Robotic disassembly line balancing problem: a mathematical model and ant colony optimization approach
• On solving the assembly line worker assignment and balancing problem via beam search
• A multiple single-pass heuristic algorithm solving the stochastic assembly line rebalancing problem
• Ergonomic risk and cycle time minimization for the U-shaped worker assignment assembly line balancing problem: a multi-objective approach
• Branch-and-bound algorithms for the multi-product assembly line balancing problem
• Assembly line balancing problems with multi-manned stations: a new mathematical formulation and Gantt based heuristic method
• Hybrid metaheuristics for the accessibility windows assembly line balancing problem level 2 (AWALBP-L2)
• A branch, bound and remember algorithm for maximizing the production rate in the simple assembly line balancing problem
• Benders' decomposition based exact solution method for multi-manned assembly line balancing problem with walking workers
• Model and heuristics for the assembly line worker integration and balancing problem
• Heuristics and simulated annealing procedures for the accessibility windows assembly line problem level 1 (AWALBP-L1)
• An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type-II
• Exact makespan minimization of unrelated parallel machines
• Model and metaheuristic for human-robot collaboration assembly line worker assignment and balancing problem

Describes a project that uses

Uses Software

• SALBPGen

This page was built for publication: A heuristic and a branch-and-bound algorithm for the assembly line worker assignment and balancing problem

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