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.
Document type :
Conference papers
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00679624
Contributor : Florent Breuil <>
Submitted on : Friday, March 16, 2012 - 9:09:03 AM
Last modification on : Thursday, October 17, 2019 - 12:36:46 PM

Identifiers

  • 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. ⟨emse-00679624⟩

Share

Metrics

Record views

130