asignación Archivos - Página 2 de 2 - Gestión de Operaciones

Problema de Asignación de Horas Académicas a Profesores aplicado a una Universidad Online

El desarrollo de las tecnologías de información ha favorecido un crecimiento sostenido en la oferta académica de las instituciones de educación superior, lo cual ha permitido sumar a la tradicional formación presencial la posibilidad de obtener grados académicos a través de una formación no presencial (online). En este contexto, en la actualidad existen numerosas «Universidades Online» las cuales deben programar horas de apoyo académico de sus distintos cursos por parte de los profesores o docentes hacia los alumnos, con el objetivo de favorecer la comprensión de los contenidos.

Problema de Asignación de Horas Académicas a Profesores

En el siguiente artículo consideraremos un problema de asignación para cubrir las necesidades de apoyo académico para un curso de Economía. Asumiremos que se desea tener exactamente un profesor de turno (para responder preguntas de los alumnos en tiempo real a través de un foro o chat) de Lunes a Viernes de 08:00 AM hasta las 23:00 PM. Los Sábados y Domingo también se desea ofrecer el servicio pero de 08:00 AM hasta las 20:00 PM. Actualmente se cuenta con 10 profesores que cuentan con los conocimientos necesarios para desarrollar los servicios de tutorias y su remuneración (en dólares por hora) depende básicamente de la experiencia en el curso y grado académico. Adicionalmente, debido a los compromisos que tienen dichos profesores con otros cursos de la Universidad, han manifestado su disponibilidad máxima (en horas) para atender los distintos requerimientos según se detalla en la siguiente tabla:

Por ejemplo el profesor 1 recibe un salario de 50 dólares la hora y puede trabajar como máximo 5 horas el Lunes, 6 horas el Miércoles y Viernes, 3 horas el Sábado y 2 horas el Domingo. Los días Martes y Jueves el profesor 1 no tiene disponibilidad de tiempo. En base a esta información la Universidad desea determinar una asignación de horas académicas a los profesores de modo de cubrir las necesidades de atención de alumnos al menor costo posible al mismo tiempo de garantizar un mínimo de 5 horas por profesor a la semana. Para enfrentar dicha situación formularemos el siguiente modelo de Programación Lineal:

Variables de Decisión:

Con i=1,…,10 representando a los profesores y j=1,…,7 los días de la semana don j=1 es el día Lunes y j=7 el día Domingo.

Parámetros:

Función Objetivo:

Se busca minimizar los costos totales de la asignación que considera la ponderación para cada profesor de la cantidad de horas que trabaja durante la semana por el salario por hora (en dólares).

Restricciones:

Se debe cumplir con la cantidad de horas para cada día de la semana (15 horas para cada día de Lunes a Viernes y 12 horas para el Sábado y Domingo).

Se desea asignar al menos 5 horas académicas semanales a cada profesor.

Se debe respetar la disponibilidad horaria de los profesores durante la semana.

Condiciones de no negatividad para las variables de decisión.

Luego de implementar computacionalmente el modelo de optimización con Solver de Excel se obtiene la siguiente solución óptima con valor óptimo V(P)=US$4.639.

El siguiente tutorial de nuestro canal de Youtube muestra la resolución del problema anterior:

Problema de Asignación aplicado a un Portal de Anuncios de Trabajos

En el siguiente artículo abordaremos un caso aplicado respecto a una situación real donde un sitio web de búsqueda de empleos en España desea determinar qué anuncios publicar en una zona preferente de exhibición dentro de su portal. Para ello será necesario formular y resolver un modelo de Programación Entera que corresponde a un caso particular del problema de asignación descrito en artículos anteriores.

Consideramos como premisa que existen más anuncios que espacios publicitarios y por tanto se debe decidir cuáles de ellos incorporar con el objetivo de maximizar el retorno de la asignación pero al mismo tiempo satisfacer una serie de criterios adicionales que se deseen imponer. Una representación de la situación descrita se resume en la tabla a continuación:

Por ejemplo el Aviso N°1 corresponde a un anuncio de trabajo en Madrid en la Categoría I, el cual fue publicado hace 15 días (antigüedad) y que provee un retorno estimado de 100 unidades monetarias. Por supuesto los datos son ficticios, no obstante, permite visualizar la extensión de esta problemática a una situación de esta naturaleza. Asumiremos adicionalmente que se desean cumplir las siguientes condiciones en la asignación:

