三峡-葛洲坝联合调度系统闸室编排快速算法

三峡—葛洲坝两坝联合调度系统是用于提高三峡—葛洲坝航道通航能力的一套系统。两坝联合调度的计划编排是一个与闸室编排相耦合的时间表问题。闸室编排可以用二维Packing模型来描述,是一个典型NP完全问题。提出一种基于分步降维思想的启发式快速编排算法,该算法把闸室编排二维Packing问题降到一维求解,有效解决三峡-葛洲坝联合调度的计划编排中与闸室编排相耦合的时间表问题。该算法在实际工程应用中取得了良好的效果,有效地提高了闸室面积利用率。     

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

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

Xen虚拟机的虚拟CPU松弛协同调度方法

目前,Xen虚拟机调度算法均采用独立调度虚拟CPU的方式,而没有考虑虚拟机各虚拟CPU之间的协同调度关系,这会使虚拟机各个虚拟CPU之间产生很大的时钟中断数量偏差等问题,从而导致系统不稳定.为了提高系统的稳定性,基于Credit算法提出了一种比RCS(relaxed co-scheduling)算法更松弛的协同调度算法MRCS(more relaxed co-scheduling).该算法采用非抢占式协同调整方法将各个虚拟CPU相对运行的时间间隔控制在同步时间检测的上限门限值Tmax之内,同时利用同步队列中虚拟CPU优化选择调度方法和Credit算法的虚拟CPU动态迁移方法,能够更加及时地协同处理虚拟CPU,并且保证了各个物理CPU的负载均衡,有效地减少客户操作系统与VMM的环境切换次数,降低了系统开销.实验结果证明该方法不但保证了系统的稳定性,而且使系统性能得到一定程度的提升.虚拟机调度算法不仅影响虚拟机的性能,更会影响虚拟机的稳定性,致力于虚拟机调度算法的研究是一项非常有意义的工作.     

Optimisation schemes to improve hybrid co-scheduling for concurrent virtual machines

Hybrid co-scheduling (CS) is an effective approach to address the synchronisation problems for concurrent virtual machines such as lock-holder preemption. However, the scheduling gaps and fragments in hybrid CS cause a serious performance degradation and unfairness if multiple concurrent domains exist. We propose three optimisation schemes for such problems named partial co-scheduling (PCS), boost co-scheduling (BCS) and precise boost co-scheduling (PBCS) using finer space granularity. PCS scheme activates the CS signals only for the indispensable central processing units (CPUs) instead of all online CPUs. BCS scheme boosts the priorities for co-scheduled virtual CPUs (VCPUs) to induce the scheduler to pick the appropriate VCPUs. PBCS combines PCS and BCS to achieve better performance and robustness. We implement three optimisations into Credit Scheduler in Xen 4.0.1. The experimental results show that our schemes achieve better performance and fairness compared to existing hybrid CS under different scenarios.     

Optimizing resource speed for two-stage real-time tasks

Multiple resource co-scheduling algorithms and pipelined execution models are becoming increasingly popular, as they better capture the heterogeneous nature of modern architectures. The problem of scheduling tasks composed of multiple stages tied to different resources goes under the name of “flow-shop scheduling”. This problem, studied since the ‘50s to optimize production plants, is known to be NP-hard in the general case. In this paper, we consider a specific instance of the flow-shop task model that captures the behavior of a two-resource (DMA-CPU) system. In this setting, we study the problem of selecting the optimal operating speed of the two resources with the goal of minimizing power usage while meeting real-time schedulability constraints. In particular, we derive an algorithm that finds the optimal speed of one resource while the speed of the other resource is kept constant. Then, we discuss how to extend the proposed approach to jointly optimize the speed of the two resources. In addition, applications to multiprocessor systems and energy minimization are considered. All the proposed algorithms run in polynomial time, hence they are suitable for online operation even in the presence of variable real-time workload.     

Co-scheduling algorithms for high-throughput workload execution

