Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads

Abstract : In this paper, a new transfer line balancing problem is considered. The main difference from the simple assembly line balancing problem is that the operations are grouped into blocks (batches). All the operations of the same block are carried out simultaneously by one piece of equipment (multi-spindle head). Nevertheless, the blocks assigned to the same workstation are executed in series. The line cost consists of the sum of block and workstation costs. At the considered line design stage, the set of all available blocks is given. The aim is to find a subset from the given set of available blocks and to find a partition of this subset to workstations such that each operation is executed once and the line cost is minimal while all the precedence, cycle time, and compatibility (operation inclusion and block exclusion) constraints are respected. A new lower bound based on solving a special set partitioning problem is presented and a branch and bound algorithm is developed. The experimental results prove the quality of the lower bound and applicability of the suggested branch and bound algorithm for medium sized industrial cases.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2009, Volume 197 (Issue 3), pp.Pages 1119-1132. 〈10.1016/j.ejor.2008.03.028〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00676013
Contributeur : Florent Breuil <>
Soumis le : vendredi 2 mars 2012 - 16:12:33
Dernière modification le : mardi 23 octobre 2018 - 14:36:08

Identifiants

Citation

Alexandre Dolgui, I. Ihnatsenka. Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads. European Journal of Operational Research, Elsevier, 2009, Volume 197 (Issue 3), pp.Pages 1119-1132. 〈10.1016/j.ejor.2008.03.028〉. 〈emse-00676013〉

Partager

Métriques

Consultations de la notice

116