基于图着色理论的最大效用频谱分配算法

研究基于图着色理论的频谱分配算法,提出一种改进的最大效用频谱分配算法。该算法生成类似于ISAA算法的用户效用矩阵和相应的干扰矩阵,选择最大效用用户或干扰值为0的用户进行频谱分配。仿真结果表明,该算法能有效减少频谱分配的时间开销,提高频谱的使用效率,最大化认知无线电系统的总效用。     

基于改进GA的救援物资中转网点定位

针对大规模救援物资调运的多目标中转运输网点定位问题,考虑运输费用、中转网点的作业变动费用和运输时间,建立一个救援物资中转运输网点的非线性多目标混合整数规划模型。为有效求解该模型,提出一种基于矩阵编码的遗传算法,利用费用矩阵标杆的寻优导向信息提高遗传变异算子的局部搜索能力,提高全局收敛速度。通过算例分析验证该模型和算法的有效性。     

基于LDA模型的新闻话题的演化

新闻话题及演化的研究可以帮助人们快速了解和获取新闻内容。提出了一种挖掘新闻话题随时间变化的方法,通过话题抽取和话题关联实现话题的演化。首先应用LDA(Latent Dirichlet Allocation Model)对不同时间段的文集进行话题的自动抽取,话题数目在不同时间段是可变的;计算相邻时间段中任意两个话题的分布距离实现话题的关联。实验结果证明该方法不但可以描述同一个话题随时间的演化过程,还可以描述话题内容随时间的变化,反映了话题(或子话题)之间多对多的演化关系。     

Inverse data envelopment analysis model to preserve relative efficiency values: The case of variable returns to scale

This paper studies the inverse Data Envelopment Analysis (inverse DEA) for the case of variable returns to scale (inverse BCC). The developed inverse BCC model can preserve relative efficiency values of all decision making units (DMUs) in a new production possibility set composing of all current DMUs and a perturbed DMU with new input and output values. We consider the inverse BCC model for a resource allocation problem, where increases of some outputs and decreases of the other outputs of the considered DMU can be taken into account simultaneously. The inverse BCC problem is in the form of a multi-objective nonlinear programming model (MONLP), which is not easy to solve. We propose a linear programming model, which gives a Pareto-efficient solution to the inverse BCC problem. However, there exists at least an optimal solution to the proposed model if and only if the new output vector is in the set of current production possibility set. The proposed approach is illustrated via a case study of a motorcycle-part company.     

Online algorithms for advance resource reservations

We consider the problem of providing QoS guarantees to Grid users through advance reservation of resources. Advance reservation mechanisms provide the ability to allocate resources to users based on agreed-upon QoS requirements and increase the predictability of a Grid system, yet incorporating such mechanisms into current Grid environments has proven to be a challenging task due to the resulting resource fragmentation. We use concepts from computational geometry to present a framework for tackling the resource fragmentation, and for formulating a suite of scheduling strategies. We also develop efficient implementations of the scheduling algorithms that scale to large Grids. We conduct a comprehensive performance evaluation study using simulation, and we present numerical results to demonstrate that our strategies perform well across several metrics that reflect both user- and system-specific goals. Our main contribution is a timely, practical, and efficient solution to the problem of scheduling resources in emerging on-demand computing environments.     

Incentive mechanism for allocating total permitted pollution discharge capacity and evaluating the validity of free allocation

In this paper, the validity evaluation method of free allocation is studied under the background of allocating the total permitted pollution discharge capacity (TPPDC). First, the free allocation method’s localization and players’ strategic behaviors are analyzed. Second, an incentive mechanism for allocating TPPDC is proposed based on the uniform price auction of divisible goods, and an evaluation model to evaluate the validity for the free allocation of TPPDC is established, and the feasibility and reasonableness of this evaluation model are proved. Third, the evaluation criterion and the evaluation process are given. Finally, this evaluation model is applied to the environmental planning of Han River basin, and the validity evaluation result of free allocation is obtained by analyzing the statistical data of chemical oxygen demand (COD) in 14 counties and cities of Hubei Province, China. The results of our study will provide the government environmental management departments with theoretical basis and scientific methods to effectively implement the pollutant gross control system and design the related environmental policies.     

