带有时间和费用双重限制的网络容量扩充问题

该文将网络容量定义为最大s-t流的流量,建立了带有时间和费用双重限制下的网络容量扩充问题的一般模型。通过网络变换,将带有时间限制的容量扩充问题转化为线性最小费用流问题,并给出了具体证明和求解容量扩充问题的算法。该模型和算法不仅适用于各种情形的容量扩充问题,而且还可应用于网络流规划。最后通过具体例子的求解,说明了模型和算法的正确性和有效性。     

考虑道路扩建的区域物流网络设计优化模型

通过对区域物流网络中边、点上费用、容量、流量等的分析,结合实际问题中对道路扩建和物流设施容量设计决策的需要,构建基于物流时间需求的区域物流网络设计数学模型。模型以最小化物流网络构建成本、初期运营成本和物流时间需求惩罚成本为目标,基于网络中物流量的特征给出了约束条件,分析模型的特点开发了改进的拉格朗日松弛算法并予以求解。计算机软件对模型和算法的仿真给出了物流网络构建中各项成本之间的关系,验证了模型和算法的有效性和实用性。     

点和边有容量约束的网络最小费用最大流算法*

分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法。概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念。依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法。该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流。最后,通过实例进行了算法测试和比较。算法测试表明：点和边有容量约束的网络最小费用最大流算法是完全可行和有效的。     

动态容量网络中的最小最大时间流问题

动态(时间依赖的)容量网络与传统静态网络相比更具现实意义,在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上,研究具有实际背景的动态容量网络的最小最大时间流问题,给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例,其时间复杂度为O(mMv)。     

求解最小费用最大流的新方法

文中给出了一种求解网络最小费用最大流的新方法,寻找由始点到终点的每条有向链,找到有向链可通过的最大容量,根据最大容量计算出此条有向链的最小费用最大流,根据最大容量和最小费用最大流可以计算出单位费用.选取单位费用最小的有向链进行最大容量的增广.文中通过对最小费用路算法进行改进,使得该算法容易理解,却又避免了最小费用路算法每次都要经过剩余网络进行增广,从而大大提高了求解最小费用最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性     

分布式多媒体系统中的同步问题研究

文中首先给出基于进程代数的ＬＯＴＯＳ形式化规范语言的基本概念,通过对传统ＬＯＴＯＳ进行基于时间的扩充,引入时间算子,并给出其相应的语法定义和形式语义。通过对分布式环境下的多媒体同步问题进行系统的分析,利用基于时间扩充的ＬＯＴＯＳ,给出了基本的同步问题和严格的多媒体唇同步问题的算法描述。同时给出一个实例系统,进一步描述了基于时间扩充的ＬＯＴＯＳ,对分布环境下多媒体信息同步问题在实际中的应用,并与传统     

应用自适应遗传算法解决集装箱装载问题

集装箱配载是一个复杂的组合优化问题，其约束条件多，属于NP完全问题，并且求解难度大．在满足一定的约束条件下。提出一种3维集装箱装载的自适应遗传算法．算法中考虑了货物放置方向和装载容积等约束条件，给出了有效的解码算法．实例仿真结果表明了该算法的有效性和实用性．     

基于最小费用最大流问题的“排序”算法

由于现有的求解最小费用最大流问题的方法都存在其局限性,为了更好地解决实际问题,在已有最短路算法以及最小费用算法的基础上作了改进,给出了一种求解基于最大流的最小费用问题的算法.文中针对小规模网络给出求两点之间最小费用的一种简单易行的方法,此外该算法可以在一个图上完成,这样可以节省许多画图时间,增强了算法的直观性和可控性.并且构建石油运输的网络模型,结合最小费用最大流算法,给出该模型从产地到销地的最优运输方案,最后通过具体的模型实例验证了该方法的效率和实用性.     

基于遗传算法的互连网络网关与路由方案设计

研究互连网络的网关与路由方案综合优化设计问题,包括：（１）确定将给定的已有网络互连起来所需的网关数及其位置;（２）给网关链路分配容量;（３）进行网内的网际路由选择,目标是要在给定的设置网关预算费用下使得网内的网际平均分组时延最小。该问题的数学模型是一个有着众多约束条件的非线性０—１规划。根据遗传算法的基本思想,设计了一个求解该问题的遗传优化算法,并将其应用于一个实例化设计。     

遗传模拟退火算法在弹药装载中的应用研究

多约束条件下的弹药装载问题是一个复杂的组合优化问题，属于NP-完全问题，其求解是很困难的。本文在考虑弹药装载中各类约束条件的情况下，将模拟退火算法作了若干改进后，融入遗传算法，提出了一种遗传模拟退火算法来求解弹药装载问题。本文对该算法的遗传算子和冷却进度表进行了详细的阐述，给出了使用该算法求解弹药装载问题的具体实现方法。     

CMST问题的新算法

本文提出了解决按约束条件求最小代价生成树(简称CMST)问题的两个新算法,即给定结点数N,每个结点的负载,链路的代价及链路的容量后,在符合某些约束条件下,求代价最小的树结构.两个新算法的计算复杂性均为O(N~2).计算结果表明,新算法所得结果的代价低于几个现有算法,而计算复杂性比现有算法小得多.     

严格无阻塞多播三级Clos网的优化

