Logo
DATOS DEL INVESTIGADOR PRINCIPAL
Nombre Juan Carlos Gutiérrez Vanegas
Nombre del perfíl Investigador Por Proyecto
Grupo de investigación Métodos Cuantitativos e investigación operativa
Línea de investigación Estrategia, planeación y programación de la producción
Equipo del proyecto
TÍTULO DEL PROYECTO MINIMIZAR EL "MAKESPAN" EN UN SISTEMA "FLOW SHOP" CONSIDERANDO EFECTOS DE APRENDIZAJE UTILIZANDO BUSQUEDA TABÚ.
PALABRAS CLAVE Flow shop, Learning Effect, Tabu Search
OBJETIVOS DEL PROYECTO Determinar secuencias cercanas al óptimo en ambiente reales de producción, al considerar un sistema flow shop con efecto de aprendizaje (learning effect).
Mostrar que tener en cuenta el efecto de aprendizaje al construir la secuencia de producción puede generar ahorros significativos en la utilización de los recursos.
Construir un algoritmo de aplicación simple para la determinar el nivel de aprendizaje a partir de datos reales de producción.
Construir un algoritmo de búsqueda tabú como soporte a la determinación de las secuencias en el problema de secuenciación de un sistema flow shop considerando efecto de aprendizaje.
Construir una interfaz de usuario simple que permita la aplicación del algoritmo desarrollado en ambientes reales de producción.
PERTINENCIA ESPISTEMOLÓGICA DEL PROYECTO La importancia de optimizar la programación de la producción, trasciende en la empresa a todas las actividades relacionadas con el proceso productivo, por ejemplo, complementa a la planeación agregada, allí la primera fija los períodos en los cuales se debe producir, mientras que la secuenciación es la encargada de lograr que dicha planeación se cumpla. Además una buena programación de la producción libera la carga de las máquinas en tiempos más cortos, permitiendo de esta manera que se facilite la programación de mantenimientos, así como también permite un nivel de cumplimiento de las fechas de entrega mucho más alto, lo que aumenta directamente el nivel de servicio que puede mantener una compañía. Otro aspecto que mejora considerablemente es el factor de utilización de los equipos, porque un resultado de una buena secuenciación es la reducción inminente de tiempos improductivos en las máquinas. Por lo tanto en un sistema productivo una mejora en la programación de la producción beneficia directa e indirectamente a todo el sistema productivo, cualquiera que éste sea.
RELEVANCIA DEL PROYECTO PARA LA INSTITUCIÓN Y PARA LOS BENEFICIARIOS DEL PROYECTO En cuanto a formación el desarrollo del proyecto permitirá al departamento de ingeniería industrial utilizar los resultados (entregables) en los cursos de Física de Planta y Scheduling. El artículo del estado del arte puede ser un proyecto de estudio para el curso de sheduling a partir del segundo semestre de 2011, mientras que el aplicativo podrá ser utilizado por los dos cursos a partir del año 2012.

