planteamiento del modelo matemÁtico bÁsico que … · planteamiento del modelo matemÁtico...
TRANSCRIPT
PLANTEAMIENTO DEL MODELO MATEMÁTICO BÁSICO QUE REPR ESENTE
DE MANERA ADECUADA EL PROBLEMA DE ASIGNACIÓN DE PER SONAL
PARA UN RESTAURANTE TIPO CALLE DE LA COMPAÑÍA FRISB Y. S.A
AUTOR
VICTORIA EUGENIA BATERO CORREA
UNIVERSIDAD TECNOLÓGICA DE PEREIRA
FACULTAD DE INGENIERÍA INDUSTRIAL
INGENIERÍA INDUSTRIAL
PEREIRA
2007
2
PLANTEAMIENTO DEL MODELO MATEMÁTICO BÁSICO QUE REPR ESENTE
DE MANERA ADECUADA EL PROBLEMA DE ASIGNACIÓN DE PER SONAL
PARA UN RESTAURANTE TIPO CALLE DE LA COMPAÑÍA FRISB Y. S.A
AUTOR
VICTORIA EUGENIA BATERO CORREA
DIRECTOR
ELIANA MIRLEDY TORO
Mg Ingeniería Eléctrica Área de Optimización
Trabajo de Grado para optar el título de Ingeniero Industrial
bajo la modalidad de Práctica Empresarial
UNIVERSIDAD TECNOLÓGICA DE PEREIRA
FACULTAD DE INGENIERÍA INDUSTRIAL
INGENIERÍA INDUSTRIAL
PEREIRA
2007
3
NOTA DE ACEPTACIÓN
Firma del Presidente del Jurado
Firma del Jurado
Firma del Jurado
Pereira, ______ _______________ de 2007
4
DEDICATORIA
A mi Padre por creer en mí.
A mi Madre por ayudarme siempre.
A mi Esposo por su apoyo incondicional.
Y a mi hija por crecer conmigo.
5
AGRADECIMIENTOS
− A Dios por darme la fortaleza para alcanzar mis metas.
− A la Universidad Tecnológica de Pereira por ser mi segundo hogar durante mi
formación profesional.
− A la Facultad de Ingeniería Industrial por enseñarme a ser una profesional
íntegra.
− A la Compañía Frisby S.A., por brindarme la posibilidad de aprender y trabajar
en una de las mejores empresas colombianas.
− Y a Eliana Mirledy Toro, Mg. En Ingeniería Eléctrica área de optimización y
Directora de este trabajo, por sus acertados consejos, su tiempo y dedicación
para compartir conmigo sus conocimientos y experiencias vividas.
6
TABLA DE CONTENIDO
GLOSARIO ............................................................................................................ 10
INTRODUCCION ................................................................................................... 11
DEFINICIÓN DEL PROBLEMA ............................................................................. 13
JUSTIFICACION .................................................................................................... 16
OBJETIVOS ........................................................................................................... 20
GENERAL ........................................................................................................... 20
ESPECÍFICOS .................................................................................................... 20
MARCO DE REFERENCIA.................................................................................... 21
MARCO CONCEPTUAL ..................................................................................... 21
Investigación de Operaciones .......................................................................... 21
Modelo Matemático .......................................................................................... 21
Función Objetivo .............................................................................................. 21
Variables .......................................................................................................... 21
Restricciones ................................................................................................... 21
MARCO TEÓRICO ............................................................................................. 22
Descripción del problema y recolección de datos ............................................ 23
Selección de variables ..................................................................................... 23
Formulación de un modelo matemático ........................................................... 23
MÉTODO DE LA UNIDAD DE ANÁLISIS .............................................................. 25
DISEÑO METODOLÓGICO .................................................................................. 25
MÉTODOS DE OPTIMIZACIÓN COMBINATORIAL ............................................. 26
Métodos de Solución para Problemas NP .......................................................... 27
Métodos Heurísticos ........................................................................................ 28
Métodos de Descomposición ........................................................................ 29
Métodos Inductivos ....................................................................................... 29
Métodos de Reducción ................................................................................. 29
Métodos Constructivos.................................................................................. 29
Métodos de Búsqueda Local ......................................................................... 29
7
Métodos Metaheurísticos ................................................................................. 30
1. ALGORITMOS GENÉTICOS .................................................................. 31
La codificación ........................................................................................... 34
Cálculo de la Función Objetivo o Algún Equivalente .................................. 35
Selección ................................................................................................... 35
Recombinación .......................................................................................... 36
Mutación .................................................................................................... 37
Ciclo Generacional ..................................................................................... 37
Programa de control del Algoritmo Genético ............................................. 37
Criterio de Parada ...................................................................................... 38
2. ALGORITMO GENÉTICO MODIFICADO – CHU - BEASLEY ................ 39
3. ALGORITMOS MEMÉTICOS ................................................................. 41
Constitución de un Algoritmo Memético ..................................................... 41
Diseño de Algoritmos Meméticos ............................................................... 43
Minimización de la epistasis .................................................................... 43
Minimización de la varianza de bondad .................................................. 44
Maximización de la correlación de bondad ............................................. 44
4. ALGORITMOS CULTURALES ............................................................... 45
5. BÚSQUEDA TABÚ ................................................................................. 48
Selección de una solución inicial xo: .......................................................... 48
Elección del entorno V(xa): ........................................................................ 49
Elección del tamaño de la lista tabú (L): .................................................... 49
Elección de los atributos para almacenar en la lista tabú: ......................... 49
Nivel de Aspiración: ................................................................................... 50
Criterio de finalización: ............................................................................... 50
La memoria a corto plazo: .......................................................................... 51
La memoria a largo plazo: .......................................................................... 51
6. SIMULATED ANNEALING ...................................................................... 54
Programa de Enfriamiento ......................................................................... 56
Temperatura inicial..................................................................................... 56
8
Algoritmo Para el Cálculo de la Temperatura Inicial (To): .......................... 57
Tasa de enfriamiento ................................................................................. 57
Temperatura final ....................................................................................... 58
Número de tentativas. Nk .......................................................................... 58
Convergencia ............................................................................................. 58
7. TÉCNICA DE COLONIA DE HORMIGAS ............................................... 59
Comportamiento de las Hormigas reales ................................................... 60
Explotación de los Rastros de Feromona y Exploración ............................ 60
Evaporación de Rastros de Feromona....................................................... 61
Sistema Hormigas ...................................................................................... 61
Hormigas Artificiales .................................................................................. 62
Matriz de Feromonas ................................................................................. 63
Construcción de Soluciones ....................................................................... 63
Construcción de Soluciones Inválidas........................................................ 65
Evolución del Algoritmo ACO .................................................................... 66
ESTADO DEL ARTE DE LA OPTIMIZACIÓN DE HORARIOS.............................. 67
1. ORGANIZACIÓN DE TURNOS DE TRABAJO EN UNA INSTALACIÓN DE
SUMINISTRO DE COMBUSTIBLE DE UN AEROPUERTO. .............................. 69
2. METODOLOGÍA DE LA ASIGNACIÓN ÓPTIMA DE MANO DE OBRA EN LA
INDUSTRIA DE LA FLORICULTURA. ................................................................ 73
3. ASIGNACIÓN DE TURNOS A OPERADORES DE TELÉFONO EN LA
NUEVA COMPAÑÍA DE TELÉFONO BRUNSWICK .......................................... 80
4. SOLUCIÓN AL PROBLEMA DE ASIGNACIÓN DE HORARIOS USANDO
GOMORY DUAL DEL PLANO CORTANTE. ...................................................... 87
5. OPERACIÓN DE UN RESTAURANTE DE COMIDA RÁPIDA ..................... 91
6. ASIGNACIÓN MULTICRITERIO DE TAREAS A TRABAJADORES
POLIVALENTES ................................................................................................. 99
PLANTEAMIENTO DEL MODELO MATEMÁTICO ............................................. 109
Generalidades ................................................................................................... 110
Modelo de Asignación ....................................................................................... 118
9
Variables de Decisión ....................................................................................... 120
TIEMPO COMPLETO .............................................................................. 122
HORAS POR SEMANA .............................................................................. 125
HORAS POR MES ...................................................................................... 127
NÓMINA POR HORAS .................................................................................. 128
HORAS POR DÍA ....................................................................................... 129
HORAS POR SEMANA ................................................................................. 131
HORAS POR MES ......................................................................................... 134
ASIGNACIONES POR CARGO .................................................................. 137
POLIFUNCIONALIDAD ............................................................................... 145
Función Objetivo: ........................................................................................ 150
COSTOS DE MANO DE OBRA .................................................................. 151
TIEMPO COMPLETO .............................................................................. 151
TIEMPO VARIABLE ................................................................................. 151
CONCLUSIONES ................................................................................................ 157
RECOMENDACIONES ........................................................................................ 159
BIBLIOGRAFÍA .................................................................................................... 161
10
GLOSARIO
AFORO: Es el proceso por el cual la compañía Frisby S.A., determina la cantidad
de personas que han de ser asignadas a cada restaurante, para ello debe tener en
cuenta las ventas y el lugar de ubicación del restaurante.
CAMA : Es una porción de tierra o substrato de 30 a 32 metros de largo por 1 a
1,2 metros de ancho, sobre la cual se siembran las plantas con una densidad que
varía de acuerdo con el tipo de cultivo y las políticas de la empresa en cuanto a su
productividad por metro cuadrado.
NAVE: Esta conformada por 4 ó 5 camas, cada una de ellas divida por el centro
mediante un camino central, el cual facilita la movilidad a los operarios.
BLOQUE: Es un conjunto de naves que varían en cantidad de acuerdo con el
espacio de la empresa y el tipo de cultivo, el bloque es la unidad estructural
utilizada para realizar los procesos de planeación y asignación de recursos.
11
INTRODUCCION
En la actualidad es necesario que las organización optimicen los recursos con los
que cuenta, ya que lo que permitirá que una empresa trascienda es la forma en
que se organiza y planea cada una de sus actividades y procesos. Las
organizaciones deben estar dispuestas al cambio continuo para competir en un
mercado en el que el cliente es cada vez más exigente y que la competencia es
tan grande que si se tolera un mínimo de error esto puede determinar el fracaso
de una lucha constante por mantenerse en un mercado avasallador.
Se han desarrollado innumerables técnicas y métodos para controlar desde el más
mínimo movimiento hasta los macroprocesos. Algunas de las áreas de mayor
importancia en las organizaciones es el recurso humano, este involucra un costo
que puede en cierta forma ir acabando con la empresa si no se maneja de manera
adecuada y óptima.
Frisby S.A., es una compañía que se encuentra en un momento de crecimiento
empresarial, pues cuenta con cerca de 102 restaurantes a nivel nacional y está
próximo a su internacionalización con la apertura de un restaurante en la ciudad
de Nueva York, es entonces una empresa a la que le augura un gran futuro. Pero
es necesario que el desarrollo al interior de la organización permita la
sistematización de los procesos de mayor importancia para la empresa. Por tal
razón Frisby S.A., ha venido desarrollando un Proyecto para la asignación óptima
de horarios en sus restaurantes, para tal fin se ha esta tesis en la que se plantea
un modelo matemático básico para la asignación de mano de obra.
En este documento se encontrarán 4 capítulos en el primero se incluye toda la
información correspondiente a las generalidades del proyecto como son la
presentación del problema, objetivo etc.
12
En el segundo capítulo se da a conocer los métodos de optimización combinatorial
que son utilizados para dar solución a los problemas de asignación horaria.
Explicando los conceptos de cada método, entre los métodos estudiados se
encuentran los algoritmos genéticos, algoritmos culturales, búsqueda tabú, etc.
En el tercer capítulo se da a conocer el estado del arte en cuanto a la optimización
de mano de obra, citando ejemplo de organizaciones que han aplicado la
investigación de operaciones para dar respuesta a sus problemas de mano de
obra, presentado de manera detallada los modelos planteados y los métodos de
solución con los que se encontró la optimización de horarios.
En el capítulo cuatro se procede con el planteamiento del modelo para el
restaurante de la Compañía Frisby S.A., allí se explica de manera detallada cada
uno de los parámetros que se tuvieron en cuenta para realizar la construcción del
modelo.
Finalmente se encuentran las conclusiones y recomendaciones tanto del trabajo
en general como de la practica realizada en la compañía.
13
DEFINICIÓN DEL PROBLEMA
El desarrollo de proyectos de investigación que determinen el comportamiento de
los recursos al interior de sistemas de producción y de prestación de servicios es
de especial interés en todas las áreas de las organizaciones. La mayoría de las
empresas necesitan determinar el número de empleados con sus respectivos
horarios de trabajo de forma tal que minimicen los gastos de personal y los
costos de oportunidad esperados.
Importantes empresas en el ámbito mundial como Taco Bell o Mc Donalds, han
invertido años de investigación buscando un modelo de asignación de personal
que les permita minimizar el número total de trabajadores y los cuales puedan
cumplir con los requerimientos operacionales del día a día. A pesar de esto, la
variabilidad en las restricciones legales, las condiciones geográficas y la diferencia
en los procedimientos hacen que cada uno de estos problemas se conviertan en
un caso particular para cada persona u organización que trata de resolverlo.
En estas empresas se trabaja durante todo el año los siete días a la semana. La
forma de organizar el trabajo es muy distinta según sea la actividad y la filosofía
de la empresa. En particular, depende de sí la carga de trabajo varía con los días
de la semana, con la época del año, si la fuerza de trabajo es fija o variable, si los
trabajadores rotan o si algunos de ellos ya están asignados a turnos o días de
descanso específicos. En la práctica hay gran variedad de tipos de asignaciones
rotativas1. Así, aunque existen principios básicos y algunas reglas que gobiernan
el diseño de estas planificaciones rotativas, cada situación requiere plantear y
resolver un problema específico.
1 ESCALAPÉS CARMÉN, 2000, Asignación de Conductores a Jornadas de Trabajo en Empresas
de Transporte Colectivo, Universidad Politécnica de Cataluña.
14
La modernización matemática de los problemas de asignación de las jornadas de
trabajo se materializa en problemas de programación binaria en los que la
incógnita Xi,j,k toma el valor de 1 si el trabajador i, el día j tiene asignada la
jornada k, y 0 en caso contrario. La asignación deberá recoger criterios con las
preferencias de los trabajadores y satisfacer todas las restricciones que traducen
las condiciones de trabajo recogidas en lo estipulado por las empresas. El criterio
de optimización es que todos los trabajadores tengan asignada al final del año una
carga de trabajo si no igual, si muy cercana a las características que rigen cada
tipo de contrato que se maneje con cada uno de los empleados. Además, el
número de jornadas a realizar varía con el día de la semana y con la época del
año y no todas las jornadas tienen igual duración horaria; esto hace que para
empresas grandes el problema de optimización tenga muchas variables y
restricciones y adquiera un tamaño demasiado grande. En estos casos los
problemas de programación entera son considerados NP - Completos y, en
general, muy difíciles de resolver.
Se encuentra una organización con un sistema de actividades que necesitan ser
satisfechas por un grupo de empleados, cada una con sus requisitos y
preferencias, además la compañía hace cumplir algunas regulaciones totales y
procura generalmente alcanzar objetivos globales como una carga justa de trabajo
y un costo mínimo de mano de obra. Las asignaciones de personal son realizadas
por una sola persona, quien tiene que considerar una cantidad de factores y
parámetros que se encuentran involucrados en la toma de decisiones, pero lo más
preocupante de ello es que en muchas ocasiones al tomar una decisión no se
tienen criterios establecidos sino que esta se realiza según el parecer de la
persona que se encuentra a cargo dependiendo de lo que considere conveniente.
El Analista de Aforo quien es la persona encargada de la realización de este
proceso, debe conocer cada cargo, sus requerimientos y actividades. Debe
programar paso a paso los horarios desde la apertura del restaurante hasta el
15
cierre del mismo, debe conocer el tiempo que consume cada actividad y la
cantidad de personas que la deben desarrollar. El Departamento de Gestión
Humana ha establecido otras reglas que deben cumplirse lo que ha provocado
que este proceso sea cada vez más demorado y que el Analista de Aforos invierta
demasiado tiempo construyendo horarios completos para cada restaurante, cada
que se considere necesario dejando de lado otras tareas vitales que pertenecen al
cargo.
La compañía Frisby S.A., requiere entonces una solución fácil de usar que aplique
las reglas de trabajo rápida y constantemente, que maneje la asignación de
recursos e incluya todos los parámetros y variables caracterizadoras del proceso,
que permita asignar al personal adecuado, en la cantidad y hora requerida, sin
pasar por encima las leyes de contratación de personal. De manera tal que las
demandas estén satisfechas y el costo total de los horarios se reduzca al mínimo
además que sirva en conjunto como una herramienta para el Departamento de
Ingeniería al realizar los seguimientos al comportamiento laboral de cada
restaurante.
Para iniciar con dicho proceso la compañía ha seleccionado un practicante
universitario el cual realizará un planteamiento matemático básico que describa la
asignación del personal para un restaurante tipo calle de la compañía; dicho
planteamiento debe ser validado por la compañía, la cual evaluará si se toma
como base para la construcción del modelo final que representará la situación de
la empresa teniendo en cuenta cada tipo de restaurante y la particularidad de cada
uno de ellos.
16
JUSTIFICACION
El valor de un modelo puede ser juzgado por su sencillez y por la aproximación
con la cual los acontecimientos o valores previstos por el modelo se ajustan a la
observación real. Un modelo no puede ser considerado como acertado o
equivocado, sino como que se ajusta satisfactoriamente a los hechos en gran
manera o en alguna de las situaciones. Un buen modelo es el que es sencillo,
pero da un buen ajuste en una gama amplia. La mejor prueba de un modelo es su
utilidad para la predicción; en este sentido la predicción abarca, no solamente los
sucesos futuros, sino también la de todos los valores o eventos no considerados al
establecer el modelo.
Cualquier modelo tendrá en último término que ser sustituido o modificado, dicho
cambio puede ser el hecho de anexarle un pequeño ajuste para tener en cuenta
nuevos factores, a fin de obtener aún mayor precisión, o quizá ser sustituido por
un modelo diferente. En todo caso, el proceso de construcción de un modelo, su
comprobación, su modificación o sustitución, es una parte esencial del estudio y
del conocimiento eventual de la dinámica del proceso evaluado y por supuesto,
de cualquier tema de estudio científico. El proceso de la construcción de modelos
es el complemento de la recolección de datos y, en realidad, solamente con la
construcción y utilización de modelos es posible decidir cuáles son los datos que
deben recogerse.
Ante la imperiosa necesidad de controlar y reducir los costos correspondientes a
los diversos productos y servicios ofrecidos por la empresa, resulta de gran
importancia recurrir a la creatividad e innovación puesta al servicio del análisis y
toma de decisiones. Así pues, inspirada en la teoría econométrica, y haciendo uso
tanto de la estadística y las matemáticas aplicadas, como de la investigación de
operaciones, la administración de la producción, el control estadístico de procesos,
el comportamiento organizacional, la ingeniería económica y la economía de la
17
empresa, es posible construir modelos matemáticos que representen las diversas
variables que hacen parte de los procesos y actividades productivos. Dichos
modelos deben permitir por un lado el cálculo proyectado de costos futuros, y por
otro el control y cálculo de los costos en que se está incurriendo, a los efectos de
la toma de decisiones y de la reducción de los mismos.
De tal forma mediante un conjunto de relaciones matemáticas que expresan en
forma simplificada las características básicas y esenciales atinentes a cada una de
las actividades y procesos participes en la generación de los productos o servicios
se puede no sólo determinar los costos, sino analizar científicamente la
composición y evolución de los mismos. Dentro de esta forma de análisis cobra
especial trascendencia el pensamiento sistémico, como metodología de análisis
destinado a definir con claridad y precisión cada uno de los factores que inciden
en el coste y su especial peso específico, como así también las posibilidades de
cambio o alteración.
Un modelo es conformado por un conjunto de ecuaciones o funciones entre las
variables más relevantes que concurren a explicar una tecnología incorporada, un
orden institucional o legal, y el comportamiento de los sujetos de la actividad
económica en un sistema, subsistema, sector o subsector. Para llegar a la
construcción de tales modelos es necesario por un lado analizar los procesos
productivos, y por otro la composición de los productos. Cuando hablamos de
procesos no sólo entran en juego las máquinas, insumos y los trabajadores, sino
además la incidencia que las motivaciones y desmotivaciones provocadas por
distintos factores tienen sobre el personal, como así también de que forma las
distintas políticas comerciales afectan los procesos. Con posterioridad al análisis
de la conformación de los procesos, se procede al análisis de datos históricos,
concluyendo el proceso en la construcción de modelos matemáticos que expliquen
la razón de ser de los costes.
18
En el último paso de ésta primera etapa se ponen los modelos a prueba para
verificar su grado de correspondencia con los hechos concretos. Una vez
corroborado el modelo, se procede a reanalizar sus componentes, investigando
aquellos aspectos o variables factibles de cambio a los efectos de lograr
reducciones de costes de los procesos, y de los productos y servicios que ellos
generan.
El modelo esta constituido por una serie de ecuaciones, las cuales se clasifican
en2:
• Ecuaciones de comportamiento;
• Ecuaciones institucionales o legales;
• Ecuaciones tecnológicas;
• Ecuaciones de definición o identidad;
• Ecuaciones de equilibrio móvil.
Una ecuación de comportamiento explica el modo de actuar de los sujetos
(empleados y obreros). Las ecuaciones institucionales o legales reflejan los
efectos que producen en un modelo la existencia de leyes o un orden institucional
dado, como por ejemplo las leyes laborales y sus efectos en el pago de las horas
extras, los tiempos de descanso diario, semanal, y anual. También sirve para
considerar el efecto de las leyes sobre temas como diseños de productos y
protección del medio ambiente.
Una ecuación tecnológica explica los modos de producción incorporados a los
procesos y actividades productivas.
Las ecuaciones de definición o identidades son relaciones que se verifican
siempre, ya sea por su construcción lógica o por la definición contable que ellas
2 F. HILLIER, G. J. LIEBERMAN. (1990) Introduction to Operations Research, McGraw Hill, Publishing Company.
19
satisfacen. Y por último tenemos a las ecuaciones de equilibrio móvil como
aquellas igualdades que resultan de una condición impuesta o postulado
introducido.
Entre las variables que componen las diversas ecuaciones tenemos:
• Endógenas
• Exógenas
• Aleatorias
• Expectativas
Las variables endógenas son aquellas cuyos valores estimados van a ser
determinados por las soluciones particulares del sistema de ecuaciones que
integran el modelo. Ellas son las variables llamadas dependientes en el análisis
matemático.
Las variables exógenas incluyen variables económicas propiamente dichas, como
no económicas.
Las variables aleatorias o estocásticas constituyen una categoría fundamental en
el análisis econométrico de los modelos estructurales. Son variables no
observables y su introducción caracteriza a los modelos probabilísticos.
Las variables expectativas son variables no observables y su introducción exige el
enunciado de un postulado adicional en el que se especifica su comportamiento
en función de variables observables.
El análisis del comportamiento de cada variable y modelo, permitirá determinar las
medidas a adoptar.
20
OBJETIVOS
GENERAL
• Planteamiento del modelo matemático básico que represente de manera
adecuada el problema de asignación de personal para un restaurante tipo
calle en la Compañía de Frisby S.A
ESPECÍFICOS
• Revisar el Estado del Arte.
• Determinar las variables caracterizadoras de la carga de trabajo por cargo
según el tipo de restaurante.
• Diseñar una adecuada estructura de recolección de información que abarque la
mayor parte de las variables componentes del sistema.
• Definición de variables operativas y de asignación para cada cargo según el
tipo de restaurante seleccionado.
• Formulación de las restricciones que se presentan en la asignación de cargos
para el restaurante.
• Planteamiento de la Función a optimizar en el modelo matemático.
21
MARCO DE REFERENCIA
MARCO CONCEPTUAL
Investigación de Operaciones Aplicación de un método científico para la toma de decisiones. El proceso
comienza por la observación cuidadosa y la formulación del problema incluyendo
la recolección de datos pertinentes. Intenta encontrar una mejor solución (llamada
solución optima), para el problema bajo consideración.
Modelo Matemático Se emplea cuando la función objetivo y las restricciones del modelo se pueden
expresar en forma cuantitativa o matemática como funciones de las variables de
decisión.
Función Objetivo Es la medida cuantitativa del funcionamiento del sistema que se desea optimizar
(Maximizar o Minimizar). Como ejemplo de función objetivo se pueden mencionar:
La minimización de los costos variables, la maximización de los beneficios netos
de venta, etc.
Variables Representan las decisiones que se pueden tomar para afectar el valor de la
función objetivo. Desde un punto de vista funcional se pueden clasificar en
variables independientes y variables dependientes.
Restricciones Representan el conjunto de relaciones (expresadas mediante ecuaciones e
inecuaciones) que ciertas variables están obligada a satisfacer.
22
MARCO TEÓRICO
La toma de decisiones es un proceso que se inicia cuando se observa un
problema y se determina que es necesario resolverlo, se procede entonces a
definirlo, formular un objetivo, reconocer sus limitaciones, generar alternativas de
solución y evaluarlas hasta seleccionar la que se considera la mejor opción. La
investigación de operaciones proporciona la base suficiente para seleccionar la
mejor decisión y permite realizar la planeación para eventos futuros, lo cual no
significa predecir el futuro, pero si ser capaz de indicar muchas cosas acerca de la
forma en que se puede esperar que un sistema opere en determinadas
circunstancias, y que consienta valorar su vulnerabilidad. Si se conocen las
debilidades del sistema se pueden implementar acciones correctivas para que
este continúe funcionando a cabalidad.
La Investigación de Operaciones tiene sin duda un enfoque modelístico, el cual
desarrolla la siguiente metodología:
1. Definir el sistema real en donde se presenta el problema. Dentro del cual se
encuentran un gran número de variables.
2. Seleccionar las variables que forman el estado actual del sistema.
3. Construir un modelo cuantitativo del sistema, identificando y simplificando las
relaciones entre las variables relevantes mediante la utilización de funciones
matemáticas.
Se procede entonces a explicar brevemente cada una de las etapas anteriormente
citadas.
23
Descripción del problema y recolección de datos
La mayor parte de los problemas prácticos a los que se enfrentan las empresas
diariamente están definidos de una manera muy superficial, por consiguiente la
primera actividad que se debe realizar es el estudio del sistema relevante y el
desarrollo de un resumen bien definido del problema que se va a analizar. Esto
incluye determinar los objetivos, restricciones acerca de lo que se puede hacer, los
diferentes cursos de acción posibles y los limites de tiempo para tomar una
decisión.
Selección de variables
Para construir un modelo matemático es necesario primero definir las variables en
función de las cuales será establecido el problema.
Formulación de un modelo matemático
Una vez definido el problema, la siguiente etapa consiste en reformularlo de
manera conveniente para su análisis. La forma convencional en que la
Investigación de Operaciones realiza esto es construyendo un modelo matemático
que represente la esencia del problema. El modelo matemático está constituido
por relaciones matemáticas (ecuaciones y desigualdades) establecidas en
términos de variables, que representan la esencia del problema que se pretende
solucionar. Se procede a determinar matemáticamente la llamada función objetivo
y las restricciones las cuales son un conjunto de barreras y obstáculos para la
consecución del objetivo.
24
Para concluir podemos decir que los modelos matemáticos tienen muchas
ventajas sobre la descripción verbal de un problema. Una ventaja obvia es que el
modelo matemático describe un problema en forma más concisa, esto tiende a
hacer que la estructura del problema sea más comprensible y ayude a revelar las
relaciones importantes entre causa y efecto. Un modelo es, necesariamente, una
idealización abstracta del problema, por lo cual casi siempre se requieren
aproximaciones y suposiciones de simplificación para que el modelo sea
manejable, pero siempre debe tenerse cuidado de que el modelo sea una
representación válida del problema.
También facilita simultáneamente el manejo del problema en su totalidad y el
estudio de todas sus interpelaciones, además de convertirse en un puente para
poder emplear técnicas matemáticas y computadoras de alto poder para analizar
un problema.
25
MÉTODO DE LA UNIDAD DE ANÁLISIS
El proyecto se basa en el planteamiento y formulación de un problema de
asignación de recursos, para un restaurante Tipo Calle de la compañía de Frisby
S.A., teniendo en cuenta todos los desarrollos que ha realizado el Departamento
de Ingeniería respecto a dicho proceso.
DISEÑO METODOLÓGICO
La investigación inicia con una fase de reconocimiento y descripción de la
situación en la que se encuentra la empresa, identificando cada una de las
variables caracterizadoras con que cuenta el problema. Después se realizará una
revisión bibliográfica para determinar el Estado del Arte acerca de la optimización
de horarios de personal.
El resultado que se espera obtener es el modelo básico de asignación de personal
para el restaurante tipo calle de la compañía Frisby S.A
26
MÉTODOS DE OPTIMIZACIÓN COMBINATORIAL
Optimizar significa mejorar un poco más lo que se tiene, sin embargo, la
argumentación científica dice que la optimización es el proceso de intentar dar con
la mejor solución posible para un determinado problema. En estos problemas,
hallar la mejor solución posible consiste en encontrar el valor de las variables de
decisión para alcanzar el valor máximo o mínimo en determinada función objetivo
y donde las variables están sujetas a unas restricciones.
Alrededor existe una gran cantidad de problemas de optimización, tanto en la
industria como en la ciencia, algunos problemas de optimización son
relativamente fáciles de resolver, por ejemplo, los problemas lineales, en los que
tanto la función objetivo como las restricciones son expresiones lineales, y
pueden ser resueltos con el conocido método Simplex; sin embargo, muchos otros
tipos de problemas de optimización son de difícil solución.
La búsqueda de una solución óptima en un problema combinatorial puede
consumir un tiempo computacional excesivo, la complejidad computacional se
define como la cantidad de recursos que se necesitan para hallar una solución a
un problema por medio del más eficiente algoritmo, siendo los recursos más
comunes: el tiempo y el espacio. Efectivamente la mayor parte de los problemas
que se encuentran en la práctica hacen parte de esta categoría, a este tipo de
problemas se les conoce como NP - Duros y para éstos no se puede encontrar
una solución óptima en poco tiempo.
Para este tipo de problemas se requiere de una técnica eficiente tal como un
algoritmo combinatorial, lo que genera un tiempo mucho mayor de respuesta y
generalmente de tipo exponencial. En los problemas de Optimización
Combinatorial el objetivo es encontrar el máximo o el mínimo de una determinada
función sobre un conjunto finito de soluciones. Es importante notar que dada la
27
finitud del conjunto de soluciones, las variables deben ser discretas, restringiendo
su dominio a una serie finita de valores. Frecuentemente el número de elementos
del conjunto de soluciones es muy elevado, haciendo difícil la evaluación de todas
sus soluciones para determinar el óptimo.
La existencia de una gran cantidad y variedad de problemas difíciles, que
aparecen en la práctica y que necesitan ser resueltos de forma eficiente, impulsó
el desarrollo de procedimientos eficientes para encontrar buenas soluciones
aunque no fueran óptimas. Estos métodos, en los que la rapidez del proceso es
tan importante cómo la calidad de la solución obtenida, se denominan heurísticos.
Se dice que método heurístico es un procedimiento para resolver un problema de
optimización muy bien delimitado por medio de una aproximación intuitiva, en la
que la estructura del problema se crea de forma adecuada para obtener una
buena solución.
Pero, no solo por lo mencionado anteriormente son utilizados los métodos
heurísticos otras razones pueden ser que el problema sea de una naturaleza tal
que no se conoce ningún método exacto para su resolución, que aún conociendo
el método exacto para resolver el problema este método sea demasiado costoso
computacionalmente, se dice también que los métodos heurísticos son más
flexibles.
Métodos de Solución para Problemas NP
Existen dos tipos de métodos para resolver los problemas de optimización
combinatorial: los exactos y los aproximados. Los métodos exactos garantizan que
la solución encontrada corresponde al óptimo global, y el tiempo requerido para
encontrar dicha solución crece exponencialmente con tamaño del problema. Los
algoritmos aproximados sacrifican la exactitud en la calidad de la solución con el
28
fin de encontrar soluciones en un tiempo polinomial, y aunque no garantizan que la
respuesta corresponde al óptimo global, las soluciones generadas son de buena
calidad y posiblemente se encuentran en las vecindades de el óptimo global, con
la ventaja de que se requiere de consumos de tiempo inferiores.
Para pequeños problemas, los algoritmos exactos consumen grandes cantidades
de recursos computacionales, y a medida que crece el problema se vuelve
intratable en algunos casos. Por lo tanto, si no se puede obtener en la práctica
soluciones en tiempos eficientes, la única posibilidad es cambiar solución óptima
por eficiencia de tiempo. En otras palabras, la garantía de encontrar soluciones
óptimas puede ser sacrificada con el fin de encontrar buenas soluciones en
tiempos polinomiales.
Métodos Heurísticos
Los métodos heurísticos son algoritmos de búsqueda que se basan en el
conocimiento y en la experiencia del problema tratado para encontrar soluciones
en corto tiempo, que aunque no garantizan que sea la solución óptima, si
aseguran el generar buenas soluciones. Los métodos aproximados refuerzan la
calidad de estas soluciones adicionando o reemplazando iterativamente
componentes de modo que se minimice (o maximice) la función objetivo.
Generalmente este procedimiento se aplica hasta superar un número limitado de
iteraciones sin que se mejore la calidad de la solución, dado que no se puede
garantizar en ningún momento que se esté encontrando el óptimo global y por lo
tanto no existe un criterio firme de parada.
Existen métodos heurísticos de naturaleza muy diferente, por lo que es
complicado dar una clasificación completa. Además, muchos de ellos han sido
diseñados para un problema específico sin posibilidad de generalización o
29
aplicación a otros problemas similares. El siguiente esquema trata de dar unas
categorías amplias en donde ubicar a los heurísticos mas conocidos:
Métodos de Descomposición
El problema original se descompone en subproblemas mas sencillos de resolver,
teniendo en cuenta, aunque sea de manera general, que ambos pertenecen al
mismo problema.
Métodos Inductivos
La idea de estos métodos es generalizar de versiones pequeñas o más sencillas al
caso completo. Propiedades o técnicas identificadas en estos casos más fáciles
de analizar pueden ser aplicadas al problema completo.
Métodos de Reducción
Consiste en identificar propiedades que se cumplen mayoritariamente por las
buenas soluciones e introducirlas como restricciones del problema. El objeto es
restringir el espacio de soluciones simplificando el problema. El riesgo obvio es
dejar fuera las soluciones óptimas del problema original.
Métodos Constructivos
Consisten en construir literalmente paso a paso una solución del problema.
Usualmente son métodos deterministas y suelen estar basados en la mejor
elección en cada iteración. Estos métodos han sido muy utilizados en problemas
clásicos como el del viajante.
Métodos de Búsqueda Local
A diferencia de los métodos anteriores, los procedimientos de búsqueda o mejora
local comienzan con una solución del problema y la mejoran progresivamente. El
procedimiento realiza en cada paso un movimiento de una solución a otra con
30
mejor valor. El método finaliza cuando, para una solución, no existe ninguna
solución accesible que la mejore.
Métodos Metaheurísticos
Los métodos metaheurísticos son algoritmos de búsqueda de soluciones óptimas
en problemas combinatoriales para los cuales no existen métodos exactos que
entreguen respuestas en tiempos polinomiales. Básicamente definen la forma de
aplicar y modificar métodos heurísticos con el fin de resolver una gran cantidad de
problemas con tan solo unas pocas variaciones al aplicarlo de un problema a otro.
Existe una gran variedad de estas técnicas metaheurísticas denominadas
combinatoriales, pero algunas han mostrado ser más exitosas que otras en
diversos problemas.
En estos momentos existe un gran desarrollo y crecimiento de estos métodos. En
este capitulo se comentarán algunos procedimientos relativamente consolidados
que han probado su eficacia sobre un gran número de problemas.
Específicamente se considerarán la Búsqueda Tabú, el Templado Simulado y
Métodos Evolutivos, incluyendo los Algoritmos Genéticos, Colonia de hormigas y
la Búsqueda Dispersa (Scatter Search). Si bien todos estos métodos han
contribuido a ampliar nuestro conocimiento para la resolución de problemas
reales, los métodos constructivos y los de búsqueda local constituyen la base de
los procedimientos metaheurísticos. Se debemos tener en cuenta que al resolver
un problema de forma heurística debemos de medir la calidad de los resultados
puesto que, como ya hemos mencionado, la optimalidad no está garantizada.
31
1. ALGORITMOS GENÉTICOS3
El algoritmo genético es una técnica de búsqueda de soluciones y que
originalmente fue idealizado usando los mecanismos de evolución y de la genética
natural, fue inventado por Holland en la década de los 70. La evolución de las
especies está influenciada por un proceso de selección que lleva a la
supervivencia de los individuos genéticamente mejor dotados frente a las
agresiones del medio que los rodea. Para que exista selección deben existir
elementos (individuos) genéticamente diferentes, la explicación de este postulado
la dio Darwin y sus seguidores basados en los siguientes aspectos:
1. División y duplicación de células reproductivas con el fin de identificar los
padres de una generación.
2. El fenómeno del Recombinación genética, dónde a través de las células de
los padres aparece la configuración genética de los descendientes.
3. El fenómeno de la mutación, considerado otra fuente de diversidad
genética, es un mecanismo que permite el surgimiento de nuevas
características en determinados genes llevando a que surjan nuevos
fenotipos con funciones diferentes.
El algoritmo genético genera una secuencia de poblaciones usando los
mecanismos de selección, recombinación y mutación como mecanismos de
búsqueda a través del espacio de configuraciones.
3 GALLEGO R. ESCOBAR. A. ROMERO. R. (2006). Técnicas de Optimización Combinatorial.
Taller Publicaciones U.T.P. Universidad Tecnológica de Pereira.
32
La unidad básica del contenido genético es el gene. El conjunto de genes forma
un cromosoma (o conjunto de cromosomas) que determina la calidad genética del
individuo. Las alteraciones y la diversificación del material genético constituyen la
esencia de la evolución.
Se puede decir que la evolución es consecuencia de la acción conjunta de la
selección natural y de todos los mecanismos que producen diversidad genética
analizados anteriormente.
El algoritmo genético usa una población de individuos, que en los problemas
combinatoriales representa un conjunto de configuraciones, para resolver un
problema de optimización complejo. El algoritmo genético debe entonces hacer lo
siguiente:
1. Representar adecuadamente una configuración del problema. La
representación más popular es la representación en codificación binaria
donde se pueden simular fácilmente los operadores genéticos de
recombinación y mutación.
2. Debe encontrar una forma adecuada para evaluar la función objetivo o su
equivalente (fitness). Así, se pueden identificar las configuraciones de
mejor calidad como aquellas que tienen las funciones objetivo de mejor
calidad.
3. Debe existir una estrategia de selección de las configuraciones con derecho
a participar en la conformación (construcción) de las configuraciones de la
nueva población (nueva generación)
4. Debe existir un mecanismo que permita implementar el operador genético
de recombinación.
33
5. Debe existir un mecanismo que permita implementar el operador genético
de mutación.
6. Debe especificar el tamaño de la población, o sea el número de
configuraciones en cada generación
Una vez especificados todos los aspectos mencionados anteriormente, para
resolver un tipo de problema conocido, se tiene un algoritmo Genético básico. Un
algoritmo genético elemental realiza la siguiente secuencia de operaciones:
1. Genera una población inicial después de escoger el tipo de codificación
para representar cada configuración.
2. Calcula la función objetivo de cada configuración de la población y
almacena la incumbente ( la mejor configuración encontrada en el proceso).
3. Realiza selección.
4. Realiza recombinación.
5. Realiza mutación y termina de generar la nueva población de la siguiente
generación.
6. Si el criterio de parada (o criterios de parada) no se han cumplido el
proceso regresa al paso 2.
Los pasos (2),(3),(4) y (5), en conjunto, son conocidos como ciclo generacional.
También es necesario mencionar que existe una equivalencia entre los términos
usados en genética y en un problema de optimización matemática.
34
Problema de optimización ↔ Genética.
Solución (configuración) ↔ Cromosoma.
Variable ↔ Gene.
Solución ↔ Alelo.
La codificación
La forma de implementar la codificación depende, entre otros aspectos, de la
naturaleza de las variables de decisión del problema o de la representación de una
configuración. Existen problemas con variables binarias (que son las más simples
de representar o codificar), con variables enteras y con variables reales. Los
primeros algoritmos genéticos usaron básicamente codificación binaria, o sea, las
variables enteras y reales de un problema eran transformadas, de alguna manera,
en variables binarias.
La codificación binaria se utilizó intensamente, y continua siendo utilizada, en las
primeras aplicaciones de los algoritmos genéticos porque con esta codificación
fueron desarrolladas todas las propiedades teóricas y las características de
convergencia de los algoritmos genéticos, sin embargo en algunos campos de la
optimización matemática es usada la codificación binaria de variables reales,
aunque algunas propuestas sugieren utilizar las variables enteras como enteras y
las variables reales como reales, eliminando la codificación binaria en el algoritmo,
pero en estos casos se tienen que redefinir parcial o completamente los
operadores genéticos.
35
Cálculo de la Función Objetivo o Algún Equivalente
Se debe tener una estrategia adecuada para encontrar el valor de la función
objetivo (o un equivalente) que determine la calidad de una configuración. Es
frecuente usar un equivalente de la función objetivo para que exista selectividad
entre las configuraciones. Los valores de la función objetivo se utilizan durante la
implementación del operador selección. Para que sea posible la selección debe
haber un subconjunto de funciones objetivo significativamente diferentes a las
demás, pues en caso contrario se perdería la selectividad del operador selección,
esto quiere decir que se perdería la capacidad de diferenciar funciones objetivo de
excelente calidad de funciones objetivo de baja calidad. También es frecuente
normalizar la función objetivo para que asuma valores en el intervalo [0,1]
Selección
Este operador genético permite seleccionar las configuraciones de la población
actual que deben participar en la generación de las configuraciones de la nueva
población (nueva generación). Por tanto la función del operador de selección
termina después de decidir el número de descendientes que debe tener cada
configuración de la población actual. En algunos casos algunas configuraciones
puede generar varios descendientes y otras ninguno, desapareciendo la
información de estas configuraciones que son consideradas de baja calidad.
La forma más simple de implementar la selección es usando el denominado
esquema de selección proporcional. En esta estrategia cada configuración tiene
derecho a generar un número de descendientes que es proporcional al valor de la
función de adaptación. Así se tiene la siguiente relación.
36
( )
( )
ii
m
z xNd
z x=
iNd = Número de descendientes de la configuración i.
n= número de configuraciones de la población.
( )iz x = Función de adaptación.
( )mz x = Media de la función objetivo
1
1( ) ( )
n
m ii
z x z xn =
= ∑
1
( )
ii n
ii
zNd n
z x=
=∑
Recombinación
Las configuraciones seleccionadas en el proceso de selección son sometidas a
recombinación. Este operador consiste en intercambiar partes de dos vectores
para formar dos nuevos vectores donde uno de los vectores nuevos tiene parte de
los elementos de un vector y parte de los elementos de otro vector. Este operador
se denomina también cruzamiento e intenta simular el fenómeno del crossing over
en genética. Generalmente a las configuraciones seleccionadas (originales) se les
denomina configuraciones padres y a las nuevas configuraciones se les denomina
configuraciones hijos.
37
Mutación
En la codificación binaria la mutación significa simplemente cambiar el valor de
una variable de 0 para 1 ó viceversa. En los trabajos teóricos iniciales de
algoritmos genéticos la mutación siempre se consideró un operador secundario,
hoy en día se está reevaluando este concepto.
La tasa de mutación mρ indica la probabilidad de que una posición (celda binaria)
puede tener su valor actual modificado. En el análisis teórico, y en las propuestas
originales, se sugiere que la mutación debe ser intentada bit por bit (celda por
celda) y así la decisión de mutación de una posición binaria es independiente de la
mutación realizada de otras celdas binarias de una configuración.
Ciclo Generacional
Es el conjunto de procesos de selección, recombinación y mutación que permiten
encontrar las configuraciones de la nueva generación (población) a partir de la
población actual. El ciclo generacional es controlado por el programa de control
del algoritmo genético.
Programa de control del Algoritmo Genético
El conjunto de parámetros que define el tamaño de la población, la tasa de
recombinación y la tasa de mutación define en gran parte el comportamiento de
un algoritmo genético. Este conjunto de parámetros es denominado programa de
control del algoritmo genético. Valores típicos en la literatura especializada son
los siguientes:
38
Población: [ ]30, 200pn ∈.
Tasa de recombinación: [ ]0.5,1.0cρ ∈ .
Tasa de mutación: [ ]0.001, 0.050mρ ∈
Criterio de Parada
Existen varios criterios de parada:
− Se ha realizado un número específico de generaciones.
− La incumbente alcanza un valor de una calidad mínima especificada.
− La población es demasiada homogénea, es decir, las configuraciones son
similares y no existe más evolución.
En implementaciones prácticas de problemas complejos se especifican criterios de
parada más objetivos y generalmente se especifica más de un criterio de parada
en un mismo algoritmo.
39
2. ALGORITMO GENÉTICO MODIFICADO – CHU - BEASLEY4
El algoritmo Chu - Beasley es una versión modificada de los algoritmos genéticos
y cuya principal característica consiste en mantener constante el tamaño de la
población; esta estrategia permite conservar en alto grado la diversidad dentro de
la población, siendo esta la característica más relevante de este algoritmo. En
cada iteración se reemplaza una alternativa de la población usando los operadores
propios de los algoritmos genéticos. De esta manera se busca beneficiar las
alternativas menos infactibles y de mejor calidad. En cada iteración la población
es reemplazada sistemáticamente por un único descendiente generado. Una
ventaja adicional es que permite encontrar múltiples soluciones.
El procedimiento seguido en el algoritmo Chu-Beasley es el siguiente:
1. Generar una población inicial.
2. Repetir los siguientes pasos 2-7 hasta cumplir con el criterio de parada
3. Se obtienen 2 alternativas padre por Selección de la población actual
4. Se obtiene una alternativa hijo aplicando Recombinación a los padres
obtenidos en el paso anterior
5. Se obtiene una alternativa modificada aplicando Mutación
6. Si la configuración es infactible se mejora la infactibilidad y se obtiene una
alternativa menos infactible, de lo contrario, ir al paso 6
7. Se mejora la optimalidad de la alternativa en estudio.
8. Si la alternativa resultante de aplicar los pasos anteriores no se encuentra
en la población, entonces aplicar estrategia de modificación de la población,
sino, volver al paso 1.
4 GRANADA M, TORO E. M, Método Híbrido Entre El Algor itmo Genético De Chu-Beasley Y
Simulated Annealing Para La Solución Del Problema D e Asignación Generalizada, Revista
Scientia et Technica (27), 61-67, U.T.P., Colombia.
40
Para modificar la población se propone la siguiente estrategia
1. Si la alternativa actual es infactible y a su vez es menos infactible que la
más infactible de la población, entonces reemplazar la más infactible por la
alternativa actual.
2. Si la configuración es factible y existe por lo menos una infactible en la
población actual, entonces reemplazar la más infactible por la alternativa
actual.
3. Si la configuración es factible y toda las alternativas de la población actual
son factibles, entonces reemplazar la alternativa con peor función objetivo
por la alternativa actual. Lo anterior se realiza sólo si la alternativa actual
es de mejor calidad que la peor de la población.
La estrategia de modificación de la población actual se realiza cambiando sólo una
alternativa por iteración y teniendo en cuenta que no se admiten alternativas
repetidas. Lo anterior evita convergencias prematuras y asegura una exploración
detallada de la región de soluciones. Adicionalmente se pueden obtener múltiples
soluciones de un mismo problema.
Esta estrategia busca preservar las mejores alternativas, asegurando factibilidad y
optimalidad. Estas características constituyen la principal diferencia con respecto
al algoritmo propuesto por Chu - Beasley, en el cual la alternativa más infactible es
reemplazada. A diferencia de los algoritmos genéticos tradicionales, no se
modifica la población de forma aleatoria.
41
3. ALGORITMOS MEMÉTICOS5
Los Algoritmos Meméticos son técnicas de optimización que combinan conceptos
de otras metaheurísticas. Sus orígenes se remontan a finales de los años
ochenta. En aquella época, el campo de la computación evolutiva estaba
comenzando a afianzarse sólidamente. En ese momento surgió la idea de
combinar conceptos y estrategias de diferentes metaheurísticas para integrar las
ventajas de las mismas. La denominación “memético” surge del termino ingles
“meme”, acuñado por R. Dawkins como el análogo del gen en el contexto de la
evolución cultural. Entonces se dice que la idea central de los Algoritmos
Memético son las mejoras individuales de las soluciones en cada uno de los
agentes junto con procesos de cooperación y competiciones de tipo poblacional.
Constitución de un Algoritmo Memético
Un Algoritmo Memético mantiene en todo momento una población de diversas
soluciones al problema considerado, y se llama agente a cada una de las mismas.
Estos agentes se interrelacionan entre sí en un marco de competición y de
cooperación, de manera muy semejante a lo que ocurre en la Naturaleza entre los
individuos de una misma especie. Cuando se considera la población de agentes
en su conjunto, esta interacción puede ser estructurada en una sucesión de
grandes pasos temporales denominados generaciones.
Cada generación consiste en la actualización de la población de agentes, usando
para tal fin una nueva población obtenida mediante la recombinación de las
características de algunos agentes seleccionados. Esto se realiza mediante el
empleo de una función guía la que se encarga de cuantificar cuán bueno es cada
uno de los agentes en la resolución del problema abordado. Por su parte, el
5 MOSCATO. P. Una Introducción a los Algoritmos Meméticos. Inteligencia Artificial, Revista
Iberoamericana de Inteligencia Artificial. No.19 (2003),pp. 131-148. Universidad de Málaga.
42
reemplazo o actualización incide en el aspecto competitivo, encargándose de la
importante tarea de limitar el tamaño de la población, esto es, eliminar algunos
agentes para permitir la entrada de otros nuevos y así enfocar la tarea de
búsqueda.
Tanto la selección como el reemplazo son procesos puramente competitivos en
los que únicamente varía la distribución de agentes existentes, esto es, no se
crean nuevos agentes. Esto es responsabilidad de la fase de reproducción. Dicha
reproducción tiene lugar mediante la aplicación de cierto número de operadores
reproductivos. Es posible emplear un número variado de operadores. No obstante,
lo más típico es emplear únicamente dos operadores: recombinación y mutación.
El primero es el responsable de llevar a cabo los procesos de cooperación entre
agentes. Dicha cooperación tiene lugar mediante la construcción de nuevos
agentes empleando información extraída del grupo de agentes recombinados, y
quizás alguna información externa.
En relación con los operadores de mutación, es posible definir un meta operador
basado en la aplicación iterativa de un operador de mutación arbitrario sobre un
agente. El empleo de estos meta operadores es uno de los rasgos más distintivos
de los Algoritmos Meméticos, dichos meta operadores iteran la aplicación del
operador de mutación, conservando los cambios que llevan a una mejora en la
bondad del agente, motivo por el cual son denominados optimizadores locales.
Los Algoritmos Meméticos pueden caracterizarse como una colección de agentes
que realizan exploraciones autónomas del espacio de búsqueda, cooperando
ocasionalmente a través de la recombinación, y compitiendo continuamente por
los recursos computacionales a través de la selección y el reemplazo. La
generación de la población inicial puede acometerse de diferentes formas, pueden
crearse una población de agentes al azar, o emplear las soluciones
proporcionadas por heurísticas existentes.
43
La función para la reiniciación de la población es otro de los componentes
fundamentales del Algoritmos Meméticos. Esto se conoce como convergencia del
Algoritmo Memético, una vez se ha detectado la convergencia la población de
agentes se reinicia, conservando una porción de la misma, y generando nuevos
agentes para completarla.
Diseño de Algoritmos Meméticos
Cuando se aborda el diseño de un Algoritmo Memético efectivo para un cierto
problema, hay que partir de la base de que no existe procedimiento sistemático
para tal fin. Ello implica que únicamente pueden considerarse heurísticas de
diseño, que probablemente resultarían en un Algoritmo Memético. Resulta
indispensable determinar la representación de las soluciones al problema, las
soluciones son rutas cerradas que visitan n ciudades sólo una vez, es posible
expresar las rutas como una permutación de las ciudades, y definir operadores
que manipulen los valores existentes en posiciones específicas de la permutación.
Es necesario capturar la relación que existe entre una representación de un
problema y su bondad. A tal efecto, se han definido diferentes criterios como los
que a continuación se mencionan.
Minimización de la epistasis
Se habla de epistasis cuando los elementos básicos de información a partir de los
cuales se construyen las soluciones interactúan de manera no aditiva sobre la
función guía. La existencia de una interacción de este tipo impide que se pueda
descomponer la función objetivo en términos optimizables de manera
independiente.
44
Minimización de la varianza de bondad
La varianza en bondad de un cierto elemento de información es la varianza en los
valores que devuelve la función guía, medida sobre un conjunto representativo de
soluciones con dicho elemento de información.
Maximización de la correlación de bondad
Asumiendo un cierto operador reproductivo, se mide la correlación existente entre
la adecuación de los agentes progenitores y los agentes descendientes, si la
correlación es alta, los agentes buenos tendrían una descendencia buena por lo
general. Es pues la selección de operadores el problema de diseño que debe
abordarse. En este sentido, existen dos vertientes: la selección de un operador de
entre un conjunto de operadores preexistentes, o la definición de nuevos
operadores. Tanto en el caso de selección de un operador “clásico" como de
creación de un operador a partir de las plantillas genéricas, se estarían empleando
típicamente operadores “ciegos", que manipulan información relevante pero lo
hacen sin usar información de la instancia del problema que se pretende resolver.
Existen dos fuerzas importantes que favorecen la aplicación de Algoritmos
Meméticos en varias tareas. Por un lado, la creciente disponibilidad de sistemas
de computación concurrente, generalmente basados en clusters, permite a los
investigadores la posibilidad de paralelizar con cierta facilidad los programas. Los
Algoritmos Meméticos se adaptan muy bien a este tipo de paralelismo, a lo que
hay que añadir la creciente relevancia de lenguajes como Java, que facilitan aún
más esta tarea. Por otro lado, ya existe una mejor comprensión, al menos
heurística, sobre como crear Algoritmos Meméticos eficientes. A ello se suman
ciertos avances recientes en la teoría de la complejidad computacional de
operadores de recombinación.
45
4. ALGORITMOS CULTURALES6
Los algoritmos culturales fueron desarrollados por Robert G. Reynolds7, están
basados en las teorías de algunos sociólogos y arqueólogos, que han tratado de
modelar la evolución cultural. Tales investigadores indican que la evolución
cultural puede ser vista como un proceso de herencia en dos niveles: el nivel
micro - evolutivo, que consiste en el material genético heredado por los padres a
sus descendientes, y el nivel macro - evolutivo, que es el conocimiento adquirido
por los individuos a través de las generaciones, y que una vez codificado y
almacenado, sirve para guiar el comportamiento de los individuos que pertenecen
a una población.
La cultura puede verse como un conjunto de fenómenos ideológicos compartidos
por una población, pero por medio de los cuales, un individuo puede interpretar
sus experiencias y decidir su comportamiento.
En estos modelos se trabaja con dos características importantes de la población:
el conocimiento codificado para que sea accesible a todos y la interpretación de
ese conocimiento codificado en. El objetivo es incrementar las tasas de
aprendizaje o convergencia, para que de esta manera el sistema responda mejor
a un gran número de problemas8.
6 LANDA. R. 2002. Algoritmos Culturales Aplicados a Optimización con Restricciones y
Optimización Multiobjetivo. Instituto Politécnico Nacional. México, D. F. 7 Robert G. Reynolds. An Introduction to Cultural Alg orithms. In A. V. Sebald and L. J. Fogel,
editors, Proceedings of the Third Annual Conference on Evolutionary Programming, pages
131–139.World Scientific, River Edge, New Jersey, 1 994. 8 Benjamin Franklin and Marcel Bergerman. Cultural al gorithms: Concepts and experiments.
In Proc. of the 2000 Congress on Evolutionary Compu tation, pages 1245–1251, Piscataway,
NJ, 2000. IEEE Service Center.
46
Los algoritmos culturales operan en dos espacios, el primero el espacio de la
población donde se tiene un conjunto de individuos y cada individuo tiene un
conjunto de características. El segundo espacio es el de creencias, donde se
almacenarán los conocimientos que han adquirido los individuos en generaciones
anteriores.
La información contenida en este espacio debe ser accesible a cualquier individuo,
quien puede utilizarla para modificar su comportamiento. Para unir ambos
espacios se establece un protocolo de comunicación que dicta las reglas del tipo
de información que se debe intercambiar entre los espacios. A continuación se
presenta el pseudo – código de un Algoritmo Cultural.
Algoritmo cultural
1. Generar población inicial
2. Iniciar el espacio de creencias
3. Evaluar población inicial
4. Repetir
− Actualizar el espacio de creencias (con los individuos
− aceptados)
− Aplicar operadores de variación (bajo la influencia
− del espacio de creencias)
− Evaluar cada hijo
− Realizar la selección
Mientras no se cumpla la condición de finalización
47
La mayoría de los pasos de un algoritmo cultural corresponden con los de los
algoritmos tradicionales de computación evolutiva, y se puede apreciar que las
diferencias están en los pasos que incluyen al espacio de creencias. En el
ciclo principal, está la actualización del espacio de creencias.
Es en ese momento donde el espacio de creencias incorpora las experiencias
individuales de un grupo selecto de individuos. Tal grupo se obtiene entre toda
la población con la función de aceptación.
Por otro lado, los operadores de variación de los individuos como la
recombinación o la mutación son modificados por la función de influencia. La
función de influencia ejerce cierta presión, para que los hijos resultantes de la
variación se acerquen a los comportamientos deseables, y se alejen de los
indeseables, según la información almacenada en el espacio de creencias.
Estas dos funciones, la de aceptación y la de influencia, son mediante las
cuales se establece la comunicación entre los espacios de la población y de
creencias.
48
5. BÚSQUEDA TABÚ9
La búsqueda tabú, a diferencia de otros algoritmos basados en técnicas aleatorias
de búsqueda de soluciones cercanas, se caracteriza porque utiliza una estrategia
basada en el uso de estructuras de memoria para escapar de los óptimos locales,
en los que se puede caer al "moverse" de una solución a otra por el espacio de
soluciones. Este algoritmo se dota, por tanto, de una "memoria" donde se
almacenan los últimos movimientos realizados, y que puede ser utilizada para
"recordar" aquellos movimientos que hacen caer de nuevo en soluciones ya
exploradas. Esta "memoria" serviría para impedir la evolución hacia esas
soluciones. A continuación se presentarán los elementos básicos que posee la
Búsqueda Tabú.
Selección de una solución inicial xo :
Un factor muy importante a tener en cuenta es la posible influencia que tenga
comenzar la búsqueda tabú con una solución inicial más o menos buena. Esta
solución dependerá del algoritmo específico que la genera. Con una solución
inicial buena, de bajo coste, generada de forma algorítmica, se puede pensar que
es posible evolucionar, a corto plazo, hacia soluciones mejores, aunque podría
suponer un gran perjuicio computacional si realmente evoluciona la búsqueda
hacia regiones de soluciones más desfavorables. Es, por tanto, necesario evaluar
la conveniencia de considerar un método algorítmico o no. En cualquier caso,
siempre será posible generar una solución de forma aleatoria.
9 GALLEGO R. ESCOBAR. A. ROMERO. R. (2006). Técnicas de Optimización Combinatorial.
Taller Publicaciones U.T.P. Universidad Tecnológica de Pereira.
49
Elección del entorno V(xa):
Para evolucionar hacia otras soluciones, el algoritmo de búsqueda tabú selecciona
éstas en un entorno de xa. Hay que definir, por tanto, el concepto de solución
cercana de xa para proceder a seleccionar una nueva solución dentro de dicho
entorno. Lo natural sería la selección completa (V(xa)-{Lista Tabú}), evaluando
cada una de las soluciones y quedándose con la mejor que no sea tabú. Según se
defina el entorno, es decir, el conjunto de soluciones a las que se puede acceder
desde xa, así será su tamaño. Para realizar una búsqueda completa, es deseable
que el tamaño no sea elevado. Si se considera un entorno de tamaño grande, con
objeto de reducir el tiempo de computación, se puede realizar la búsqueda en un
subconjunto tomado aleatoriamente, o bien realizar la búsqueda hasta que se
mejora el coste de la solución actual.
Elección del tamaño de la lista tabú (L):
Varios autores toman el valor 7 como "número mágico" sin explicación lógica. Más
recientemente, se toman valores dependientes del tamaño del problema. En
cualquier caso, constituye un parámetro importante cuya influencia habría que
analizar y del cual dependerá la evolución del algoritmo en gran medida.
Elección de los atributos para almacenar en la list a tabú:
Almacenar la descripción completa de las últimas soluciones exploradas y
comprobar si cada movimiento se encuentra en la lista puede ocupar mucho
tiempo. Los atributos que se consideren, así como la forma de almacenarlos
dependerán, en cierta medida, del problema a resolver.
50
Nivel de Aspiración:
Si todos los movimientos de la lista tabú se prohiben, se evita entrar en ciclos,
pero se pueden perder movimientos que acerquen a mejores soluciones. En
definitiva, el nivel de aspiración supone un criterio para aceptar soluciones que
están incluidas en la lista tabú. Una posibilidad podría ser definir una Función de
aspiración Fa para cada coste, de forma que un movimiento tabú podría ser
elegido si la nueva solución tiene un coste menor que Fa(F(xa)), siendo xa la
solución actual. También se puede considerar como tal nivel el coste de la mejor
solución alcanzada hasta el momento F(x*). Podría ocurrir que un movimiento tabú
diese lugar a una solución cuyo coste fuese menor que dicho nivel. En tal caso,
parece no tener sentido rechazarla. Este caso podría ser posible según sean los
atributos considerados para caracterizar a un movimiento tabú.
Criterio de finalización:
Se puede establecer un número máximo de iteraciones, o un número máximo de
pasos sin mejorar el costo.
Como en la búsqueda local, la búsqueda tabú selecciona de modo agresivo el
mejor de los movimientos posibles en cada caso, a pesar de esto, al contrario de
lo que ocurre en una búsqueda local, la búsqueda tabú permite moverse en su
vecindad, a pesar de que el movimiento seleccionado no sea tan bueno como el
actual. De este modo, se puede escapar de los óptimos locales y continuar la
búsqueda en otras regiones. Para evitar que el proceso regrese a los óptimos
locales y entre en un ciclo repetitivo, la búsqueda clasifica los movimientos más
recientes como “movimientos tabú”, con lo cual se prohibe que una configuración
sea visitada de nuevo. Este método contiene dos tipos de memoria: memorias de
corto plazo y largo plazo.
51
La memoria a corto plazo:
La estrategia de movimientos rechazados del algoritmo de búsqueda tabú en su
forma más simple se denomina memoria a corto plazo, debido a que la búsqueda
que se realiza es local, utilizando la memoria de los movimientos prohibidos en la
lista tabú. Para problemas más complejos se pueden considerar estrategias de
memorias a plazos más largos. La memoria a medio plazo tiene como objetivo
registrar los atributos más comunes de un subconjunto de soluciones
seleccionadas durante un cierto período de búsqueda que con más probabilidad
lleven hacia mejores zonas para explorar. Estos atributos sirven de modelos para
intensificar la búsqueda de soluciones.
La memoria a largo plazo:
Diversifica la búsqueda sobre regiones poco exploradas. En las consideraciones
de largo plazo, se utiliza la llamada memoria basada en frecuencia, esta contiene
información relacionada con el tiempo en que ciertos atributos pertenecen o no a
las soluciones visitadas. Esta información es fundamental para definir estrategias
de diversificación, las cuales permiten saltar para regiones no visitadas
anteriormente. Existen tres aspectos fundamentales relacionados con la memoria
de largo plazo: La memoria basada en frecuencia, La estrategia de intensificación
y La estrategia de diversificación.
La memoria basada en frecuencia consiste básicamente en almacenar la
información del número de veces en que un atributo fue seleccionado para
generar o participar en la formación de las configuraciones durante el proceso de
la búsqueda tabú. Así existen dos tipos de memoria basadas en frecuencia: las
frecuencias de transición que almacena el número de veces en que un atributo es
retirado o adicionado para formar nuevas configuraciones, y la frecuencia de
residencia o permanencia que almacena la información del número de veces en
52
que un atributo permanece en las nuevas configuraciones o en todas las
configuraciones generadas durante el proceso la búsqueda tabú. Esta información
basada en frecuencia puede ser utilizada para penalizar o incentivar
configuraciones con determinados atributos.
Con relación a las estrategias de intensificación y diversificación, en la primera se
establece una búsqueda detallada alrededor de las buenas soluciones; en la
segunda, es posible pasar para otras regiones.
Las estrategias de intensificación y diversificación pueden ser integradas usando
la estrategia denominada ”encadenamiento de trayectorias” path relinking,
mediante la generación de nuevas soluciones obtenidas al explorar las
trayectorias que conectan las buenas soluciones.
Otra estrategia de búsqueda muy importante es la oscilación estratégica, en esta
los movimientos son guiados hasta un límite y después, en el proceso, se permite
cruzar ese límite regresando y cruzando el límite nuevamente en el sentido
opuesto. La repetición de este procedimiento es oscilatorio.
El método de búsqueda tabú al contrario de otros métodos tales como Simulated
Annealing, Algoritmos Genéticos, Colonia de Hormigas y GRASP, se basa en
movimientos determinísticos y no aleatorios. La búsqueda tabú hace uso de
estructuras especiales de memoria y de estrategias de búsqueda dinámica.
53
La búsqueda tabú es diferente de un algoritmo de búsqueda local en dos aspectos
fundamentales:
1. A partir de la configuración actual, se pasa para la mejor configuración
vecina o a la que menos degradación produce en la función objetivo, esto
implica que es permitido un empeoramiento de la calidad de la función
objetivo.
2. El conjunto de vecinos de x no se caracteriza de manera estática. Así, la
búsqueda tabú define una nueva estructura de vecindad, N*(x) que varía
dinámicamente en estructura y tamaño durante todo el proceso de
optimización. Esta estrategia permite a la búsqueda tabú realizar una
búsqueda eficiente e inteligente. Se pueden indicar las siguientes normas:
− Usando una lista tabú que almacena los atributos de las configuraciones
consideradas tabú (prohibidas).
− Usando estrategias para disminuir la vecindad o la lista de
configuraciones candidatas.
− Usando configuraciones de elite y “path relinking” para caracterizar y
encontrar nuevas configuraciones candidatas.
− Redefinir el conjunto N(x) durante el proceso de optimización.
54
6. SIMULATED ANNEALING10
Simulated Annealing es una metaheurística para problemas de optimización
global, es decir, encontrar una buena aproximación al óptimo global de una
función en un espacio de búsqueda grande.
La denominación del algoritmo, Recocido Simulado, o Simulated Annealing en
inglés, proviene de la estrecha analogía, analogía que es la que le ha dado origen,
que guarda con el proceso del Recocido tal y como se usa en metalurgia. Éste
consiste en que un metal fundido se va enfriando lentamente de manera que sus
moléculas van adoptando poco a poco una configuración de mínima energía.
Cuando comienza el proceso, a alta temperatura, las moléculas vibran y se
desplazan caóticamente adoptando todo tipo de configuraciones en la estructura
del metal de la que forman parte. A medida que la temperatura disminuye se va
ralentizando el movimiento de las moléculas y estas, de acuerdo con la
Termodinámica, tienden a adoptar paulatinamente las configuraciones de menor
energía, siendo ésta nula en el cero absoluto. Durante sus vibraciones en la red
metálica las moléculas podrán saltar de una configuración a otra con una
probabilidad que será directamente proporcional a la temperatura e inversamente
proporcional a la diferencia de energías entre las configuraciones inicial y final y
que vendrá dada por la distribución de Boltzmann:
E
k T
i E j
bp e
−
=
Donde T representa la temperatura y kb es la constante física conocida como
constante de Boltzmann.
10 GALLEGO R. ESCOBAR. A. ROMERO. R. (2006). Técnicas de Optimización Combinatorial.
Taller Publicaciones U.T.P. Universidad Tecnológica de Pereira.
55
Si la disminución de la temperatura se efectúa de manera gradual, el sólido podría
alcanzar el estado de equilibrio en cada nivel de temperatura. En el algoritmo de
Metrópolis esto se consigue después de generar un gran número de transiciones
en un nivel dado de temperatura.
Para cada valor de temperatura T, el sólido encuentra un equilibrio térmico,
caracterizado por la probabilidad de estar en un estado i con energía Ei dado por
la distribución de Boltzman:
{ } 1
( )
E
k
T
j
b Tp x i ez T
− = = =
Donde:
X denota una variable estocástica del estado actual del sólido; es un factor de
normalización, conocido como función de partición.
( )
E
k
j
j
b Tz T e − = ∑
Kb es la constante de Boltzman; y es conocido como factor de Boltzman
E
k
j
b Te −
En este algoritmo se aplica una acción combinada del mecanismo de generación
de alternativas y del criterio de aceptación. Tk denota el valor del parámetro de
control (temperatura) y Nk el número de alternativas generadas en la k - ésima
iteración del algoritmo.
56
Inicialmente cuando T es grande, se aceptan grandes cambios en la función
objetivo; cuando T decrece, solamente pequeñas deterioraciones son aceptadas;
cuando T tiende a cero, ninguna deterioración es aceptada. Esta característica
hace que el algoritmo Simulated Annealing sea diferente a los algoritmos de
búsqueda local. A partir del estado i con costo f(i) se genera el estado j con costo
f(j). El criterio de aceptación para el problema de minimización, determina si este
nuevo estado es aceptado; para esto se calcula la siguiente probabilidad.
{ } ( ) ( )
1 ( ) ( )
( ) ( )f i f jT j
T
s i f j f iP a cep ta
e s i f j f i−
↔ ≤ = ↔ >
Programa de Enfriamiento
No existen reglas para seleccionar el mejor programa de enfriamiento, esto
dependerá del tipo de aplicación y la forma como los parámetros están asociados
a la representación del problema.
Temperatura inicial
Una característica que debe cumplir toda heurística de búsqueda es la de no ser
dependiente de la solución inicial. Para resolver esta dificultad, el Simulated
Annealing inicia con una temperatura alta. La temperatura inicial debe ser
calculada de tal manera que sólo será aceptado un número determinado de
configuraciones propuestas; de estas, las que tengan peor valor en la función
objetivo no podrán sobrepasar un porcentaje de empeoramiento en relación a la
función objetivo que las originó, de tal forma que la configuración no se aleje a
regiones poco atractivas, lo que implicará mas tiempo de computación, al intentar
regresar a las regiones más atractivas.
57
Algoritmo Para el Cálculo de la Temperatura Inicial (To):
1. Inicializar To= 0;
2. Ejecutar la cadena m0;
3. Intentar nueva alternativa.
4. Si ( ) ( ) 0F i F j− ≤ , entonces 1 1 1m m= + y aplique la fórmula:
− Caso contrario, 2 2 1m m= + y aplique la fórmula para el cálculo de To
− Si 1 2 0 +m m m= , terminó la cadena y el valor de To (calculado en la
última transición) es asumido como la temperatura inicial del proceso.
En caso contrario, regrese al paso 3.
Tasa de enfriamiento
El valor de la cadena Nk deberá ser lo suficientemente grande para que el sistema
pueda alcanzar su estado de equilibrio para ese nivel de temperatura Tk, esto
significa un gran número de iteraciones. Como esto no es posible, al calcular los
parámetros tiene que haber un equilibrio entre la tasa de enfriamiento β y la
longitud de la cadena Nk. En la literatura se recomiendan tasas de enfriamiento en
el intervalo [0,8 ; 0,99], que corresponden a un enfriamiento lento. Con el fin de
que se permita una exploración más intensa en las temperaturas bajas. Puede
considerarse un Nk creciente cuando decrece Tk. Esta regla no es general y cada
aplicación podrá tener un programa de enfriamiento más específico.
58
Temperatura final
La temperatura correspondiente al “sistema frío" deberá ser aquella para la cual
Tf = 0. No obstante, antes de llegar a este valor la probabilidad e
T
δ− , de que
sea aceptada una solución peor, es casi nula. Por lo tanto Tf > 0. Los criterios de
parada están basados en el argumento de que la ejecución del proceso debe ser
interrumpida si la mejoría esperada en la función objetivo, en el caso de continuar
ejecutando el algoritmo es pequeña.
Número de tentativas. Nk
El valor de Nk debe permitir que el proceso pueda llegar al estado de cuasi -
equilibrio para el nivel de temperatura Tk y la disminución de Tk para no debe ser
grande a fin de restaurar el nuevo estado de cuasi-equilibrio para el nuevo valor de
temperatura. Así el cuasi - equilibrio del proceso podrá ser garantizado con
elevados valores de Nk y grandes disminuciones de Tk o con pequeños valores de
Nk y también pequeñas disminuciones en Tk.
Convergencia
Teóricamente se tiene demostrado que el algoritmo es convergente en el sentido
que se podrá tener probabilidad tan cerca de 1 como se quiera; el algoritmo
encuentra la solución óptima del problema independientemente de la solución
inicial de que inicie. Aunque computacionalmente es extremadamente costoso por
el tiempo de procesamiento.
59
7. TÉCNICA DE COLONIA DE HORMIGAS1112
El algoritmo “Ant Colony Optimization”, ACO, es una clase de los denominados
sistemas de Hormigas y fue propuesto inicialmente por Colorni, Dorigo y
Maniezzo. Las hormigas son insectos sociales que viven en colonias y que, debido
a su colaboración mutua, son capaces de mostrar comportamientos complejos y
realizar tareas difíciles desde el punto de vista de una hormiga individual. Un
aspecto interesante del comportamiento de muchas especies de hormigas es su
habilidad para encontrar los caminos más cortos entre su hormiguero y las fuentes
de alimento. Este hecho es especialmente interesante si se tiene en cuenta que
muchas de las especies de hormigas son casi ciegas, lo que evita el uso de pistas
visuales.
Mientras que se mueven entre el hormiguero y la fuente de alimento, algunas
especies de hormigas depositan una sustancia química denominada feromona. Si
no se encuentra ningún rastro de feromona, las hormigas se mueven de manera
básicamente aleatoria, pero cuando existe feromona depositada, tienen mayor
tendencia a seguir el rastro.
En la práctica, la elección entre distintos caminos toma lugar cuando varios
caminos se cruzan. Entonces, las hormigas eligen el camino a seguir con una
decisión probabilística sesgada por la cantidad de feromona: cuanto más fuerte es
el rastro de feromona, mayor es la probabilidad de elegirlo. Puesto que las
hormigas depositan feromona en el camino que siguen, este comportamiento lleva
11 GALLEGO R. ESCOBAR. A. ROMERO. R. (2006). Técnicas de Optimización Combinatorial.
Taller Publicaciones U.T.P. Universidad Tecnológica de Pereira. 12 GRANADA M, TORO E. M, TABARES P. Método de Colonia de Hormigas Aplicado a la Solución
del Problema de Asignación Generalizada. Revista Tecnura No 15, Universidad Distrital F.J.C., II-
2004.
60
a un proceso de autorefuerzo que concluye con la formación de rastros señalados
por una concentración de feromona elevada. Este comportamiento permite
además a las hormigas encontrar los caminos más cortos entre su hormiguero y la
fuente del alimento.
Comportamiento de las Hormigas reales
Deneubourg y sus colegas (Aron, Goss, & Pasteles) presentaron en 1990 el
informe sobre un experimento realizado bajo condiciones controladas usando un
puente de dos vías, el cual interconectaba por medio de dos caminos de distinta
longitud un nido de hormigas con una fuente de alimento. Cada individuo de la
colonia se desplaza con libertad por todo el recorrido y la decisión de elegir un
camino u otro es voluntad propia de cada hormiga. Al cabo de un tiempo el
resultado global es que un alto porcentaje de las hormigas se desplaza por el
camino más corto, y el tiempo requerido para llegar a esta instancia depende de la
relación entre las distancias de los dos caminos; mientras mas amplia sea la
diferencia menor será el tiempo requerido.
Explotación de los Rastros de Feromona y Exploració n
En el momento en que uno de los individuos de la colonia encuentra un camino
hacia una fuente de alimento, se inicia un proceso de explotación, es decir que los
demás individuos de la colonia se ven atraídos a recorrer frecuentemente dicho
camino que conduzca a la fuente de alimento. De esta manera se incrementa
progresivamente los rastros feromona y prácticamente se desecha la búsqueda de
vías alternativas.
61
En otras palabras, la explotación de un camino permite que el sistema converja
rápidamente sobre una solución, que para el caso del puente doble consiste en
que un porcentaje ampliamente mayor de hormigas transite por el camino corto. Si
la relación de distancias entre los brazos del puente se aumenta, el sistema
explota más rápidamente el camino corto y margina progresivamente el camino
largo.
Evaporación de Rastros de Feromona
El motivo por el cual los caminos con recorridos largos son desplazados de la
preferencia de las hormigas a pesar de que existan rastros acumulados, se debe a
un proceso de Evaporación de la feromona. En ambientes naturales, la feromona
depositada tiende a perder su intensidad debido al efecto del sol, la lluvia, el viento
o cualquier otro factor externo. La existencia de caminos más atractivos disminuye
la presencia de hormigas transitando por los caminos largos. El poco incremento
de feromona combinado con el proceso de evaporación reduce gradualmente la
cantidad de feromona acumulada sobre los caminos largos y aumenta la
preferencia de las hormigas por transitar en los caminos cortos.
Sistema Hormigas
Las primeras versiones de optimización basadas en hormigas se presentaron
como Ant-density y Ant-quality. Más adelante se introdujo un algoritmo que
presentó mayor eficiencia, conocido como Ant-cycle, por lo que al hablar del
sistema hormigas se hace referencia en esta versión.
El Sistema Hormigas es una meta heurística en la cual una colonia artificial
compuesta por pequeños programas computacionales (conocidos como hormigas)
cooperan entre sí para la búsqueda de soluciones óptimas a problemas de tipo
62
combinatorial. Observando a gran escala, el proceso de optimización con el
Sistema Hormigas se efectúa realizando iterativamente los siguientes pasos:
1. Construcción de soluciones.
2. Evaluar de las soluciones en la función objetivo.
3. Depositar feromona.
4. Evaporar rastros de feromona.
El Sistema Hormigas se clasifica dentro del grupo de algoritmos de aproximación
de tipo constructivo a problemas de optimización combinatorial, ya que una
población de m individuos, conocidos como hormigas artificiales, se encargan de
generar iterativamente soluciones a un problema determinado y luego evaluar la
calidad de dichas soluciones, conservando siempre la mejor que se halla
encontrado durante todo el proceso.
Hormigas Artificiales
El primer paso en la aplicación del algoritmo en cualquier tipo de problema
consiste en definir: ¿qué es una hormiga artificial para el problema?, ya que de
aquí se desprende el tipo de solución que se debe construir y la forma que
adoptará la matriz de feromonas. Retomando el ejemplo del problema del agente
viajero, se encuentra una analogía directa con el problema enfrentado por la
hormiga natural al viajar desde el nido en busca del alimento y viceversa:
encontrar el camino más corto. Por lo tanto, una hormiga para el problema del
agente viajero representa una forma de recorrer en su totalidad el conjunto de
ciudades. En un principio, no interesa el orden con el cual la hormiga pase por las
ciudades, lo único que interesa es encontrar una trayectoria que cumpla las
restricciones. El optimizar el camino es un trabajo conjunto con los otros individuos
de la colonia y se logra mediante una comunicación indirecta a base de feromona
artificial.
63
De esta manera la población de la colonia de hormigas estará formada por grupos
de m soluciones diferentes, y en cada iteración los m individuos crearán otras
alternativas en base a la información acumulada en la matriz de feromonas. La
cantidad de hormigas a usar en el proceso es determinada de acuerdo al tamaño
del problema, es decir que para el presente caso es igual al número de ciudades.
Matriz de Feromonas
El espacio de almacenamiento de feromonas contiene las acumulaciones de
feromona sobre todos los elementos que son necesarios para construir el conjunto
de soluciones (S) del problema. Las trayectorias creadas por cada hormiga están
conformadas por la selección de unos caminos específicos de entre una gran
cantidad de alternativas a elegir. Se supone que la hormiga inició su trayectoria en
el nodo 1 y tenía la posibilidad de partir hacia 11 locaciones distintas. A medida
que avanzó de ciudad en ciudad encontró el mismo número de posibles
conexiones (algunas prohibidas por las restricciones y otras no). La dimensión de
la matriz de feromonas por tanto debe ser tal que albergue cada posibilidad
existente, es decir todas las conexiones sin importar restricciones, ya que estas
varían de acuerdo al orden en que se avance.
Construcción de Soluciones
Cada hormiga de la colonia artificial debe disponer de herramientas para armar
soluciones factibles como las mostradas por m1 y m2 del ejemplo anterior, y
dichas herramientas se centran principalmente en el uso de la información
acumulada en la matriz de feromonas.
Una hormiga k tratando de construir su trayectoria se encuentra en un momento
dado posicionada en la ciudad i, donde debe decidir sobre cuál será su próximo
destino al elegir de entre una serie de caminos los cuales están marcados con
64
cantidades de feromona y con información heurística diferentes. La probabilidad
con la cual la hormiga k escogerá el camino de i a j; donde j es una ciudad que
aún no han sido visitada, está dada por:
[ ] [ ][ ] [ ]∑
∈⋅
⋅=
ki
ijijij
Nlilil
kpβα
βα
ητητ
Donde ijτ es el elemento (i,j) acumulado en la matriz de feromonas que define la
deseabilidad aprendida por dirigirse al nodo j estando ubicado en el nodo i, es
decir que informa sobre el grado de aceptación por parte de anteriores hormigas
por recorrer el arco de i hacia j, entre más sean las hormigas que hayan transitado
el arco i - j mayor será la acumulación de feromona y por tanto aumentará la
probabilidad de elegirlo.
El término ijη es un valor proveniente de alguna información heurística mediante
una ecuación, en la cual se mide el impacto de adicionar el elemento j sobre la
construcción de la reciente solución.
ijη representa la información heurística y el valor almacenado en la matriz de
feromonas de cada elemento l que se encuentre en la vecindad del nodo i durante
la construcción de la hormiga k (Nik).
(Nik) es conocido como la vecindad de i para la hormiga k y alberga el conjunto de
posibilidades existentes para agregar una nueva ciudad en la construcción de la
presente solución, es decir el conjunto de arcos disponibles para continuar el
recorrido. Se hace aclaración de que pertenece a una hormiga determinada ya
que dos hormigas posicionadas en el mismo nodo pueden tener vecindades
distintas.
65
Construcción de Soluciones Inválidas
Opcionalmente; y con el fin de generar una mayor exploración sobre el espacio de
solución; se permite en ocasiones la formación de soluciones con elementos que
van en contra de las restricciones del problema, siendo en tal caso penalizada la
función objetivo con un incremento determinado por el tipo de violación. Se puede
considerar una solución en la cual se visita un mismo nodo en más de una
ocasión, y a pesar del incremento por la penalización se dé que la evaluación de la
función objetivo genere la mejor respuesta encontrada hasta ese instante, siendo
además probable que no se encuentre otra solución que la mejore. Por tal motivo
resulta inapropiado eliminar estrictamente toda función que viole el conjunto de
restricciones, y en tal caso es mejor admitirla con el respectivo incremento de la
función objetivo original f(s) dado por una función ipn , conocida como “Acción del
Demonio” , quedando de la forma de:
∑⋅+=S
ipnwsfsF )()(
La formulación del problema debe administrar al algoritmo la cuantificación a cada
tipo de violación, es decir el valor que adquiere ipn cuando el elemento i usado en
la construcción de la solución s incumple el conjunto de restricciones del
problema. El factor w es un parámetro de inicialización del algoritmo que
determina el impacto de cada penalización en el cálculo global de la función F(s).
La sumatoria de la ecuación indica la posible presencia de más de un elemento
inválido en la construcción de la solución s.
66
Evolución del Algoritmo ACO
Desde la presentación del primer algoritmo basado en hormigas en 1992, se han
presentado variaciones a la versión original inspiradas en comportamientos
particulares del ambiente natural de las colonias de hormigas. Las diferencias
radican básicamente en la forma de evaluar y depositar los rastros de feromona y
en el momento en cual se realizan los depósitos sobre la matriz de feromona.
67
ESTADO DEL ARTE DE LA OPTIMIZACIÓN DE HORARIOS
En esta sección se presenta una breve descripción de los problemas que han sido
modelados de forma matemática en empresas de un tamaño relevante;
presentando el modelo planteado y el método que se ha utilizado para dar
solución al problema de programación de mano de obra.
La construcción de horarios de trabajo ha sido reconocida durante un largo tiempo
como una parte elemental para mejorar la productividad en los servicios. Muchas
empresas tienen demandas que varían significativamente de una hora a otra y de
un día a otro. Si esas empresas carecen de capacidad para satisfacer la demanda
cuando esta se presenta pueden incurrir en pérdidas o aumentar sus costos. De
igual forma si la capacidad de oferta del servicio supera a la demanda, este
exceso podría conducir al despilfarro.
Dantzing13 fue el primero en formular el problema de Labor Scheduling como un
modelo matemático. La formulación propuesta por él es la siguiente:
∑=
m
j
CjXjMin1
Sujeto a:
rxa ij
m
jij
≥∑=1
,
; i = 1… h
0≥x j Zx j
∈
13 A Comment on Edie´s “Trafic Delays at Tool Booths”. 1954 Operation Research, 2,3, pp. 339 –
341.
68
Donde:
h = número de periodos de tiempo considerados (normalmente horas)
m = número de turnos posibles o permitidos.
1, si el periodo i está incluido en el turno j,
ai,j =
0, en otro caso i = 1... h y j = 1... m
cj = costo de tener un empleado trabajando durante un turno j, j = 1...m
ri = nivel requerido de trabajadores en el periodo i, i = 1... h
xj = número de empleados trabajando en el turno j, j = 1... m
El objetivo de este modelo es minimizar el costo de los turnos programados en el
horizonte temporal considerado (ya sea un día o una semana) sujeto a que haya
suficiente número de trabajadores en todos los periodos para satisfacer la
demanda.
Las empresas presentan flexibilidad en sus horarios, por tal razón el número de
turnos es muy alto, además conocemos que este tipo de problemas son NP-
Duros, es decir que se requiere de mucho tiempo para obtener la solución óptima
esto crea la necesidad de explorar técnicas tales como las heurísticas y
metaheurísticas que entregan respuestas de buena calidad en tiempos
aceptables.
69
1. ORGANIZACIÓN DE TURNOS DE TRABAJO EN UNA INSTALA CIÓN DE
SUMINISTRO DE COMBUSTIBLE DE UN AEROPUERTO. 14
El trabajo aquí expuesto consiste en el desarrollo de un sistema informático para
organizar los turnos de trabajo de CLH (antigua Campsa) en los aeropuertos. Esta
es una compañía del grupo Repsol que entre otras actividades se encarga del
suministro de combustible a todos los aviones que aterrizan en los aeropuertos
españoles. El problema de confeccionar automáticamente los turnos de trabajo
para los empleados se podría describir sencillamente como determinar la hora de
entrada y salida de cada trabajador, durante los días comprendidos en el horizonte
de planificación que el administrador decida, cubriendo las necesidades de carga
de trabajo del aeropuerto donde se está planificando en cada momento y
respetando las normas del convenio colectivo de la compañía. La planificación se
realiza por semanas enteras siendo, por tanto, el horizonte de planificación un
conjunto de semanas consecutivas. Para resolver el problema se desglosaron tres
etapas claramente diferenciadas:
1. Cálculo de los esquemas de turnos de trabajo nec esarios.
Un esquema de trabajo es una serie de posiciones de actividad (mañana, tarde,
noche o descanso) de un trabajador que cubren su actividad laboral durante una
semana como, por ejemplo, NNNDDTT. Todo esquema ha de contener como
mínimo un día de descanso. Los objetivos que se persiguen en esta etapa son
conseguir unos buenos descansos semanales y la rotación de los turnos.
La formulación del problema sería la siguiente :
14 R.Alvarez-Valdés1, E. Crespo2 y J.M. Tamarit1, VI Jornadas ASEPUMA, Santiago de
Compostela, 25 y 26 de Septiembre de 1998
70
S: Conjunto de esquemas.
t: Periodos de la semana t: 0,...,T
Variables: Xs: Cantidad de apariciones del esquema s.
Cs: Costo del esquema s.
Matriz de restricciones:
Función Objetivo:
Sujeto a:
Xs entero ≥ min valor y compatible con la semana anterior.
Donde rt es el nivel de requerimientos de trabajadores activos en un periodo
determinado y min valor es el número de esquemas con fin de semana necesarios
para garantizar que cada trabajador descanse, como mínimo, uno de cada 4 como
exige el Convenio.
Esta primera etapa es la parte más difícil del problema y se aborda con un
procedimiento de Tabú Search en el cual se incluyen técnicas de oscilación
estratégica que combinan fases constructivas y destructivas. En las primeras se
aumenta el número de esquemas mientras que en las segundas se reduce.
Es decir, si se inicia desde una solución infactible se va aumentando el número de
esquemas para producir una solución posible. Recíprocamente, si se encuentra en
XCSsMIN ss∈=
rXASs tsts ≥∈ Tt ,...,0=∀
= contrario. caso en
periodo el cubre si 1
0
tsAts
71
la región de soluciones posibles la fase destructiva conducirá a la región infactible.
Este proceso está controlado por un parámetro de amplitud que varía según unas
determinadas reglas y que indica cuanto se puede adentrar en cada una de las
dos regiones.
El proceso de búsqueda va guiado por una función objetivo donde se ponderan los
costos de los esquemas elegidos, costos que son menores según la bondad del
esquema, y que se trata de minimizar. El status tabú de los movimientos viene
determinado por la información sobre la distancia en el tiempo y la frecuencia,
obtenida cuando se encuentran acontecimientos críticos, que son aquellas
soluciones obtenidas nada más por cruzar la frontera.
Este tipo de situaciones son consideradas básicas en el proceso y cuando se
encuentra alguno de ellos y antes de seguir adentrándose en la nueva región, se
realiza una búsqueda local para obtener mejores soluciones factibles.
El final de esta etapa proporciona una solución con N esquemas para A
trabajadores. Si N > A, el problema es infactible. Si N = A se pasa a la segunda
fase y si N < A el sistema añade esquemas predefinidos para dedicarlos a
actividades de mantenimiento de instalaciones.
2. Asignación de los trabajadores a los esquemas.
Los períodos de la semana vienen determinados por los diversos momentos en los
que un grupo de trabajadores puede incorporarse al trabajo (8:00, 8:30, 9:15…) y
abarcan el lapso de tiempo hasta el inicio del siguiente período (8:00 - 8:30, 8’30 –
9:15…). No todos los días que tenga el mismo turno de trabajo (M,T,N) tiene
porque tener el mismo horario.
72
Consiste entonces en ponderar los costos de cada asignación y evitar las
asignaciones que sean imposibles, por violar el contrato de cada trabajador,
ponderándolas con valores muy altos. A la hora de fijar los costos hay que mirar
hacia adelante y considerar varios requerimientos anuales de equilibrio entre los
trabajadores en diversos aspectos (noches realizadas hasta el momento, distancia
del último descanso que realizó en fin de semana, muchos días seguidos de
trabajo sin descansos...).
Por tanto, aquí no se busca solamente la mejor solución para la semana que se
está programando sino soluciones que garanticen que, a medio y largo plazo, se
satisfacen las restricciones.
3. Determinación de las horas de entrada y salida d el personal.
En la tercera etapa se trata de fijar la jornada exacta de cada trabajador, es decir
su hora de entrada y salida exacta cada día. Esta etapa tiene dos partes
diferenciadas. Comienzan tratando de cubrir todos los requerimientos y cuando
esto está conseguido se trata de mejorar la solución respecto a objetivos
secundarios. Para todo esto se aplica una serie de reglas heurísticas de manera
que se asegure que se cubre la carga de trabajo en los momentos de cambio de
turno al tiempo que se reduce al máximo la jornada diaria de cada persona para
no sobrepasar la cantidad anual de horas pactada.
4. Implementación
El algoritmo está incluido en un paquete informático llamado PAUTA que está
diseñado para ser usado por los jefes de cada instalación. Contiene módulos de
entrada, edición y modificación de datos y el de resolución para un número de
semanas a elegir, así como un módulo de salida para visualizar e imprimir los
resultados según las diversas necesidades del usuario.
73
2. METODOLOGÍA DE LA ASIGNACIÓN ÓPTIMA DE MANO DE O BRA EN LA
INDUSTRIA DE LA FLORICULTURA. 15
Este documento diseña una metodología óptima de asignación en la industria de
Flores en Colombia, partiendo de la base de un modelo matemático de
optimización. El modelo es formulado de acuerdo con las condiciones laborales y
administrativas de las empresas Colombianas. El objetivo es asignar, al menor
costo de mano de obra de producción posible, las tareas sobre las plantas, las
cuales se encuentran distribuidas dentro del cultivo en porciones de tierra
denominadas camas, que a su vez se encuentran agrupadas en estructuras
llamadas naves. Los grupos de naves conforman los denominados bloques.
Modelo de asignación de personal en el sector floricultor:
∑∑∑∑∑== = = =
+m
iiiijij
p
l
NCl
k
n
j
m
iijkl CTEYcxMIN
11 1 1 1λ
La función objetivo, minimiza los costos de asignación de trabajadores i a trabajos
j sobre las camas k que pertenecen al bloque l, (Xijkl λij Cij). Además minimiza el
costo por asignación de los operarios en tiempo extra (YiCTEi).
Sujeto a:
Precedencia:
∑∑∑∑= == =
+≤
NCl
k
m
iijkl
NCl
k
m
iklij xx
1 11 11
; plnj ,...,1;,...,1 ==∀
Donde el trabajo j es predecesor del trabajo j+1. Esta restricción obliga al modelo a
guardar las precedencias de las labores. Siempre que j sea predecesor de j+1 es
15 GUZMÁN H. F, Metodología De Asignación Optima De Mano De Obra En La Industria
Floricultora Colombiana, Universidad de los Andes.
74
necesario hacer primero j y luego j+1. La sumatoria sobre todas las camas k del
bloque l, asegura que hasta tanto no se termine la labor j sobre la totalidad de las
camas del bloque no es posible comenzar la labor j+1.
Unidad: F – G = 0
Hace referencia a la necesidad de que un trabajador i asignado a un trabajo j
sobre una cama k realice, sobre la misma cama, los trabajos j+1, j+2,..., h (h ≤ n).
Donde h son los trabajos requeridos para la cama durante el horizonte de
planeación. El trabajador i debe realizar todas las labores que se requieren
durante una semana sobre las mismas camas k, la asignación para la cama 1, el
trabajador 1 y el bloque 1.
Cumplimiento:
NCx l
m
i
NCl
kijkl
=∑∑= =1 1 ; plnJ ,...,1;,...,1 ==∀
Se asegura que el modelo asigna la totalidad de las camas k pertenecientes al
bloque l que requieren el trabajo j a uno o más trabajadores i.
Disponibilidad:
125*DAi≤ ; mi ,...,1=∀
El modelo asigna a los trabajadores de acuerdo con su disponibilidad durante el
horizonte de planeación, el cual es de una semana.
75
Asignación por cama:
1
1
≤∑=
m
iijklx
; nj ,...,1=∀ ; NClk ,...,1= ; pl ,...,1=
{ }1,0,,,, ∈GFTYX iiijkl ; mi ,...,1=∀ ; nj ,...,1=∀ NClk ,...,1= ; pl ,...,1=
Con esta restricción se asegura que el trabajo j sobre la cama k, no es fraccionado
y se asigna a un solo trabajador.
Notación y Definición de Parámetros
i : Personas i =1,...,m
j : Trabajos j =1,...,n
k : Camas k = 1,...,NCl donde NCl es el número de camas que conforman el
bloque l.
l : Bloques l = 1,...,p ; donde p es el número de bloques que conforman la finca.
Ci : Costo de una hora de trabajo del trabajador i :
El salario es el valor pagado al operario i dentro de la compañía. En la fórmula se
adiciona un 50% al salario para tener en cuenta el costo por prestaciones legales.
Para el denominador suponemos la jornada laboral diaria de 8 horas durante 6
días a la semana y 4 semanas al mes, obteniendo 192 horas de trabajo al mes.
Esta relación proporciona el valor de una hora en tiempo regular de trabajo para la
persona i.
=
mesHoras
iPersonaSalarioC i /_192
5.1*__
76
λij : Es el tiempo que tarda el trabajador i realizando la labor j sobre una cama,
esta definido como :
Donde :
α*j: Es el tiempo estándar que tarda el mejor trabajador en realizar el trabajo j
sobre una cama, expresado en horas/cama.
δij: Es un factor de ineficiencia del trabajador i haciendo el trabajo j. Este valor es
definido para cada uno de los trabajos j.
Cij: Costo de asignar el trabajo j al trabajador i en tiempo regular. Se define como
el producto entre el costo de una hora de trabajo del trabajador i (Ci), multiplicado
por el tiempo que se tarda el trabajador i realizando la labor j (λij).
C*ij: Costo de asignar el trabajo j al trabajador i en tiempo extra.
La legislación colombiana define el valor para la hora extra de la siguiente forma :
Valor hora extra diurna = Valor hora regular x (1,25)
Valor hora extra nocturna = Valor hora regular x (1,75)
De tal forma que, para efectos de la aplicación general del modelo, ya que no se
conoce si las horas extras serán diurnas o nocturnas, se toma el porcentaje de
incremento promedio de los establecidos por la ley. (50%)
NCl : Número total de camas del bloque l.
h : Horas laborables por día.
d : Días laborables por semana.
δαλ ijjij*
*=
λ* ijiij CC =
5.1**
CC ijij=
77
D : Disponibilidad de los trabajadores en tiempo regular, durante el horizonte de
planeación.
D = h * d
Ai es la cantidad de horas asignadas a un trabajador durante el período de
planeación. Esta dada por la sumatoria sobre los bloques l, las camas k y los
trabajos j del producto entre las camas asignadas al trabajador por el tiempo que
se tarda el trabajador en realizar cada uno de los trabajos sobre dichas camas.
Yi es la variable binaria que determina si el costo del tiempo extra se activa en la
función objetivo o no. De tal forma que si la asignación es menor a la
disponibilidad en tiempo regular esta variable es 0 y no se activa en la función
objetivo. Si la asignación es mayor entonces el valor que toma es 1 afectando el
valor de la función objetivo.
CTEi es el costo del tiempo extra en la asignación de un trabajador, el cual se
define como el producto entre el costo de una hora en tiempo extra para el
trabajador i (C*i), por la cantidad de horas extras asignadas a dicho trabajador
(Ai - D).
=contrario. caso en
trabajador al asignada es trabajo el requere que bloque del cama la si 1
0
ijlkxijkl
∑∑∑= = =
=p
l
NCl
k
n
jijijkli xA
1 1 1λ mi ,...,1=∀
miAY i,...,1=∀
>
= contrario. caso en 0
D si 1i
( )[ ]CDACTE iii
**−=
78
F y G son dos variables binarias definidas como 1 si el trabajador i es asignado a
una cama k y 0 en caso contrario. De tal forma que si el trabajador i se asigna
para realizar el trabajo j , el mismo trabajador i debe realizar los trabajos j+1, j+2,
j+3,...,h donde h son los trabajos que requiere la cama k durante el horizonte de
planeación.
Aplicación del Modelo:
La metodología de aplicación del modelo se presenta en la Figura 1, dicha
aplicación del modelo fue realizada utilizando el programa What´sBest, el cual es
un programa de LINDO System que trabaja sobre Excel. La razón por la cual se
realiza la aplicación sobre este programa se fundamenta en el hecho de facilitar la
utilización del modelo por parte del personal administrativo que labora en las
industrias floricultoras. Ya que puede utilizarse sobre Excel o Lotus 1,2,3 , los
cuales son programas comunes dentro de las organizaciones. Otra razón es la
posibilidad de utilizar Visual Basic a fin de facilitar la interface hombre - máquina,
generando una aplicación con ventanas que minimice el tiempo de programación y
facilite su uso constante.
===−== ∑ ∀−
=
plNClkmicontrariocasoennsin
jijklxF ,...,1_;,...,1_;,...,1;___0_;1_1
1
1
===−== ∑ ∀=
+plNClkmicontrariocasoennsi
n
jklijxG ,...,1_;,...,1_;,...,1;___0_;1_1
21
79
FIGURA 1
80
3. ASIGNACIÓN DE TURNOS A OPERADORES DE TELÉFONO EN LA
NUEVA COMPAÑÍA DE TELÉFONO BRUNSWICK 16
GARY M. THOMPSON desarrolló un procedimiento para asignar los turnos de
trabajo a operadores del teléfono en la Nueva Compañía de Teléfono de
Brunswick (NBT). NBT requería que todos los turnos fueran asignados a los
empleados, y se obligaba a satisfacer las preferencias de los empleados en
relación a los turnos y se debían cumplir teniendo en cuenta la antigüedad de cada
empleado.
El Jefe de la sección de servicios en la nueva Compañía de Teléfono Brunswick
enfrentó un problema de asignación de turnos a los operadores de teléfono, el
objetivo de la compañía era asegurar que todos los turnos se cubrirían, mientras
se satisfacía tanto como fuese posible las expectativas del empleado en relación
con los turnos de trabajo. Se caracterizó el problema de planificación de mano de
obra en cuatro pasos:
1. La demanda de cliente.
2. Convertir la demanda presupuestada en requisitos de empleados.
3. Desarrollar el horario del empleado.
4. Entregar la planificación en el menor tiempo posible.
16 GARY M. THOMPSON Assigning Telephone Operators to Shifts at New Bru nswick
Telephone Company Instute for Operations Research and the Management Sciences 4 July -
August 1997 (pp. 1-11).
81
El problema de la asignación de turnos:
Hay varias entradas al problema de asignación de turnos. Primero, las semanas
de planificación, los horarios identifican los turnos que se necesitarán satisfacer
de acuerdo con la demanda esperada del cliente, ellos usan un conjunto de turnos
básicos a los que se agregan turnos suplementarios si es preciso. Los turnos son
de 11 tipos, y cada tipo depende de las habilidades que se necesiten para
resolver cada situación que se pueda presentar. La segunda entrada es la
disponibilidad de los empleados. Los empleados reciben fines de semana libres de
forma alternada y los trabajadores también pueden pedir días específicos libres
durante la semana. Un horario típico tiene de 70 a 90 empleados que trabajan
aproximadamente 40 turnos diarios, en promedio.
La prioridad es asignar tantos turnos como sea posible. Una asignación completa
de turnos no siempre es posible, debido al número y características de los turnos y
el número, situación, y habilidades de los empleados disponibles, las restricciones
que están presentes aseguran que sólo se asignan empleados a turnos en los
cuales ellos están disponibles cuentan con las habilidades necesarias; otra es que
todos los empleados son asignados por lo menos a un turno en la semana; que un
empleado no puede asignarse a más de un turno por día.
La gerencia estaba insatisfecha debido a que el proceso que se tenía para la
asignación de turnos era manual, y por tal razón requería de demasiado tiempo,
ellos se apoyaban en una hojas de cálculo que les permitía pronosticar las
demandas y cuanto personal requerían; pero no solo la gerencia se preocupaba
por el problema sino que sus empleados estaban muy descontentos pues su
necesidades no estaban siendo satisfechas lo que ocasionaba inconvenientes con
los empleados. Como resultado de este descontento, NBT buscó la manera de
automatizar la herramienta que poseían, se pretendía llegar a un acercamiento
82
que permitiera la planificación de turnos de trabajo con las preferencias del
empleado.
Modelo:
El modelo matemático que describe el problema de asignación de turnos para
NBT, consiste en lo siguiente:
S = Conjunto de turnos.
E = Conjunto de empleados, teniendo en cuenta las reglas de antigüedad.
Ce = Las categorías de turnos en las cuales el empleado puede laborar.
De = días que el empleado e puede trabajar.
Variables de decisión (Binarias)
1, si empleado e se asigna al turno s
0, en caso contrario
1, si empleado e se asigna al número máximo de turnos
0, en caso contrario
1, si el turno s no es asignado
0, en caso contrario
=xes
=ye
=u s
83
Parámetros:
=y0
Número máximo de turnos para asignar al empleado e
=ves Asignarle al empleado e a cambiar el turno s.
=cs Categoría del turno s
=d s Día en el cual se asigna el turno s
Función objetivo:
La función objetivo es un conjunto de prioridades a cumplir. La primera prioridad
es minimizar el número de turnos no asignados. Las prioridades subsecuentes
especifican que las opciones de turno de los empleados serán satisfechas, si
posible, en orden de antigüedad.
{ }( )1
,
+
= ∑∑∑∈∈∈∈∈
eses DdcSseses
Eee
Ssso
cMinimizarZ xvPuP
Donde la PP ii +>1 (la prioridad para el componente i muchísimo mayor que la
prioridad para el componente i + 1).
84
Restricciones: Asigne todos los turnos
Por lo menos un turno a cada empleado
No asignar más turnos de los especificados por el empleado.
No más de un turno para cada empleado por día.
Cumplir con las reglas de antigüedad es decir asignar turnos primero a los
empleados que llevan más tiempo en la empresa.
{ }( )2 Ss 1
,
∈∀=+∑∈∈∈ eses DdcSs
ses
cux
{ }( )3 Ee 1
,
∑∈∈∈
∈∀≥eses DdcSs
es
cx
{ }( )4 Ee
,
∑∈∈∈
∈∀≤eses DdcSs
ees
cmx
{ }( )5 D i E,e 1
1,
e∑=∈∈
∈∈∀≤ses dcSses
cx
( ){ }
{ } ( )6 1 1 1,
1>∈∀−+≤∑
∈∈∈−
eEec eses DdcSs
eees ymx
{ }{ } ( )7
,
EeEec eses DdcSs
esee xym <∈∀≤ ∑∈∈∈
85
En práctica, es una cuestión simple para determinar el número de cambios que
cada empleado se asignará después de primero identificar el número total de
cambios ser asignado. Habrá un empleado, diga /, tal que todos los más mayores
empleados trabajarán su número deseado de cambios, todos que los menos
mayores empleados trabajarán un cambio, y empleado / testamento trabajo por lo
menos uno, pero ningún más de los cambios del mj. Así, constreñimiento (6) y (7)
puede reemplazarse con:
Restricciones que imponen la naturaleza binaria de las variables
Se hizo uso del algoritmo Simulated - Annealing el cual consiste en varias rutinas
que se usan interactivamente hasta que el tiempo disponible ha expirado. Cada
iteración empieza con INICIALICE. INICIALICE calcula el número de turnos para
los cuales cada empleado será asignado. Luego, ASIGNE les asigna turnos a los
empleados.
{ }{ }
( )8 ,
∑∈∈∈
<∈∀=eses DdcSs
ees
cjeEemx
{ }( )
{ }{ }
( )10 1
9
,
,
∑
∑
∈∈∈
∈∈∈
>∈∀=
=
eses
esjs
DdcSses
DdcSsjjs
cjeEe
c
x
mx
{ } Eexes∈∀= __1,0 ( )Ddcc eses
Ss ∈∈∈ , ( )11
{ } { }EeEeye
<∈∀= __1,0 ( )12
{ } Ssus∈∀= __1,0 ( )13
86
Esta asignación se hace en el orden de antigüedad del empleado y con una
selección del azar de turnos igualmente deseables, para que cada iteración de
SSAH rinda una solución final diferente típicamente. Cuando se asignan los
turnos, el conjunto de turnos no asignados se hará cada vez más pequeño.
Si, después de ASIGNE se han asignado tantos turnos como sea posible y hay
todavía alguno no asignados, MAKEFEAS intentar asignar los turnos restantes.
Después de MAKEFEAS, si la asignación es factible, es decir, todos los turnos se
asignan, MEJORE intentar encontrar una asignación mejorada, evalúa todos los
cambios de turnos de manera bidireccional entre todos los pares del empleado.
El Resultado: Dirección y empleados han expresado satisfacción con el algoritmo Simulated -
Annealing. De hecho, provocó un cambio inesperado en el proceso del especificar
las opciones de los empleados en cuanto al turno que prefieren, esto ha producido
un proceso del orden de turnos mucho más aerodinámico. Los empleados saben
que ellos apenas tienen que especificar sus características de turno deseadas, y el
algoritmo Simulated - Annealing asegurará que en esas asignaciones de turno
tendrán prioridad los empleados de más antigüedad.
87
4. SOLUCIÓN AL PROBLEMA DE ASIGNACIÓN DE HORARIOS U SANDO
GOMORY DUAL DEL PLANO CORTANTE. 17
En el personal que fija literatura, un horario es definido por un número de días de
trabajo, y los turnos diarios durante cada día de trabajo, para un horizonte de la
planificación de uno o más semanas. Por ejemplo, un horario para un empleado
jornada completa podría consistir en los siguientes cinco turnos:
Lunes: 8: 00 a.m a 4:00 p.m
Martes: 10:30 a.m a 6:30 p.m
Miércoles: 8:00 a.m a 4:00 p.m
Viernes 10:30 a.m a 6:30 p.m
Sábado 1:00 p.m a 9:00 p.m
El horario del personal presenta variaciones y puede asociarse con numerosos
tipos de objetivos y restricciones. Por ejemplo, algún horario que presenta
múltiples turnos, o solo un tipo de turno, con un día de descanso, en el horario en
que se presentan múltiples turnos se asume unos turnos predefinidos cada uno de
ellos con requisitos específicos de personal en el horizonte de planificación. El
objetivo es asignar empleados a los turnos de trabajo para minimizar el tamaño de
la fuerza obrera satisfaciendo los requisitos de los empleados, restricciones del
modelo en el horizonte de trabajo y restricciones de ampliación de la jornada de
trabajo y fin de semana, a parte de lo determinado en las políticas.
17 BRUSCO M. Solving personnel tour scheduling problemsusing the dual all-integer cutting plane
IIE Transactions (1998) 30, 835 – 844.
88
El problema es determinar el número de empleados que se asignan en cada
horario para satisfacer los requisitos de personal en cada periodo de la
planificación de la semana, mientras se minimiza los costos de personal o las
horas obreras totales fijadas.
Las variables de decisión representan el número de empleados asignados en cada
horario factible y el coeficiente de la función objetivo que corresponde a cada
variable representa el número de las horas obreras asignadas para cada
empleado. Para reducir el número total de horas obreras fijadas, puede ser
necesario aumentar la flexibilidad en los horarios. Esto puede lograrse de varias
formas, como por ejemplo aumentar el número de turnos diarios, aumentando el
número de puestos polifuncionales y permitiendo el uso de empleados en
jornadas incompletas.
Sin embargo, la flexibilidad de los horarios puede producir que se creen miles,
millones, o billones de variables de decisión. Para dar solución a este tipo de
problemas se han desarrollado muchos procedimientos de solución heurísticos. El
propósito de este estudio es evaluar la efectividad de Gomory dual, plano cortante
para resolver los horarios de planificación de la mano de obra.
Modelo de asignación de personal:
El modelo de este estudio se presenta como sigue:
xc jTj
jMinimizarZ ∑
∈
= ( )1Mi ≤≤∀ 1_rxa ij
Tjij
≥∑∈
( )2
0≥x j ( )3Tj∈∀ _
89
Donde los parámetros del modelo son:
=M Número de periodos en el horizonte de la planificación semanal Mi ,...,1=
=T Turnos factibles Tj∈
=c j Número de horas asignadas a un empleado en un turno j.
=r i Número de empleados para el periodo i.
= contrario. caso en 0
j horario el en está i periodo el si 1aij
Variables de decisión:
{ } j horairo el para asignados empleados de Número=x j
Algunos investigadores han considerado en el problema de asignación la fuerza
obrera de tiempo completo y otros estudios se han enfocado en problemas en los
cuales el periodo de planificación se divide se divide en un conjunto de horarios
de tiempo parcial. En estos casos, una restricción adicional que limita el número
total de empleados de tiempo parcial se presenta como sigue:
El problema de asignación y planeación de horarios se representó en la forma de
un cuadro de Beale, y se resolvió usando Gomory dual del plano cortante. El
cuadro de Beale es una alternativa al cuadro del simplex normal y se usa a
menudo para programar algoritmos cuya solución deben ser enteros.
( )4( ) 01 ≥−− ∑∑∈∈ pf Tk
kTj
j xx ππ
90
El cuadro de Beale inicial para cada problema de la prueba era asociado a un
vector de la solución nula, es decir, Tj Xj ∈∀== 0x j , para ilustrar este cuadro,
es útil definir a N como el número total de horarios, entonces ( )NN pf
como el
número total de turnos completos y turnos parciales. Con estas definiciones, el
cuadro de Beale inicial se presenta en la figura 2:
FIGURA 2
La primera fila (fila 0) del cuadro de Beale corresponde a la función objetivo,
considerando que las filas restantes corresponden a todas las variables básicas y
no básicas. La solución valora las variables que se encuentran en la columna 0 del
cuadro y en las columnas restantes y las variables no básicas. A cada iteración,
una fila de la fuente se selecciona para generar un corte. El corte se añade y el
cuadro se pone al día. Este proceso se continua hasta que la solución factible, es
decir no hay negativos en ninguna columna y en este momento la solución óptima
se ha identificado.
91
5. OPERACIÓN DE UN RESTAURANTE DE COMIDA RÁPIDA 18
Muchos negocios pequeños enfrentan el problema de planificación de empleados
obedeciendo de las habilidades que se necesiten para realizar el trabajo y por
supuesto dependiendo de la disponibilidad de tiempo de trabajo y preferencias
para satisfacer los requisitos de la mano de obra, que fluctúan de hora a hora y día
a día. Un dueño y operador de algunos restaurantes de comida rápida reemplazó
el tiempo consumido en una tarea improductiva por un sistema que regularizó el
proceso de planificación de sus restaurantes, y teniendo como resultado horarios
de más alta calidad.
En 1984 Al Boxley, un dueño muy progresivo y operador de cuatro restaurantes de
McDonald en el Cumberland, área de Maryland, enfrentó un problema operacional
todas las semanas el gerente en cada restaurante estaba gastando más de ocho
horas para preparar los programas de trabajo del empleado. Esta rutina por
semana involucró las ventas presupuestadas por hora; traduciendo estas ventas a
los requisitos del personal de cada hora en la parrilla.
Este esfuerzo de planificación era tiempo esencialmente improductivo que podría
usarse realizando deberes de supervisión para asegurar el funcionamiento de los
restaurantes. Boxley había comprado a una computadora personal en 1983 y con
la ayuda de Hoey las nóminas de sus restaurantes y varias funciones de
contabilidad de oficina centrales se habían automatizado.
18 LOVE R. HOEY J. Management Science Improves Fast – Food Operations. The Institute of
Management Sciences. 2 March - April 1990 (pp. 21-29.
92
Era necesario solucionar cuatro tareas primarias: (1) determinar el modelo
matemático y técnica de la solución que resolvieran los horarios de trabajo para
150 empleados en un tiempo considerable. (2) minimizar la inversión en hardware
para construir los métodos de solución para los horarios, (3) hacer que el sistema
de planificación fuera bastante simple y que pudiese ser usado por gerentes que
no tuviesen experiencia en computadores. (4) reducir el tiempo de preparación de
horarios al menos en un 75%.
Los turnos de trabajo en establecimientos de comida rápida normalmente varían
de tres a ocho horas, y un objetivo de planificación es determinar demandas para
cada turno y para cada clase de habilidad que satisfaga los requisitos de mano de
obra. Los trabajos de comida rápida tienen muchos empleados de tiempo parcial,
y la preocupación primaria es nivelar las habilidades del empleado y
disponibilidades de tiempo de trabajo.
Primero encontraron un modelo matemático y una técnica de solución para
proporcionar un horario factible para el empleado. El plan de trabajo era usar la
oficina central con un sistema en el disco duro para procesar los horarios para los
restaurantes. Se consideraron varios aspectos en el problema de planificación de
la mano de obra.
1. Los requisitos del empleado en cada área de trabajo varían dramáticamente
durante el día porque los volúmenes de las ventas fluctúan. Para los
restaurantes de McDonald, los requisitos en la parrilla y las áreas de trabajo
de varían de una persona a otra durante tiempos. Estos requisitos deben
satisfacerse para asegurar un servicio adecuado al cliente; sin embargo, la
proporción del costo entre mano de obra y ventas es crítica debido a que la
rentabilidad se da en volúmenes alto de venta pero en márgenes de baja
ganancia.
93
2. Los restaurantes de comida rápida no tienen turnos de trabajo normales o
semanas de trabajo. Los turnos varían típicamente de tres a ocho horas; la
longitud de cambio de máximo es restringida a menudo por ley para los
empleados más jóvenes. Los Gerentes frecuentemente establecen un
conjunto de turnos que ellos consideran deseables basados en la moral del
empleado, la fatiga, y otros factores. Algunos empleados pueden especificar
el número de días por semana que les gustaría trabajar.
3. Los empleados difieren por las veces en que ellos están disponibles para
trabajar o sus preferencias de trabajo, por ejemplo, por actividades
familiares o los horarios escolares. Los Gerentes deben construir horarios
que se adhieren a estas disponibilidades; y se mejora la moral de los
empleados si se consideran sus preferencias del trabajo.
4. Las habilidades de los empleados y niveles de actuación para las varias
áreas de trabajo son diferentes.
Si un restaurante típico tiene tres áreas de trabajo, 150 empleados, y 30 turnos de
trabajo, formular el problema de planificación da como resultado 100,000 variables
enteras y 3,000 restricciones. La solución de semejante problema lineal entero en
15 minutos está ciertamente más allá de la capacidad de la computadora personal.
Se descompuso el problema lineal entero en dos redes de flujo subalternas. Se
diseñó una red de flujo subalterna para generar horarios de los empleados que
encuentren el criterio siguiente:
1. Satisfaga los requisitos del personal cada hora con un mínimo de fijó horas.
2. Dar el mismo número de días laborables y horas de trabajo, con días laborables
marginales dados a los empleados con evaluaciones de habilidades en cada
empleado.
94
3. Asignar a los empleados a trabajar en áreas en donde se desempeñen mejor.
Un análisis de optimalidad se realizó para investigar entre la solución óptima
alternante para mejorar el horario del empleado propuesto con respecto a las
condiciones siguientes:
1. El horario para cada empleado debe ser aproximadamente el mismo en cada
uno de sus días laborables.
2. Proporcionar una media habilidad adecuada que este durante cada medio
periodo de tiempo de hora en cada área de trabajo.
Incluso con la descomposición, uno de los problemas subalternos de la red podría
tener aproximadamente 100,000 arcos y 2,000 nodos. Se desarrolló algoritmos de
flujo de red personalizados que usan el método original dual reforzados con una
lista que procesa las técnicas y el embalaje extenso de costo y se marcó la
información de la solución.
El menú del administrador le permite al usuario acceder a cuatro menús
subalternos para poner al día la información de entrada, generar o modificar el
horario del empleado. El usuario puede seleccionar la transacción específica a ser
procesada del submenu apropiado.
Se debía minimizar la cantidad de datos entrada para cada semana, los datos de
ventas para cada hora constituían 1,008 elementos representados en tres áreas
de trabajo para siete días a la semana y 48 intervalos de tiempo por día, para 24
actividades por hora, los restaurantes de McDonald estaban abiertos
aproximadamente 18 horas por día (6:00 a.m a 12:00 p.m), la disponibilidad del
empleado podría ser de 336 elementos (siete días x 48 intervalos de tiempo por
día) para cada empleado.
95
Para resolver el problema de entrada de datos de ventas, se le permitió a los
usuarios entrar las cantidades de ventas diarias y tener la distribución de ventas
de la semana anterior. Una vez el gerente estaba satisfecho con las proyecciones
de las ventas, la computadora utilizó la interface y definió tablas de conversión de
ventas para calcular el número de empleados necesitados durante cada media
hora en el restaurante en cada área de trabajo.
Durante una semana dada, el gerente tenía sólo que entrar los datos para los
empleados cuya disponibilidad había cambiado de la semana anterior. Quizás el
aspecto más importante de la interface del usuario es la colección de informes que
el sistema genera. La forma preferida para los horarios era el informe del horario
diario que mostraba en forma de barra, durante cada día el área de trabajo y
tiempo que cada empleado había sido programado para trabajar. Finalmente, el
sistema tenía que producir horarios que requirieran un ajuste manual muy
pequeño.
El beneficio más claro era el tiempo ahorrado al eliminar la tarea tediosa de
preparar los horarios semanal de los empleados. Los gerentes del restaurante
informaron una reducción del 80% al 90% de tiempo para la generación de
horarios. Otro beneficio era la reducción en el costo directo de mano de obra,
reduciendo el exceso de empleados asignados en el horizonte de planeación. La
eficacia del empleado y la moral de los mismos mejoraron subsecuentemente
debido a que se tienen en cuenta las preferencias de los trabajadores en los
turnos en los cuales ello pueden y desean trabajar.
96
Modelo: La formulación matemática del problema usa la anotación siguiente:
El modelo de asignación de personal puede escribirse como un problema lineal
entero:
., lhbhl área el en periodo el en trabajar para requeridos empleados de Número =
.,, lkjx jkl área el en periodo el en turno al asignados empleados de Número =
=contrario. caso en
día el en , turno del parte hace , periodo el si 1
0
kjhahjk
=contrario. caso en
día el trabaja , empleado el si 1 0
.kiyik
= contrario. caso en
trabajo de área el en y día el en , turno al asignado es empleado el si 1 0
., lkjiwijkl
.,, lkjr jkl área el en día el turno el en empleados de Escaces =
., lhshl área el en periodo el en laborando empleados de Exceso =
.izi empleado el trabaja que días de Número =
=contrario. caso en
semana la a mínimo como trabaja , empleado el si 1 0
.kivik
( )1 vdrgwcf ikik
ikjkljkl
jklijklijkl
ijklhl
hlZMinimizar ∑∑∑∑ +++=
97
d ik
fhl
cijkl
d ik
Sujeto a:
n la función objetivo, el se selecciona lo suficientemente grande para
minimizar así el exceso de horas asignadas. refleja el grado de
habilidad del empleado i en el área de trabajo j, así como su disponibilidad y
preferencia para trabajar en el turno j, en el día k, y se utiliza para
nivelar los días laborables entre los empleados y considerar casos especiales
donde los empleados solo pueden trabajar un número específico de días. La
ecuación (2) representa la requisición de empleados, la ecuación (3) considera la
asignación de empleados a los turnos.
La restricción (4) asegura que un empleado trabaja como mínimo un turno al día
en cualquier día de la semana, y las ecuaciones (5) y (6) junto con el
parámetro controla el número de días trabajados a la semana para cada
empleado.
( )
( )
( )
( )
( )
( )( )8
7
6
5
4
3
2
ki
ki
i
i
ki
lkj
lh
vy
zv
zy
yw
xrw
bsxa
ik
ik
ik
ik
ik
ik
ikjl
ijkl
jkljkli
ijkl
hlhljkljk
hjk
,1
,1
0
0
,0
,,0
,
∀≤
∀≤
∀=−
∀=−
∀=−
∀=−+
∀=−
∑
∑
∑
∑
∑
98
La técnica de la solución descompone el problema (1) - (8) en dos problemas
subalternos dado por:
Sujeto a la ecuación (2). Desde la ecuación (2) se exhibe la característica de la
adyacencia del bloque, es decir, todas las entradas distintas a cero en cualquier
columna son consecutivas, los subproblemas pueden resolverse como una red de
flujo del costo mínimo del problema. El primer subproblema determina los
requisitos de turnos para los empleados, para satisfacer las necesidades de
empleados y minimizar el exceso de horas programadas. El segundo subproblema
es minimizar el resto de función objetiva (1), eso es desde (1) hasta (9), sujeto a
las ecuaciones (3) a la (8). Desde cada columna en las ecuaciones (3) a la (6) se
tiene a lo más dos entradas distintas a cero y estas ecuaciones se pueden
construir tales que cada columna con dos entradas distintas a cero tiene +1 y -1,
este segundo subproblema se pueden solucionar también como un problema de
red de flujo de costo mínimo. Y el segundo subproblema determina la asignación
de empleados a los turnos requeridos desde el primer subproblema.
( )9 sf hlhl
hl∑
99
6. ASIGNACIÓN MULTICRITERIO DE TAREAS A TRABAJADORE S
POLIVALENTES 19
La Asignación de Tareas (AT) es un elemento más de la Organización del Tiempo
de Trabajo (OTT), se parte de un conocimiento previo de la cantidad de personal
disponible y de la demanda de las tareas y se quiere satisfacer, de forma óptima,
la demanda, utilizando el personal del que se dispone y siguiendo ciertas pautas
de comportamiento. Estas pautas surgen por razones económicas, ergonómicas,
de calidad, prioridad de las organizaciones, preferencias del personal, aspectos
sociales, disposiciones legales, sistemas de trabajo, etc. Por ejemplo, dichas
pautas pueden definir el tiempo que el personal ha de pasar de forma continua en
una tarea, el tiempo requerido que se debe dedicar a realizar una tarea para llegar
al nivel de entrenamiento adecuado, entre otros muchos más aspectos que son
considerados al llevar acabo la AT.
Se basa en un análisis exhaustivo de la problemática de la asignación de tareas,
en la que se hace una clasificación general de los tipos de problemas que pueden
suscitarse, esto acorde a una ordenación de las características que se presentan
en este campo y la diversidad de criterios de evaluación que han de ser
considerados. Enfatizar, que se presenta un modelo que permite abordar una
amplia gama de problemas y además permite resolverlos de forma efectiva
utilizando PLEM, mediante una evaluación multicriterio (criterios priorizados).
19 ZULEMA E. Asignación Multicriterio De Tareas A Trabajadores Polivalentes. Instituto de
Organización y Control de Sistemas Industriales. Universidad Politécnica De Cataluña. Mayo de
2006
100
Asignación de tareas: Este apartado se enfoca a la presentación de la información existente sobre la
tercera fase de la OTT y la cual es el centro de interés de la presente
investigación. Aquí se describe a fondo el tema y se presentan los antecedentes
más relevantes encontrados en la literatura existente sobre asignación de tareas.
El método para asignar las tareas según depende si las tareas son movibles, si
existen descansos intermedios en los turnos de trabajo, si el personal extra está
permitido, considerar también si ciertas tareas requieren de habilidades
específicas.
La asignación del personal se debe realizar tomando en cuenta el ambiente en
que se encuentra inmerso, y por lo tanto la persona responsable de realizarla debe
tener en cuenta, además del ambiente, por supuesto el personal del que dispone
para satisfacer la demanda y sus características, para aprovechar al máximo de la
capacidad de personal que dispone. El desarrollar esta actividad de forma manual
requiere invertir mucho tiempo y esfuerzo.
La asignación de personal se realiza de forma manual y además basada en
prueba y error, lo que consume tiempo y no es muy viable cuando la asignación ha
de ser realizada en un tiempo corto o bien cuando se tiene que hacer la
reasignación porque se presentan sucesos imprevistos.
Un problema de asignación es definido como: dadas n tareas y m recursos, el
problema es determinar una asignación de cada tarea a un recurso, optimizando
una función objetivo y satisfaciendo las restricciones adicionales. Para el enfoque
del problema de asignación que aquí se presenta, el recurso hace referencia al
personal disponible en cada uno de los intervalos.
101
Modelado del problema: El modelado se presenta mediante programación matemática, específicamente
haciendo uso de la programación lineal entera mixta (mixed integer linear
programming). La identificación del modelo se inicia con la sigla que hace
referencia al tipo de asignación que le corresponde, es decir, si es de tipo de
asignación “B” (la problemática corresponde a una asignación para un conjunto de
intervalos determinados, donde no se tiene un historial previo de asignación), una
segunda letra que identifica a el modelo, es la que hace referencia si las
características del personal involucrado en el problema se presentan de forma
individual “P”
Variables − Las variables asociadas al trabajo que está realizando cada una de las
personas.
− Las relacionadas directamente con la cobertura de la demanda de las tareas.
Variables asociadas al personal: Una primera variable básica y a partir de la cual se definen otras variables es:
(1) Xpth Variable binaria que toma valor de 1 si la persona p ( ∀ p) ha sido
asignada a tarea t (∀ t) en el intervalo h ( ∀ h), y 0 en caso contrario.
{0,1}.
(2) N = [nt] Vector que indica la naturaleza de la tarea, es decir el nivel de
capacidad necesaria para realizar la tarea t ( ∀ t). Los valores que puede
tomar están comprendidos entre 0 a 1, donde 1 representa que se
requiriere de toda la capacidad de personal para desarrollar la tarea t si
esta es asignada. Se puede determinar el valor de la variable siguiente:
102
(3) XIph Indica la carga de trabajo equivalente asignada a cada persona p
(∀ p) en cada intervalo de tiempo h ( ∀ h), y se calcula
∀ p; ∀ h y puede tomar valores [0,1]
(4) PS = [psph] Matriz binaria que indica si la persona p (∀ p) está presente
o ausente en cada intervalo h ( ∀ h).
El conocer la presencia del personal a lo largo del horizonte de asignación nos
permite definir la siguiente variable de proporción, que puede tomar un valor
comprendido entre [0,1] y es:
(5) XITpt Valor de porción de tiempo dedicado por la persona p (∀ p) a la
tarea t ( ∀ t) en el horizonte H.
Se calculan otras variables a partir de las calculadas anteriormente.
(6) Mpth Variable auxiliar binaria {0,1}, que adopta valor de 1 si la persona p
ha empezado a realizar la tarea t ( ∀ t) en el intervalo h ( ∀ h) y 0 en caso
contrario.
nXXI t
T
tphph*
1
∑=
=
PpsP
pph
≤∑=1
tpH
hph
H
hpth
pt
PS
XXIT ∀∀
=
∑
∑
=
= ;;
1
1
103
rXX ptPp
pthth*
1
´
∑=∈∀
=
Variables asociadas a la cobertura de demanda de la s tareas
Definidas las variables de asignación del personal p en cada uno de los intervalos
h en que está presente (Xpth) se describen a continuación las variables, que se
refieren a los requerimientos de las tareas.
Lo más necesario es determinar como se cubren las necesidades de las tareas:
(7) R = [rpt] Matriz que indica las tareas ( ∀ t) que puede realizar cada
persona.
(8) X´th Nos indica la cantidad total de personal equivalente asignado a
realizar la tarea t ( ∀ t) en el instante h ( ∀ h) y puede tomar un valor [0, P]
y se determina con la ecuación:
(9) D = [dth] Matriz de capacidad necesaria para la tarea t (∀ t) en el
intervalo h (∀ h).
(10) D` = [d`th] Matriz de demanda de capacidad equivalente necesario en la
tarea t (∀ t) en el intervalo h ( ∀ h). el cual es definido en base a la
cantidad de personal necesario en la tarea t y la naturaleza de dicha
tarea.
d`th = dth * nr
(11) d+th , d-
th Exceso y escacez de capacidad asignada a la tarea t en el
intervalo h.
104
Datos Adicionales
(12) M = [mp] Vector binario que indica la polivalencia del personal p ( ∀ p).
donde tomar un valor de 1 para el caso en que el personal es compatible
para asignarle más de una tarea a la vez y de 0 en el caso contrario.
(13) SD = [sdt] Vector de porcentaje que indica el nivel de escacez de
personal permitido en la tarea t ( ∀ t).
sd`t = sdt * d
´th ∀ t; ∀ h
(14) SE = [set] Vector de porcentaje que indica el nivel de escacez de
personal permitido en la tarea t ( ∀ t). [0, 1]
(15) SE´ = [se´t] Vector de porcentaje que indica el nivel de escacez de
personal permitido en la tarea t ( ∀ t). se`t = set * d
´th ∀ t; ∀ h
(16) IT = [itct] Matriz de proporción ideal de tiempo de dedicaciòn a lo largo
del horizonte de asignación de cada tarea t ( ∀ t) para la persona p (∀ p).
11
=∑=
T
tptit
(17) TOL Tolerancia general permitida para alejarse de la proporción ideal de
intervalos de dedicación a cada tarea t (∀ t). Esta tolerancia no depende
de las tareas. [0, 1]
105
(18) ITmin = [ ]it ptmin
Matriz de proporción mínima de tiempo que una persona p
ha de dedicar a una tarea t a lo largo del horizonte de asignación.
( ) [ ]1,0__;_;1*min
valorcontptolitit ptpt∀∀−=
(18) ITmax = [ ]it ptmax
Matriz de proporción máxima de tiempo que una persona p
ha de dedicar a una tarea t a lo largo del horizonte de asignación.
( ) [ ]1,0__;_;1*max
valorcontptolitit ptpt∀∀+=
(19) PT = [ptt] Vector que indica la prioridad de satisfacción de la tarea t
(∀ t). Es decir cuando no se tienen la capacidad de satisfacer la
demanda de todas las tareas, indica cual de ellas ha de ser cubierta
primero, o bien a cual se recomienda asignar más personal.
11
=∑=
T
tt
pt
(20) CP = [cpp] Vector que indica la prioridad de cada persona p (∀ p)
respecto al conjunto del personal P. [0, 1]
(21) XIT pt
+ Valor de la proporción del tiempo, que la persona p dedica por
encima de la proporción del tiempo ideal de dedicación a la tarea t.
( )1,0___;;_; valorsuocomprendidhtpXITXITitXIT ptptptpt∀∀∀−=− −+
106
(22) XIT pt
− Valor de la proporción del tiempo, que la persona p dedica por
debajo de la proporción del tiempo ideal de dedicación a la tarea t.
( )1,0___;;_; valorsuocomprendidhtpXITXITitXIT ptptptpt∀∀∀−=− −+
(23) PP = [pppt] Matriz de preferencia que indica la proporción de tiempo que
la persona p ( ∀ p) desearía trabajar en cada tarea t ( ∀ t).
11
=∑=
T
tpt
pp
Restricciones:
(1) hpXI ph∀∀≤ ;_;1 Restricción que limita que la cantidad de trabajo
asignado a una persona en un intervalo de tiempo, no sobrepase la
cantidad máxima que pueda realizar.
(2) hpPSX ph
T
tpth
∀∀≥∑=
;_;1
Restricción a utilizar, si se desea asegurar que al
menos se asigne una tarea al personal p presente en el intervalo h.
(3) ( )[ ] htsedX tthth∀∀≤ + ;_;1
´´ Restricción que controla que la cantidad de
capacidad, asignada a cada tarea, sea inferior a un cierto valor límite.
107
(4) ( )[ ] htsddX tthth∀∀≥ + ;_;1
´´ Restricción que controla que la cantidad de
capacidad, asignada a cada tarea, sea superior a un cierto valor límite.
(5) tpitXITit ptptpt∀∀≤≤ ;_;
maxminRestricciones que limita que la proporción de
tiempo dedicado a cada tarea esté dentro del rango de proporción de
tiempo permitido.
(6) htdX th
P
ppth
∀∀=∑=
;_;´
1
´ Restricción que garantiza que la asignación de
personal a la tarea t en el intervalo h satisfaga exactamente su demanda.
(7) ( ) htpXITitX pthptpth∀∀∀−+≤ ;;_;1 Esta restricción garantiza que no se
asigne la persona p a la tarea t cuando ya se llegó al número de intervalos
para lograr la proporción ideal de intervalos que se debe realizar cada una
de las tareas a lo largo del horizonte.
Funciones Objetivo:
(1) [ ]∑∑= =
−=H
h
T
ttht dptMINZ
1 1
* Función que busca la solución óptima que minimice la
ponderación de la insatisfacción de las tareas, de acuerdo a una prioridad de
satisfacción previamente establecida.
(2) [ ]∑∑= =
−+ +=P
p
T
tptpt XITXITMINZ
1 1
Función que busca la solución óptima basada
en la mínima discrepancia entre el porcentaje de intervalos en que una persona
realiza una tarea a lo largo del horizonte de planificación y el porcentaje de
tiempo ideal que ha de realizar dicha tarea en el horizonte de planificación.
108
(3) ( ) ( )XITr pt
P
p
T
tpt
MAXZ *1 1
∑∑= =
= Función que busca la solución óptima basada en
la máxima utilización del personal en la tarea para la que tenga el mejor
rendimiento.
(4) [ ]∑∑= =
−+ +=T
t
H
hthth ddMINZ
1 1
Función que busca la solución óptima basada en la
mínima discrepancia entre capacidad asignada y la necesidad en cada tarea.
(5) XITpp pt
P
p
T
tpt
MAXZ *1 1
∑∑= =
= Función que busca la solución óptima que
maximice la preferencia del personal en la ejecución de las tareas.
Existe una gran diversidad de características en el problema de asignación de
tareas, el modelo planteado anteriormente incluye sólo algunas de ellas. Pero se
aclara que el modelo presentado es flexible permitiendo así ser adaptado
conforme las necesidades de la organización.
109
PLANTEAMIENTO DEL MODELO MATEMÁTICO
Después de conocer como se ha dado solución a la asignación de personal en
otras organizaciones y adicionalmente qué métodos han sido utilizados para tal
fin, en esta sección se detallará el problema de asignación de personal y para su
planteamiento es indispensable tener un conocimiento previo de las necesidades
que se presentan a lo largo del horizonte de planeación. La determinación de las
necesidades se hace a partir de la demanda que se presenta en el periodo de
servicio y atención a los clientes, la cual es convertida en requisiciones de mano
de obra, para cada cargo según el comportamiento de la misma. Se dice que de
demanda es determinista ya que se realiza un pronóstico de ventas teniendo en
cuenta los registros de periodos pasados.
El objetivo es resolver el problema de asignación de personal para un restaurante
de la Compañía Frisby S.A. para un horizonte de tiempo determinado a semanas
el cual a su vez se divide en días, los días se dividen en intervalos de tiempo de
una hora, donde para cada uno de ellos se tiene un conocimiento preliminar de la
demanda del restaurante, por lo que el problema consiste en determinar conforme
a los criterios de valoración el cargo al que se ha de dedicar el personal presente
en cada uno de los intervalos de tiempo que forman el horizonte de asignación. Se
define también la Función Objetivo, en donde se pretende se minimice el costo de
mano de obra.
El modelo se construye haciendo uso de la programación lineal entera mixta y
teniendo en cuenta los aspectos que se han considerado dominan el problema de
asignación de personal.
110
Se plantearán las restricciones básicas y la Función Objetivo. Para dar inicio con
el modelo se especifica primero unos supuestos básicos y se da una información
general para conocer detalladamente la situación en la que se encuentra el
Restaurante sobre el cual se procederá a plantear el modelo matemático.
Generalidades
La Compañía Frisby S.A., tiene 100 Restaurantes aproximadamente a Nivel
Nacional los cuales se han dividido por categorías de acuerdo a las ventas, los
restaurantes se clasifican por la ubicación y diseño que presente y por el tipo de
servicio prestado, es decir, si son tipo calle o tipo ventana y si es servicio a la
mesa, semiautoservicio y autoservicio.
A continuación se explicará algunos conceptos básicos para entender con más
claridad cada tipo de clasificación.
TIPO DE RESTAURANTE:
Tipo Calle: Restaurantes que tienen salón y algunos pueden tener parque
infantil y salón especial para fiestas.
Tipo Ventana: Son los restaurantes que se encuentran ubicados en los
centros comerciales y almacenes de cadena como Éxito y
Carrefour.
Tipo Parque: Restaurantes que se encuentran en Parques Temáticos como
por ejemplo Panaca y el Parque del Café.
111
CLASIFICACIÓN POR TIPO DE SERVICIO:
Servicio a la mesa: Cuando el cliente llega al restaurante y es atendido por un
vendedor de salón el cual toma el pedido en la mesa, una vez
anotado el pedido se dirige al cajero y dicta el pedido, luego de
procesado el pedido el vendedor de salón lo lleva a la mesa en
donde lo recibe el cliente.
Semiautoservicio: El cliente llega al restaurante y se dirige al cajero en donde
éste toma el pedido. Después de facturado el pedido el cliente
cancela la cuenta y se sienta en una mesa a esperar que un
auxiliar de salón llegue con el pedido facturado.
Autoservicio: El cliente llega al restaurante y se dirige al cajero para que
éste tome el pedido, una vez facturado el cliente cancela la
cuenta y se sienta a esperar que lo llamen para reclamar el
pedido.
En el Sistema de Descripción de cargos, la empresa ha definido todos los cargos
para restaurantes, se aclara que no todos los cargos se asignan a los
restaurantes, esto depende del tipo de servicio que preste el restaurante. A
continuación se describe cada cargo20:
20 Sistema de Descripción de Cargos para Restaurantes de FRISBY S.A. Área de Gestión
Humana.
112
Auxiliar de Producción: Este cargo tiene dependencia directa del
Administrador. Sus responsabilidades principales
son: preparar, organizar y asear el área de
producción limpiando y desinfectando
oportunamente los materiales y equipos. Mezclar,
apanar y freír el pollo y preparar los demás
productos conforme a las condiciones de
operación establecidas. Verificar el color del
aceite revisando cada una de las máquinas que
tiene a su disposición. Hacer el filtrado y lavado
de las máquinas fritadoras.
Despacho Combos: Este cargo tiene dependencia directa del
Administrador. Sus responsabilidades principales
son: preparar y empacar los combos a llevar, a la
mesa y a domicilio. Verificar la rotación y calidad
de las materias primas, revisando las fechas de
vencimiento y rotulando las materias primas de
acuerdo a las especificaciones establecidas.
Abastecer el área de mostrador de materias
primas y suministros organizando, empacando y
rotulando las mismas. Organizar y asear el área
de combos, limpiando y desinfectando
oportunamente los materiales, materias primas y
equipos.
113
Despacho: Este cargo tiene dependencia directa del
Administrador. Sus responsabilidades son:
preparar, organizar y asear el área de despacho,
despachar los productos a llevar, a la mesa y
domicilio, empacando los mismos de acuerdo a
las estructuras establecidas y entregándolos al
cliente, vendedor de salón, auxiliar de salón,
cliente o domicilio.
Cajero: Este cargo tiene dependencia directa del
Administrador. Sus responsabilidades son:
operar la caja registrando la venta, recibiendo el
pago y entregar la factura al cliente.
Vendedor de Salón: Este cargo tiene dependencia directa del
Administrador. Sus responsabilidades principales
son: atender las solicitudes del cliente, ofrecer los
productos, tomar el pedido al cliente, llevar
pedido al cajero, llevar el pedido hasta la mesa y
entregar la factura. Realizar inventario de los
suministros del área de salón.
114
Auxiliar de Salón: Este cargo tiene dependencia directa del
Administrador. Sus responsabilidades principales
son: preparar, organizar y asear el área de salón
limpiando y desinfectando oportunamente mesas
y piso. Abastecer el área de mostrador de las
materias primas y suministros organizando,
empacando y rotulando las mismas. Entregar el
producto en la mesa al cliente, revisando la
factura y permaneciendo atento a las
necesidades del mismo.
Oficios Varios: Este cargo tiene dependencia directa del
Administrador. Sus responsabilidades principales
son: limpiar los baños, los pisos, la planta
eléctrica, los cuartos fríos, los salones, y las
áreas asignadas por el jefe inmediato,
organizando, limpiando y desinfectando los
mismos.
Enrutador de Domicilios: Este cargo tiene dependencia directa del
Administrador. Sus responsabilidades principales
son: asignar a los domicilios la ruta de pedidos
de acuerdo a las direcciones, registrar los
mismos en el sistema y verificar cantidades,
presentación y calidad de los productos antes del
envío al cliente. Preparar y empacar los
productos pedidos a domicilio. Llevar el control
del dinero de las ventas a domicilio, registrando
la venta en el sistema entregando al
administrador.
115
Coordinador de Domicilios: Este cargo tiene dependencia directa del
Administrador. Se desempeña atendiendo
telefónicamente las solicitudes del cliente
registrando el pedido en el sistema y entregando
la factura al despachador. Supervisa las labores
de los domicilios, coordina el recorrido
considerando las direcciones y verifica el tiempo
de entrega del servicio.
Domicilios: Este cargo tiene dependencia directa del
Administrador. Sus responsabilidades principales
son: distribuir los pedidos a domicilio de acuerdo
a la ruta asignada anotando los tiempos de salida
y llegada, entregando el producto al cliente, la
factura y el cambio cuando se requiera.
Administrador: Este cargo tiene dependencia directa con el Jefe
de Zona. Sus responsabilidades principales son:
dirigir la venta del producto y servicio en el punto
de venta mediante la programación de personal.
Analizar las ventas diarias compararlas con las
presupuestadas. Analizar la reposición de
materias primas y suministros, verificando los
inventarios, las ventas, los presupuestos de
ventas y haciendo el pedido respectivo. Solicitar
la dotación de personal. Controlar el dinero en la
caja registradora.
116
Supernumerario: Este cargo tiene dependencia directa del
Administrador. Cada restaurante cuenta con su
supernumerario, el cual es asignado entre
semana para cubrir los descansos de todos los
empleados del restaurante y los fines de semana
a reforzar el los cargos que se presente más
actividad. No cubre los descansos de cajero ni
administrador, debido a que son cargos de más
especialización y para ello se cuenta con una
planta de cajeros y administradores
supernumerarios.
La compañía Frisby S.A., flexibiliza los contratos de trabajo de manera tal que
puedan satisfacer las necesidades que se presentan en la empresa, pero sin dejar
de lado la Legislación Laboral. De acuerdo con lo anterior Frisby S.A., maneja 2
tipos de contratación, el primero es el de tiempo completo en donde se puede
laborar como mínimo 8 Horas diarias, 48 horas semanales y 206 horas al mes,
este tipo de trabajador hace parte de la nómina operativa; el segundo tipo de
contrato es de tiempo variable y surge de la necesidad que tiene la empresa para
cumplir con el aforo propuesto, evitar la generación de horas extras y de la
necesidad de reforzar algunos cargos en horas pico algunos días de la semana,
con este tipo de contrato se debe cumplir con trabajar como mínimo 3 horas
diarias y máximo 6 horas diarias, adicionalmente a la semana solo pueden laborar
mínimo 16 horas semanales y hasta 47 horas como máximo, los trabajadores con
este tipo de contrato pertenecen a la nómina por horas.
117
Cada tipo de contrato tiene una liquidación diferente, lo que se debe a que se ha
buscado que tanto la empresa como el trabajador se beneficien, sin afectarse el
uno al otro. A continuación se presenta la forma como se debe liquidar cada tipo
de contrato21.
NÓMINA OPERATIVA:
Salario Base = (Salario Básico) / 240
Horas Dominicales = (Valor Hora) X (# horas dominicales (75%))
Horas Festivas = (Valor Hora) X (# horas festivas (150%))
Recargo Nocturno = (Valor Hora X 0.35) X (# Horas con Recargo
Nocturno)
Subsidio de Transporte = $50.800
NÓMINA POR HORAS:
Salario Base = (Salario Básico) / 240
Horas Dominicales = (Valor Hora) X (# horas dominicales (75%))
Horas Festivas = (Valor Hora) X (# horas festivas (150%))
Recargo Nocturno = (Valor Hora X 0.35) X (# Horas con Recargo
Nocturno)
Bonificación = # Horas Trabajadas X $240 (máximo 100 horas/
mes)
Dominical Proporcional = (# Horas Trabajadas X 16) / (104 X Valor Hora)
Subsidio de Transporte = (# Días Laborados) X (Valor de 1 Día de
Transporte)
21 Módulo de Nómina de FRISBY S.A. Área de Gestión Humana.
118
Luego de conocer las generalidades de los Restaurantes de la Compañía de
Frisby S.A., aclaramos que el restaurante que ha sido seleccionado como base
para el planteamiento del modelo es F35, el cual se encuentra ubicado en el
Barrio Cuba, en la ciudad de Pereira, es un Restaurante Tipo Calle sin parque
infantil y sin salón de fiestas, su servicio es semiautoservicio, con domicilio,
Restaurante Tipo B con ventas aproximadas de 74 millones de pesos (Sin IVA).
Modelo de Asignación
Para dar inicio al modelo de asignación de personal se debe tener en cuenta que
se hará la asignación para un mes de ventas normal, es decir que no incluye
vacaciones de mitad ni fin de año, día de la madre, 31 de Octubre, semana santa.
De los cargos descritos con anterioridad se debe aclarar que el vendedor de salón
se presenta cuando es un restaurante Tipo Calle con servicio a la Mesa, El cargo
de oficios varios es únicamente cuando el Restaurante es tipo Calle y el número
de personas que son asignadas depende mucho del tamaño del restaurante, es
decir si se tiene varias salones, parque infantil y salón para fiestas; lo normal que
se asigna a un restaurante tipo calle es un oficios varios.
El cargo de Administrador es un cargo particular debido a que dependiendo de la
categoría por ventas en el que se encuentre el restaurante se asigna el tipo de
administrador. Siempre se asignará Administrador, por tal razón esta información
es considerada como variables de entrada, en el programa que se desarrolle para
la validación del modelo.
Es decir que para nuestro modelo en particular NO Tendremos el Cargo de
Vendedor de Salón, y los cargos de Oficios Varios y Administrador son costos
Fijos que serán sumados a la Función Objetivo a minimizar.
119
El horizonte de trabajo del restaurante es Domingo a Jueves de 9:00 A.M. a 9:00
P.M. y de Viernes a Sábado de 9:00 A.M. a 10:00 P.M.
El horario de atención al público es de Domingo a Jueves de 11:00 A.M. a 9:00
P.M y de Viernes a Sábado de 11:00 A.M. a 10:00 P.M.
El cargo de Auxiliar de Producción debe estar presente en todo el horizonte de
trabajo, es decir desde que inicia el horizonte hasta la hora de cierre, entrará
entonces desde las 9:00 A.M., debido a que debe realizar labores de
prealistamiento y aseo, y en particular para este restaurante se estipula que se
gasta 2 horas en la realización de estas actividades.
El cargo de Despacho Combos entrará una hora antes del horario de atención al
público, dicho tiempo será empleado para prealistamiento y aseos.
El cargo de Despacho no tiene horas de aseo y prealistamiento, es decir entrará a
la hora exacta en que se presente la solicitud del cargo por el nivel de actividad.
En todo el horario de preapertura es necesaria la presencia de dos personas en el
restaurante tipo calle.
Los cargos de Administrador y/o Cajero deben mantenerse durante todo el horario
de atención de los Restaurantes como responsables del manejo administrativo y
operación de caja en la apertura, horario de atención (especialmente horas de alto
movimiento) y cierre.
El cargo de supernumerario no será asignado debido a que este cargo es el que
cubre el descanso de los demás cargos por lo tanto en el momento en que se
planteó la restricción horaria está implícito el descanso de los cargos, entonces lo
120
que se procederá a ser es que la otra persona que aparezca asignada para cada
cargo será reemplazada por el supernumerario.
Variables de Decisión
Las variables de decisión son variables binarias enteras, tomarán el valor de 1 si
se asigna una persona de nómina operativa o nómina por horas, a determinado
cargo, a una hora determinada y a un día de la semana. O de lo contrario el valor
de 0.
Donde:
i = Tipo de Contrato que tiene el Trabajador
i = 1, 2
1 = Contrato Jornada Completa
2 = Contrato Jornada Variable
j = Cargo que puede desempeñar
j = 1,..., 6
1 = Auxiliar de Producción
2 = Despacho
3 = Cajero
4 = Auxiliar de Salón
5 = Enrutador de Domicilios
6 = Domicilios
=x ijkl1 Asignar a la persona i, al cargo j, en la hora k, el día l. 0 En caso contrario
121
k = Hora a la cual es asignado
k = 1... 13
1 = 9:00 a.m. – 9:59 a.m.
2 = 10:00 a.m. – 10:59 a.m.
3 = 11:00 a.m. – 11:59 a.m.
4 = 12:00 p.m. – 12:59 p.m.
5 = 13:00 p.m. – 13:59 p.m.
6 = 14:00 p.m. – 14:59 p.m.
7 = 15:00 p.m. – 15:59 p.m.
8 = 16:00 p.m. – 16:59 p.m.
9 = 17:00 p.m. – 17:59 p.m.
10 = 18:00 p.m. – 18:59 p.m.
11 = 19:00 p.m. – 19:59 p.m.
12 = 20:00 p.m. – 20:59 p.m.
13 = 21:00 p.m. – 21:59 p.m.
l = Día en el cual debe laborar
l = 1,..., 7
1 = Lunes
2 = Martes
3 = Miércoles
4 = Jueves
5 = Viernes
6 = Sábado
7= Domingo
122
Restricciones de Carga Horaria
Se planteará inicialmente las restricciones para los trabajadores que pertenecen a
la Nómina Operativa.
TIEMPO COMPLETO • Horas por día: 8 Horas • Horas por semana: 48 Horas • Horas por mes: 208 Horas
HORAS POR DÍA
Las restricciones se plantearán para cada cargo.
AUXILIAR DE PRODUCCIÓN:
Las unidades de la variable son horas diarias
Se puede simplificar de la siguiente manera:
Donde: i = 1 es un persona que pertenece a la nómina operativa. j = 1 representa el cargo de Auxiliar de Producción k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo.
813
1111≥∑
=kkX
8...111311112111111111011141113111211111
≥++++++++ XXXXXXXX
813
1
≥∑=k
ijklX ∀ 1=i 7,...,1=l1=j
123
DESPACHO:
Donde: i = 1 es un persona que pertenece a la nómina operativa. j = 2 representa el cargo de Despacho k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo. CAJERO:
Donde: i = 1 es un persona que pertenece a la nómina operativa. j = 3 representa el cargo de Cajero k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo. AUXILIAR DE SALÓN:
Donde: i = 1 es un persona que pertenece a la nómina operativa. j = 4 representa el cargo de Auxiliar de Salón k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo.
díaHorask
ijklX /_813
1
≥∑=
∀ 1=i 2=j 7,...,1=l
díaHorask
ijklX /_813
1
≥∑=
1=i 4=j 7,...,1=l∀
1=i 3=j 7,...,1=l∀díaHorask
ijklX /_813
1
≥∑=
124
ENRUTADOR DE DOMICILIOS:
Donde: i = 1 es un persona que pertenece a la nómina operativa. j = 5 representa el cargo de Enrutador de Domicilios k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo. DOMICILIO:
Donde: i = 1 es un persona que pertenece a la nómina operativa. j = 6 representa el cargo de Domicilios k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo.
díaHorask
ijklX /_813
1
≥∑=
1=i 5=j 7,...,1=l∀
díaHorask
ijklX /_813
1
≥∑=
1=i 6=j 7,...,1=l∀
125
HORAS POR SEMANA
Las restricciones se plantearán para cada cargo.
AUXILIAR DE PRODUCCIÓN:
Las unidades de la Variable son Horas a la semana.
DESPACHO:
CAJERO:
SemanalesHorask
ijklk
ijklk
ijklk k
ijklijklk
ijklk
ijkl XXXXXXX __4813
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++ ∑∑∑∑ ∑∑∑==== ===
1
1
1
===
l
j
i
2
1
1
===
l
j
i
4
1
1
===
l
j
i
3
1
1
===
l
j
i
5
1
1
===
l
j
i
6
1
1
===
l
j
i
7
1
1
===
l
j
i
SemanalesHorask
ijklk
ijklk
ijklk k
ijklijklk
ijklk
ijkl XXXXXXX __4813
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++ ∑∑∑∑ ∑∑∑==== ===
1
2
1
===
l
j
i
2
2
1
===
l
j
i
4
2
1
===
l
j
i
3
2
1
===
l
j
i
5
2
1
===
l
j
i
6
2
1
===
l
j
i
7
2
1
===
l
j
i
SemanalesHorask
ijklk
ijklk
ijklk k
ijklijklk
ijklk
ijkl XXXXXXX __4813
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++ ∑∑∑∑ ∑∑∑==== ===
1
3
1
===
l
j
i
2
3
1
===
l
j
i
3
3
1
===
l
j
i
5
3
1
===
l
j
i
6
3
1
===
l
j
i
7
3
1
===
l
j
i
4
3
1
===
l
j
i
126
AUXILIAR DE SALÓN:
ENRUTADOR DE DOMICILIO:
DOMICILIO:
SemanalesHorask
ijklk
ijklk
ijklk k
ijklijklk
ijklk
ijkl XXXXXXX __4813
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++ ∑∑∑∑ ∑∑∑==== ===
1
4
1
===
l
j
i
2
4
1
===
l
j
i
3
4
1
===
l
j
i
5
4
1
===
l
j
i
6
4
1
===
l
j
i
7
4
1
===
l
j
i
4
4
1
===
l
j
i
SemanalesHorask
ijklk
ijklk
ijklk k
ijklijklk
ijklk
ijkl XXXXXXX __4813
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++ ∑∑∑∑ ∑∑∑==== ===
1
5
1
===
l
j
i
2
5
1
===
l
j
i
3
5
1
===
l
j
i
5
5
1
===
l
j
i
6
5
1
===
l
j
i
7
5
1
===
l
j
i
4
5
1
===
l
j
i
SemanalesHorask
ijklk
ijklk
ijklk k
ijklijklk
ijklk
ijkl XXXXXXX __4813
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++ ∑∑∑∑ ∑∑∑==== ===
1
6
1
==
=
l
j
i
2
6
1
==
=
l
j
i
3
6
1
==
=
l
j
i
5
6
1
==
=
l
j
i
6
6
1
===
l
j
i
7
6
1
==
=
l
j
i
4
6
1
==
=
l
j
i
127
HORAS POR MES
Las restricciones se plantearán para cada cargo.
AUXILIAR DE PRODUCCIÓN:
Las unidades de la Variable son Horas al Mes.
DESPACHO:
CAJERO:
AUXILIAR DE SALÓN:
1
1
1
===
l
j
i
2
1
1
===
l
j
i
4
1
1
===
l
j
i
3
1
1
===
l
j
i
5
1
1
===
l
j
i
6
1
1
===
l
j
i
7
1
1
===
l
j
i
MesalHorask
ijklk
ijklk
ijklk
ijklk
ijklk
ijklk
ijkl XXXXXXX ___208413
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++ ∑∑∑∑∑∑∑=======
1
2
1
===
l
j
i
2
2
1
==
=
l
j
i
4
2
1
==
=
l
j
i
3
2
1
==
=
l
j
i
5
2
1
===
l
j
i
6
2
1
==
=
l
j
i
7
2
1
==
=
l
j
i
MesalHorask
ijklk
ijklk
ijklk
ijklk
ijklk
ijklk
ijkl XXXXXXX ___208413
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++ ∑∑∑∑∑∑∑=======
1
3
1
===
l
j
i
2
3
1
===
l
j
i
3
3
1
===
l
j
i
5
3
1
===
l
j
i
6
3
1
===
l
j
i
7
3
1
===
l
j
i
4
3
1
===
l
j
i
MesalHorask
ijklk
ijklk
ijklk
ijklk
ijklk
ijklk
ijkl XXXXXXX ___208413
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++ ∑∑∑∑∑∑∑=======
1
4
1
===
l
j
i
2
4
1
===
l
j
i
3
4
1
===
l
j
i
5
4
1
===
l
j
i
6
4
1
==
=
l
j
i
7
4
1
==
=
l
j
i
4
4
1
==
=
l
j
i
MesalHorask
ijklk
ijklk
ijklk
ijklk
ijklk
ijklk
ijkl XXXXXXX ___208413
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++ ∑∑∑∑∑∑∑=======
128
ENRUTADOR DE DOMICILIO:
DOMICILIO:
NÓMINA POR HORAS A continuación se plantearán las restricciones de carga horaria para la Nómina por
Horas, éstas se plantearán para cada cargo. Para los trabajadores que se
encuentran por este tipo de Nómina se especifica que tienen unas horas de mínima
asignación, esto se realiza con el fin de facilitar la contratación y el proceso para
conseguir el personal. Las horas asignadas a una persona de Nómina por Horas
NO deben ser iguales o mayores a una de Nómina Operativa, debido a que la
Nómina por horas tiene unas bonificaciones adicionales que se otorgan con el fin
de hacer que el trabajo sea un poco más gratificante para el personal contratado
bajo esta modalidad.
1
5
1
==
=
l
j
i
2
5
1
==
=
l
j
i
3
5
1
===
l
j
i
5
5
1
==
=
l
j
i
6
5
1
==
=
l
j
i
7
5
1
==
=
l
j
i
4
5
1
==
=
l
j
i
MesalHorask
ijklk
ijklk
ijklk
ijklk
ijklk
ijklk
ijkl XXXXXXX ___208413
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++ ∑∑∑∑∑∑∑=======
1
6
1
==
=
l
j
i
2
6
1
==
=
l
j
i
3
6
1
==
=
l
j
i
5
6
1
==
=
l
j
i
6
6
1
==
=
l
j
i
7
6
1
==
=
l
j
i
4
6
1
==
=
l
j
i
MesalHorask
ijklk
ijklk
ijklk
ijklk
ijklk
ijklk
ijkl XXXXXXX ___208413
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++ ∑∑∑∑∑∑∑=======
129
HORAS POR DÍA
AUXILIAR DE PRODUCCIÓN: Donde: i = 2 es un persona que pertenece a la nómina por horas. j = 1 representa el cargo de Auxiliar de Producción k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo. DESPACHO:
Donde: i = 2 es un persona que pertenece a la nómina por horas. j = 2 representa el cargo de Despacho k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo.
díaHorasMAXIMASHORAS
díaHorasMINIMASHORAS
kijkl
kijkl
X
X
/_8
/_3
13
1
13
1
≤=−
≥=−
∑
∑
=
= ∀ 2=i 7,...,1=l1=j
díaHorasMAXIMASHORAS
díaHorasMINIMASHORAS
kijkl
kijkl
X
X
/_8
/_3
13
1
13
1
≤=−
≥=−
∑
∑
=
= ∀ 2=i 7,...,1=l2=j
130
CAJERO:
Donde: i = 2 es un persona que pertenece a la nómina por horas. j = 3 representa el cargo de Cajero k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo. AUXILIAR DE SALÓN:
Donde: i = 2 es un persona que pertenece a la nómina por horas. j = 4 representa el cargo de Auxiliar de Salón k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo. ENRUTADOR DE DOMICILIOS:
Donde: i = 2 es un persona que pertenece a la nómina por horas. j = 5 representa el cargo de Enrutador de Domicilios k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo.
díaHorasMAXIMASHORAS
díaHorasMINIMASHORAS
kijkl
kijkl
X
X
/_8
/_3
13
1
13
1
≤=−
≥=−
∑
∑
=
= ∀ 2=i 7,...,1=l3=j
díaHorasMAXIMASHORAS
díaHorasMINIMASHORAS
kijkl
kijkl
X
X
/_8
/_3
13
1
13
1
≤=−
≥=−
∑
∑
=
= ∀ 2=i 7,...,1=l4=j
díaHorasMAXIMASHORAS
díaHorasMINIMASHORAS
kijkl
kijkl
X
X
/_8
/_3
13
1
13
1
≤=−
≥=−
∑
∑
=
= ∀ 2=i 7,...,1=l5=j
131
DOMICILIO:
Donde: i = 2 es un persona que pertenece a la nómina por horas. j = 6 representa el cargo de Domicilios k= Hora en el horizonte de trabajo y va de la hora 1 hasta la hora 13 l = 1,…,7 es el día al cual es asignado y varia desde el Lunes hasta el
Domingo.
HORAS POR SEMANA
Las restricciones se plantearán para cada cargo.
AUXILIAR DE PRODUCCIÓN:
Las unidades de la Variable son Horas a la semana.
díaHorasMAXIMASHORAS
díaHorasMINIMASHORAS
kijkl
kijkl
X
X
/_8
/_3
13
1
13
1
≤=−
≥=−
∑
∑
=
= ∀ 2=i 7,...,1=l6=j
SemanalesHoras
SEMANAMINIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __16
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
1
2
==
=
l
j
i
2
1
2
==
=
l
j
i
4
1
2
==
=
l
j
i
3
1
2
==
=
l
j
i
5
1
2
==
=
l
j
i
6
1
2
==
=
l
j
i
7
1
2
==
=
l
j
i
SemanalesHoras
SEMANAMAXIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __47
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
1
2
==
=
l
j
i
2
1
2
==
=
l
j
i
4
1
2
==
=
l
j
i
3
1
2
==
=
l
j
i
5
1
2
==
=
l
j
i
6
1
2
==
=
l
j
i
7
1
2
==
=
l
j
i
132
DESPACHO:
CAJERO:
SemanalesHoras
SEMANAMINIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __16
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
3
2
==
=
l
j
i
2
3
2
==
=
l
j
i
3
3
2
==
=
l
j
i
5
3
2
==
=
l
j
i
6
3
2
==
=
l
j
i
7
3
2
==
=
l
j
i
4
3
2
==
=
l
j
i
SemanalesHoras
SEMANAMÁXIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __47
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
3
2
==
=
l
j
i
2
3
2
==
=
l
j
i
3
3
2
==
=
l
j
i
5
3
2
==
=
l
j
i
6
3
2
==
=
l
j
i
7
3
2
==
=
l
j
i
4
3
2
==
=
l
j
i
SemanalesHoras
SEMANAMAXIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __47
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
2
2
==
=
l
j
i
2
2
2
==
=
l
j
i
3
2
2
==
=
l
j
i
5
2
2
==
=
l
j
i
6
2
2
==
=
l
j
i
7
2
2
==
=
l
j
i
4
2
2
==
=
l
j
i
SemanalesHoras
SEMANAMINIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __16
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
2
2
==
=
l
j
i
2
2
2
==
=
l
j
i
3
2
2
==
=
l
j
i
5
2
2
==
=
l
j
i
6
2
2
==
=
l
j
i
7
2
2
==
=
l
j
i
4
2
2
==
=
l
j
i
133
AUXILIAR DE SALÓN:
ENRUTADOR DE DOMICILIO:
SemanalesHoras
SEMANASMÍNIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __16
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
4
2
==
=
l
j
i
2
4
2
==
=
l
j
i
3
4
2
==
=
l
j
i
5
4
2
==
=
l
j
i
6
4
2
==
=
l
j
i
7
4
2
==
=
l
j
i
4
4
2
==
=
l
j
i
SemanalesHoras
SEMANAMÁXIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __47
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
4
2
==
=
l
j
i
2
4
2
==
=
l
j
i
3
4
2
==
=
l
j
i
5
4
2
==
=
l
j
i
6
4
2
==
=
l
j
i
7
4
2
==
=
l
j
i
4
4
2
==
=
l
j
i
SemanalesHoras
SEMANAMÍNIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __16
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
5
2
==
=
l
j
i
2
5
2
==
=
l
j
i
3
5
2
==
=
l
j
i
5
5
2
==
=
l
j
i
6
5
2
===
l
j
i
7
5
2
==
=
l
j
i
4
5
2
==
=
l
j
i
SemanalesHoras
SEMANAMÁXIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __47
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
5
2
==
=
l
j
i
2
5
2
==
=
l
j
i
3
5
2
==
=
l
j
i
5
5
2
==
=
l
j
i
6
5
2
==
=
l
j
i
7
5
2
==
=
l
j
i
4
5
2
==
=
l
j
i
134
DOMICILIO:
HORAS POR MES
Las restricciones se plantearán para cada cargo.
AUXILIAR DE PRODUCCIÓN:
Las unidades de la Variable son Horas al Mes.
SemanalesHoras
SEMANAMÍNIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __16
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
6
2
==
=
l
j
i
2
6
2
==
=
l
j
i
3
6
2
==
=
l
j
i
5
6
2
==
=
l
j
i
6
6
2
==
=
l
j
i
7
6
2
==
=
l
j
i
4
6
2
==
=
l
j
i
SemanalesHoras
SEMANAMÍNIMASHORAS
kijkl
kijkl
kijkl
k kijklijkl
kijkl
kijkl XXXXXXX __47
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤++++++
−−
∑∑∑∑ ∑∑∑==== ===
1
6
2
==
=
l
j
i
2
6
2
==
=
l
j
i
3
6
2
==
=
l
j
i
5
6
2
==
=
l
j
i
6
6
2
==
=
l
j
i
7
6
2
==
=
l
j
i
4
6
2
==
=
l
j
i
1
1
2
===
l
j
i
2
1
2
===
l
j
i
4
1
2
===
l
j
i
3
1
2
===
l
j
i
5
1
2
===
l
j
i
6
1
2
===
l
j
i
7
1
2
===
l
j
i
MesalHoras
MESMÍNIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___604
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++
−−
∑∑∑∑∑∑∑=======
1
1
2
===
l
j
i
2
1
2
===
l
j
i
4
1
2
===
l
j
i
3
1
2
===
l
j
i
5
1
2
===
l
j
i
6
1
2
===
l
j
i
7
1
2
===
l
j
i
MesalHoras
MESMÁXIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___2074
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤
++++++
−−
∑∑∑∑∑∑∑=======
135
DESPACHO:
CAJERO:
1
2
2
===
l
j
i
2
2
2
===
l
j
i
3
2
2
===
l
j
i
5
2
2
===
l
j
i
6
2
2
===
l
j
i
7
2
2
===
l
j
i
MesalHoras
MESMÍNIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___604
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++
−−
∑∑∑∑∑∑∑=======
4
2
2
===
l
j
i
1
2
2
===
l
j
i
2
2
2
===
l
j
i
3
2
2
===
l
j
i
5
2
2
===
l
j
i
6
2
2
===
l
j
i
7
2
2
===
l
j
i
MesalHoras
MESMÁXIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___2074
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤
++++++
−−
∑∑∑∑∑∑∑=======
4
2
2
===
l
j
i
1
3
2
===
l
j
i
2
3
2
===
l
j
i
3
3
2
===
l
j
i
5
3
2
===
l
j
i
6
3
2
===
l
j
i
7
3
2
===
l
j
i
4
3
2
===
l
j
i
MesalHoras
MESMÍNIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___604
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++
−−
∑∑∑∑∑∑∑=======
1
3
2
===
l
j
i
2
3
2
===
l
j
i
3
3
2
===
l
j
i
5
3
2
===
l
j
i
6
3
2
===
l
j
i
7
3
2
===
l
j
i
4
3
2
===
l
j
i
MesalHoras
MESMÁXIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___2074
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤
++++++
−−
∑∑∑∑∑∑∑=======
136
AUXILIAR DE SALÓN:
ENRUTADOR DE DOMICILIO:
1
4
2
===
l
j
i
2
4
2
===
l
j
i
3
4
2
===
l
j
i
5
4
2
===
l
j
i
6
4
2
===
l
j
i
7
4
2
===
l
j
i
4
4
2
===
l
j
i
MesalHoras
MESMÍNIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___604
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++
−−
∑∑∑∑∑∑∑=======
1
4
2
===
l
j
i
2
4
2
===
l
j
i
3
4
2
===
l
j
i
5
4
2
===
l
j
i
6
4
2
===
l
j
i
7
4
2
===
l
j
i
4
4
2
===
l
j
i
MesalHoras
MESMÁXIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___2074
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤
++++++
−−
∑∑∑∑∑∑∑=======
1
5
2
===
l
j
i
2
5
2
===
l
j
i
3
5
2
===
l
j
i
5
5
2
===
l
j
i
6
5
2
===
l
j
i
7
5
2
===
l
j
i
4
5
2
===
l
j
i
MesalHoras
MESMÍNIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___604
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++
−−
∑∑∑∑∑∑∑=======
1
5
2
===
l
j
i
2
5
2
===
l
j
i
3
5
2
===
l
j
i
5
5
2
===
l
j
i
6
5
2
===
l
j
i
7
5
2
===
l
j
i
4
5
2
===
l
j
i
MesalHoras
MESMÁXIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___2074
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤
++++++
−−
∑∑∑∑∑∑∑=======
137
DOMICILIO:
ASIGNACIONES POR CARGO
La compañía Frisby S.A., ha establecido capacidades para determinar el número
de personas que se deben asignar a cada cargo, cada cargo atiende diferentes
funciones por tal razón se presentará la asignación para cada cargo
específicamente.
AUXILIAR DE PRODUCCIÓN:
Según los estudios realizados con anterioridad se ha determinado que un auxiliar
de Producción puede procesar 20 pollos por hora, la asignación de personal para
este cargo se define a continuación:
1
6
2
===
l
j
i
2
6
2
===
l
j
i
3
6
2
===
l
j
i
5
6
2
===
l
j
i
6
6
2
===
l
j
i
7
6
2
===
l
j
i
4
6
2
===
l
j
i
MesalHoras
MESMÍNIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___604
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≥
++++++
−−
∑∑∑∑∑∑∑=======
1
6
2
===
l
j
i
2
6
2
===
l
j
i
3
6
2
===
l
j
i
5
6
2
===
l
j
i
6
6
2
===
l
j
i
7
6
2
===
l
j
i
4
6
2
===
l
j
i
MesalHoras
MESMÁXIMASHORAS
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl
kijkl XXXXXXX ___2074
13
1
13
1
13
1
13
1
13
1
13
1
13
1
≤
++++++
−−
∑∑∑∑∑∑∑=======
138
Las variables de asignación que se han planteado son de tipo entera binaria, es
decir que toma valor de 1 si la persona es asignada al cargo o valor de 0 en caso
contrario, por tal razón es necesario definir un parámetro que nos permita
determinar el número de personas a asignar teniendo en cuenta la demanda que
se presenta en cada intervalo de tiempo. Creamos el parámetro a el cual se
multiplicará por la variable y nos dará el número de personas a asignar en el
cargo. A su vez el parámetro a estará condicionado por el nivel de actividad para
el cargo, en este caso es el número de pollos a procesar en un hora determinada.
La restricción se plantea así:
Donde:
Las unidades son:
a = Pollos * hora_________________________ (# de personas en el cargo de auxiliar de producción, en una hora k, el día l)
b = Pollos * Hora b representa el nivel de actividad.
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→≤→
→
=
2001.180_10
1801.160__9
1601.140__8
1401.120__7
1201.100__6
1001.80__5
801.60__4
601.40__3
401.20__2
20______1
____
bbbbbbbbb
bX
a
ijkl
HoraPollosbaX ijkl*≤ ∀ 2,1=i 7,...,1=l14,...,1=k1=j
139
DESPACHO:
Este cargo presenta una particularidad importante y es que presenta dos
ramificaciones, que son el cargo de Despacho Combos y el cargo de Despacho,
ambos cargos fueron explicados en las generalidades al inicio de este capítulo.
La Compañía Frisby S.A., cuenta con un modelo de simulación desarrollado en
Promodel, y en el cual se simula la operación de un restaurante, en donde se
incluyen todos los cargos y los productos con los que cuenta la empresa. Cuando
se realiza la simulación los datos obtenidos son analizados y almacenados en
unas bases de datos, lo que permite ver como se está comportando el restaurante
a partir de las ventas.
El comportamiento del restaurante viene explicado detalladamente en un hoja
llamada facturas en donde se puede ver claramente cuantas porciones se
vendieron en esa hora determinada, los productos vendidos son asignados a
cada cargo teniendo en cuenta las operaciones y las actividades que se deben
realizar para elaborar el producto, y es en este punto en donde se define si la
persona asignada al cargo de despacho es para ubicarla en la parte de atrás del
mostrador y cuyas funciones son las del despacho combos, o si por el contrario
se ubica adelante en donde se desempeñará como despacho.
Se toma entonces como base para asignar a las personas a este cargo un nivel de
actividad dado en porcentaje de utilización de este recurso. Y para asignar si es
Despacho Combos o Despacho es necesario verificar en la hoja de facturas en
donde se ubicará. Se presenta a continuación el nivel de actividad con el que se
asigna el número de personas a dicho cargo.
140
Porcentaje de utilización del rec urso Personas 0 – 100% 1 101% - 200% 2 201% - 300% 3 301% - 400% 4 401% - 500% 5 501% - 600% 6 601% - 700% 7 701% - 800% 8
La restricción se plantea así:
Donde:
Las unidades son:
a = % utilización del recurso por hora____________ __ (# de personas en el cargo de Despacho, en una hora k, el día l)
b = % Utilización del recurso por hora CAJERO:
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
→
=
%800%701______8
%700%601______7
%600%501______6
%500%401______5
%400%301______4
%300%201______3
%200%101______2
%100%0______1
____
bbbbbbb
bbX
a
ijkl
recurso nutilizació %baX ijkl≤ ∀ 2,1=i 7,...,1=l14,...,1=k2=j
141
Para el este cargo el nivel de actividad está representado en pedidos a llevar y a la
mesa, las capacidades de asignación se presenta en la siguiente tabla.
Pedidos Mesa y llevar Personas 0 – 15 0 16 – 35 1 36 – 70 2 > 71 3
La restricción se plantea así:
Donde:
Las unidades son:
a = pedidos * hora_______________ (# de personas en el cargo de cajero, en una hora k, el día l)
b = pedidos * hora
≤→
≤≤→
≤≤→≤→
→
=
71______3
7036______2
3516______1
150______0
____
bbb
bX
a
ijkl
HoraPedidosbaX ijkl*≤ ∀ 2,1=i 7,...,1=l14,...,1=k3=j
142
AUXILIAR DE SALÓN: Recordemos que el restaurante en el que estamos trabajando es un tipo calle
semiautoservicio por lo tanto no tiene Vendedor de Salón sino Auxiliar de Salón y
su nivel de actividad está dado en pedidos a la mesa como se muestra a
continuación:
Pedidos a la mesa Personas 6 – 12 1 12.1 – 24 2 24.1 – 36 3 > 36.1 4
La restricción se plantea así:
Donde:
Las unidades son:
a = pedidos a la mesa * hora________________________ s (# de personas en el cargo de auxiliar de salón, en una hora k, el día l)
b = pedidos a la mesa * hora
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
→
=
301.25______6
251.20______5
201.15______4
151.10______3
101.5______2
0.53______1
____
bbbbb
bbX
a
ijkl
HoramesalaaPedidosbaX ijkl*___≤ ∀ 2,1=i 7,...,1=l14,...,1=k3=j
143
ENRUTADORES DOMICILIO: Referente a los domicilios se manejan 3 cargos específicos los cuales son
Coordinador de Domicilios, Enrutador de Domicilios y Domicilios. El cargo de
Coordinador es asignado únicamente en los restaurantes que no cuentan con el
sistema Telefrisby, este sistema trabaja con una Central de Domicilios que maneja
un número único de atención al cliente, este número pertenece a una línea local y
que en el momento en el que el cliente marca la llamada es transferida de manera
inmediata a la Central de Domicilios en donde el sistema toma el pedido y
dependiendo de la zona en que se solicite se envía al restaurante más cercano o
el que esté asignado para este territorio, por ende no se necesita Coordinador de
Domicilio. El restaurante seleccionado trabaja con este sistema entonces no se
hará asignación para este cargo. En cuanto al cargo de enrutador es necesario
solo después de tener mínimo 9 pedidos de domicilio por hora, la condición para el
aforar el Enrutador se cumple siempre y cuando se presente durante dos (2)
horas consecutivas.
Pedidos a domicilio Personas > 9 1
La restricción se plantea así:
Donde:
Las unidades son:
a = pedidos domicilio * hora________________________ s (# de personas en el cargo de Enrutador de Domicilio, en una hora k, el día l)
b = pedidos a domicilio * hora
>→
→=
9______1
____
bbX
aijkl
HoradomicilioaPedidosbaX ijkl*__≤ ∀ 2,1=i 7,...,1=l14,...,1=k5=j
144
DOMICILIOS: En la parte de domicilios encontramos que la Compañía Frisby S.A., maneja 2 tipo
de zona dependiendo de la ubicación del restaurante y del tamaño de territorio que
abarque para la entrega de pedidos, se establecen entonces la Zona Amplia y la
Zona Normal; para nuestro restaurante elegido encontramos que maneja el
servicio de domicilio hasta lugares que se encuentran muy lejos respecto al punto
de venta del restaurante. Se clasifica entonces en un restaurante que maneja una
Zona Amplia para el servicio de domicilio. Y el nivel de actividad para asignar los
domicilio se hace con base en los pedidos a domicilio por hora. A continuación se
presenta las capacidades por persona.
ZONA AMPLIA
Pedidos a domicilio Personas 0 – 2 1 2 – 4 2 4 – 9 3 9.1 – 12 4 12.1 – 17 5 17.1 – 21 6 21.1 – 24 7 24.1 – 28 8 28.1 – 31 9 31.1 – 35 10
La restricción se plantea así:
HoradomicilioaPedidosbaX ijkl
*__≤ ∀ 2,1=i 7,...,1=l14,...,1=k6=j
145
Donde:
Las unidades son:
a = Pedidos a domicilio * hora___________________ (# de personas en el cargo de Domicilio, en una hora k, el día l)
b = Pedidos a domicilio * Hora
POLIFUNCIONALIDAD
La polifuncionalidad en los cargos permite que el personal pueda realizar
diferentes tipos de tareas en los cargos. El desarrollo de la polifuncionalidad se
logra capacitando a los empleados en las diferentes tareas para conseguir así el
desarrollo de las habilidades que se necesitan para desempeñar cada cargo. La
polifuncionalidad genera beneficios importantes para la empresa como son la
reducción de costos, mejoramiento en la prestación del servicio, mejora en la
calidad de los productos y mejor utilización de los recursos. La compañía ha
incursionado en el manejo de este tema y para iniciar en ello ha definido la
polifuncionalidad de los cargos dependiendo de la afinidad que se presente entre
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
≤≤→
<≤→
<≤→
→
=
351.31_10
311.28__9
281.24__8
241.21__7
211.17__6
171.12__5
121.9__4
94__3
42__2
20__1
____
bbbbbbb
bbbbX
a
ijkl
146
ellos. A continuación se muestra la relación y la polifuncionalidad que se puede
presentar para cada cargo.
La Compañía Frisby S.A., maneja la polifuncionalidad para los dos tipos de
contratación, pero en particular para el modelo desarrollado se aplicará solo a las
personas que pertenecen a la nómina por horas, con el fin de facilitar de manera
alguna la consecución de personal y permitir a los trabajadores un ingreso de
mejor calidad.
CARGO CAPACITACIÓN EN: Auxiliar de Producción Despacho Despacho Producción - Enrutador de Domicilios – Auxiliar de Salón Auxiliar de Salón Despacho Cajero Despacho - Enrutador Domicilios Enrutador Domicilios Despacho - Cajero - Domicilio Domicilio Enrutador Domicilio - Despacho
Para el planteamiento de la polifuncionalidad se creará una nueva variable
definida para cada cargo de manera específica.
VARIABLES DE POLIFUNCIONALIDAD Serán de igual forma variables enteras y binarias. En donde tomarán el valor de 1
si es asignada y 0 en el caso de no ser asignada. Es bueno aclarar que para las
variables de polifuncionalidad aplican las mismas restricciones de asignación por
cargo. En cuanto a la asignación de capacidad horaria se complementarán las
planteadas con anterioridad con una nuevas restricciones formuladas a
continuación.
1 Asignar la persona que desempeña el cargo i, al nuevo cargo j, en la hora k, el día l
0 en caso contrario Indices:
=Yijkl
147
i = Cargo ocupado actualmente .
i = 1,..., 6
1 = Auxiliar de Producción.
2 = Despacho.
3 = Cajero.
4 = Auxiliar de Salón.
5 = Enrutador de Domicilio.
6 = Domicilio.
j = Cargo al cual es asignado.
j = 1,..., 6
1 = Auxiliar de Producción.
2 = Despacho.
3 = Cajero.
4 = Auxiliar de Salón.
5 = Enrutador de Domicilio.
6 = Domicilio.
k = Hora en la cual es asignada la persona del cargo i al cargo j.
k = 1... 13
1 = 9:00 a.m. – 9:59 a.m.
2 = 10:00 a.m. – 10:59 a.m.
3 = 11:00 a.m. – 11:59 a.m.
4 = 12:00 p.m. – 12:59 p.m.
5 = 13:00 p.m. – 13:59 p.m.
6 = 14:00 p.m. – 14:59 p.m.
7 = 15:00 p.m. – 15:59 p.m.
8 = 16:00 p.m. – 16:59 p.m.
9 = 17:00 p.m. – 17:59 p.m.
10 = 18:00 p.m. – 18:59 p.m.
148
11 = 19:00 p.m. – 19:59 p.m.
12 = 20:00 p.m. – 20:59 p.m.
13 = 21:00 p.m. – 21:59 p.m.
l = Día en el cual es asignado
l = 1,..., 7
1 = Lunes
2 = Martes
3 = Miércoles
4 = Jueves
5 = Viernes
6 = Sábado
7= Domingo
CARGA HORARIA DIARIA
1 Asignar a un Auxiliar de producción, al cargo de despacho, a la hora k, el día l 0 en caso contrario
Para todo k = 1,...,13 y todo l = 1,..., 7 Auxiliar de Producción Despacho Se debe cumplir:
Despacho Auxiliar de Producción
=Y kl12
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1211
13
7,...,1121
≤+ ∑∑
====
====
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1121
13
7,...,1221
≤+ ∑∑
==
==
====
149
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1531
13
7,...,1321
≤+ ∑∑
====
====
Despacho Auxiliar de Salón
Despacho Enrutador de Domicilios
Auxiliar de Salón Despacho
Cajero Despacho
Cajero Enrutador de Domicilios
Enrutador de Domicilios Despacho
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1421
13
7,...,1221
≤+ ∑∑
====
====
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1521
13
7,...,1221
≤+ ∑∑
====
====
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1241
13
7,...,1421
≤+ ∑∑
====
====
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1231
13
7,...,1321
≤+ ∑∑
====
====
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1251
13
7,...,1521
≤+ ∑∑
====
====
150
Enrutador de Domicilios Cajero
Enrutador de Domicilios Domicilio
Domicilio Enrutador de Domicilios
Domicilio Despacho
Función Objetivo:
La función objetivo para nuestro modelo consiste en minimizar el costo de mano
de obra asignado al restaurante F35. Para dar inicio al planteamiento de la función
objetivo es necesario conocer los costos de mano de obra para cada tipo de
contratación, teniendo en cuenta la nómina a la que pertenezcan los empleados.
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1351
13
7,...,1521
≤+ ∑∑
====
====
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1651
13
7,...,1521
≤+ ∑∑
====
====
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1561
13
7,...,1621
≤+ ∑∑
====
====
diahoras
ljik
ijkl
ljik
ijkl YX *_813
7,...,1261
13
7,...,1621
≤+ ∑∑
====
====
151
COSTOS DE MANO DE OBRA
TIEMPO COMPLETO
Salario Mínimo: $441.838 / mes
Auxilio de Transporte: $50.800
Recargo Nocturno: 75%
Día de descanso remunerado
Cajero: $545.833
Administrador: $850,801
Subvención Domiciliario: $159.572
TIEMPO VARIABLE
Salario Mínimo: $441.838
Auxilio de Transporte: $1693.3 / día
Auxilio de Movilización: $240 / Hora Sí labora ≤ 100 horas al mes
$24.000 Sí labora > 100 horas al mes
Dominical Proporcional: X = 32*Horas Laboradas al mes
208
Subvención Domicilios: Proporcional a los días trabajados
Se da inicio calculando el valor promedio de horas para cada cargo y cada tipo de
nómina. Se trabaja con el mes de Marzo de 2007, el cual se considera un mes
normal, debido a que no presenta días festivos ni fechas de especial atención.
152
Nómina Operativa:
Vr Hora = $441.838 = $1841 / Hora
240 Horas Como se está trabajando con un mes normal se tiene que son 2 fines de semana
en donde se encuentran 2 días domingo y los cuales son considerados como días
festivo, por ende se paga un recargo festivo a estas horas laboradas. Como
pertenecen a la Nómina Operativa son personas que trabajan 8 horas diarias, es
decir en los 2 fines de semana son 16 horas con recargo festivo.
Vr Recargo Festivo al mes = ($1841/ hora * 0.75) * 16 horas = $ 22.100
Se les paga un auxilio de transporte por valor de $ 50.800
Con estas cifras se procede a calcular el valor de una hora promedio para un
trabajador de Nómina Operativa, en un mes normal.
Auxiliar e Producción, Auxiliar de Salón, Enrutador de Domicilios y Despacho.
Vr Hora Promedio = Salario mínimo + Recargo Festivo + Auxilio de Transporte
# de horas laboradas al mes
Vr Hora Promedio = $441.838 + $ 22.100 + $ 50.800
240 horas
Vr Hora Promedio = $2145 / Hora
Cajero
Vr Hora Promedio = $ 545.833 + 22.100 + 50.800
240 Horas
Vr Hora Promedio = $2579 / Hora
153
Domicilio:
Para el cálculo del valor de la hora promedio de los domiciliarios hay que tener en
cuenta la subvención que se les paga por la moto. Como se mostró anteriormente
la subvención depende de la zona a donde pertenezca el restaurante y para
nuestro caso en particular se tiene que pertenece a la zona 1 en donde se incluye
la ciudad de Pereira, Armenia, Ibagué y Neiva, y su valor es de $159.572
Vr Hora Prom. = Salario mínimo + subvención + recargo festivo + auxilio de
transporte
Vr Hora Prom. = $ 441.838 + $159.572 + $22.100 + $50.800
240 Horas
Vr Hora Prom. = $ 2810 / Hora
Estos son los valores de horas promedio para los trabajadores que Pertenecen a
la Nómina Operativa. Se procede a calcular la hora para la nómina por horas.
Nómina por Horas:
Para el cálculo en la nómina por horas se decidió consultar cuantos trabajadores
tiene asignados el restaurante F35 en este momento y verificar en nómina cuantas
horas laboró cada uno para buscar un promedio, esto se debe a que en el
momento la Compañía no cuenta con este dato. Se encontró que F35 tiene
asignadas 3 personas en la Nómina por horas y las cuales laboraron en el mes de
Marzo como aparece a continuación:
154
Trabajador 1 $/mes
Auxilio moviliza: 21,480
Subsidio de Transporte: 37,253
Dominical Proporcional: 26,766
Salario Nómina por Horas: 173,973
Hora dominical: 28,995
Total empleado: 288467
Total horas Laboradas: 119
Trabajador 2 $/mes
Auxilio moviliza: 14,760
Subsidio de Transporte: 16,933
Dominical Proporcional: 17,419
Salario Nómina por Horas: 113,221
Hora dominical: 41,422
Total empleado: 203755
Total horas Laboradas: 91
Trabajador 3 $/mes
Auxilio moviliza: 24,000
Subsidio de Transporte: 40,640
Dominical Proporcional: 42,484
Salario Nómina por Horas: 280,152
Hora dominical: 37,280
Total empleado: 424.556
Total horas Laboradas: 179
Se toma el salario y el número de horas de las tres persona y se promedia para
sacar un valor de hora promedio.
155
Vr Hora Promedio = ($ 288.467 + $ 203.755 + $ 424.556) / 3
(119 + 91+ 179) / 3
Vr Hora Promedio = ($916.778) / 3
(389) / 3
Vr Hora Promedio = $305.593
130 Horas
Vr Hora Promedio = $2.351 / Hora
Para el cálculo de la Función Objetivo se debe tener en cuenta lo siguiente:
Tipo de Restaurante y servicio que presta, debido a que se debe definir que tipo
de Administrador se debe asignar y si se asigna el cargo de Oficios Varios.
Como el restaurante seleccionado es Tipo Calle y Tipo B entonces tenemos como
Coto fijo lo siguiente:
Costo Administrador = Salario Administrador + Auxilio de Transp + Recargo
Festivo
Costo Administrador = $850.801 + $50.800 + $22.100
Costo Administrador = $923.701
Costo Oficios Varios = Salario mínimo + Auxilio de Transp + Recargo Festivo
Costo Oficios Varios = $441.838 + $ 50.800 + $22.100
Costo Oficios Varios = $ 514.738
Costos Fijos = $ 514.738 + $ 923.701
Costos Fijos = $ 1.438.439
156
MINIMIZAR Z =
FIJOSCOSTOSHoraHoraHoraHoraHora
ljik ijkl
ljik ijkl
ljik ijkl
ljik ijkl
ljik ijkl
YXXXX _351.2$351.2$810.2$579.2$145.2$
13
7,...,16,...,16,...,1
1
13
7,...,16,...,1
21
13
7,...,1611
13
7,...,1311
13
7,...,15,4,2,1
11
+++++ ∑∑∑∑∑
====
====
====
====
====
157
CONCLUSIONES
− Se revisó el estado del arte en cuanto a la optimización de horarios y
asignación de personal, lo que permitió una mejor contextualización del
problema que se encontró en la Compañía de Frisby S.A.
− Se presentó los conceptos básicos de los métodos de optimización
combinatorial más usados para dar solución a este tipo de problemas, para
tener un conocimiento previo de la forma de solución para el problema
especifico de la compañía.
− Se determinó las variables de asignación de personal para cada cargo,
teniendo en cuenta el tipo de contrato celebrado con los empleados, para así
determinar el costo según la valoración de cargos de la empresa.
− Se planteó restricciones de carga horaria para no ir en contra de la Legislación
Colombiana y de las políticas con las que cuenta la compañía en el área de
Gestión Humana. De igual forma se plantean restricciones de asignación por
cargo debido a que en la compañía se cuenta con un modelo de simulación de
un restaurante en el cual se transforman la demanda en requisiciones para
cada cargo dependiendo de la mezcla de productos vendidos. Por tal razón
cada cargo tiene un nivel de actividad diferente.
158
− En la función objetivo se logró la relación de los costos para cada cargo,
adicionalmente el cálculo de unos costos fijos que es necesario tener en
cuenta para la minimización del costo total de mano de obra en el restaurante.
− Se puede concluir que la práctica empresarial permite al estudiante un
intercambio de información y experiencias que van a proporcionar una
contextualización mucho más amplia entre el medio y el estudiante
desencadenando una formación integral para un futuro laboral y profesional
exitoso.
− El proceso de construcción de un modelo matemático que permita programar
de manera óptima los recursos de la empresa, teniendo en cuenta cada una de
las características esenciales que permiten que el modelo sea acertado para lo
que se busca, es muy interesante debido a que se puede conocer de forma
detallada el proceso que se debe desarrollar para lograr que una empresa que
cuenta con demasiados restaurantes pueda contar con el personal adecuado,
en la cantidad necesario y que aparte el costo sea el justo para no incurrir en
pérdidas, en el momento apropiado para brindar a sus clientes un excelente
servicio y una muy buena calidad en sus productos.
159
RECOMENDACIONES
− Se recomienda que la Compañía de Frisby S.A., valide el modelo planteado
para el restaurante tipo calle seleccionado.
− Se recomienda también que se realice un estudio que permita determinar un
valor más exacto de una hora para un empleado de la nómina por horas,
debido a que para el modelo aquí planteado se hizo un promedio normal entre
tres empleados, por tal razón se sugiere la validación de dicha información.
− Es necesario que la compañía continúe con la ampliación del modelo
abarcando todo tipo de restaurante y de servicio, vinculando así las variables y
parámetros que se consideren esenciales para el proceso de construcción.
− Es fundamental que la empresa inicie con el desarrollo de software para dar
continuación al Proyecto de Aforo, este software con el fin de convertir la
programación y asignación de horarios en un módulo de interfaces entre el
Analista de Aforos, Administradores, Gestión humana, los empleados y todos
los cargos que tienen de alguna u otro forma alguna relación con los costos de
mano de obra.
− Se sugiere que en la construcción del software se cuente con la presencia de
un Ingeniero Industrial, pues se considera que es la persona idónea para
brindar un asesoramiento en cuanto a lo que la empresa necesita y la manera
de programar el modelo construido.
160
− En cuanto a las prácticas empresariales se recomienda que tanto la empresa
como la Universidad establezcan unos lineamientos claros, no solo de
cumplimento sino en lo referente a lo que la empresa desea y lo que la
Universidad puede cubrir de o desarrollar referente a las requisiciones de la
empresa. Esto con el fin de no perder tiempo valioso en la determinación de
qué es lo que se va a trabajar en la práctica y qué se espera alcanzar.
161
BIBLIOGRAFÍA
ALVAREZ R, CRESPO E, TAMARIT J.M. (1998) VI Jornadas ASEPUMA,
Santiago de Compostela. Universidad de Valencia.
BRUSCO M. Solving personnel tour scheduling problemsusing the dual all-integer
cutting plane IIE Transactions (1998) 30, 835 – 844.
ESCALAPÉS C. 2000, Asignación de Conductores a Jornadas de Trabajo en
Empresas de Transporte Colectivo, Universidad Politécnica de Cataluña.
GALLEGO R. ESCOBAR. A. ROMERO. R. (2006). Técnicas de Optimización
Combinatorial. Taller Publicaciones U.T.P. Universidad Tecnológica de Pereira.
GRANADA M, TORO E. M, ROMERO R, Algoritmo memético aplicado al problema
de asignación generalizada, Revista Tecnura No 16, Universidad Distrital F.J.C., I-
2005, Colombia.
GRANADA M, TORO E. M, TABARES P. Método de Colonia de Hormigas
Aplicado a la Solución del Problema de Asignación Generalizada. Revista
Tecnura No 15, Universidad Distrital F.J.C., II-2004.
GRANADA M, TORO E. M, Método Híbrido Entre El Algoritmo Genético De Chu-
Beasley Y Simulated Annealing Para La Solución Del Problema De Asignación
Generalizada, Revista Scientia et Technica (27), 61-67, U.T.P., Colombia.
GRANADA M. Y TORO M, (2004) Solución al Problema de la Asignación
Generalizada Usando el Método de Búsqueda Tabú. Revista Scientia et Technica
(24), 61-67, U.T.P., Colombia.
162
GUZMÁN H. F, Metodología De Asignación Optima De Mano De Obra En La
Industria Floricultora Colombiana, Universidad de los Andes.
LANDA. R. 2002. Algoritmos Culturales Aplicados a Optimización con
Restricciones y Optimización Multiobjetivo. Instituto Politécnico Nacional. México,
D. F.
LOVE R. HOEY J. Management Science Improves Fast – Food Operations. The
Institute of Management Sciences. 2 March - April 1990 (pp. 21-29)
MOSCATO. P. Una Introducción a los Algoritmos Meméticos. Inteligencia Artificial,
Revista Iberoamericana de Inteligencia Artificial. No.19 (2003),pp. 131-148.
Universidad de Málaga.
PRAWDA J. Métodos y Modelos de Investigación de operaciones. Vol 1.Editorial
Limusa. México 1986
THOMPSON G. Assigning Telephone Operators to Shifts at New Brunswick
Telephone Company Instute for Operations Research and the Management
Sciences 4 July - August 1997 (pp. 1-11).
ZULEMA E. Asignación Multicriterio De Tareas A Trabajadores Polivalentes.
Instituto de Organización y Control de Sistemas Industriales. Universidad
Politécnica De Cataluña. Mayo de 2006
A Comment on Edie´s “Trafic Delays at Tool Booths”. 1954 Operation Research,
2,3, pp. 339 – 341.