Size-reduction heuristics for the unrelated parallel machines scheduling problem

In this paper we study the unrelated parallel machines problem where n independent jobs must be assigned to one out of m parallel machines and the processing time of each job differs from machine to machine. We deal with the objective of the minimisation of the maximum completion time of the jobs, usually referred to as makespan or C_max. This is a type of assignment problem that has been frequently studied in the scientific literature due to its many potential applications. We propose a set of metaheuristics based on a size-reduction of the original assignment problem that produce solutions of very good quality in a short amount of time. The underlying idea is to consider only a few of the best possible machine assignments for the jobs and not all of them. The results are simple, yet powerful methods. We test the proposed algorithms with a large benchmark of instances and compare them with current state-of-the-art methods. In most cases, the proposed size-reduction algorithms produce results that are statistically proven to be better by a significant margin.     

The kinematic design of spatial,hybrid closed chains including planar parallelograms

It is presented an integral approach for the kinematic design of spatial, hybrid closed chains which include planar parallelograms into their kinematic structure. It is based on a systematic application of recursive formulae intended for describing the evolution of screws through time. Due to the particular nature of the proposed approach, it can be closely related with Lie algebras and allows to overcome the lacking of group structure offered by a parallelogram when it is going to be considered as a component of a hybrid closed chain. Several application examples are presented in order to show the potential of the proposed approach.     

一种求解Ramsey数的DNA计算机算法

Ramsey理论是组合数学中一个庞大而又丰富的领域,在集合论、逻辑学、分析以及代数学上具有极重要的应用.Ramsey数的求解是非常困难的,迄今为止只求出9个Ramsey数的准确值.探讨了DNA生物分子超级计算在求解这一困难数学问题的可能性.将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型...     

并行入侵检测系统的预测负载均衡方法

数据流的高速化使得网络入侵检测系统(network intrusion detection system,NIDS)往往会出现严重的漏报率,并且面对某连接上突发流量的情况,基于连接的负载均衡很难做出较好的应对措施,针对该问题,提出了一种基于包预测的并行入侵检测的负载均衡方案。该方案通过观察每个探测器上数据包的进出情况,由包预测负载均衡算法预测下一个时刻各探测器上的负载情况,避免了将新连接加入到流量突发探测器的可能,提高了负载均衡的效率。仿真实验结果表明了该方案的可行性及有效性,它能有效的均衡负载,减少系统的丢包率。     

基于CUDA的泥石流模拟计算研究

针对泥石流仿真过程中海量数据计算问题,采用CUDA技术即结合CPU与GPU的优点研究了一种协同计算方法以提高数据计算效率和仿真性能。同时,搭建了基于GPU的泥石流仿真计算平台,对优化的CUDA并行计算方法进行验证。实验结果表明,该方法对海量数据的计算具有快速准确、低成本、低功耗的特点,能为灾害预测提供及时准确的决策支持,满足了高密集型计算的需求。     

Bottleneck-based heuristics to minimize total tardiness for the flexible flow line with unrelated parallel machines

This paper considers the flexible flow line problem with unrelated parallel machines at each stage and with a bottleneck stage on the line. The objective of the problem is to minimize the total tardiness. Two bottleneck-based heuristics with three machine selection rules are proposed to solve the problem. The heuristics first develop an indicator to identify a bottleneck stage in the flow line, and then separate the flow line into the upstream stages, the bottleneck stage, and the downstream stages. The upstream stages are the stages ahead of the bottleneck stage and the downstream stages are the stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage. Using the new approach, the bottleneck-based heuristics develop two decision rules to iteratively schedule the jobs at the bottleneck stage, the upstream stages, and the downstream stages. In order to evaluate the performance of the bottleneck-based heuristics, seven commonly used dispatching rules and a basic tabu search algorithm are investigated for comparison purposes. Seven experimental factors are used to design 128 production scenarios, and ten test problems are generated for each scenario. Computational results show that the bottleneck-based heuristics significantly outperform all the dispatching rules for the test problems. Although the effective performance of the bottleneck-based heuristics is inferior to the basic tabu search algorithm, the bottleneck-based heuristics are much more efficient than the tabu search algorithm. Also, a test of the effect of the experimental factors on the dispatching rules, the bottleneck-based heuristics, and the basic tabu search algorithm is performed, and some interesting insights are discovered.     

OpenMP compiler for distributed memory architectures

OpenMP is an emerging industry standard for shared memory architectures. While OpenMP has advantages on its ease of use and incremental programming, message passing is today still the most widely-used programming model for distributed memory architectures. How to effectively extend OpenMP to distributed memory architectures has been a hot spot. This paper proposes an OpenMP system, called KLCoMP, for distributed memory architectures. Based on the partially replicating shared arrays memory model, we propose ...     

RAPWBN计算模型上的快速并行归并排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出该模型上的一种并行归并排序算法,在具有N~α(1＜α＜2)个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,对长度为N的序列进行归并排序,可以在O((loglogN)~2)时间完成.     

一种面向多核系统的并行计算任务分配方法

随着多核处理器的普及,目前的大规模并行处理系统普遍采用多核处理器,这对于资源管理和调度提出了更高的要求.提出了基于共享Cache资源划分的方法,建立了面向多核处理器支持Cache资源分配的进程调度模型,设计并实现了并行任务到多核处理器的映射算法,更好地解决了大规模资源管理系统中面向多核处理器的任务分配问题,降低了使用共享Cache的多个进程运行时的相互干扰,提升了应用程序性能.     

无约束最优化问题的BFGS并行算法与实现

介绍无约束最优化问题的BFGS算法及其收敛性,提出利用行卷帘格式并行Cholesky分解法、同步并行Wolfe-Powell非线性搜索和并行处理BFGS修正公式来构建BFGS的并行算法,并对该算法的时间复杂性、加速比进行分析。在PC机群数值实验的结果表明,BFGS并行算法提高了无约束最优化问题的求解速度,理论分析与实验结果相一致,并行算法具有线性加速比。