运输调度问题的蚁群算法研究

蚁群算法是一种用于求解复杂组合优化的较新的启发式算法.本文简述了蚁群算法的基本原理及算法模型,通过分析研究现状指出了蚁群算法在实际应用中的局限性,最后给出解决一般运输调度问题的蚁群算法,并分析了其今后的发展方向.     

砼拌和输送浇筑生产调度模型与算法仿真研究

针对混凝土(简称砼)拌和输送浇筑系统的实际问题,在分析系统工艺特点的基础上,对实际系统进行了数学描述,提出了调度目标.通过对问题的分析,选择启发式调度算法,建立了系统的调度规则,仿真结果验证了生产调度模型和算法的有效性.     

三峡工程两坝联合通航调度的混合模拟退火算法

对三峡大坝和葛洲坝的一共5座船闸进行统一的船舶通航调度管理,是提高长江三峡水域航运能力的关键,然而其优化调度算法还缺乏必要的研究.本文首先提出了该问题的混合整数非线性规划模型,在实际通航调度环境中,该模型属于强NP-hard复杂度的大规模组合优化问题,因此设计了一种混合模拟退火算法来搜索次优化调度方案,该算法将解分解为闸次时间表和船舶调度计划两部分,在搜索过程中用启发式规则对闸次时日表进行调整,然后用深度优先搜索(DFS)算法根据闸次时间表求解船舶调度计划,最后根据Metropolis规则对当前解进行更新.针对实际通航数据的测试结果表明其优化效果明显优于原有的启发式算法.目前该算法已经成功地应用于实际的两坝联合通航调度系统中.     

应用离散事件系统控制理论求解生产调度的新方法

众所周知, 生产调度问题属组合优化问题, 一般来说不存在求得精确最优解的多项式算法. 因此, 对于大规 模调度问题, 人们应用启发式算法和元启发式算法以企求得满意解. 在实际的应用中, 许多工业过程需要满足严格 的工艺约束. 对于这类过程的调度问题, 很难应用启发式算法和元启发式算法, 因为这些方法难于保证所求得调度 的可行性. 为了解决这一问题, 本文以半导体芯片制造中组合设备的调度问题作为例子, 介绍了一种基于离散事件 系统控制理论的生产调度新方法. 利用Petri网建模, 任何违反约束的状态均被描述为非法状态, 而使非法状态出现 的调度则是不可行调度. 通过可行调度的存在性分析, 该方法获得可行解空间并将调度问题转化为连续优化问题, 从而可以有效求解. 并且指出, 该方法可以应用于其他应用领域.     

最短路径的一种搜索和记忆方法

交通运输图上最短路径计算是运输调度系统的重要问题之一,提高求解速度又是关键所在。已有算法难于实用。本文首先从人工智能启发式搜索的观点出发,提出一种启发式算法,其次对记忆和搜索方法做了初步分析,并给出了一种记忆与搜索相结合的方法。实际公路图上弧对应的耗散值(里程数)_0,目前较好的算法是E W.Dijkstra在1959年提出的,然而直接使用运算量仍较大。参照人们在使用真实地图时充分利用了位置和方向提供的信息可建立一种启发式算法。     

基于约束满足方法求解炼钢—连铸生产调度问题

针对各阶段均有并行机的炼钢—连铸生产调度问题,建立了问题的约束满足模型．通过分析炼钢—连铸调度问题特点,将其归结为最小化操作开工时间偏移的调度问题．在求解过程中,首先用变量选择和值选择启发式方法构造时间可行的初始调度,然后应用冲突检查算法检测资源冲突，基于回跳的后向修剪组合算法修复冲突,直至得到一个一致性的最终解．数据实验表明本文提出的方法是有效的.     

基于强化学习的多技能项目调度算法

多技能项目调度存在组合爆炸的现象, 其问题复杂度远超传统的单技能项目调度, 启发式算法和元启发式 算法在求解多技能项目调度问题时也各有缺陷. 为此, 根据项目调度的特点和强化学习的算法逻辑, 本文设计了基 于强化学习的多技能项目调度算法. 首先, 将多技能项目调度过程建模为符合马尔科夫性质的序贯决策过程, 并依 据决策过程设计了双智能体机制. 而后, 通过状态整合和行动分解, 降低了价值函数的学习难度. 最后, 为进一步提 高算法性能, 针对资源的多技能特性, 设计了技能归并法, 显著降低了资源分配算法的时间复杂度. 与启发式算法的 对比实验显示, 本文所设计的强化学习算法求解性能更高, 与元启发式算法的对比实验表明, 该算法稳定性更强, 且 求解速度更快.     

