Cookies y Privacidad
Usamos cookies propias y de terceros para mejorar la experiencia de nuestros usuarios, analizar el tráfico del sitio y personalizar contenido. Si continúas navegando, asumimos que aceptas su uso. Para más información, consulta nuestra Política de Cookies
Un algoritmo branch-and-bound para el problema de programación de proyectos con recursos limitados, coste de disponibilidad de recursos y modos múltiples
En un estudio reciente (YAMASHITA; MORABITO, 2007a), se propuso un algoritmo exacto para resolver problemas de programación de proyectos con restricciones de recursos y costes de disponibilidad de recursos bajo múltiples modos de ejecución. Dicho algoritmo es una adaptación de otro algoritmo exacto registrado en la literatura para el caso particular en el que sólo existe un único modo de ejecución de las tareas. En el presente estudio, proponemos un nuevo algoritmo exacto basado en el método branch and bound para tratar el problema de múltiples modos de ejecución. Dado que el problema es NP-difícil, el algoritmo es computacionalmente viable sólo para problemas de tamaño moderado. Se han realizado numerosas pruebas computacionales utilizando el generador ProGen para comparar el rendimiento del algoritmo propuesto con el algoritmo anterior y con el software CPLEX. Los resultados muestran que la versión propuesta del algoritmo es competitiva con los otros métodos y animan a seguir investigando para el desarrollo de versiones más elaboradas de este algoritmo.
1. INTRODUCCIÓN
Los problemas de programación de proyectos consisten en planificar en el tiempo actividades que requieren recursos para su realización. Esta programación también debe tener en cuenta las restricciones de precedencia entre las actividades, es decir, ciertas actividades sólo pueden iniciarse después de que otras se hayan completado. Ejemplos de problemas de programación de proyectos aparecen en diversas áreas (MODER et al., 1983; POLLACK-JOHNSON; LIBERATORE, 1998), como la construcción civil (TAKAMOTO et al., 1995), la fabricación (NEUMANN et al., 2002), las telecomunicaciones, el desarrollo de software/ordenadores, el mantenimiento de aeronaves (GEMMILL; EDWARDS, 1999), entre otros. Por ejemplo, en la construcción de un puente, la adquisición de material, la contratación de mano de obra y las diversas etapas que componen la construcción, como la preparación del terreno, la cimentación, las estructuras de pilares, las vigas y losas, la pavimentación, son algunas de las actividades del proyecto. Estas actividades tienen una duración prevista en función de los recursos asignados y, para poder llevarse a cabo, también están sujetas a relaciones de precedencia. La ejecución de las actividades consume diferentes recursos como máquinas, mano de obra, dinero, etc.
Algunos problemas de programación de proyectos permiten que las actividades se ejecuten de formas alternativas (múltiples modos de ejecución). Por ejemplo, una actividad que requiere 10 periodos de tiempo para ser ejecutada por 1 trabajador, podría realizarse alternativamente en 4 periodos de tiempo utilizando 2 trabajadores.
Autores: Sato Yamashita, Denise; Morabito, Reinaldo
Idioma: Portugues
Editor: UFSCar Universidade Federal de Sao Carlos
Año: 2007
Disponible con Suscripción Virtualpro
Artículos
Categoría
Gestión y administración
Licencia
Atribución
Consultas: 8
Citaciones: Gestão & Produção Vol. 14 Núm. 3
Este documento es un artículo elaborado por Denise Sato Yamashita y Reinaldo Morabito (Universidade Federal de São Carlos, Brasil) para la revista Gestão & Produção. Gestão & Produção Vol 14, Núm 3. Publicación de UFSCar Universidade Federal de Sao Carlos. Contacto: contato@editoracubo.com.br
En un estudio reciente (YAMASHITA; MORABITO, 2007a), se propuso un algoritmo exacto para resolver problemas de programación de proyectos con restricciones de recursos y costes de disponibilidad de recursos bajo múltiples modos de ejecución. Dicho algoritmo es una adaptación de otro algoritmo exacto registrado en la literatura para el caso particular en el que sólo existe un único modo de ejecución de las tareas. En el presente estudio, proponemos un nuevo algoritmo exacto basado en el método branch and bound para tratar el problema de múltiples modos de ejecución. Dado que el problema es NP-difícil, el algoritmo es computacionalmente viable sólo para problemas de tamaño moderado. Se han realizado numerosas pruebas computacionales utilizando el generador ProGen para comparar el rendimiento del algoritmo propuesto con el algoritmo anterior y con el software CPLEX. Los resultados muestran que la versión propuesta del algoritmo es competitiva con los otros métodos y animan a seguir investigando para el desarrollo de versiones más elaboradas de este algoritmo.
1. INTRODUCCIÓN
Los problemas de programación de proyectos consisten en planificar en el tiempo actividades que requieren recursos para su realización. Esta programación también debe tener en cuenta las restricciones de precedencia entre las actividades, es decir, ciertas actividades sólo pueden iniciarse después de que otras se hayan completado. Ejemplos de problemas de programación de proyectos aparecen en diversas áreas (MODER et al., 1983; POLLACK-JOHNSON; LIBERATORE, 1998), como la construcción civil (TAKAMOTO et al., 1995), la fabricación (NEUMANN et al., 2002), las telecomunicaciones, el desarrollo de software/ordenadores, el mantenimiento de aeronaves (GEMMILL; EDWARDS, 1999), entre otros. Por ejemplo, en la construcción de un puente, la adquisición de material, la contratación de mano de obra y las diversas etapas que componen la construcción, como la preparación del terreno, la cimentación, las estructuras de pilares, las vigas y losas, la pavimentación, son algunas de las actividades del proyecto. Estas actividades tienen una duración prevista en función de los recursos asignados y, para poder llevarse a cabo, también están sujetas a relaciones de precedencia. La ejecución de las actividades consume diferentes recursos como máquinas, mano de obra, dinero, etc.
Algunos problemas de programación de proyectos permiten que las actividades se ejecuten de formas alternativas (múltiples modos de ejecución). Por ejemplo, una actividad que requiere 10 periodos de tiempo para ser ejecutada por 1 trabajador, podría realizarse alternativamente en 4 periodos de tiempo utilizando 2 trabajadores.
Descripción
En un estudio reciente (YAMASHITA; MORABITO, 2007a), se propuso un algoritmo exacto para resolver problemas de programación de proyectos con restricciones de recursos y costes de disponibilidad de recursos bajo múltiples modos de ejecución. Dicho algoritmo es una adaptación de otro algoritmo exacto registrado en la literatura para el caso particular en el que sólo existe un único modo de ejecución de las tareas. En el presente estudio, proponemos un nuevo algoritmo exacto basado en el método branch and bound para tratar el problema de múltiples modos de ejecución. Dado que el problema es NP-difícil, el algoritmo es computacionalmente viable sólo para problemas de tamaño moderado. Se han realizado numerosas pruebas computacionales utilizando el generador ProGen para comparar el rendimiento del algoritmo propuesto con el algoritmo anterior y con el software CPLEX. Los resultados muestran que la versión propuesta del algoritmo es competitiva con los otros métodos y animan a seguir investigando para el desarrollo de versiones más elaboradas de este algoritmo.
1. INTRODUCCIÓN
Los problemas de programación de proyectos consisten en planificar en el tiempo actividades que requieren recursos para su realización. Esta programación también debe tener en cuenta las restricciones de precedencia entre las actividades, es decir, ciertas actividades sólo pueden iniciarse después de que otras se hayan completado. Ejemplos de problemas de programación de proyectos aparecen en diversas áreas (MODER et al., 1983; POLLACK-JOHNSON; LIBERATORE, 1998), como la construcción civil (TAKAMOTO et al., 1995), la fabricación (NEUMANN et al., 2002), las telecomunicaciones, el desarrollo de software/ordenadores, el mantenimiento de aeronaves (GEMMILL; EDWARDS, 1999), entre otros. Por ejemplo, en la construcción de un puente, la adquisición de material, la contratación de mano de obra y las diversas etapas que componen la construcción, como la preparación del terreno, la cimentación, las estructuras de pilares, las vigas y losas, la pavimentación, son algunas de las actividades del proyecto. Estas actividades tienen una duración prevista en función de los recursos asignados y, para poder llevarse a cabo, también están sujetas a relaciones de precedencia. La ejecución de las actividades consume diferentes recursos como máquinas, mano de obra, dinero, etc.
Algunos problemas de programación de proyectos permiten que las actividades se ejecuten de formas alternativas (múltiples modos de ejecución). Por ejemplo, una actividad que requiere 10 periodos de tiempo para ser ejecutada por 1 trabajador, podría realizarse alternativamente en 4 periodos de tiempo utilizando 2 trabajadores.