Seleccionar un Máximo de 5 Anuncios (entre los 10 candidatos posibles).
El tiempo promedio de Publicación de los Anuncios que se seleccionen no debe superar los 7[días].
Por razones estratégicas se debe publicar al menos un Anuncio de Madrid.
Se impone un máximo de 2 Anuncios de la Categoría II.
Se impone un mínimo de 1 Anuncio de la Categoría I.
Se impone un mínimo de 1 Anuncio de la Categoría II.
Se impone un mínimo de 1 Anuncio de la Categoría III.

Un modelo de Programación Entera que permite encontrar una asignación para la situación descrita es el siguiente:

Variables de Decisión: Permite dar respuesta al problema de selección de anuncios publicitarios a incluir en la zona preferente. (i=1,…,10)

Función Objetivo: Maximizar el retorno total de la asignación, donde Ri es el retorno (en U.M.) asociadas al anuncio i.

Restricciones: Satisfacer las condiciones expuestas. Se detallan a continuación en el mismo orden en el que fueron detalladas. (Ti representa el tiempo de publicación (en días) del anuncio i).

Al implementar computacionalmente el problema con Solver de Excel se obtiene la siguiente solución óptima que otorga un valor óptimo de 465[U.M]. Con ello la empresa debería implementar los anuncios 1, 4, 5, 6 y 8.

Problema de Plan de Personal en un Call Center (Programación Entera)

Una línea aérea está considerando incorporar vuelos desde y hacia su aeropuerto base y por lo tanto necesita contratar más agentes de servicio al cliente. Sin embargo, no está claro cuántos más debe contratar. La administración reconoce la necesidad de controlar el costo y al mismo tiempo brindar un nivel de atención satisfactorio. Se ha realizado un análisis del número mínimo de agentes de servicio que deben encontrarse de guardia en diferentes momentos del día para proporcionar un nivel satisfactorio de servicio.

Se ha acordado que cada agente trabaje un turno de 8 horas en los turnos mostrados en la tabla anterior. Por ejemplo, el turno 3 va desde las 12:00 hasta las 20:00. Los sueldos de cada turno son diferentes debido a que unos son más deseables que otros. Por ejemplo, a cada agente que cumpla el turno 3 debemos pagarle diariamente $175.

Se busca formular y resolver un modelo Programación Entera que permita a la línea aérea encontrar el plan de asignación de agentes al menor costo posible y que cumpla los requerimientos impuestos.

1. Variables de Decisión: Establecer un plan de asignación de agentes a los distintos turnos de trabajo.

Xi: Número de Agentes asignados al Turno i con i=1,2,3,4,5 con Xi>=0 {Enteros}

2. Función Objetivo: Minimizar el costo total de la asignación de agentes.

Minimizar 170X1+160X2+175X3+180X4+195X5

3. Restricciones: Se busca garantizar que en cada período del día se cuenta con la cantidad mínima de agentes requeridos.

X1 >= 48
X1 + X2 >= 79
X1 + X2 >= 65
X1 + X2 + X3 >= 87
X2 + X3 >= 64
X3 + X4 >= 73
X3 + X4 >= 82
X4 >= 43
X4 + X5 >= 52
X5 >= 25

A continuación implementamos el modelo anterior en Solver. Notar que las celdas color amarillo son las asignadas a las variables de decisión y éstas a la vez vinculan las combinaciones posibles entre turnos y períodos atendidos.

Adicionalmente en la columna I se ha guardado el valor del lado izquierdo de las restricciones que garantizan el mínimo número de agentes por período.

Finalmente la función objetivo (celda color naranjo) corresponde a la suma producto entre las variables de decisión y los parámetros que representan el costo diario por agente en los respectivos turnos (SUMAPRODUCTO(C4:G4;C19:G19)).

La implementación del modelo anterior en la interfaz de Solver es la siguiente:

Alcanzando la solución óptima del problema que considera la asignación de 48, 31, 39, 43 y 25 personas a los turnos 1,2,3,4 y 5, respectivamente, con un costo total (mínimo) de $32.560.

El siguiente video de nuestro canal en Youtube muestra la resolución del problema anterior:

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?.

[sociallocker]Descargar Aquí Problema Agentes Call Center[/sociallocker]

Formulación de un Problema de Asignación en Programación Entera

