Con el fin de mejorar el uso de los recursos utilizados en la realización de tareas, el académico de la Universidad de Santiago, Dr. Óscar Vásquez, aborda el problema de su secuenciamiento de manera eficiente, en particular en ambientes denominados no lineales, donde existe la capacidad de aprendizaje (seres humanos) o desgastes técnicos (maquinarias).

Desde el ensamblaje de un producto hasta la planificación de las actividades diarias exigen un orden, una secuencia. Realizarla de buena forma tiene un sentido si se espera que esta sea eficiente en el uso del recurso en el tiempo, algo fundamental si es escaso.

Debido a esto, el estudio de como secuenciar tareas ha cobrado relevancia en la comunidad científica, donde en el área es denominada ‘Scheduling’.

En esta área, en general, se analizan dos tipos de recursos, los lineales donde los recursos realizan los trabajos de una manera constante y los no lineales, donde no se cumple la regla anterior.

“No existe una velocidad constante, ya que el recurso que realiza la tarea tiene la capacidad de aprender o desgastarse. Por ejemplo, una persona que desarrolla una tarea repetitiva se demora una gran cantidad de tiempo cuando comienza, pero con el pasar de los días va aprendiendo a hacerlo más rápido. En el caso contrario, un buen ejemplo son las máquinas que se desgastan, haciendo su actividad cada vez más lento. Para capturar ese efecto uno habla de recursos no lineales”, expresa el especialista en el área, Dr. Óscar Vásquez.

El proyecto

Estos son los casos que indaga este académico del Departamento de Ingeniería Industrial en su proyecto Fondecyt de Iniciación (11140566) “Problema de secuenciamiento con recursos no lineales”.

“En la literatura, la mayoría de los trabajos existentes consideran recursos lineales en sus problemas. Nuestro proyecto busca ampliar el conocimiento -tanto de manera teórica como práctica- abordando problemas con recursos no lineales, motivados por aplicaciones reales tales como el secuenciamiento de trabajos en sistemas informáticos, medioambientales, publicitarios, salud, emergencia, entre otros”, señala.

Una de las principales formas de abordar estos casos es la búsqueda de propiedades estructurales, reglas propias de un problema que mejoran los métodos de resolución.

“No es lo mismo poner una actividad pequeña al principio o al final de un proceso. Por eso, uno trata de encontrar propiedades estructurales, ya que esta información permite desarrollar métodos de resolución que encuentran el secuenciamiento óptimo de las actividades de forma más rápida”, destaca.

La primera etapa de la investigación es la búsqueda de dichas propiedades estructurales de cada problema abordado. Luego desarrollarán métodos de resolución, que incorporarán o no estas características encontradas. Finalmente, describirán problemas con recursos no lineales, señalando la información recabada de los mismos y los presentarán a la comunidad científica, quienes pueden tomarlos como punto de partida para futuros análisis.

Aplicación

Esta retroalimentación entre la comunidad es fundamental, según expone el Doctor en Ciencias de la Computación. De hecho, una de las primeras publicaciones de este Fondecyt fue inspirada por el reabastecimiento de combustible de aviones, propuesta por los profesores George Gamow y Marvin Stern en el Libro ‘Puzzle-Math’, y complejizada con recursos no lineales por el Dr. Woeginger el 2010.

“En este libro se plantea cuál es el máximo de aviones que pueden viajar, si se pueden traspasar combustible, cuando el fin es llegar lo más lejos posible. Este problema está resuelto con aviones que son iguales, recursos lineales. Por esto, en el Seminario de Dagstuhl (Alemania) el profesor extiende el problema, proponiendo una forma de modelarlo, que se traduce luego a un problema de Scheduling, cuando los aviones son distintos”, recuerda el académico.

La respuesta del Dr. Vásquez a este problema, publicada en la revista Optimization Letters (9(4):663-675. 2015),planteó propiedades estructurales basadas en el consumo de los aviones y la capacidad de almacenamiento de combustible. Es así como logró dar con un método de resolución que permite una tasa de mejora de entre seis y mil veces; siendo más alta mientras más disímiles son los aviones.

“Este resultado puede tener otras aplicaciones. En un caso de emergencia, por ejemplo, podría usar este método para organizar automóviles para que lleguen lo más lejos posible traspasándose combustible. Sin embargo, y a pesar de los resultados, este problema puede modelarse aún mejor, algo que estamos desarrollando en este Fondecyt”, indica.

Este proyecto comenzó en noviembre del año 2014 y tiene una duración de 3 años. Durante este tiempo se tienen contempladas colaboraciones con académicos de diferentes partes del mundo, siendo los principales Christoph Dürr de la Universidad Pierre y Marie Curie (Francia); Nikhil Bansal, de la Universidad Técnica de Eindhoven (Holanda), y Luciana Buriol con Marcus Ritt, de la Universidad Federal de Río Grande del Sur (Brasil), entre otros.

“La indagación de esta área permite modelar una serie de problemas que son contingentes a nuestro país. Uno sería el problema de desastres naturales cuando hay que organizar recursos en tiempos de catástrofes. Otro es la escasez de energía cuando se busca optimizar el uso recursos energéticos, etcétera. Abordaremos motivaciones específicas, claro, pero buscando modelos y teorías que puedan aplicarse en otras problemáticas macros en el futuro”, expresa el Dr. Vásquez.