A heuristic and a branch-and-bound algorithm for the assembly line worker assignment and balancing problem
From MaRDI portal
Publication:336970
DOI10.1016/J.COR.2013.12.002zbMATH Open1348.90220arXiv1308.0299OpenAlexW2021558860MaRDI QIDQ336970FDOQ336970
Authors: Leonardo Borba, Marcus Ritt 
Publication date: 10 November 2016
Published in: Computers \& Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1308.0299
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
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10) Production models (90B30)
Cites Work
- A classification of assembly line balancing problems
- State-of-the-art exact and heuristic solution procedures for simple assembly line balancing
- A survey on problems and methods in generalized assembly line balancing
- Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing
- A branch, bound, and remember algorithm for the simple assembly line balancing problem
- The stochastic U-line balancing problem: a heuristic procedure
- Stochastic assembly line balancing using beam search
- A branch-and-bound algorithm for assembly line worker assignment and balancing problems
- An linear programming based lower bound for the simple assembly line balancing problem
- Amortized efficiency of a path retrieval data structure
- Exact and approximation algorithms for makespan minimization on unrelated parallel machines
- Branch and bound procedures for solving the assembly line worker assignment and balancing problem: Application to sheltered work centres for disabled
- An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type-II
- Duality-Based Algorithms for Scheduling Unrelated Parallel Machines
- On solving the assembly line worker assignment and balancing problem via beam search
Cited In (25)
- A multiple single-pass heuristic algorithm solving the stochastic assembly line rebalancing problem
- Exact makespan minimization of unrelated parallel machines
- Model and metaheuristic for human-robot collaboration assembly line worker assignment and balancing problem
- Branch and bound procedures for solving the assembly line worker assignment and balancing problem: Application to sheltered work centres for disabled
- 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
- A memetic algorithm for the cost-oriented robotic assembly line balancing problem
- 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
- Robotic disassembly line balancing problem: a mathematical model and ant colony optimization approach
- Ergonomic risk and cycle time minimization for the U-shaped worker assignment assembly line balancing problem: a multi-objective approach
- 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
- Traveling worker assembly line (re)balancing problem: model, reduction techniques, and real case studies
- Enhanced branch-bound-remember and iterative beam search algorithms for type II assembly line balancing problem
- A Branch and Cut Approach for Workload Smoothing on Assembly Lines
- Model and heuristics for the assembly line worker integration and balancing problem
- An heuristic algorithm for the production line layout problem
- On solving the assembly line worker assignment and balancing problem via beam search
- A systematic approach for an application of personnel selection in assembly line balancing problem
- Branch-and-bound algorithms for the multi-product assembly line balancing problem
- Flow shop scheduling with heterogeneous workers
- Exact and heuristic methods for a workload allocation problem with chain precedence constraints
- A branch-and-bound algorithm for assembly line worker assignment and balancing problems
Uses Software
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)
