求解Job shop的一种快速混合算法

结合车间调度问题本身的特点,采用关键路径块邻域结构,混合禁忌搜索算法和粒子群优化算法,设计了一种快速混合调度算法.该算法对预选择的块邻域解的性能进行快速估计,对不可行解尽早舍去,大大减小了邻域解的搜索空间.仿真结果表明,该算法在求解平均时间和性能方面均具备明显优势.     

基于改进蜂群优化的图像分割算法

针对图像分割算法各个性能不均衡的问题,提出一种基于蜂群优化与多颜色空间特征提取的图像分割算法.首先,对CIE颜色空间的L分量使用Gabor滤波器提取图像的纹理特征,并且在图像的HSV颜色空间计算图像的局部一致性,共提取图像的7个特征,组成特征向量;然后,本文对蜂群搜索算法进行优化,设计了一个有效的局部搜索算法,使得蜂群可高效地收敛至较优的帕累托最优解;最终,使用改进的蜂群算法对种子区域生长法进行改进与优化,指定种子的最优位置,决定每个种子点一致性准则的最优阈值,并将多准则作为多目标优化的问题,使用蜂群优化搜索帕累托最优解,最终获得分割结果.对比实验结果表明,该分割算法的时间效率、一致性误差以及类内散布度等性能较为均衡,具有较好的实用价值.     

类进化算法驱动的动态电力经济调度优化

动态电力经济调度（Dynamic Economic Dispatch,DED）属于一种在时间和空间上相互耦合的多阶段动态决策问题,一般被转化为一个高维的约束数值优化问题来求解.本文提出了一种新型全局优化算法--类进化算法（Cluster Evolutionary Algorithm,CEA）,并将其应用于DED问题的计算.CEA通过聚类过程在进化个体间构建一定结构的连接关系,并利用这种虚拟的簇类化组织来协调和控制群体的优化计算过程,提高算法对高维问题空间的搜索效率和抗早熟能力.在仿真实验中2个DED测试系统被用于对CEA的性能进行检验,其所得最佳计算结果要好于目前已报道的最优解,而实验统计数据则显示CEA是一种求解DED问题可行且有效的方法.     

数字视频监控系统中数据的存储算法

目前视频监控系统在多路存储情况下大多采用轮巡式,该存储方式效率低下,而且存在因硬盘剩余空间不足而造成的存储异常中断等问题.文中结合实际视频监控系统,讨论了视频数据的存储算法,采用多磁盘调度算法实现了将多路存储"平均"分配于多个硬盘中,充分提高存储访问的效率;并且设计实现了定时检测增加磁盘当前剩余空间算法,保证磁盘剩余空间始终维持在一定的容量,从而很好地解决了存储异常中断的问题.     

改进蚁群算法在景区路径规划中的应用研究

随着旅游业的发展,景区的车辆调度问题也逐渐成为一项需要研究的课题,怎样使得运输成本降低且路径最优成为考虑问题的关键.本文针对旅游景区路径问题,在研究了基本的蚁群算法后,利用遗传算法快速寻找可行解并将其转换成蚁群算法的信息素,然后在蚁群算法中更改了信息素更新策略.通过实验结果表明,改进后的蚁群算法提高了寻优效率,有效的降低了运输成本.     

空间一致性约束谱聚类算法用于图像分割

近来出现的谱聚类算法在模式识别和图像分割中得到了广泛应用.与传统的聚类算法相比,谱聚类算法能在任意形状的样本空间上聚类且收敛于全局最优解.本研究从谱聚类和权核K-均值的等价性出发,基于图像的空间一致特性,提出了一种基于空间约束特性的谱聚类算法.该算法通过对加权核K-均值的目标函数加上空间一致约束项,利用近似逼近将目标函数最小化与谱聚类算法等价起来.仿真实验表明,此算法在图像分割中取得了比原始谱聚类算法更好的分割效果.     

任务可定点拆分的资源受限项目调度问题研究

任务可定点拆分的资源受限项目调度问题是标准资源受限项目调度问题的一个扩展.针对这一问题提出了一种离散人工蜂群求解算法.离散人工蜂群算法中采用基于任务排列的食物源编码方式,并提出了能够一种保证解的可行性和离散型的候选食物源生成方法.项目中允许定点拆分的任务首先要转换为满足先序关系的分任务,然后在通过串行调度机制生成可行调度.实算表明,该算法能够有效求解任务可定点拆分的资源受限项目调度问题,同时也看到在不影响完成质量情况下,项目通过任务拆分能够在一定程度上缩短项目工期.     

变邻域结构Tabu搜索算法及其在JobShop调度问题上的应用

本文针对最小化完工时间的Job Shop调度问题提出一种变邻域结构Tabu搜索算法,该算法使用的邻域结构随算法的进程而改变,不仅邻域规模小,而且仍保持了可达性这一重要的属性.对不同规模的实例进行了数值计算,计算结果表明,该算法具有非常高的效率,且初始解对算法的影响很小.     

极小化总完工时间的单机连续型批调度问题