Por otra parte, incluyendo el aspecto de pertinencia y proyección social y empresarial, se puede utilizar el aplicativo desarrollado en el proyecto para buscar un acercamiento de la universidad con el entorno empresarial. Este objetivo, además de servir al compromiso social de la universidad, permitirá a los estudiantes, a través de prácticas o proyectos de investigación, que se centren en la implementación del aplicativo en diferentes compañías productivas logrando un contacto directo con la solución de problemas que aumenten la competitividad de nuestra industria.
PROBLEMA DE INVESTIGACIÓN ¿Es posible construir un algoritmo de búsqueda tabú que encuentre una secuencia de forma eficiente para procesar n trabajos en m máquinas en un sistema flow shop con tiempos de proceso dependientes de la secuencia y de tal manera que minimice el MAKESPAN?
METODOLOGÍA Tipo de investigación: Cuantitativa
Universo de investigación: Artículos en publicaciones indexadas que incluyan los problemas de secuenciación en sistemas flow shop o aquellos que ataquen el problema considerando efecto de aprendizaje.
Características de la muestra: en al muestra se incluirán todos los artículos relevantes, priorizando los publicados a partir del año 2000.
Técnicas para la recolección de la muestra: Se consultaran las principales bases de datos: ScienceDirect, ProQuest. Adicionalmente se consultarán los principales textos sobre los temas básicos.
Descripción general: La solución al problema comienza con la revisión bibliográfica de artículos relevantes para establecer el estado del arte en este campo. Una vez establecida la base de conocimiento se procederá a desarrollar el esquema conceptual del algoritmo propuesto, al igual que un aplicativo de fácil aplicación para la determinación del efecto de aprendizaje en un ambiente
productivo. Después se programara el algoritmo propuesto en un lenguaje de programación de propósito general y se conectará con el aplicativo construido anteriormente para el efecto de aprendizaje. Finalmente, el desempeño del algoritmo se determinará a partir de instancias construidas para tal fin siguiendo los lineamientos encontrados en la revisión bibliográfica.
RESULTADOS ESPERADOS Al final del proyecto se espera contar con un algoritmo eficiente que permita resolver el problema de secuenciación en un sistema flow shop al considerar efectos de aprendizaje. Dicho algoritmo deberá estar programado en un lenguaje de propósito general y con una interfaz de usuario sencilla que permita su rápida implementación en diferentes compañías productivas. En detalle al final del proyecto se espera obtener:
Artículo de revisión (Estado del arte en los problemas de scheduling considerando efecto de aprendizaje)
Software registrado ante Colciencias: (Aplicativo conjunto para medir el efecto de aprendizaje y para hallar la secuencia)
El articulo de revisión será en una publicación subtipo A y deberá obtener 1.0 punto en la categoría de Nuevo conocimiento.
El software registrado ante Colciencias será subtipo A y deberá obtener 1.0 punto en la categoría de Nuevo conocimiento.
DURACIÓN DEL PROYECTO
POSIBLES FUENTES DE FINANCIACIÓN EXTERNA
REVISIÓN BIBLIOGRÁFICA En lo que concierne a estudios del efecto de aprendizaje en problemas de secuenciación el desarrollo es muy pobre, los pocos trabajos que se han encontrados se concentran en una sola máquina (Single-Machine) y máquinas en paralelo (Parallel-Machine), en el primer caso se puede destacar el publicado por D. Biskup [4] en 1999 quien mostró que por lo menos en una máquina los objetivos de tiempo total de terminación de todos los trabajos (Total Flowtime) y desviación de la fecha de entrega (Deviation From A Common Due Date) se siguen resolviendo en un tiempo polinomial al incluir el efecto del aprendizaje en los tiempos de proceso de la forma pij = pij(r)c. Después G. Mosheiov [6] en su trabajo añade la solución para el problema del máximo tiempo de terminación de todos los trabajos en una sola máquina, y presenta algoritmos de solución para 2 problemas multicriterio en una máquina que aunque se resuelven en tiempo polinomial requieren un esfuerzo computacional más alto que para el caso tradicional, esto es, sin considerar efecto de aprendizaje. Finalmente también extiende sus alcances hasta sistemas de máquinas en paralelo en donde muestra que la regla SPT (Shortest Processing Time) no es óptima para el problema del tiempo total de terminación de todos los trabajos.

Referencias

A Bachman, TCE Cheng, A Janiak, CT Ng. Scheduling start time dependent jobs to minimize the total weighted completion time. Journal of the Operational Research Society (2002) 53, 688–693.

A Kononov, S Gawiejnowicz. NP-hard cases in scheduling deteriorating jobs on dedicated machines. Journal of the Operational Research Society (2001) 52, 708-717.

B Alidaee, NK Womer. Scheduling with time dependent processing times: Review and extensions. Journal of the Operational Research Society (1999) 50, 711-720.

Baker K, Trietsch D, Principles of Sequencing and Scheduling. Wiley, (2009).

Chen C, Neppalli V, Aljaber N. Genetic algorithms applied to the continuous flow shop problem. Computers Ind Engng (1996) 30: 919–929.

