Solución del Problema de Flow Shop Flexible Aplicando el Algoritmo Genético de Chu- Beasley
Resumen
El problema de secuenciación de tareas en sistemas de producción lineal Flow Shop ha sido un tema de gran importancia en la investigación de operaciones donde se busca establecer la programación óptima de trabajos en máquinas dentro de un proceso de producción en una industria en general. En este trabajo se presenta una metodología para dar solución al problema de Flow Shop Flexible teniendo en cuenta las particularidades del problema y aprovechando las características combinatoriales del mismo. El modelo matemático es resuelto usando Algoritmo Genético de Chu-Beasley. La metodología es validada mediante la evaluación de 9 casos de prueba de la literatura especializada de baja, media y alta complejidad matemática.
Descargas
Citas
R. Gallego, A. Escobar y E. Toro, “Técnicas Metaheurísticas de Optimización”, Texto Universitario Universidad Tecnológica de Pereira, Segunda Edición, 2008.
S. M. Johnson, “Optimal Two and Three Stage Production Schedules with Setup Times Included”, The Rand Corporation, pp 402 (1 a t10), 1953.
C. Reeves, “A Genetic Algorithm for Flow-Shop Sequencing” .Computers Ops. Vol. 22, N° 1, pp 5-13, 1995
C. Rajendran, H Ziegler, “An Efficient Heuristic for Scheduling in a Flow-Shop to Minimize Total Weighted Flow time of Jobs”, European Journal of Operational Research 103, pp 129-138, 1997.
C. Koulamas, “A New Constructive Heuristic for The Flow-Shop Scheduling Problem”, European Journal of Operational Research 105, pp 66-71, 1998.
M.C. Portmann, A. Vignier, D. Dardilhac, D. Dezalay, “Branch and Bound Crossed With GA to Solve Hybrid Flow-Shops”, European Journal of Operational Research 107, pp389-400, 1998.
E. Nowicki, C. Smutnicki, “The Flow-Shop with Parallel Machines: A Tabu Search Approach”. European Journal of Operational Research 106, pp226-253, 1998.
T. Sawik, “Mixed Integer Programming for Scheduling Flexible Flow Lines with Limited Intermediate Buffers”, Mathematical and Computer Modelling 31, pp39-52, 2000.
M. Azizoglu, E. Cakmak, S. Kondakci, “A Flexible Flow-Shop Problem with Total Flow Time Minimization”, European Journal of Operational Research 132, pp 528-538, 2001.
J. Liu, C. Reeves, “Constructive and Composite Heuristic Solutions to the P//ΣCi Scheduling Problem”, European Journal of Operational Research 132, pp 439-452, 2001.
V. T’kindt, N. Monmarché, F. Tercinet, D. Laugt, “An Ant Colony Optimization Algorithm to Solve a 2-Machine Bicriteria Flow-Shop Scheduling Problem”, European Journal of Operational Research 142, pp250–257, 2002.
E. Stafford., F Tseng, “Two Models for a Family of Flow-Shop Sequencing Problems”, European Journal of Operational Research 142, pp 282–293, 2002.
X. Sun, K. Morizawa, H. Nagasawa, “Powerful Heuristics to Minimize Makespan in Fixed, 3-Machine, Assembly-type FlowShop Scheduling”, European Journal of Operational Research 146, pp498–516, 2003.
A. Fink, “Solving the Continuous Flow-Shop Scheduling Problem by Metaheuristics”, European Journal of Operational Research 151, pp 400–414, 2003.
B. Wardono, Y. Fathi, “A Tabu Search Algorithm for the MultiStage Parallel Machine Problem with Limited Buffer Capacities”, European Journal of Operational Research 155, pp 380–401, 2004.
S. Bertel, J.-C.Billaut, “A Genetic Algorithm for an Industrial Multiprocessor Flow Shop Scheduling Problem with Recirculation”, European Journal of Operational Research 159, pp 651–662, 2004.
C. Rajendran, H. Ziegler, “Ant-Colony Algorithms for Permutation Flow-Shop Scheduling to Minimize Makespan/Total Flowtime of Jobs”, European Journal of Operational Research 155, pp 426–438, 2004.
M Kurz, R. Askin, “Scheduling Flexible Flow Lines with SequenceDependent Setup Times”, European Journal of Operational Research 159, pp 66–82, 2004.
C.Akkan, S. Karabatı, “The Two-Machine Flow-Shop Total Completion Time Problem: Improved Lower Bounds and a BranchAnd-Bound Algorithm”, European Journal of Operational Research 159, pp420–429, 2004.
R. Ruizy C. Maroto, “A Comprehensive Review and Evaluation of Permutation Flow-ShopHeuristics”, European Journal of Operational Research 165, pp479–494, 2005.
T.K. Varadharajan, C. Rajendran, “A Multi-Objective SimulatedAnnealing Algorithm for Scheduling in Flow-Shops to Minimize the Makespan and Total Flowtime of Jobs”, European Journal of Operational Research 167, pp 772–795, 2005.
J. Arroyo, V. Amaral, “Genetic Local Search for Multi-Objective Flow-Shop Scheduling Problems”, European Journal of Operational Research 167, pp717–738, 2005.
R. Ruiz, C. Maroto, J.Alcaraz, “Solving the Flow-Shop Scheduling Problem with Sequence Dependent Setup Times Using Advanced Metaheuristics”, European Journal of Operational Research 165, pp34–54, 2005.
R. Ruiz y C.Maroto, “A Genetic Algorithm for Hybrid Flow-Shops with Sequence Dependent Setup Times and Machine Eligibility”. European Journal of Operational Research 169, pp781–800, 2006.
M. Tasgetiren, Y. Liang, M.Sevkli, G. Gencyilmaz, “A Particle Swarm Optimization Algorithm for Makespan and Total Flowtime Minimization in the Permutation Flow-Shop Sequencing Problem”, European Journal of Operational Research 177, pp 1930–1947, 2007.
M. Zandieh, E. Mozaffari, M. Gholami, “A Robust Genetic Algorithm for Scheduling Realistic Hybrid Flexible Flow Line Problems”, J IntellManuf, pp 731–743, 2009.
D. Sipper, y B. Robert, “Planeación y Control de la Producción”, México, McGraw Hill. 1998.
http://portal.ku.edu.tr/~coguz/research.htm Koç University
<
Revista Entre Ciencia e Ingeniería .png)
entrecei@ucp.edu.co.png)
ISSN (Impreso) 1909-8367 - ISSN (En Línea) 2539-4169
Attribution-NonCommercial 4.0 International (CC By-NC 4.0)
.png)
Carrera 21 No. 49-95 Av. de las Américas, Pereira, Risaralda, Colombia