连续型批处理机调度问题是一种新型的批调度问题,它是从钢铁工业加热炉对管坯的加热过程中提炼出来的.批的加工时间取决于该批的大小、批中工件的最大加工时间及机器的容量.本文研究了目标函数是极小化总完工时间问题,对最优解的性质进行了理论分析,提出了最优的分批策略及批间序的确定方法,给出了一个多项式可解的动态规划算法.     

基于分支定界法的相控阵雷达事件调度算法

为解决相控阵雷达事件调度问题中调度成功率、时间偏移率与算法时效性三者之间的矛盾，本文提出一种基于分支定界法的调度算法；该算法首先在现有调度结果上调取所有可执行事件，即获得若干"节点"，多步递推后由多"层"节点形成若干条备选"分支"，扩大解空间范围，提高算法性能；然后通过"删减"操作删减掉收益较低分支，将解空间控制在一适当范围内，减小搜索盲目性，降低算法计算量.仿真实验表明，与基于综合优先级算法的调度结果相比，利用本文算法调度时调度成功率提升了52%；与基于时间指针算法的调度结果相比，本身算法时间偏移率降低了61%；与基于遗传算法的调度结果相比，本文算法调度耗时仅为前者1~2%.     

Average waiting time assignment. II. The integrated servicesnetwork case

For pt.I see ibid., vol.38, p.2049-51 (Nov. 1990). Priority scheduling as a means of selectively controlling the average delay of the users in a virtual circuit integrated services network is investigated. Specifically, quantifying the end-to-end delay preferences of the users on an individual basis through associated delay cost functions, the selection of the scheduling strategies on the links of the network is formulated as a convex optimization problem whose objective consists of minimizing the overall delay cost. A set of optimality conditions is given for this problem, and two distributed algorithms for solving it are constructed. The first algorithm always converges to an optimal solution, while the second algorithm is approximate. However, the second algorithm requires less coordination than the first, and by appropriately selecting the parameters the solution can be brought as close to optimality as desired. With simple modifications, the algorithms also solve the problem of selecting the scheduling strategies on the links so as to minimize the lexicographic ordering of the cost vector     

Distributed Lifetime and Data Rate Optimization with Dynamic Approximation in Wireless Networks

In this paper, we study the problem of jointly maximizing network lifetime and data rate in wireless networks. For this problem, we introduce a general network utility maximization (NUM) cross-layer formulation that accommodates routing, scheduling and stream control from different layers of network with relevant constraints. In particular, based on both Lagrangian approach and Markov Chain Monte Carlo method, we extend our programming model to distributed algorithms that can dynamically approximate the optimal solution to this problem. Finally, we present computational results for the insight that can be gained from the cross-layer optimization and the distributed algorithms.     

QIACO:一种多QoS约束网格任务调度算法

网格环境下的任务调度问题属于NP难解,难以得到精确的最优解,适合使用蚁群算法等智能优化算法对最优解进行逼近;同时,服务质量(QoS)也是衡量网格性能的一个重要指标,网格任务调度应该满足用户的QoS需求.为解决具有QoS保证的网格任务调度问题.本文以带有Qos约束的任务为研究对象,结合改进的蚁群算法,提出了一种基于蚁群算...     

Energy-aware scheduling with probabilistic deadline constraints in wireless networks

In a shared-medium wireless network, an effective technique that allows for a tradeoff of message transmission time for energy savings is to transmit messages over multiple smaller hops as opposed to using the long direct source-destination hop. In this context, we address the problem of scheduling messages with probabilistic deadline constraints. Unlike most other works in this area, we consider the practical aspects of the erroneous channel condition and the receiver energy consumption while solving the scheduling problem. Our solution is three fold – first we prove that the problem is NP-hard. We then present an Integer Linear Program (ILP) formulation for the scheduling problem. Finally, we present efficient heuristic scheduling algorithms which minimize the energy consumption while providing the required guarantees. Our simulation studies show that the proposed heuristic algorithms achieve energy savings comparable to that obtained using the linear programming methodology under practical channel conditions.     

Deadline-aware scheduling of cooperative relayers in TDMA-based wireless industrial networks

In this paper we consider a scenario in which a set of source nodes wishes to transmit real-time data packets periodically to a central controller over lossy wireless links, while using a TDMA-based medium access control protocol. Furthermore, a number of relay nodes are present which can help the source nodes with packet retransmissions. The key question we consider in this paper is how to schedule the TDMA slots for retransmissions while taking advantage of the relay nodes, so that the average number of packets missing their deadlines is minimized. We provide a problem formulation for the general deadline-aware TDMA relay scheduling problem. Since the design space of the general problem is large, we also present one particular class of restricted TDMA relay scheduling problems. We suggest and numerically investigate a range of algorithms and heuristics, both optimal and suboptimal, of the restricted scheduling problem, which represent different trade-offs between achievable performance and computational complexity. Specifically, we introduce two different Markov Decision Process (MDP) based formulations for schedule computation of the restricted TDMA relay scheduling problem. One MDP formulation gives an optimal schedule, another (approximate) formulation gives a sub-optimal schedule which, however, comes very close to the optimal performance at much more modest computational and memory costs.     

