Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time

This paper extends the algorithms which were developed in Part I to cases in which there is no affine schedule, i.e. to problems whose parallel complexity is polynomial but not linear. The natural generalization is to multidimensional schedules with lexicographic ordering as temporal succession. Multidimensional affine schedules, are, in a sense, equivalent to polynomial schedules, and are much easier to handle automatically. Furthermore, there is a strong connection between multidimensional schedules and loop nests, which allows one to prove that a static control program always has a multidimensional schedule. Roughly, a larger dimension indicates less parallelism. In the algorithm which is presented here, this dimension is computed dynamically, and is just sufficient for scheduling the source program. The algorithm lends itself to a divide and conquer strategy. The paper gives some experimental evidence for the applicability, performances and limitations of the algorithm.     

实验室排课系统开发与使用

实验室是学生实践实验的必要场所,但是所有高校都会面临着实验室少,学生人数多,如何更好分配实验室的使用,是实验室管理人员值得考虑的首要问题。针对此问题,本院校实验室结合自己实验室的真实情况编写实验室排课系统。     

栅栏覆盖最大化生存周期调度算法

栅栏覆盖是近年来无线传感器网络的研究热点之一,如何延长生存周期是无线传感器网络研究的一个重要问题。针对无线传感器网络的栅栏覆盖应用,设计了两种最大化网络生存周期的调度算法:集中式的Greedy调度算法和分布式的DBCS调度算法。仿真实验表明:两种算法显著地延长了网络的生存周期;在较稀疏的网络中,DBCS算法与Greedy算法性能接近,分布式的DBCS算法适合应用于大规模传感器网络。     

高风电渗透率下考虑需求侧管理策略的智能微电网调度方法

提出了一种高风电渗透率下考虑需求侧管理策略的智能微电网调度方法。首先,考虑经济、环境成本指标、清洁能源就地消纳量以及可中断负荷和可转移负荷策略,建立了多目标优化调度模型。然后,引入ε约束法生成Pareto前沿解集,利用归一化方法求出最优折衷解。最后,基于24节点配电系统对所提方法进行分析验证。算例结果表明:建立的多目标优化模型能够有效提升清洁能源的消纳率,提高调度方案经济性,同时有效降低发电污染排放。采用的需求侧管理策略能够有效平抑负荷波动,达到削峰填谷的目的。     

基于可行空间并行的安全约束最优潮流

为了提高电网控制决策的实时性,文中将计及预想故障安全约束的经济性优化问题分解为以发电成本最小为目标的基态最优潮流主问题和预想故障安全校核子问题,并提出一种基于可调空间切片并行的分解协调算法进行求解,以避免交替迭代。首先,按不同比例对可调空间进行切片形成多个切片方案,并基于并行计算平台采用原始-对偶内点法对各切片方案进行基态最优潮流主问题求解;然后,对各优化后方式进行预想故障并行安全校核;接着从通过安全校核的切片方案中挑选出发电成本最小的方案;最后,以贵州省某市电网为算例分析验证了所提方法的有效性。     

微电网跟踪调度计划双层双时间尺度实时控制策略

为了提升微电网跟踪调度计划的能力,并降低分布式电源和负荷的功率波动对跟踪效果的影响,提出一种利用由超级电容和电池储能组成的混合储能系统跟踪调度计划的双层双时间尺度实时控制策略。上层基于模型预测控制方法建立日内滚动优化模型,结合分布式电源和负荷的超短期功率预测结果,综合考虑一段时域内的跟踪偏差及混合储能系统的功率和荷电状态对跟踪调度计划进行滚动优化;下层在上层优化结果的基础上,采用基于荷电状态的混合储能系统实时控制策略对超级电容和电池储能的实时功率进行协调分配,进一步降低分布式电源和负荷的实时功率波动对跟踪效果的影响。通过仿真算例对所提控制策略进行验证,结果表明:所提策略不但实现了良好的实时跟踪调度计划的控制效果,而且优化了超级电容和电池储能的荷电状态。     

计及风电置信风险的源网协调多目标优化调度

为了更为合理灵活地评估风电高估/低估给电力系统优化调度带来的风险性以及降低调度决策的保守性,基于风电机会约束提出风电高估/低估置信风险功率偏差量化计算方法,并在决策变量中引入变压器变比调节和无功补偿容量优化,构建计及风电置信风险和源网协调运行的经济/风险多目标优化调度模型。提出一种基于可行性和非劣性综合排序回溯搜索算法,从而实现对调度模型的高效准确求解。IEEE 30节点系统算例结果验证了所提方法的有效性和优越性。     

基于模型的子空间聚类与时间段蚁群算法的合同生产批量调度方法

针对目前冷轧薄板厂生产流程复杂、大量的多品种小批量合同并线生产,导致难以制定生产计划的问题,本文提出了混合模型子空间聚类（Subspace clustering mixed model,SCMM）方法,以合同中待加工钢卷的宽度、冷轧机组的入口厚度、 出口厚度以及合同的交货期为约束,对待生产合同进行组批. 依据冷轧厂实际生产过程,将冷轧机组视为核心节点,考虑准时交货、 在制品库存和生产流向产能分配的要求,对组批后的生产合同建立全流程合同计划模型,并且利用提出的时间段蚁群算法（Time-section ant colony optimization,TSA）,制定合同计划.利用生产过程的实际数据测试,本文的方法优于人工排产,可以满足制定冷轧薄板全流程生产计划的要求.     

Single-machine parallel-batching scheduling with family jobs to minimize weighted number of tardy jobs

We consider the problem of scheduling n jobs in batches on a single parallel-batching machine, where the jobs are partitioned into jobs families and the jobs in each family have the same due date. The objective is to minimize the weighted number of tardy jobs. We first devise an efficient pseudo-polynomial time and a fully polynomial time approximation scheme for the weighted problem. Then we present $O(n^2)$-time and $O(n\log n)$-time algorithms for the case where the jobs have the same weight and for the case where the jobs have the same processing time, respectively.     

Efficient fault-tolerant collision-free data aggregation scheduling for wireless sensor networks

This paper investigates the design of fault-tolerant TDMA-based data aggregation scheduling (DAS) protocols for wireless sensor networks (WSNs). DAS is a fundamental pattern of communication in wireless sensor networks where sensor nodes aggregate and relay data to a sink node. However, any such DAS protocol needs to be cognisant of the fact that crash failures can occur. We make the following contributions: (i) we identify a necessary condition to solve the DAS problem, (ii) we introduce a strong and weak version of the DAS problem, (iii) we show several impossibility results due to the crash failures, (iv) we develop a modular local algorithm that solves stabilising weak DAS and (v) we show, through simulations and an actual deployment on a small testbed, how specific instantiations of parameters can lead to the algorithm achieving very efficient stabilisation.