Chin-Chia Wu & Wen-Chiung Lee. Single-machine and flowshop scheduling with a general learning effect model. Computers & Industrial Engineering (2009) 56: 1553-1558

Chin-Chia Wu, Wen-Chiung Lee & Wei-Chieh Wang. A Two Machine Flowshop Maximun Tardiness Scheduling Problem with a Learning Effect. Int. J. Manufacturing Tecnology (2007) 31: 743-750

CT Daniel Ng, TCE Cheng, MY Kovalyov. Batch scheduling with controllable setup and processing times to minimize total completion time. Journal of the Operational Research Society (2003) 54, 499–506.

Dirk Biskup. A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research (2008) 188: 315-329

Gangadharan R, Rajendran C. Heuristic algorithms for scheduling in the no-wait flowshop. International Journal Prod Econo (1993) 32: 285–290.

Garey MR, Johnson DS, Sethi R. Complexity of flow-shop and job-shop scheduling. Mathemathical Operations Research (1976) 1: 117–129.

Gonzalez T. y S Shani. Flowshop and Jobshop schedules: Complexity and approximation. Operations Research (1978) 26; 36-52.

Gupta JND. A functional heuristic algorithm for the flow-shop scheduling problem. Opl Res Quart (1971) 22: 39–47.

Ignall E. J., Schrage L.E., Application of the Branch and Bound technique to some flow shop scheduling problem. Operations research (1965) 13: 3.

Igor Averbakh; Oded Berman. A simple heuristic for m-machine flow-shop and its applications in routing-scheduling problems. Operations Research; Jan/Feb (1999) 47, 1; ABI/INFORM Global pg. 165.

Ishibuchi H, Murata T. A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans Systems, Man, Cybern—Part C: Appl Rev (1998) 28: 392–403.

Ji-Bo Wang & Li-Li Liu. Two-machine flow shop problem with effects of deterioration and learning. Computers & Industrial Engineering (2009) 57: 1114-1121

Ji-Bo Wang, Lin Lin and Feng Shan. Flow Shop Scheduling with Effects of Learning and Deterioration. Journal of Applied Mathematics and Computing (2000) Volume 26, Numbers 1-2, 367-379

JR Wang. A fuzzy set approach to activity scheduling for product development. Journal of the Operational Research Society (1999) 50, 1217-1228.

Lominicki Z., A Branch and Bound algorithm for the exact solution for the Tree-Machines scheduling problem. Operational Research Quarterly (1965) 16; 1.

MingBao Cheng, ShiJie Sun & Ying Yu. A Note on Flow Shop Scheduling Problems with a Learning Effect on No-Idle Dominant Machines. Applied Mathematics and Computation (2007) 184: 945-949

MS Nagano, JV Moccellin. A high quality solution constructive heuristic for flow shop sequencing. Journal of the Operational Research Society (2002) 53, 1374–1379.

Morton T, Pentico D, Heuristic Scheduling Systems: With Applications to Production Systems and Project Management. Wiley, (1993)

Nagar A, Haddock J, Heragu S. A branch-and-bound approach for a two-machine flowshop scheduling problem. Journal of Operatinal Research Society (1995) 46: 721–734.

Nagar A, Haddock J, Heragu S. A combined branchand- bound and genetic algorithm based approach for a flowshop scheduling problem. Annals of Operations Research (1996) 46: 397–414.

Nawaz M, Enscore Jr. EE, Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega (1983) 11: 91–95.

Philip Kaminsky; David Simchi-Levi .The asymptotic óptimality of the SPT rule for the flow shop mean completion time problem. Operations Research; Mar/Apr (2001); 49, 2; ABI/INFORM Global pg. 293.


Pinedo M, Scheduling: Theory, Algorithms, and Systems, Third Edition. Springer, (2008)

Prawda Witenberg Juan. Métodos y modelos de investigación de operaciones, V,2. (1993) Limusa Noriega Editores.

