Reduction approaches for a generalized line balancing problem - Mines Saint-Étienne Access content directly
Journal Articles Computers and Operations Research Year : 2012

Reduction approaches for a generalized line balancing problem


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.

Dates and versions

emse-00660791 , version 1 (17-01-2012)



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



Gmail Facebook X LinkedIn More