Skip to Main content Skip to Navigation
Conference papers

Combinatorial design of a minimum cost machining line

Abstract : We study a problem related to the optimal design of a machining line. This type of line is used for a mass production of a single type of product. To produce an item of this product a given set of operations has to be performed. The line is a sequence of workstations, whose number has to be decided, and each workstation has to be assigned a number of processing modules (blocks). Each block performs a set of operations. A set of available blocks is given. There are the same basic cost associated with each workstation and different additional costs associated with the blocks. The problem is to design a minimum cost machining line of this type. The specicity of the problem is that all operations of the blocks assigned to the same workstation are performed in parallel. Furthermore, there are inclusion, exclusion and precedence relations that restrict the assignment of blocks and operations to the same workstation and the processing order of operations on the line. We suggest two combinatorial approaches for solving this problem, which are theoretically efficient if the number of blocks assigned to the same workstation and the number of workstations are upper bounded by given constants. The first approach is to combinatorially enumerate all feasible solutions, and the second consists in reducing the problem to the well studied maximum weight clique problem. A boolean linear program based on a set packing formulation of the latter problem is presented, and computer experiments with benchmark data are described.
Document type :
Conference papers
Complete list of metadata
Contributor : Florent Breuil Connect in order to contact the contributor
Submitted on : Friday, March 16, 2012 - 11:02:27 AM
Last modification on : Wednesday, August 4, 2021 - 3:42:04 PM


  • HAL Id : emse-00679704, version 1


Alexandre Dolgui, Xavier Delorme, Mikhail Y. Kovalyov. Combinatorial design of a minimum cost machining line. Workshop New Challenges in Scheduling Theory, Sep 2010, Frejus, France. ⟨emse-00679704⟩



Record views