Rajendran C. A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria. International Journal of Production Research (1994) 32: 2541–2558.

Rajendran C. A no-wait flowshop scheduling heuristic to minimize makespan. Journal of Operatinal Research Society (1994) 45: 472–478.

Rajendran C, Chaudhuri D. Heuristic algorithms for continuous flow-shop problem. Nav Res Log (1990) 37: 695–705.

Ramudhin, Amar; Bartholdi, John J III; Calvin, James M; Vande Vate, John H; Weiss G. A probabilistic analysis of two-machine flowshops. Operations Research; Nov/Dec (1996) 44, 6; ABI/INFORM Global pg. 899.

Shiqiang Liu, H L Ong. A comparative study of algorithms for the flowshop scheduling problem. Asia - Pacific Journal of Operational Research; Nov (2002) 19, 2; ABI/INFORM Global pg. 205.

Sivrikaya-Serifoglu F, Ulusoy G. A bicriteria two-machine permutation flowshop problem. European Journal of Operatinal Research (1998) 107: 414–430.

Sridhar J, Rajendran C. Scheduling in flowshop and cellular manufacturing systems with multiple objectives—a genetic algorithm approach. Prod Plan Control (1996) 7: 374–382.

Tamer Eren & Ertan Güner. A bicriteria flowshop scheduling with a learning effect. Applied Mathematical Modelling (2008) 32: 1719 - 1733

T C E Cheng; A Janiak. A permutation flow-shop scheduling problem with convex models of operation processing times. Annals of Operations Research (2000) 96, 1; ABI/INFORM Global pg. 39.

Writh T.P., Factors affecting the cost of airplanes, Journal of Aeronautical Sciences 3 (1936), 122 -128.

Yeh WC. A new branch-and-bound approach for the n=2 flowshop a F||bCmax flowshop scheduling problem. Computers Operations Research (1999) 26: 1293–1310.

Yeh WC. An efficient branch-and-bound algorithm for the two-machine bicriteria flowshop scheduling problem. J Manuf Systems (2001) 20: 113–123.

Zhang Xingong & Yan Guangle. Machine Scheduling Problems with a General Learning Effect. Mathematical and Computer Modelling (2010) 51: 84-90

Zhiyong Xu, Linyan Sun & Juntao Gong. Worst-case analysis for flow shop scheduling with a learning effect. Int. J. Production Economics (2008) 113: 748-753
ENTREGABLES
CRONOGRAMA
TIPO DESCRIPCIÓN F.INICIO F.FINAL
Actividad Revisión Bibliográfica 01/06/2011 23/09/2011
Entregable Artículo del Estado del Arte 04/08/2011 23/09/2011
Actividad Desarrollo aplicativo para medir el efecto de aprendizaje 02/09/2011 01/11/2011
Actividad Modelo conceptual del algoritmo de búsqueda tabú 02/09/2011 01/11/2011
Actividad Programación del algoritmo en software de propósito general 06/10/2011 02/01/2012
Actividad Verificación del algoritmo 04/11/2011 02/01/2012
Actividad Combinación del algoritmo de búsqueda tabú y el aplicativo de efecto de aprendizaje 01/12/2011 30/01/2012
Actividad Creación de las instancias de prueba 01/12/2011 30/01/2012
Actividad Validación de los resultados y ajustes generales 05/01/2012 28/02/2012
Entregable Software: Interfaz y manual del usuario. 03/02/2012 30/03/2012
PEDIDO DE BIBLIOGRAFÍA
AUTOR TÍTULO EDITORIAL
Michael Pinedo Scheduling: Theory, Algorithms, and Systems (Third Edition) Springer
Thomas Morton, David W. Pentico Heuristic Scheduling Systems: With Applications to Production Systems and Project Management Wiley
Kenneth R. Baker, Dan Trietsch Principles of Sequencing and Scheduling Wiley
David R. Anderson, Dennis J. Sweeney, Thomas A. Williams Quantitative Methods for Business, 10th Edition Cengage Learning
ANEXOS