This paper investigates co-scheduling algorithms for processing a set of parallel applications. Instead of executing each application one by one, using a maximum degree of parallelism for each of them, we aim at scheduling several applications concurrently. We partition the original application set into a series of packs, which are executed one by one. A pack comprises several applications, each of them with an assigned number of processors, with the constraint that the total number of processors assigned within a pack does not exceed the maximum number of available processors. The objective is to determine a partition into packs, and an assignment of processors to applications, that minimize the sum of the execution times of the packs. We thoroughly study the complexity of this optimization problem, and propose several heuristics that exhibit very good performance on a variety of workloads, whose application execution times model profiles of parallel scientific codes. We show that co-scheduling leads to faster workload completion time (40 % improvement on average over traditional scheduling) and to faster response times (50 % improvement). Hence, co-scheduling increases system throughput and saves energy, leading to significant benefits from both the user and system perspectives.     

虚拟机协同调度问题研究

由于虚拟化技术能对多个服务有效隔离避免其相互间干扰而得到广泛应用。对于需要多个服务协同工作的大型应用,传统虚拟机监控器调度时忽视了虚拟机间的协同性,降低了虚拟机间并行工作的可能性,从而影响了服务质量。对虚拟机的协同调度进行研究,分析了调度对虚拟机协同性及服务质量的影响,提出了一种虚拟机协同调度算法。实验表明,协同调度使虚拟化平台服务器响应时间降低了1/3,且没有对调度的公平性造成明显影响。     

Discrete multi-objective artificial bee colony algorithm for green co-scheduling problem of ship lift and ship lock

This paper investigates a multi-objective green co-scheduling problem of ship lift and ship lock (GCP-SL&SL) at the Three Gorges Cascade Hub (TGCH). A mathematical model of GCP-SL&SL with objectives of the average utilizations rate of the lock chamber, average waiting time and total energy consumption of vessels, is proposed by separating it into three sub-problems: the facility assignment, lockage assignment and lockage operation scheduling. To solve this problem, a discrete multi-objective artificial bee colony (DMOABC) algorithm is developed. Within the DMOABC, a two-dimensional matrix encoding scheme is designed to encode and a group right-shift decoding scheme is specifically proposed to decode each food source. Then, a novel fitness evaluation mechanism based on fuzzy relative entropy is introduced to hand this multi-objective problem. Next, the food sources are improved from three aspects: (1) the employed bee phase uses new evolutionary operators for fast local search; (2) the onlooker bee phase adopts a modified tabu search for strong global search; (3) the scout bee phase embeds chemical reaction optimization for disturbing population. Finally, extensive experiments are conducted with the real data from historical traffic at TGCH. The results demonstrate our proposed algorithm is significantly better at solving the GCP-SL&SL than other five well-known multi-objective algorithms. The effect analysis under different scenarios indicates that the average waiting time of vessels at the dam is greatly reduced because of considering the synchronous moving process.     

面向水生态的闸坝调度方法

淮河流域是我国水环境治理的重点之一.由于淮河流域水情复杂,所以容易发生水污染事件.本文立足于突发水污染情况,研究如何调动闸坝和水库的生态用水并在最短时间内初步治理水污染问题.闸坝调度问题是组合优化问题,水资源调度效率为目标函数,约束条件包括蓄水、水中物质浓度和闸坝距离等.本文采用人工鱼群调度算法（AFSA）,并加以约束条件,满足治水需求.人工鱼群算法有快速的跟踪变化和跳出局部极值的优点,能避免算法初期早熟的问题.实验结果表明,基于人工鱼群算法的生态水调度方法,在处理这类问题,不仅精确有效,并且能在较少的迭代次数内找到满意解,具有很高的可行性,参考性.     

Structural Properties,LQG Control and Scheduling of a Networked Control System with Bandwidth Limitations and Transmission Delays

The problem of simultaneous LQG control and scheduling of a Networked Control System (NCS) with constant network induced delays at input and output and bandwidth limitations is investigated. Delays are considered at plant as well as controller side. Sufficient conditions for controllability, stabilizability, reconstructibility and detectability of the underlying networked control system are drawn. The proposed conditions extend previous works on structural properties of NCS by capturing both plant and controller side delays together with bandwidth limitations. A framework for computing the optimal LQG controller for the NCS with a fixed scheduling is provided. The proposed modeling approach facilitates use of LQG as well as other control methods for NCSs with delays and bandwidth limitations. In order to optimize performance, a semi-online scheduling procedure is proposed based on an offline look up table. The look up table assigns an optimal schedule with associated optimal LQG controller to initial conditions. The proposed scheme improves previous results by online deployment of schedule and LQG control with stability guarantees and very low computational overhead. A simulation example with communication delays, packet losses and bandwidth limitations in both sensor and actuator sides is included. Static optimal periodic communication sequence, Optimal Pointer Placement (OPP) approach proposed in previous works, a random access scheduling method representing contention based access policies and the proposed method are simulated and compared.      

