Aplicación de la Programación lineal a la asignación de personal en un centro de llamadas

[ES] La necesidad de gestionar y repartir eficazmente los recursos escasos entre las diferentes operaciones de las empresas, hacen que éstas recurran a aplicar técnicas de la Investigación de Operaciones. Éste es el caso de los centros de llamadas, un sector emergente y dinámico que se encuentra en constante desarrollo. En este sector, la administración del trabajo requiere de técnicas predictivas para determinar el número de trabajadores adecuado y así evitar en la medida de lo posible tanto el exceso como la escasez del mismo. Este trabajo se centrará en el estudio del centro de llamadas de emergencias 112 de Andalucía. Partiendo de los datos estadísticos del número medio de llamadas que se realiza en cada franja horaria, facilitados por la Junta de esta Comunidad Autónoma, formularemos y modelizaremos el problema aplicando la Programación Lineal. Posteriormente, lo resolveremos con dos programas de software, con la finalidad de obtener una distribución óptima de agentes que minimice el coste salarial, ya que supone un 65% del gasto de explotación total. Finalmente, mediante la teoría de colas, observaremos los tiempos de espera en cola y calcularemos el número objetivo de agentes que permita no sólo minimizar el coste salarial sino mejorar la calidad de servicio teniendo unos tiempos de espera razonables.

Otimização da programação das limpezas em redes de trocadores de calor utilizando técnicas de programação matemática

Redes de trocadores de calor são bastante utilizadas na indústria química para promover a integração energética do processo, recuperando calor de correntes quentes para aquecer correntes frias. Estas redes estão sujeitas à deposição, o que causa um aumento na resistência à transferência de calor, prejudicando-a. Uma das principais formas de diminuir o prejuízo causado por este fenômeno é a realização periódica de limpezas nos trocadores de calor. O presente trabalho tem como objetivo desenvolver um novo método para encontrar a programação ótima das limpezas em uma rede de trocadores de calor. O método desenvolvido utiliza o conceito de horizonte deslizante associado a um problema de programação linear inteira mista (MILP). Este problema MILP é capaz de definir o conjunto ótimo de trocadores de calor a serem limpos em um determinado instante de tempo (primeiro instante do horizonte deslizante), levando em conta sua influência nos instantes futuros (restante do horizonte deslizante). O problema MILP utiliza restrições referentes aos balanços de energia, equações de trocadores de calor e número máximo de limpezas simultâneas, com o objetivo de minimizar o consumo de energia da planta. A programação ótima das limpezas é composta pela combinação dos resultados obtidos em cada um dos instantes de tempo.O desempenho desta abordagem foi analisado através de sua aplicação em diversos exemplos típicos apresentados na literatura, inclusive um exemplo de grande porte de uma refinaria brasileira. Os resultados mostraram que a abordagem aplicada foi capaz de prover ganhos semelhantes e, algumas vezes, superiores aos da literatura, indicando que o método desenvolvido é capaz de fornecer bons resultados com um baixo esforço computacional

Closing the gap: Improved bounds on optimal POMDP solutions

POMDP algorithms have made significant progress in recent years by allowing practitioners to find good solutions to increasingly large problems. Most approaches (including point-based and policy iteration techniques) operate by refining a lower bound of the optimal value function. Several approaches (e.g., HSVI2, SARSOP, grid-based approaches and online forward search) also refine an upper bound. However, approximating the optimal value function by an upper bound is computationally expensive and therefore tightness is often sacrificed to improve efficiency (e.g., sawtooth approximation). In this paper, we describe a new approach to efficiently compute tighter bounds by i) conducting a prioritized breadth first search over the reachable beliefs, ii) propagating upper bound improvements with an augmented POMDP and iii) using exact linear programming (instead of the sawtooth approximation) for upper bound interpolation. As a result, we can represent the bounds more compactly and significantly reduce the gap between upper and lower bounds on several benchmark problems. Copyright © 2011, Association for the Advancement of Artificial Intelligence. All rights reserved.

