基于组合双向拍卖的云资源调度方法

针对跨数据中心的资源调度问题，提出了一种基于组合双向拍卖（PCDA）的资源调度方案。首先，将云资源拍卖分为三个部分：云用户代理报价、云资源提供商要价、拍卖代理组织拍卖；其次，在定义用户的优先级及任务紧迫度的基础上，在拍卖过程中估算每一个工作发生的服务等级协议（SLA）违规并以此计算云提供商的收益，同时每轮竞拍允许成交多项交易；最终达到根据用户等级合理分配云资源调度的效果。仿真实验结果表明该算法保证了竞拍成功率，与传统一次拍卖成交一项的组合双向拍卖方案相比，PCDA在竞拍时间段产生的能耗降低了35.00%，拍卖云提供商的利润提高了约38.84%。     

一种非对称互联型粒子群算法

提出了一种非对称互联型粒子群算法(AFIPSO),它是对互联型粒子群算法的改进。此算法重新构造了加权函数,体现了粒子之间的非对称影响。随后对六种加权函数及其4种交叉组合进行了测试。试验结果表明:组合加权函数对算法的收敛速度和稳定性均有非常好的改善,在收敛率上几近完美。     

Infinite-horizon Scheduling Algorithms for Optimal Search for Hidden Objects

This paper considers discrete search problems in which a decision-maker has to find objects lost or hidden in a given set of locations so as to minimize the expected losses incurred. Given a chance to look for a hidden object in the same location infinitely many times, this type of problem, in contrast to standard scheduling problems, has an infinite sequence as its solution. Thus we are concerned to find an algorithm that yields an optimal solution, rather than the optimal sequence itself. Using combinatorial techniques, fast optimal algorithms for solving the problems are obtained, and optimality conditions are presented for search criteria, under which the local-search algorithms yield the global optimum.     

一些有趣数列及其组合恒等式

研究了一些有趣数列的性质，同时给出了一些组合恒等式。     

Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times

In this article we study thetabu search (TS) method in an application for solving an important class of scheduling problems. Tabu search is characterized by integrating artificial intelligence and optimization principles, with particular emphasis on exploiting flexible memory structures, to yield a highly effective solution procedure. We first discuss the problem of minimizing the sum of the setup costs and linear delay penalties when N jobs, arriving at time zero, are to be scheduled for sequential processing on a continuously available machine. A prototype TS method is developed for this problem using the common approach of exchanging the position of two jobs to transform one schedule into another. A more powerful method is then developed that employs insert moves in combination with swap moves to search the solution space. This method and the best parameters found for it during the preliminary experimentation with the prototype procedure are used to obtain solutions to a more complex problem that considers setup times in addition to setup costs. In this case, our procedure succeeded in finding optimal solutions to all problems for which these solutions are known and a better solution to a larger problem for which optimizing procedures exceeded a specified time limit (branch and bound) or reached a memory overflow (branch and bound/dynamic programming) before normal termination. These experiments confirm not only the effectiveness but also the robustness of the TS method, in terms of the solution quality obtained with a common set of parameter choices for two related but different problems.     

Metaheuristic downhill simplex method in combinatorial optimization

The concept of combinatorial objects is formalized. It allows strict definition of a combinatorial optimization problem (COP). An efficient metaheuristic method to solve COPs (H-method) is considered. It includes stochastic local search algorithms as a built-in procedure. A parallel implementation of the H-method is set forth and analyzed. The results from a numerical experiment and solution of some well-known COPs on personal computers and on the SKIT cluster supercomputer are presented. The study was supported by INTAS (Project 06-1000017-8909). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–79, November–December 2007.     

An approach to automatic display layout using combinatorial optimization algorithms

The introduction of automatic display layout (ADL), i.e. the automatic placing and sizing of windows in a window-oriented graphical user interface, is a major contribution towards an improved user interface. Our approach to ADL is to treat this problem as a combinatorial optimization problem. In this article we describe the concepts we used for implementing an experimental system which controls the computer screen contents and its layout. We give two examples of different standard applications into which we included ADL successfully, namely hypertext for a window layout problem and graph-browser for a hierarchical graph layout problem within a particular window. The results show that automatic (and tool independent) display layout will be possible in the near future even in an interactive environment.     

一种嵌入式软件的组合测试指标获取方案

为了获取组合测试中适应值函数所需要覆盖率、测试运行代价等信息,设计实现了基于嵌入式软件源代码插桩的指标获取方案。该方案使用交叉开发环境,完成了对源代码语法、词法分析,插桩库和插桩策略的制定,目标机／宿主机通讯方式设计,获得了语句覆盖率、分支覆盖率、运行时间、被测程序程序复杂度等关键指标,并以图表的方式提供统计结果,为组合测试设计适应值函数,进行测试用例约减提供了依据。     

基于改进指针网络的卫星对地观测任务规划方法

针对卫星观测任务规划问题约束复杂、求解空间大和输入任务序列长度不固定的特点,使用深度强化学习（DRL）方法对卫星观测任务规划问题进行求解. 综合考虑时间窗口约束、任务间转移机动时间和卫星电量、存储约束,对卫星观测任务规划问题进行建模. 基于指针网络（PN）的运行机制建立序列决策算法模型,使用Mask向量来考虑卫星观测任务规划问题中的各类约束,并通过Actor Critic强化学习算法对模型进行训练,以获得最大的收益率. 借鉴多头注意力（MHA）机制的思想对PN进行改进,提出多头注意力指针网络（MHA-PN）算法. 根据实验结果可以看出,MHA-PN算法显著提高了模型的训练速度和泛化性能,训练好的MHA-PN算法模型可以直接对输入序列进行端到端的推理,避免传统启发式算法迭代求解的过程,具有较高的求解效率.     

基于SVM-BP神经网络的气象能见度数据缺失值预估

自动气象站能见度检测仪多采用光学装置采样,雨雪、粉尘等天气因素会对部分仪器镜头造成污染,导致能见度要素数据缺测.针对能见度数据缺失问题,本文选用安徽部分气象站的历年数据,首先运用灰色关联分析方法筛选出与能见度密切相关的其他气象要素,通过支持向量机和BP神经网络单一预估方法预估不同地形的能见度缺失值,然后采用最优权重组合将两种方法预估的能见度值进行组合,并与单一预估方法进行对比.结果表明组合方法的预估结果误差均值小、整体准确度高,可以保证台站观测资料的完备性,为短时天气预报、实况分析和气象公共服务工作提供有效依据.