Approximation algorithms for simple assembly line balancing problems

Santiago Valdés Ravelo ()
Additional contact information
Santiago Valdés Ravelo: Federal University of Rio Grande do Sul

Journal of Combinatorial Optimization, 2022, vol. 43, issue 2, No 7, 432-443

Abstract: Abstract This work considers the three main optimization variants of the Simple Assembly Line Balancing problem (SALBP): SALBP-1, SALBP-2 and SALBP-E. These problems have origin in typical industrial production processes, where, to obtain a final product, partially ordered operations must be processed in workstations connected by a transportation equipment. Each version determines a different objective to be optimized: SALBP-1 focuses on minimizing the number of workstations while maintaining a certain production rate, SALBP-2 tries to maximize the production rate with a bounded number of workstations, and SALBP-E attempts to maximize the line efficiency. These problems are NP-hard and have been largely studied in the literature, however, the results on their approximability are scarce. This work approaches SALBP-1, SALBP-2 and SALBP-E, proving an equivalence on approximating in polynomial time SALBP-2 and a generalization of SALBP-E, and proposing very efficient polynomial time 2-approximation algorithms for each one of these three versions of SALBP.

Keywords: Simple assembly line balancing problem; Approximation algorithm; NP-hard; Combinatorial optimization (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00778-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:43:y:2022:i:2:d:10.1007_s10878-021-00778-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00778-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().