Hybrid Scheduling and Quantized Output Feedback Control for Networked Control Systems

A novel co-design scheme of hybrid scheduling strategy, adaptive logarithmic quantizer and dynamic robust H-infinity output feedback controller for a class of networked control system (NCS)with communication constraints and time delay is proposed. The hybrid scheduling scheme integrates dead zone scheduling and Try Once Discard (TOD) scheduling so as to get the stronger adaptability and flexibility than the single scheduling. In this scheme, dead zone scheduling which updates the threshold according to mode-dependent control strategy is used for single node of NCS to reduce the network bandwidth utilization while TOD scheduling is used for the whole node of NCS in order to meet the requirements of communication constraints and guarantee the overall system performance.We develop the integrated design for the hybrid scheduling strategy, adaptive quantizer and dynamic robust output feedback controller to maintain asymptotic stability of the closed-loop NCS by using the multiple-Lyapunov function and switched system theory. The proposed method can improve the the quality of service (QoS) meanwhile ensure the quality of control (QoC) of overall systems, which make a better trade-off between network utilization and control performance. An simulation example demonstrates the efficiency of the proposed method.     

Coordinated optimized scheduling of locks and transshipment in inland waterway transportation using binary NSGA‐II

Traffic congestion in inland waterways caused by insufficient throughput capacity of locks has become a compelling problem in developed inland shipping countries. In order to avoid excessive time wasted in waiting for lock service, it is suggested that some types of cargoes should be unloaded at the quays and transported by road/train to their destinations, which is called water–land transshipment. By this means, the ships are divided into two groups that either pass the lock or are transshipped at the quays, engendering the lock and water–land transshipment co‐scheduling (LWTC) problem. This paper focuses on the LWTC, where the roll‐on roll‐off ships, passenger ships, and general cargo ships that can be transshipped and other ships that can only pass the lock are considered in a lock‐quay co‐scheduling system. The LWTC problem is decomposed into an outer‐layer main 0‐1 optimization problem and two inner‐layer subproblems: lock scheduling and berth allocation. A multiobjective optimization model is proposed for the LWTC problem based on its two‐layer structure. To solve the LWTC problem, a hybrid heuristic method is proposed, where a modified binary nondominated sorting genetic algorithm II is proposed to solve the main problem, and the two subproblems are solved by specific heuristics. The proposed model and hybrid method are tested on instances extracted from historical data of traffic at Three Gorges Dam, the results of which demonstrate the feasibility of the model and the superiority of the proposed hybrid heuristic method over other comparisons.     

SCHEDULING AND CONTROL CO‐DESIGN FOR DELAY COMPENSATION IN THE NETWORKED CONTROL SYSTEM

The networked control system (NCS) is currently receiving increasing attention from researchers. Researches on this subject, however, have not considered the co‐design of network quality of service (QoS) and control quality of performance (QoP). This paper proposes a novel NCS design framework based on scheduling and control co‐design to compensate for random network‐induced delays. In the framework, a scheduling algorithm used to find the optimal sampling regions of control loops performs rough adjustment and guarantees the network QoS, while a novel adaptive fuzzy PID controller is designed to perform accurate adjustment to guarantee the control QoP. Practical application results obtained with a multi‐loop NCS show that the framework can ensure satisfactory performance due to its robustness against network uncertainty.     

Bandwidth allocation and scheduling of networked control systems with exponential and quadratic approximations

This paper investigates bandwidth allocation and scheduling of networked control systems (NCSs) with nonlinear-programming techniques. The bandwidth utilization (BU) is defined in terms of sampling frequency. An exponential and a quadratic approximation are formulated to describe system performance versus the sampling frequencies. The optimal sampling frequencies are obtained by solving the approximations with Karush–Kuhn–Tucker (KKT) conditions. Experimental results verify the effectiveness of the proposed approximations and scheduling algorithms. The two approximations could find an optimal BU of an NCS with a given sequence of plants and maximize the total BU up to 98% of the total available bandwidth.     

