Genetic algorithm for a balancing machining lines problem

Abstract : We consider the problem of designing a reconfigurable machining line. Such a line is composed of a sequence of workstations performing specific sets of operations. Each workstation is consists in several identical CNC machines (machining centers). The line is required to satisfy the given precedence order, inclusion, exclusion and accessibility constraints on the given set of operations. Inclusion and exclusion are types of zoning constraints which oblige or forbid certain operations to be performed on the same workstation. The accessibility constraints imply that each operation has a set of possible part positions under which it can be performed. All the operations performed on the same workstation must have a common part position. The workstation times are computed taking into account processing and setup times for operations and must not exceed a given bound. The number of CNC machines at one workstation is limited, and the total number of machines must be minimized. A genetic algorithm is proposed. This algorithm is based on the permutation representation of solutions. A heuristic decoder is proposed to construct a solution from a permutation, so that the output solution is feasible w.r.t. precedence, accessibility, cycle time, and exclusion constraints. The other constraints are treated by a penalty approach. For a local improvement of the solutions, a mixed integer programming model is suggested for an optimal design of workstations if the order of operations is fixed. An application of such a procedure ensures that an optimal solution can be found with a nonzero probability. The algorithm is implemented in GAMS and the computer experiments on large scale test instances are performed.
Type de document :
Communication dans un congrès
41st International Conference on Computers & Industrial Engineering, Oct 2011, Los Angeles, United States. pp. 116-121, 2011
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00710372
Contributeur : Florent Breuil <>
Soumis le : mercredi 20 juin 2012 - 17:01:38
Dernière modification le : mardi 23 octobre 2018 - 14:36:11

Identifiants

  • HAL Id : emse-00710372, version 1

Citation

Pavel Borisovsky, Xavier Delorme, Alexandre Dolgui. Genetic algorithm for a balancing machining lines problem. 41st International Conference on Computers & Industrial Engineering, Oct 2011, Los Angeles, United States. pp. 116-121, 2011. 〈emse-00710372〉

Partager

Métriques

Consultations de la notice

94