El siguiente problema fue enviado por uno de nuestros usuarios de la ciudad de Valparaíso, Chile:

En un evento atlético de gimnasia las competencias comprenden cuatro disciplinas: salto, barras asimétricas, viga de equilibrio y manos libres. Cada equipo debe presentar 5 deportistas por disciplina. Un deportista puede participar como especialista en una o dos disciplinas o bien como un all-rounder que participa en las cuatro disciplinas. Al menos 3 de los miembros del equipo deben ser all-rounder. Un deportista es evaluado en una escala de 1 a 10. De acuerdo a las estadísticas del equipo de gimnasia de la universidad, se tienen las siguientes calificaciones para cada uno de los 6 miembros del equipo actual:

Formule y resuelva un modelo de Programación Entera que permita seleccionar a los 5 deportistas que presentará la universidad en cada disciplina del evento.

A continuación detallamos la formulación de este problema de Programación Entera:

1. Variables de Decisión:

Con i=1,…,6 (deportistas) y j=1,….,4 (deportes)

2. Función Objetivo: Maximizar el puntaje a obtener por los deportistas

Donde Pij representa el puntaje que tiene el deportista i en la disciplina j. Estos valores son parámetros del modelo y son los que se resumen en la tabla del enunciado. Por ejemplo: P13=9.

3. Restricciones:

Si un deportista es all-rounder se debe asignar a todas las disciplinas:

Deben haber al menos 3 deportistas all-rounder:

Se requiere de exactamente 5 deportistas por disciplina:

Límite de disciplinas por deportistas según su categoría:

Problema de Asignación en Programación Entera resuelto con Solver

Cuando necesitamos asignar recursos escasos a determinadas funciones y dichos recursos no son fraccionables, la utilización de modelos de Programación Entera resultan ser de utilidad para la toma de decisiones. En este contexto los problemas de asignación de personal a determinadas tareas es una aplicación típica de la Programación Entera que a continuación desarrollaremos a través de un ejemplo.

Problema de Asignación

Consideremos una empresa que dispone de 5 ingenieros que deben desarrollar 7 proyectos. La tabla a continuación resume el tiempo que demora cada ingeniero (en horas) en completar un determinado proyecto. El problema consiste en determinar una asignación óptima que permita realizar cada uno de los proyectos con la limitante que por motivos estratégicos cada ingeniero debe desarrollar al menos un proyecto y en ningún caso hacer más de 2 proyectos. Por supuesto se busca que el tiempo requerido para realizar los 7 proyectos sea el menor posible.

Una alternativa sería buscar intuitivamente una asignación que cumpla con los requisitos de la empresa y tenga un bajo tiempo asociado. Sin embargo, este tipo de estrategias de resolución queda claramente acotada a problemas de tamaño menor y ni siquiera en ese tipo de situaciones nos asegura la mejor solución posible. Por ello definiremos el siguiente modelo de optimización de Programación Entera:

1. Variables de Decisión: Utilizamos las siguientes variables de decisión binarias

2. Función Objetivo: Minimizar el tiempo total requerido para completar los proyectos

Donde Tij (parámetros) es el tiempo (en horas) requerido por el ingeniero i en realizar el proyecto j. Por ejemplo T(A,P5)=7.

3. Restricciones:

Cada proyecto debe ser realizado por un solo ingeniero:

Cada ingeniero debe ser al menos un proyecto y no puede hacer más de 2:

El siguiente tutorial muestra cómo resolver este problema de asignación con Solver de Excel:

Se puede observar que para efectos de Solver, las variables de decisión binarias se deben definir como una restricción adicional. También puede resultar que luego de resolver Solver no encuentre inmediatamente la mejor solución posible. Para enfrentar esta situación se puede «volver a resolver» sobre la solución que el programa nos haya proporcionado hasta el momento para verificar si se puede lograr algo mejor. Esta situación es la que sucedió en el tutorial y a continuación se muestra la solución óptima (final) encontrada por Solver.

En total se requieren 56 horas para realizar los 7 proyectos. El ingeniero A realiza el P7, el ingeniero B el P3 y P5, el ingeniero C el P6, el ingeniero D el P2 y P4 y el ingeniero E el P1. Notar que cada proyecto es realizado por un ingeniero y cada ingeniero al menos realiza un proyecto, pero no más de 2 proyectos.