Reduction approaches for a generalized line balancing problem

Abstract : An NP-hard optimization problem dealing with the assignment of operations to the workstations and spindle heads of a machining transfer line is studied. Precedence, inclusion and exclusion constraints among the operations, capacity and cycle time constraints exist. The objective is to minimize the cost of the line being designed. This problem has been referred to as the Transfer Line Balancing Problem (TLBP) and is a generalized case of well-known simple assembly line balancing problem. In literature, few exact methods have been proposed to solve it. Since the problem is NP-hard, those that do are too time-consuming for solving real life industrial cases. This paper presents effective pre-processing methods which can reduce the size of the initial problem in order to shorten the solution time required. These methods are evaluated on three datasets of new generated problem instances and known benchmarks. The results obtained show that for certain cases the solution time can be significantly reduced when these pre-processing methods are applied.
Document type :
Journal articles
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00660791
Contributor : Florent Breuil <>
Submitted on : Tuesday, January 17, 2012 - 4:34:42 PM
Last modification on : Thursday, October 17, 2019 - 12:36:12 PM

Identifiers

Citation

Olga Battaïa, Alexandre Dolgui. Reduction approaches for a generalized line balancing problem. Computers and Operations Research, Elsevier, 2012, Volume 39 (Issue 10), pp.Pages 2337-2345. ⟨10.1016/j.cor.2011.11.022⟩. ⟨emse-00660791⟩

Share

Metrics

Record views

220