Optimal and Approximate Mobility-Assisted Opportunistic Scheduling in Cellular Networks

This paper considers the problem of scheduling multiple users in the downlink of a time-slotted cellular data network. For such a network, opportunistic scheduling algorithms improve system performance by exploiting time variations of the radio channel. We present novel optimal and approximate opportunistic scheduling algorithms that combine channel fluctuation and user mobility information in their decision rules. The algorithms modify the opportunistic scheduling framework of Liu et al., (1993) with dynamic constraints for fairness. These fairness constraints adapt according to the user mobility. The adaptation of constraints in the proposed algorithms implicitly results in giving priority to the users that are in the most favorable locations. The optimal algorithm is an offline algorithm that precomputes constraint values according to a known mobility model. The approximate algorithm is an online algorithm that relies on the future prediction of the user mobility locations in time. We show that the use of mobility information in opportunistic scheduling increases channel capacity. We also provide analytical bounds on the performance of the approximate algorithm using the fundamental inequality of Dyer et al., (1986) for linear programs. Simulation results on high data rate (HDR) illustrate the usefulness of the proposed schemes for elastic traffic and macrocell structures     

Meta‐heuristic algorithms for channel scheduling problem in wireless sensor networks

The channel scheduling problem is to decide how to commit channels for transmitting data between nodes in wireless networks. This problem is one of the most important problems in wireless sensor networks. In this problem, we aim to obtain a near‐optimal solution with the minimal energy consumption within a reasonable time. As the number of nodes increases in the network, however, the amount of calculation for finding the solution would be too high. It can be difficult to obtain an optimal solution in a reasonable execution time because this problem is NP‐hard. Therefore, most of the recent studies for such problems seem to focus on heuristic algorithms. In this paper, we propose efficient channel scheduling algorithms to obtain a near‐optimal solution on the basis of three meta‐heuristic algorithms; the genetic algorithm, the Tabu search, and the simulated annealing. In order to make a search more efficient, we propose some neighborhood generating methods for the proposed algorithms. We evaluate the performance of the proposed algorithms through some experiments in terms of energy consumption and algorithm execution time. The experimental results show that the proposed algorithms are efficient for solving the channel scheduling problem in wireless sensor networks. Copyright © 2011 John Wiley & Sons, Ltd.     

用于资源动态预留的航天测控资源配置优化算法

针对航天测控资源配置优化问题这类约束条件繁杂且数量众多的组合优化问题,提出了可用于资源动态预留的航天测控资源配置优化算法。具体来讲,考虑测控设备和航天器执行任务的唯一性约束以及时间窗口冲突约束,建立了基于原子型任务调度的0-1整数规划模型;设计了能将实际需求和求解算法进行解耦的求解框架,并基于最大化利用测控资源的思想获得了可回溯的并行最佳优先搜索算法。仿真结果表明,所提算法达到了能在国内东部、西部、南部和北部四大测控区域中更加均衡地动态预留出更多、更重要测控设备的资源配置优化效果。     

EDA-Based Scheduling of Users in the MIMO Multiple Access Channel

In this paper, we address a user scheduling (selection) problem in the uplink multiuser multiple input multiple output (MIMO) wireless communication system. For this problem, the computational complexity of exhaustive search grows exponentially with the number of users. We present an iterative, low-complexity, sub-optimal algorithm for this problem. We apply an Estimation of Distribution Algorithm (EDA) for the user scheduling problem. An EDA is an evolutionary algorithm and updates its chosen population at each iteration on the basis of the probability distribution learned from the population of superior candidate solutions chosen at the previous iterations. The proposed EDA has a low computational complexity and can find a nearly optimal solution in real time for the user scheduling problem. Beyond applying the general EDA to user scheduling, we also present specific improvements that reduce computation for obtaining an acceptable solution. These improvements include the idea of generating an initial population by cyclically shifting a candidate solution. The simulation results show that our proposed algorithm performs better than other scheduling algorithms with comparable complexity.     

The design and implementation of real-time schedulers in RED-linux

Researchers in the real-time system community have designed and studied many advanced scheduling algorithms. However, most of these algorithms have not been implemented since it is very difficult to support new scheduling algorithms on most operating systems. To address this problem, we enhance the scheduling mechanism in Linux to provide a flexible scheduling framework. In the real-time and embedded Linux (RED-Linux) project, we implement a general scheduling framework which divides the system scheduler into two components: dispatcher and allocator. The dispatcher provides the mechanism of system scheduling and resides in the kernel space. The allocator is used to define the scheduling policy and implemented as a user space function. This framework allows users to implement application-specific schedulers in the user space which is easy to program and to debug. The framework also relieves the deficiency from the stock Linux scheduler which is not designed for real-time applications. To further enhance its power, a hierarchical scheduling mechanism has been provided in RED-Linux to allow a system designer to integrate different real-time applications together. Using scheduling groups, real-time jobs can be managed and scheduled in a hierarchical manner. In this paper, we discuss how the group mechanism is implemented in RED-Linux.