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.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2012, Volume 39 (Issue 10), pp.Pages 2337-2345. 〈10.1016/j.cor.2011.11.022〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00660791
Contributeur : Florent Breuil <>
Soumis le : mardi 17 janvier 2012 - 16:34:42
Dernière modification le : mardi 22 mars 2016 - 01:16:37

Identifiants

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〉

Partager

Métriques

Consultations de la notice

117