Learning automata-based solutions to the optimal web polling problem modelled as a nonlinear fractional knapsack problem

We consider the problem of polling web pages as a strategy for monitoring the world wide web. The problem consists of repeatedly polling a selection of web pages so that changes that occur over time are detected. In particular, we consider the case where we are constrained to poll a maximum number of web pages per unit of time, and this constraint is typically dictated by the governing communication bandwidth, and by the speed limitations associated with the processing. Since only a fraction of the web pages can be polled within a given unit of time, the issue at stake is one of determining which web pages are to be polled, and we attempt to do it in a manner that maximizes the number of changes detected. We solve the problem by first modelling it as a stochastic nonlinear fractional knapsack problem. We then present an online learning automata (LA) system, namely, the hierarchy of twofold resource allocation automata (H-TRAA), whose primitive component is a twofold resource allocation automaton (TRAA). Both the TRAA and the H-TRAA have been proven to be asymptotically optimal. Finally, we demonstrate empirically that the H-TRAA provides orders of magnitude faster convergence compared to the learning automata knapsack game (LAKG) which represents the state-of-the-art for this problem. Further, in contrast to the LAKG, the H-TRAA scales sub-linearly. Based on these results, we believe that the H-TRAA has also tremendous potential to handle demanding real-world applications, particularly those which deal with the world wide web.     

一种求解随机有限缓冲区流水线调度的混合差分进化算法

针对随机有限缓冲区流水线调度问题(Flow shop scheduling problem, FSSP), 提出混合差分进化(Differential evolution, DE)算法OHTDE, 用来最小化提前/拖后指标和最小化总体完成时间指标. OHTDE将DE和最优计算量分配(Optimal computing budget allocation, OCBA)技术以及假设检验(Hypothesis test, HT)有效结合. DE用于执行全局搜索和局部搜索; OCBA用于对有限计算量进行合理分配, 从而保证优质解得到较多仿真计算量, 提高了在噪声环境下获得优质解的置信度; HT用于在统计意义上比较解的性能, 从而一定程度上避免在解空间相近区域进行重复搜索. 进而, 对由OCBA和HT确定的优质解执行一种特殊的交叉操作, 加强DE的局部开发能力. 同时也采用有限马氏链理论对OHTDE的随机收敛性进行了分析. 仿真实验和算法比较验证了算法的有效性和鲁棒性.     

The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach

In this paper, we consider the manpower allocation problem with time windows, job-teaming constraints and a limited number of teams (m-MAPTWTC). Given a set of teams and a set of tasks, the problem is to assign to each team a sequential order of tasks to maximize the total number of assigned tasks. Both teams and tasks may be restricted by time windows outside which operation is not possible. Some tasks require cooperation between teams, and all teams cooperating must initiate execution simultaneously. We present an integer programming model for the problem, which is decomposed using Dantzig–Wolfe decomposition. The problem is solved by column generation in a branch-and-price framework. Simultaneous execution of tasks is enforced by the branching scheme. To test the efficiency of the proposed algorithm, 12 realistic test instances are introduced. The algorithm is able to find the optimal solution in 11 of the test instances. The main contribution of this article is the addition of synchronization between teams in an exact optimization context.     

Optimal testing resource allocation during module testing considering cost, testing effort and reliability

Software reliability is one of the most important quality attributes of commercial software. During software testing, software reliability growth models (SRGMs) are commonly used to describe the phenomenon of failure occurrence and/or fault removal which consequently enhancements software reliability. Large software systems are developed by integrating a number of relatively small and independent modules, which are tested independently during module testing phase. The amount of testing resource available is limited which is desired to be consumed judiciously so as to optimize the testing process. In this paper we formulate a resource allocation problem of minimizing the cost of software testing under available amount of testing resource, given a reliability constraint. We use a flexible SRGM considering testing effort which, depending upon the values of parameters, can describe either exponential or S-shaped failure pattern of software modules. A systematic and sequential Algorithm is proposed to solve the optimization problem formulated. Numerical examples are given to illustrate the formulation and solution procedures. Sensitivity analysis is performed to examine the behavior of some parameters of SRGM with most significant influence.