Comparison of stochastic methods for control in air traffic management

This paper provides a direct comparison of two stochastic optimisation techniques (Markov Chain Monte Carlo and Sequential Monte Carlo) when applied to the problem of conflict resolution and aircraft trajectory control in air traffic management. The two methods are then also compared to another existing technique of Mixed-Integer Linear Programming which is also popular in distributed control. © 2011 IFAC.

Continuous dynamical systems that realize discrete optimization on the hypercube

We study the problem of finding a local minimum of a multilinear function E over the discrete set {0,1}n. The search is achieved by a gradient-like system in [0,1]n with cost function E. Under mild restrictions on the metric, the stable attractors of the gradient-like system are shown to produce solutions of the problem, even when they are not in the vicinity of the discrete set {0,1}n. Moreover, the gradient-like system connects with interior point methods for linear programming and with the analog neural network studied by Vidyasagar (IEEE Trans. Automat. Control 40 (8) (1995) 1359), in the same context. © 2004 Elsevier B.V. All rights reserved.

Processing network models of energy/environment systems

Processing networks are a variant of the standard linear programming network model which are especially useful for optimizing industrial energy/environment systems. Modelling advantages include an intuitive diagrammatic representation and the ability to incorporate all forms of energy and pollutants in a single integrated linear network model. Added advantages include increased speed of solution and algorithms supporting formulation. The paper explores their use in modelling the energy and pollution control systems in large industrial plants. The pollution control options in an ethylene production plant are analyzed as an example. PROFLOW, a computer tool for the formulation, analysis, and solution of processing network models, is introduced.

a constraint solver and its application to path feasibility analysis

Many testing methods are based on program paths. A well-known problem with them is that some paths are infeasible. To decide the feasibility of paths, we may solve a set of constraints. In this paper, we describe constraint-based tools that can be used for this purpose. They accept constraints expressed in a natural form, which may involve variables of different types such as integers, Booleans, reals and fixed-size arrays. The constraint solver is an extension of a Boolean satisfiability checker and it makes use of a linear programming package. The solving algorithm is described, and examples are given to illustrate the use of the tools. For many paths in the testing literature, their feasibility can be decided in a reasonable amount of time.

Optimal design of a 7 T highly homogeneous superconducting magnet for a Penning trap

A Penning trap system called Lanzhou Penning Trap (LPT) is now being developed for precise mass measurements at the Institute of Modern Physics (IMP). One of the key components is a 7 T actively shielded superconducting magnet with a clear warm bore of 156 mm. The required field homogeneity is 3 x 10(-7) over two 1 cubic centimeter volumes lying 220 mm apart along the magnet axis. We introduce a two-step method which combines linear programming and a nonlinear optimization algorithm for designing the multi-section superconducting magnet. This method is fast and flexible for handling arbitrary shaped homogeneous volumes and coils. With the help of this method an optimal design for the LPT superconducting magnet has been obtained.

逆向物流流量不确定闭环供应链鲁棒运作策略设计

考虑一类同时具有再分销、再制造和再利用的闭环供应链在逆向物流流量不确定环境下的运作问题.采用具有已知概率的离散情景描述逆向物流流量的不确定性,利用基于情景分析的鲁棒线性优化方法建立该闭环供应链的多目标运作模型.设计了一个数值算例,其结果验证了运作策略的鲁棒性.在该算例基础上,分析了逆向物流流量的大小对闭环供应链系统运作性能的影响.

聚类引导搜索的移动机器人路径规划方法

本文提出一种聚类引导搜索（cluster guide searching，CGS）的路径规划方法。采用基于最大最小距离的K均值聚类方法对样本进行离线聚类学习，学习结果以相似环境相似决策的知识形式进行存储。路径规划过程中，机器人在线整理环境信息，获得输入空间样本，通过与知识库匹配，检索到最近的类别，然后在该类别内部采用速度优先策略和方向优先策略交替的方式搜索输出空间。若知识不完备导致检索失败，可重启线性规划算法（linear programming，LP）进行在线路径规划，并更新聚类知识库。仿真结果表明该方法是一种有效的路径规划学习方法。