如何在严格无阻塞情况下保持最低的硬件代价,是多播三级Clos网设计中的一个重要问题.提出一种优化网络硬件代价的方法,分别给出了在没有多播受限和中间级多播受限两种情况下,严格无阻塞多播三级Clos网硬件代价的最优值.分析表明,优化后网络的硬件代价得到了有效降低,在某些情况下甚至低于广义无阻塞网.同时,与广义无阻塞网相比,该网络无需特定的路由算法就能始终保持严格无阻塞状态,在一定程度上降低了时间复杂度.     

Multiproduct production/inventory control under random demands

Studies the optimal production/inventory control policy for a single machine multiproduct production system. The machine produces to fill the end-product inventory stock and the demand is satisfied from the inventory when available; unsatisfied demand is backlogged until the product becomes available as the result of production. For each product, the demand follows a Poisson process and the unit processing time is known. When the machine switches production from one product to another, it incurs a set-up time and a set-up cost. The relevant costs include the set-up cost, a cost per unit time while the machine is running, and linear costs for inventory and backlogging. This problem is modeled as a semi-Markov decision process using the criterion of minimizing expected total cost with discounting over an infinite horizon. Procedures for computing near-optimal policies and their error bounds are developed. The error bound given by the authors' procedure is shown to be much tighter than the one given by the “norm-based” approach. Computational test results are presented to show the structure of the near-optimal policy and how its accuracy is affected by the system characteristics such as capacity utilization and set-up time     

基于包对测量的路径容量估计方法改进

测量样本的统计分析是基于包对技术的路径容量估计的关键.提出一种路径容量包对估计方法改进,将端到端路径视为离散控制过程的系统,以路径容量描述其状态.首先以包对探测方式连续发送一定数量的背靠背包对序列,获取足够的路径容量测量样本;再采用卡尔曼过滤算法对测量样本进行统计分析,以准确估计路径容量.建立了路径容量估计的滤波方程,给出了路径容量估计过程.实验表明,与pathrate算法相比,提高了估计的准确性并降低了测量探测量和测量时间.     

带拒绝箱覆盖问题的局内算法

作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题.设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用.物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱.如果物品被放入箱中,则产生费用.该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景.给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果.     

基于P4P的CDN系统中内容分发节点选择算法

对内容分发网络(CDN)和对等网络(P2P)分别进行了分析对比,指出了它们各自的优缺点,并根据电信运营商主动参与P2P网络(P4P)技术的特点,给出了一种结合P4P、P2P与CDN技术的混合系统的设计方案,以及混合系统中协助CDN节点分发内容节点(伪CDN节点)的选择算法.该算法利用P4P技术获得运营商提供的网络信息,选择合适的边缘节点,贡献出其容量和带宽,为其他节点服务,以减少了系统边缘代理服务器的数量,增大系统容量,同时减少网络骨干网上的负载.模拟实验分析了考虑底层网络情况后,系统在链路花费、时间花费上的改进,结果表明该算法减少了跨网络运营商(ISP)流量,提高了系统性能.     

Optimal adaptive bandwidth monitoring for QoS based retrieval

Network aware multimedia delivery applications are a class of applications that provide certain level of quality of service (QoS) guarantees to end users while not assuming underlying network resource reservations. These applications guarantee QoS parameters like media object transmission time limit by actively monitoring the available bandwidth of the network and adapting the object to a target size that can be transmitted within a given time limit. A critical problem is how to obtain an accurate enough estimation of available bandwidth while not wasting too much time in bandwidth testing. In this paper, we present an algorithm to determine optimal amount of bandwidth testing given a probabilistic confidence level for network-aware multimedia object retrieval applications. The model treats the bandwidth testing as sampling from an actual bandwidth population. It uses statistical estimation method to quantify the benefit of each new bandwidth-testing sample, which is used to determine the optimal amount of bandwidth testing by balancing the benefit with the cost of each sample. Our implementation and experiments shows the algorithm determines the optimal amount of bandwidth testing effectively with minimum computation overhead.     

An optimal replacement policy for repairable cold standby system with priority in use

In this article, a cold standby repairable system consisting of two nonidentical components and one repairman is studied. It is assumed that component 2 after a repair is “as good as new” while component 1 after a repair is not, but component 1 is given priority in use. Under these assumptions, by using the geometric process repair model, we consider a replacement policy N based on the number of failures of component 1 under which the system is replaced when the number of failures of component 1 reaches N. Our problem is to determine an optimal policy N* such that the long-run average cost per unit time (i.e. the average cost rate) of the system is minimized. The explicit expression of the average cost rate of the system is derived and the corresponding optimal replacement policy N* can be determined numerically. Finally, a special system with Weibull-distributed working time and repair time of component 1 is given to illustrate the theoretical results in this article.     

On-line maintenance job scheduling and assignment to resources in distributed systems by heuristic-based optimization

A heuristic-based optimization algorithm is proposed in this paper for on-line scheduling and assignment of preventive maintenance jobs to processors, to minimize under availability constraints, on a given time-window, the total cost of the maintenance operations of a distributed system. This algorithm minimizes the cost of discharge of preventive maintenance tasks or jobs, while assigning the tasks along with balancing the processors load. It is shown that the problem is NP-hard. To solve it, the concept of job emergency is introduced and the priority rule for total flow time (PRTF) criterion is used in an adapted heuristic job-scheduling model. In addition, the algorithm considers the constraints of precedence among consecutive standby jobs and their emergency. It is depicted the specific properties of the proposed heuristic allowing jobs scheduling in the right order. Computational results illustrate the efficiency of the approach implemented on different system configurations.