New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Combinatorial design of a minimum cost machining line

SpeakerAlexandre Dolgui

Co-authorXavier Delorme (Ecole des Mines de Saint-Etienne, France) and Mikhail Y. Kovalyov (National Academy of Sciences of Belarus)

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.