三维重建网格系统中资源调度的研究

网格系统中存在着大量动态、异构的资源,有效的利用这些资源可以达到提高图像三雏重构的速度的目的.设计了图像三维重建系统的资源调度结构,基于该结构提出了改进启发式调度算法,并对算法的执行过程和并行任务集的存储方法进行论述.最后,利用GridSim对调度算法进行仿真测试.仿真测试结果表明,在图像三维重建系统中,改进启发式调度算法比传统的Min-Min算法具有更高的执行效率.     

蚁群算法在服务器集群批量任务调度中的应用

服务器集群中的负载均衡和作业调度是影响系统性能的重要因素.本文描述服务器集群批量任务的作业调度问题,对该问题建立了基于图的模型.由于使用一般的启发式算法或动态规划算法解决该问题具有局限性,本文引入蚁群算法进行求解,并针对该问题具体求解提出了启发式距离合适的计算方法.最后在仿真的基础上,讨论了算法的优化效果和收敛性,结果表明蚁群算法解决该问题具有优异的性能.     

考虑能耗成本和拖期成本的非同等并行机调度

针对橡胶轮胎硫化车间能源消耗大,浪费严重的现象,提出一类考虑能耗成本与拖期成本的非等同并行机调度问题,建立基于硫化机正常运行、空闲、停机三种运行状态的能源消耗成本与拖期成本的调度模型。设计了基于优先调度规则的启发式算法、基于能耗优化的启发式算法、组合启发式算法用于模型求解,并通过仿真实验分析、比较了各种算法的有效性与适用环境。同时,仿真实验结果也表明本文提出的考虑能耗成本和拖期成本的非同等并行机调度问题具有一定的理论与实践意义。     

Application of explicit criterion minimization in adaptive control

The explicit criterion minimization (ECM) algorithm for adaptive control is investigated. From an engineering point of view, a boundedness condition based on the incremental quantity of controller parameters, Δρ, is employed in the present study. It is found that successful operation is achieved by using control amplitude constraints rather than switching between an ECM and a pole-placement algorithm, as suggested by Trulsson. To reduce the effect of disturbances, an integral term is added to the controller. With these modifications the ECM algorithm is found to perform satisfactorily. The effect of different orders of the system model and controller is discussed for a varying dead-time control system. The application of ECM on the tuning parameters of a proportional-integral-derivative (PID) controller is also presented in the paper. The ECM algorithm was also evaluated by applying this algorithm in the experiment of a pilot scale coupled-tank liquid level control system.     

考虑数据量化的改进无模型自适应迭代学习控制算法

针对一类存在数据量化的离散时间单输入单输出非线性系统,提出一种带有编码解码量化机制的无模型自适应迭代学习控制(MFAILC)算法.首先使用伪偏导数将受控非线性系统动态线性化,进而考虑系统输出数据经由均匀量化器进行量化处理的过程,并设计了一种编码解码量化机制,最后基于这种编码解码量化机制提出了一种改进的MFAILC算法.理论上给出了算法的收敛性分析,结果表明,当系统存在数据量化时,所提出的算法仍可保证系统收敛.与已有算法相比,所提算法仅利用较少的输入输出数据,就可以实现跟踪误差的零收敛.仿真进一步验证了算法的有效性.     

改进的RBF神经网络在非线性系统中的应用

在RBF神经网络的各种学习算法中,最近邻聚类算法学习时间短、计算量小,不需要事先确定隐单元的个数,完成聚类所得到的网络是最优的,并且可以在线学习,是一种自适应聚类学习算法,非常适合非线性实时系统的应用。但常规最近邻聚类算法在实时性要求较高的系统预测中学习时间相对较长。针对这一问题,提出了系统离线学习时采用减聚类算法,在线学习时采用改进的最近邻聚类算法,并变步长修正聚类半径和限制学习样本数。在函数拟合实验中,这种改进算法明显缩短了RBF神经网络的学习时间,在钢包精炼炉电极系统的在线辨识中的成功应用进一步表明对最近邻聚类算法的改进是有效的。     

Input-output block decoupling of linear time-varying singularsystems

The input-output block decoupling problem by state feedback is studied for linear time-varying singular systems. First, an algorithm, the regularization algorithm, is developed such that the system can be made by state feedback to have a unique impulse-free solution. Second, another algorithm, the block decoupling algorithm, is proposed, which provides sufficient conditions for the solvability of the input-output block decoupling problem. Then, a decoupling feedback law is constructed such that the corresponding closed-loop system is regular, impulse-free, and noninteractive. Finally, an example is given to illustrate the applicability of the algorithms     