任务分配问题的建模与求解

建立了极大极小任务分配问题的混合整数线性规划模型,提出一种矩阵作业解答,并与穷举解及混合整数线性规划解的计算复杂度进行了比较.理论分析和数值试验表明矩阵作业法对两类任务分配问题,极大极小和总体极小任务分配问题,有效地提供最优解.

多目标追逐问题的一种混合整数线性规划解

研究多车辆多目标追逐的路径规划问题。提出两个基于混合整数线性规划(Mixed integer linear programming,MILP)的多目标追逐(Multi-target pursuit,MTP)模型:就近追逐和"一对一"使能追逐。在两个MIP追逐模型中,小车运动的状态方程考虑为具有线性阻尼的质点动力学方程。采用整数变量描述小车与障碍物的相对位置信息,提出"目标膨胀尺寸"的概念来描述对目标的追逐,定义小车的"追逐方向"。采用选取整变量的等高面法求解MILP追逐问题,并给出初始内点整变量的确定方法。最后给出仿真试验1对两个多目标追逐模型进行对比研究,仿真试验2证实了算法的效率。

加速度空间中基于线性规划的移动机器人路径规划方法

针对动态不确定环境下移动机器人的路径规划问题,提出了加速度空间中一种基于线性规划(Linear programming,LP)的方法.在机器人的加速度空间中利用相对信息,把机器人路径规划这一非线性问题,描述成满足一组线性约束同时使目标函数极小的线性规划问题,嵌入基于线性规划方法的规划器,得到一条满足性能要求的最优路径.仿真试验验证了算法的实用性及有效性,与势场引导进化计算的方法(Artificial potential guided evolution algorithm,APEA)相比更优化,更实时.

柔性制造系统的负荷分配及路径规划方法

柔性是柔性制造系统（ＦＭＳ）的一个基本优点，但这一基本优点却往往被人们所忽视，许多现在运行的ＦＭＳ不是缺乏柔性，就是没能充分利用可获得的柔性来提高生产效率柔性制造系统的负荷分配和路径规划问题正是这种柔性的一个主要方面．然而，路径规划决策却往往被忽视．其中一个主要原因就是人们仍不能从传统的生产管理概念中解放出来．本文在明确概念区分的基础上，提出了一种柔性制造系统的负荷分配和路径规划的线性规划模型，其主要特点是将负荷分配和路径规划问题有机地结合起来，并通过仿真实验验证并分析了此方法对ＦＭＳ性能上的影响。

Residual Vibration Reduction in Computer Controlled Machines

Control of machines that exhibit flexibility becomes important when designers attempt to push the state of the art with faster, lighter machines. Three steps are necessary for the control of a flexible planet. First, a good model of the plant must exist. Second, a good controller must be designed. Third, inputs to the controller must be constructed using knowledge of the system dynamic response. There is a great deal of literature pertaining to modeling and control but little dealing with the shaping of system inputs. Chapter 2 examines two input shaping techniques based on frequency domain analysis. The first involves the use of the first deriviate of a gaussian exponential as a driving function template. The second, acasual filtering, involves removal of energy from the driving functions at the resonant frequencies of the system. Chapter 3 presents a linear programming technique for generating vibration-reducing driving functions for systems. Chapter 4 extends the results of the previous chapter by developing a direct solution to the new class of driving functions. A detailed analysis of the new technique is presented from five different perspectives and several extensions are presented. Chapter 5 verifies the theories of the previous two chapters with hardware experiments. Because the new technique resembles common signal filtering, chapter 6 compares the new approach to eleven standard filters. The new technique will be shown to result in less residual vibrations, have better robustness to system parameter uncertainty, and require less computation than other currently used shaping techniques.