algoritmo

RESUMEN
En este estudio se propone e implementa computacionalmente un algoritmo genético secuencial para
resolver el problema del Job Shop Flexible (existente en la Gestión de Operaciones), el cual es parte de
la familia de los problemas de programación de tareas o trabajos (Scheduling) en un taller que funciona
a pedido. Surge como una generalización del problema del Job Shop y permiteoptimizar el uso de los
recursos (máquinas) con mayor flexibilidad, ya que cada máquina puede realizar más de una operación. Este
problema ha sido estudiado por numerosos autores, los que han propuesto diversos modelos matemáticos
y enfoques heurísticos. Debido a la naturaleza combinatoria, los métodos exactos que resuelven modelos
matemáticos encuentran soluciones sólo para instancias pequeñas osimples del problema mencionado.
Los resultados muestran la efectividad del algoritmo propuesto para entregar buenas soluciones en tiempos
computacionales razonables en más de 130 instancias encontradas en la literatura.
Palabras clave: Problema Job Shop Flexible, algoritmos genéticos, programación de trabajos, optimización
combinatoria, gestión de operaciones.
ABSTRACT
This study proposesand computationally implements a sequential genetic algorithm to solve the Flexible
Job Shop problem (found in Operations Management), which is part of the family of job or task scheduling
problems in a shop that works on demand. It is a generalization of the Job Shop problem, and allows
optimizing the use of resources (machines) in the shop, with greater flexibility, since each machine canperform more than one operation. This problem has been studied by many authors, who have proposed
various mathematical models and heuristic approaches. Due to the combinatorial nature of the problem,
the exact methods that solve the mathematical models are often solutions for small and simple instances
of the problem. The results show the effectiveness of the proposed algorithm to provide goodsolutions
in reasonable computational times in over 130 instances found in the literatura.
Keywords: Flexible Job Shop problem, genetic algorithms, scheduling, combinatorial optimization,
operations management.
1 Departamento de Ingeniería Industrial. Facultad de Ingeniería. Universidad de Concepción. Casilla 160-C. Correo 3. Concepción,
Chile. E-mail: rosmedina@udec.cl; lpradena@udec.cl
2Departamento de Ingeniería Informática. Facultad de Ingeniería. Universidad de Santiago de Chile. Avda. Ecuador 3659. Santiago,
Chile. E-mail: victor.parada@usach.cl
INTRODUCCIÓN
En la programación de la producción de las
industrias manufactureras se debe decidir sobre
la asignación de los recursos a las tareas o
trabajos para optimizar, uno o más objetivos
en el corto plazo. Para apoyar estasdecisiones
tradicionalmente se utiliza el modelo de Job Shop,
el cual considera un conjunto de máquinas y un
conjunto de trabajos compuestos por una secuencia
ordenada de operaciones que se deben procesar
en las máquinas con el objetivo de minimizar,
entre otros, el tiempo de completación de la
última operación, makespan.
Ingeniare. Revista chilena de ingeniería, vol. 19 Nº 1, 2011
54
Elproblema de Job Shop Flexible es una generalización
del problema de Job Shop. Considera que las
operaciones pueden ser procesadas por un grupo
de máquinas, razón por la cual también se requiere
decidir sobre cuáles de las máquinas procesan cada
operación.
Por ejemplo, consideremos un taller metal-mecánico,
en el que se reciben dos trabajos compuestos por una
secuencia fija de tresoperaciones a realizar en tres
máquinas. El primero requiere las operaciones de
perforar, ranurar y pulir, mientras el segundo trabajo
requiere cortar, limar y perforar. El taller dispone
de un torno, que puede realizar las operaciones de
perforar, pulir y cortar; una fresadora que puede
perforar, ranurar, pulir y limar; y un taladro que
puede perforar, ranurar y cortar. Los tiempos de
las...