Solución de un problema de secuenciamiento en configuración jobshop flexible utilizando un Algoritmo de Estimación de Distribuciones.

R. Pérez, S. Jöns, A. Hernández

Resumen

El problema de secuenciamiento en configuración jobshop flexible se refiere en asignar operaciones de diversos trabajos a un conjunto de equipos disponibles. La asignación mencionada busca generalmente minimizar el tiempo de culminación de todos los trabajos conocido en la literatura como ‘makespan’. Se propone un Algoritmo de Estimación de Distribuciones para Secuenciamiento, AEDS por simplicidad y funcionalidad. El AEDS intenta encontrar una relación o interacción entre las variables de entrada, trabajos, operaciones y turnos de trabajo, para optimizar la variable de salida de procesos de manufactura reales, el makespan. En este sentido el algoritmo AEDS es usado para guiar la búsqueda y resolver el problema. En el marco del algoritmo, tres modelos gráficos fueron usados para encontrar mejores soluciones. Establecer horas fuera de servicio para los operadores antes de iniciar sus actividades en cada turno de trabajo como parámetro de entrada y su desarrollo a través del algoritmo AEDS constituye una novedad de esta investigación respecto los trabajos existentes. La comparación entre AEDS y un algoritmo genético muestra la efectividad del AEDS resolviendo el problema enunciado. Usando el AEDS propuesto, el desempeño de procesos de manufactura reales mejora notablemente cuando diferentes equipos disponibles son asignados a diferentes programas de producción.

Palabras clave

Secuenciamiento; Algoritmo de Estimación de Distribuciones

Texto completo:

PDF

Referencias

Baluja S., Davies S., 1997. Combining multiple optimization runs with optimal dependency trees. Technical Report CMU-CS-97-157, Carnegie Mellon University.

Bean J., Norman B., 1993. Random keys for job shop scheduling problem. Technical Report TR 93-7, The University of Michigan.

Chen S.H., Chen M.C., Chang P.C., Zhang Q., Chen Y.M., 2010a. Guidelines for developing effective Estimation of Distribution Algorithms in solving single machine scheduling problems. Expert Systems with Applications 37, 6441-6451.

Chen S.H., Chang P.C., Cheng T., Zhang Q., 2012b. A Self-guided Genetic Algorithm for permutation flowshop scheduling problems. Computers and Operations Research 39, 1450-1457.

Chen Y.M., Chen M.C., Chang P.C., Chen S.H., 2012c. Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems. Computers and Industrial Engineering 62, 536-545.

De Bonet J., Isbell C., Viola P., 1997. MIMIC: Finding Optima by Estimation Probability Densities. Advances in Neural Information Processing Systems 9.

Greenwood A., Vanguri S., Eksioglu B., Jain P., Hill T., Miller J., Walden C., 2005. Simulation Optimization Decision Support System for Ship Panel Shop Operations. En Kuhl M.E., Steiger N.M., Armstrong F., Joines J. (Eds.), Proceedings of the 2005 Winter Simulation Conference, pp. 2078- 2086.

Jarboui V., Eddaly M., Siarry P., 2009. An Estimation of Distribution Algorithm for minimizing the total flow time in permutation flowshop scheduling problems. Computers and Operations Research 36, 2638-2646.

Larrañaga P., Exteberria R., Lozano J., Peña J., 2000. Optimization in continuous domains by learning and simulation of Gaussian networks. En Wu A. (Ed.), Proceedings of the 2000 Genetic and Evolutionary Computation Conference Workshop Program, pp. 201-204.

Liu H., Gao L., Pan Q., 2011. A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem. Experts Systems with Applications 38, 4348-4360.

Mühlenbein H., Paaß G., 1996. From recombination of genes to the estimation of distributions: I. binary parameters. En Voigt H., Ebeling W., Rechenberg I., Schwefel H. (Eds.), Parallel Problem Solving from Nature PPSN IV, Springer, Berlin, pp. 178–187.

Pan Q.K., Ruiz R., 2012. An estimation of distribution algorithm for lotstreaming flow shop problems with setup times. Omega 40, 166-180.

Peña J., Peña-Robles V., Larrañaga P., Herves V., Rosales F., Pérez M., 2004. Ga-eda: hybrid evolutionary algorithm using genetic and estimation of distribution algorithms. En Orchard B., Yang C., Ali M. (Eds.), Innovations in applied artificial intelligence 3029, Lecture notes in computer science, Berlin/Heidelberg, pp. 361-371.

Rudolph G., 1991. Global optimization by means of distributed evolution strategies. En Schwefel H., Manner R. (Eds.), Parallel Problem Solving from Nature PPSN I, Lectures Notes in Computer Science. 496, SpringerVerlag, pp. 209-213.

Shim V.A., Chen Tan K., Yong Chia J., Kiat Chong J., 2011. Evolutionary algorithms for solving multi-objective travelling salesman problem. Flexible Service and Manufacturing Journal 23, 207-241.

Wang L., Wang S., Xu Y., Zhou G., Liu M., 2012. A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem. Computers and Industrial Engineering 62, 917-926.

Zhang Y., Li X., 2011. Estimation of distribution algorithm for permutation flow shops with total flowtime minimization. Computers and Industrial Engineering 60, 706-718.

Abstract Views

807
Metrics Loading ...

Metrics powered by PLOS ALM




Creative Commons License

Esta revista se publica bajo una Licencia Creative Commons Attribution-NonCommercial-CompartirIgual 4.0 International (CC BY-NC-SA 4.0)

Universitat Politècnica de València     https://doi.org/10.4995/riai

e-ISSN: 1697-7920     ISSN: 1697-7912