A Minimum Cost Transfer Line Design Problem : A Set Partitioning Model And Computer Experiments

Abstract : A transfer line can be viewed as a sequence of (work)stations such that a part moves along them in the same direction, and machining modules, called blocks, perform required operations. A block is associated with a set of operations it can perform. We study a design problem, in which there is a (ground) set of blocks, from which a subset of blocks must be selected and its blocks must be assigned to a number of stations such that each required operation is performed once. The objective is to minimize the total cost associated with the stations and the blocks. The specific conditions are that operations of the same station are performed in parallel, and there are the following constraints : upper bound m0 on the number of stations, upper bound n0 on the number of blocks of each station, plural exclusion constraints on the set of blocks, plural inclusion constraints and binary precedence constraints on the set of operations. Blocks of a given set exclude each other if all of them cannot be assigned to the same station, while any their proper subset can be assigned to the same station. Inclusion relations specify that all the operations of a certain set must be assigned to the same station. Finally, if operation i precedes operation j, then j cannot be executed on the station of i or any preceding station. This problem, denoted as P, was introduced by Dolgui et al. [3] and Belmokhtar et al. [1]. Belmokhtar et al. [2] described existing solution methodologies for this problem and computationally tested them on benchmark instances. We reduce problem P to a set partitioning problem by using a new concept of locally feasible (LF) station. An LF-station is a collection of blocks, W, such that jWj n0, each operation of W belongs to exactly one block ofW, and the exclusion, inclusion and precedence relations are satisfied for the blocks and operations ofW. The set of all possible LF-stations, W = fW1; : : : ;WKg, can be constructed in polynomial time if n0 is a given constant.
Type de document :
Communication dans un congrès
12ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2011), Mar 2011, Saint Etienne, France. pp.submission 399, 2011
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00679624
Contributeur : Florent Breuil <>
Soumis le : vendredi 16 mars 2012 - 09:09:03
Dernière modification le : dimanche 28 janvier 2018 - 15:22:05

Identifiants

  • HAL Id : emse-00679624, version 1

Citation

Pavel Borisovski, Alexandre Dolgui, Sergey Kovalev. A Minimum Cost Transfer Line Design Problem : A Set Partitioning Model And Computer Experiments. 12ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2011), Mar 2011, Saint Etienne, France. pp.submission 399, 2011. 〈emse-00679624〉

Partager

Métriques

Consultations de la notice

102