Frequency response computation via trigonometric continued fraction

An efficient algorithm for computing the frequency response of discrete-time systems described by rational transfer functions is presented. The algorithm is simple, fast, recursive, and can be used for equally or unequally spaced frequencies. Based on an initial expansion of the system transfer function to a novel Jacobi-type trigonometric continued fraction, the algorithm proposed permits all operations to be performed by real arithmetic, guarantees real results, saves a number of operations, and produces accurate results. The algorithm is easily programmable and needs only 2nN real multiplications/divisions for evaluating the frequency response of an nth-order system at N different frequencies     

一类线性离散时间结构随机跳变系统的逼近滤波算法

提出了具有条件马尔可夫跳变结构的离散时间随机系统的条件滤波方法, 应用随机变结构系统的性质对滤波算法进行简化处理, 并将后验概率密度函数用条件高斯函数来逼近, 得到具有条件马尔可夫结构离散随机系统的逼近最优滤波算法, 最后给出滤波算法的计算步骤并仿真验证了算法的正确性.     

Model Predictive Control of Nonlinear Discrete Time Systems with Guaranteed Stability

This paper presents the design of a new robust model predictive control algorithm for nonlinear systems represented by a linear model with unstructured uncertainty. The linear model is obtained by linearizing the nonlinear system at an operating point and the difference between the nonlinear and linear model is considered as a Lipschitz nonlinear function. The controller is designed for the linear model, which fulfills the stabilization condition for the nonlinear term. Unlike previous studies that have not considered a valid Lipschitz matrix of nonlinear term in the design process, we propose an algorithm in this paper in which it is considered. Therefore, the closed loop stability of the nonlinear system is guaranteed. A novel SOS optimization problem to determine design parameters is introduced, which leads to improved closed‐loop performance in comparison to a trial and error tuning procedure. Furthermore, an algorithm is presented to enlarge the region of attraction for the nonlinear closed‐loop system. Stability is improved by checking some additional conditions if which the system may be unstable if not considered. The validity of the proposed algorithm is confirmed by examples.     

A Priority Based Distributed Deadlock Detection Algorithm

Deadlock handling is an important component of transaction management in a database system. In this paper, we contribute to the development of techniques for transaction management by presenting an algorithm for detecting deadlocks in a distributed database system. The algorithm uses priorities for transactions to minimize the number of messages initiated for detecting deadlocks. It does not construct any wait-for graph but detects cycles by an edge-chasing method. It does not detect any phantom deadlock (in the absence of failures), and for the resolution of deadlocks it does not need any extra computation. The algorithm also incorporates a post-resolution computation that leaves information characterizing dependence relations of remaining transactions of the deadlock cycle in the system, and this will help in detecting and resolving deadlocks which may arise in the future. An interesting aspect of this algorithm is that it is possible to compute the exact number of messages generated for a given deadlock configuration. The complexity is comparable to the best algorithm reported. We first present a basic algorithm and then extend it to take into account shared and exclusive lock modes, simultaneous acquisition of multiple locks, and nested transactions.     

Necessary and sufficient conditions on information for causal message ordering and their optimal implementation

Summary. This paper formulates necessary and sufficient conditions on the information required for enforcing causal ordering in a distributed system with asynchronous communication. The paper then presents an algorithm for enforcing causal message ordering. The algorithm allows a process to multicast to arbitrary and dynamically changing process groups. We show that the algorithm is optimal in the space complexity of the overhead of control information in both messages and message logs. The algorithm achieves optimality by transmitting the bare minimum causal dependency information specified by the necessity conditions, and using an encoding scheme to represent and transmit this information. We show that, in general, the space complexity of causal 0message ordering in an asynchronous system is , where is the number of nodes in the system. Although the upper bound on space complexity of the overhead of control information in the algorithm is , the overhead is likely to be much smaller on the average, and is always the least possible. Received: January 1996 / Accepted: February 1998     

操作系统微内核技术研究*

文章介绍了作者在过去5年中在微内核技术上所做的工作.给出了3个算法.① 通过将任务调度和线程调度算法相结合的方法，来解决单纯以线程为单位的调度系统的效率和公平性问题；② 一个改进的写时拷贝算法，它结合写时拷贝算法和访问时拷贝算法的优点，来解决写时拷贝算法在I386体系结构上的适应性问题；③ 提出了一个微内核操作系统计时模型，它解决了传统计时算法在微内核系统中计时不准确的问题.