https://hal-emse.ccsd.cnrs.fr/emse-00679704Dolgui, AlexandreAlexandreDolguiLaboratoire en Sciences et Technologies de l'Information - MSGI-ENSMSE - Département Méthodes Scientifiques pour la Gestion Industrielle - Mines Saint-Étienne MSE - École des Mines de Saint-Étienne - IMT - Institut Mines-Télécom [Paris] - Centre G2I - ROGI-ENSMSE - Equipe : Recherche Opérationnelle pour le Génie Industriel - Mines Saint-Étienne MSE - École des Mines de Saint-Étienne - IMT - Institut Mines-Télécom [Paris] - UR LSTIDelorme, XavierXavierDelormeMSGI-ENSMSE - Département Méthodes Scientifiques pour la Gestion Industrielle - Mines Saint-Étienne MSE - École des Mines de Saint-Étienne - IMT - Institut Mines-Télécom [Paris] - Centre G2IROGI-ENSMSE - Equipe : Recherche Opérationnelle pour le Génie Industriel - Mines Saint-Étienne MSE - École des Mines de Saint-Étienne - IMT - Institut Mines-Télécom [Paris] - UR LSTIKovalyov, Mikhail Y.Mikhail Y.KovalyovNASB - National Academy of Sciences of BelarusCombinatorial design of a minimum cost machining lineHAL CCSD2010Line designbuffer allocationcomplexitygenetic algorithm[INFO.INFO-MO] Computer Science [cs]/Modeling and SimulationBreuil, Florent2012-03-16 11:02:272021-08-04 15:42:042012-03-16 11:02:27enConference papers1We 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.