基于MVC模式的三峡通航数据维护系统的实现

三峡-葛洲坝联合调度系统是保证葛洲坝和三峡船闸调度顺利进行的关键,系统要求有较好的安全性、实时性和分布式结构。针对系统性能要求,采用Hibernate2,WebWork2.1等多种技术,设计并在J2EE平台实现了一个采用MVC模式的三峡船闸调度系统中的通航数据维护系统。这种设计模式使系统结构层次清晰,各部分模块划分明确。文中还用系统中的实例介绍了Hibernate映射Oracle关系数据库、DAO模式实现对数据模型的透明访问等关键技术。实际应用证明采用B/S模式更能适应联合调度系统的数据维护需要,数据完整性和实时性都得到了良好的保证。     

一种网格环境下的资源协同调度算法

基于传统的DAGs调度算法,提出了一种适于网格环境下使用的协同调度算法,目标是使得一组应用程序的整体执行时间最小,并且算法中提供了对资源的提前预约的支持。模拟结果表明,该算法与传统的调度算法相比,性能有了较大的提高 。     

分布式网络化控制系统优化协同设计

网络化控制系统的性能不仅与控制器的设计有关还与网络QoS有密切的联系;针对基于CAN总线协议的多闭环控制系统共享网络带宽的控制与资源调度协同设计问题,首先给出连续控制系统性能指标与传输延迟、采样周期的近似线性关系,然后以此为目标函数,以不可抢占RM可调度性和控制系统稳定性为约束条件,分配网络带宽,使控制系统整体性能最优,并对得到的传输周期进行谐调化处理,提高网络利用率;采用资源预留方法在不影响周期数据实时性的前提下,保证非周期数据的平均响应时间;最后将协调设计结果应用于某基于CANopen协议的分布式控制实验系统,控制3组倒立摆,通过研究脉冲响应并已有的调度策略比较说明了所提出策略可以有效提高控制系统性能及带宽利用率.     

基于Matlab环境的网络控制系统仿真平台

网络控制系统NCS(NetworkedControlSystem)是一种分布式实时控制系统,网络控制系统的设计与研究涉及系统控制与网络调度两个方面,目前集成的控制与调度仿真工具很少。该文对网络控制系统的仿真平台进行了分析,给出了Matlab构建的网络控制系统框架,分析了网络控制系统仿真模型,介绍了一种基于Matlab的网络控制系统的理想仿真工具TrueTime。     

Predicting dam failure risk for sustainable flood retention basins: A generic case study for the wider Greater Manchester area

This study aims to provide a rapid screening tool for assessment of sustainable flood retention basins (SFRBs) to predict corresponding dam failure risks. A rapid expert-based assessment method for dam failure of SFRB supported by an artificial neural network (ANN) model has been presented. Flood storage was assessed for 110 SFRB and the corresponding Dam Failure Risk was evaluated for all dams across the wider Greater Manchester study area. The results show that Dam Failure Risk can be estimated by using the variables Dam Height, Dam Length, Maximum Flood Water Volume, Flood Water Surface Area, Mean Annual Rainfall (based on Met Office data), Altitude, Catchment Size, Urban Catchment Proportion, Forest Catchment Proportion and Managed Maximum Flood Water Volume. A cross-validation R² value of 0.70 for the ANN model signifies that the tool is likely to predict variables well for new data sets. Traditionally, dams are considered safe because they have been built according to high technical standards. However, many dams that were constructed decades ago do not meet the current state-of-the-art dam design guidelines. Spatial distribution maps show that dam failure risks of SFRB located near cities are higher than those situated in rural locations. The proposed tool could be used as an early warning system in times of heavy rainfall.     

网络控制系统的性能优化研究

网络控制系统(NCS)是基于网络的分布式控制系统。文章结合网络调度和系统控制,以网络的可调度性和系统稳定性为约束条件,给出了NCS的性能优化模型,并利用基于Matlab/Simulink的实时控制系统仿真软件包True Time对其进行了仿真。仿真结果表明:该方法既提高了控制系统的性能,又优化了网络调度性能,提高了网络资源的利用率。