Marginal productivity index policies for dynamic priority allocation in restless bandit models

Laburpena

ESTA TESIS ESTUDIA TRES COMPLEJOS PROBLEMAS DINAMICOS Y ESTOCASTICOS DE ASIGNACION DE RECURSOS : 1, ENRUTAMIENTO Y CONTROL DE ADMISION CON INFORMACION RETRASADA 2. PROMOCION DINAMICA DE PRODUCTOS Y EL PROBLEMA DE LA MOCHILA PARA ARTICULOS PERECEDEROS 3. CONTROL DE CONGESTION EN "ROUTERS" CON INFORMACION DE RECORRIDO FUTURO DEBIDO A QUE LA SOLUCIÓN ÓPTIMA DE ESTOS PROBLEMAS NO ES ASEQUIBLE COMPUTACIONALMENE A GRAN Y MEDIA ESCALA, NOS CONCENTRAMOS EN CAMBIO EN DISEÑAR POLITICAS HEURISTICAS DE PRIORIDAD QUE SEAN COMPUTACIONALMENTE TRATABLES Y CUYO RENDIMIENTO SE CUASI-OPTIMO. MODELAMOS LOS PROBLEMAS ARRIBA MENCIONADOS COMO PROBLEMAS DE "MULTI-ARMED RESTLESS BANDIT" EN EL MARCO DE PROCESOS DE DECISIÓN MARKOVIOANOS CON ESTRUCTURA ESPECIAL. EMPLEAMOS Y ENRIQUECEMOS RESULTADOS EXITENTES EN LA LITERATURA, LOS QUE CONSTITUYEN UN PRINCIPIO UNIFICADOR PARA EL DISEÑO DE POLITICAS DE INDICES DE PRIORIDAD BASADAS EN LA RELAJACION LAGRAGIANA Y AL DESCOMPOSICIÓN DE DICHOS PROBLEMAS. ESTA DESCOMPOSICION PERMITE CONSIDERAR SUBPROBLEMAS DE OPTIMIZACIÓN PARAMETRICA, Y EN CIERTOS CASOS "INDEXABLES", RESOLVERLOS DE MANERA O'PTIMA MEDIANTE EL INDICE DE PRODUCTIVIDAD MARGINAL (MP). EL INDICE MP ES USADO COMO MEDIA DE PRIORIDAD DINAMICA PARA DEFINIR REGLAS HEURISTICAS DE PRIORIDAD PARA LOS PROBLEMAS ORIGINALES INTRATABLES.