Exact and parallel metaheuristic algorithms for the single processor total weighted completion time scheduling problem with the sum-of-processing-time based models

In this paper, the single processor scheduling problem to minimize the total weighted completion times is analysed, where the processing times of jobs are described by functions dependent on the sum of the normal processing times of previously processed jobs, which can model learning or aging (deteriorating) effects. We construct the exact pseudopolynomial time algorithm based on the dynamic programming, which solves the problem, where the processing time of each job is described by an arbitrary stepwise function. Moreover, the parallel metaheuristic algorithms are provided for the general version of the problem with arbitrary sum-of-processing time based models. The efficiency of the proposed algorithms is evaluated during numerical analysis.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

CPU/GPU 异构环境下图像协同并行处理模型

随着GPU通用计算能力的不断发展,一些新的更高效的处理技术应用到图像处理领域.目前已有一些图像处理算法移植到GPU中且取得了不错的加速效果,但这些算法没有充分利用CPU/GPU组成的异构系统中各处理单元的计算能力.文章在研究GPU编程模型和并行算法设计的基础上,提出了CPU/GPU异构环境下图像协同并行处理模型.该模型充分考虑异构系统中各处理单元的计算能力,通过图像中值滤波算法,验证了CPU/GPU环境下协同并行处理模型在高分辨率灰度图像处理中的有效性.实验结果表明,该模型在CPU/GPU异构环境下通用性较好,容易扩展到其他图像处理算法.     

分段处理的1／p概率字符串匹配

现有的概率字符串匹配算法通过计算字符串之间的最小失配字符数(编辑距离),可求出字符串之间的相似度.这些算法平等地看待模式串和文本串,虽然可求出二者之间完整的编辑距离,但并不能解决以下问题:即判断是否模式串中至少有1/p的字符顺序地出现在文本串中.基于动态规划字符串匹配算法,提出了一个改进算法.该算法通过将字符串分段,在段内执行改进的概率匹配算法可求出段内的编辑距离,再结合回溯策略可以很好地解决上述问题.该算法的复杂性要低于基本动态规划匹配算法,且在某些情况下效率更高.就问题的一般性而言,该算法可广泛地应用于计算生物学、信息安全和信号处理等诸多领域.     

基于动态双子种群的差分进化K中心点聚类算法

随着海量大数据的出现,聚类算法需要新型计算模式来提高计算速度与运行效率。本文提出一种基于动态双子种群的差分进化K中心点聚类算法DGP-DE-K-mediods(Dynamic Gemini Population based DE-K-mediods)。DGP-DE-K-mediods利用动态双子种群方法,解决聚类算法在维持种群密度的时候避免陷入局部最优的问题;采用差分进化(Differential Evolution, DE)算法来提高全局最优能力的强健性;基于Hadoop云平台来并行处理DGP-DE-K-mediods,加快算法的运行速度和效率;描述基于MapReduce的并行聚类算法的编程过程;DGP-DE-K-mediods利用UIC的大数据分类的案例数据和网络入侵检测这种大数据应用来仿真算法的效果。实验结果表明,与已有的聚类算法相比,DGP-DE-K-mediods在检测精度、运行时间上有明显的优势。     

HEART: Unrelated parallel machines problem with precedence constraints for task scheduling in cloud computing using heuristic and meta-heuristic algorithms

Cloud computing is becoming a profitable technology because of it offers cost-effective IT solutions globally. A well-designed task scheduling algorithm ensures the optimal utilization of clouds resources and reducing execution time dynamically. This research article deals with the task scheduling of inter-dependent subtasks on unrelated parallel computing machines in a cloud computing environment. This article considers two variants of the problem-based on two different objective function values. The first variant considers the minimization of the total completion time objective function while the second variant considers the minimization of the makespan objective function. Heuristic and meta-heuristic (HEART) based algorithms are proposed to solve the task scheduling problems. These algorithms utilize the property of list scheduling algorithm of unrelated parallel machine scheduling problem. A mixed integer linear programming (MILP) formulation has been provided for the two variants of the problem. The optimal solution is obtained by solving MILP formulation using A Mathematical Programming Language (AMPL) software. Extensive numerical experiments have been performed to evaluate the performance of proposed algorithms. The solutions obtained by the proposed algorithms are found to out-perform the existing algorithms. The proposed algorithms can be used by cloud computing service providers (CCSPs) for enhancing their resources utilization to reduce their operating cost.     

多目标动态规划时段轮换并行算法

针对SIMD和MIMD结构的并行机提出多目标动态规划时段轮换并行算法,多目标动 态规划的时段轮换迭代算法,将全过程优化问题转化成子过程优化问题,然后在子过程非劣解 集中寻找全过程非劣解.这样,将多目标动态规划内存不足的问题转化成时间问题,然后利用 并行机超高速运算的优势来有效地解决内存不足问题.通过时间复杂性、加速比分析及实例. 说明了算法的有效性及优越性.     

Parallel genetic algorithms: a survey and problem state of the art

In relation with development of computer capabilities and the appearance of multicore processors, parallel computing made it possible to reduce the time for solution of optimization problems. At present of interest are methods of parallel computing for genetic algorithms using the evolutionary model of development in which the main component is the population of species (set of alternative solutions to the problem). In this case, the algorithm efficiency increases due to parallel development of several populations. The survey of basic parallelization strategies and the most interesting models of their implementation are presented. Theoretical ideas on improvement of existing parallelization mechanisms for genetic algorithms are described. A modified model of parallel genetic algorithm is developed. Since genetic algorithms are used for solution of optimization problems, the proposed model was studied for the problem of optimization of a multicriteria function. The algorithm capabilities of getting out of local optima and the influence of algorithm parameters on the deep extremum search dynamics were studied. The conclusion on efficiency of application of dynamic connections of processes, rather than static connections, is made. New mechanisms for implementation and analysis of efficiency of dynamic connections for distributed computing in genetic algorithms are necessary.     

基于动态规划和遗传算法的混合算法研究

动态规划法和遗传算法是目前在水电站厂内经济运行中广泛应用的两种优化算法，文章提出了一种基于动态规划法和遗传算法的混合优化算法来分别解决大规模机组组合问题中空间最优化和时间最优化的计算机求解问题。避免了遗传算法计算速度缓慢的问题，又避免了动态规划法的“维数灾”问题。最后使用清江隔河岩水电站的4台机组的运行数据进行了仿真研究，并和完全使用动态规划法的结果进行了比较，获得了良好的效果，说明该混合优化算法对于厂内经济运行是一种可行的算法。     

基于CUDA的梯级泵站调度算法实现

动态规划方法求解梯级泵站调度问题十分经典,但在计算上存在“维数灾难”问题,GPU并行计算技术能对重复性计算进行加速,提高算法计算性能。本文对梯级泵站调度问题进行动态规划方法分析,利用CUDA（统一计算设备架构）对调度算法进行改进,给出改进动态规划方法的算法实现,并比较不同计算规模下调度算法计算耗时。实验结果表明,基于CUDA改进动态规划方法实现的梯级泵站调度算法能够降低计算维度,在计算规模较大时,加速效果较好。     

面向边缘计算的Storm边缘节点调度优化方法

边缘计算有高实时性和大数据交互处理的需求,边缘异构节点间的调度时耗长、通信时延高以及负载不均衡是影响边缘计算性能的核心问题,传统的云计算平台难以满足新的要求。文中研究了在边缘计算环境下Storm边缘节点的调度优化方法,建立了面向边缘计算的Storm任务卸载调度模型。针对拓扑任务在边缘异构节点间的实时动态分配问题,提出了一种启发式动态规划算法(Inspire Dynamic Programming,IDP),通过改变Storm的Task实例的排序分配方式以及Task实例和Slot任务槽的映射关系实现全局的优化调度;同时,针对拓扑任务的并发度受限于JVM栈深度的缺陷,提出了一种基于蝙蝠算法的调度策略。实验结果表明,与Storm调度算法相比,所提算法在边缘节点CPU利用率指标上平均提升了约60%,在集群的吞吐量指标上平均提升了约8.2%,因此能够满足边缘节点之间的高实时性处理要求。     

Fault-Tolerant Recursive Least-Squares Computations on a Mesh-Connected Parallel Processor

Recursive least squares (RLS) is a popular iterative method used for the modeling of systems while in operation. RLS provides an estimate for unknown parameters of a system based on some known parameters and inputs and outputs of that system. This technique is used frequently in digital signal processing and control applications, where it is not possible to completely determine the current state of the system. The RLS procedure incurs intensive computations in every iteration of the algorithm. To implement RLS in situ at a reasonable sampling rate, the complexity of the system's model must be reduced, or the available computing power must be increased. This paper examines methods for increasing the computing power by implementing RLS algorithms on a parallel processing platform. While there has been a large body of research on using parallel processors for the computation of adaptive algorithms, little of this research has examined fault tolerant aspects. As fault tolerance is a critical aspect of any real-time system, this work will examine some factors that should be considered when implementing a real-time adaptive algorithm on a parallel processor system.     

Single processor scheduling with job values depending on their completion times

The paper deals with a single processor scheduling problem in which the sum of values of all jobs is maximized. The value of a job is characterized by a stepwise nonincreasing function with one or more moments at which the changes of job value occur. Establishing an order of processing of datagrams which are sent by router is a practical example of application of such problems. We prove that the special case of our problem, with a single moment of change of job values, is equivalent to the well-known, NP-hard in the ordinary sense, problem of minimizing weighted number of late jobs. Next, we show that, based on this equivalence, the existing algorithms for solving the latter problem can be adopted to solve special cases of our problem. Additionally, we construct a pseudopolynomial time algorithm based on the dynamic programming method, for the case with arbitrary number of common moments of job value changes. At the end of the paper, we generalize this algorithm to the corresponding case with parallel processors. Thus, we show that these two problems are also NP-hard in the ordinary sense. Moreover, we construct exact polynomial time algorithms for two further special cases of our problem. Finally, in order to solve the general version of the problem, we construct and experimentally test a number of heuristic algorithms.     

求解多段图问题的并行动态规划算法

多段图问题是一类特殊的单源最短路径问题。在串行动态规划算法的两种实现方法的基础上,根据图中顶点的编号,提出两种在集群环境下进行任务分割的并行化求解方法,并使用MPI进行实现。实验结果表明,所提出的算法具有较高的加速比和较低的通信复杂度、时间复杂度。算法不限于某种结构的集群,通用性强。     

云平台下基于粗糙集的并行增量知识更新算法

日益复杂和动态变化的海量数据处理,是当前人们普遍关注的问题,其核心内容之一是研究如何利用已有的信息实现快速的知识更新.粒计算是近年来新兴的一个研究领域,是信息处理的一种新的概念和计算范式,主要用于描述和处理不确定的、模糊的、不完整的和海量的信息,以及提供一种基于粒与粒间关系的问题求解方法.作为粒计算理论中的一个重要组成部分,粗糙集是一种处理不确定性和不精确性问题的有效数学工具.根据云计算中的并行模型MapReduce,给出了并行计算粗糙集中等价类、决策类和两者之间相关性的算法;然后,设计了用于处理大规模数据的并行粗糙近似集求解算法.为应对动态变化的海量数据,结合MapReduce模型和增量更新方法,根据不同的增量策略,设计了两种并行增量更新粗糙近似集的算法.实验结果表明,该算法可以有效地快速更新知识;而且数据量越大,效果越明显.     

基于GPU的遥感图像配准并行程序设计与存储优化

遥感图像配准是遥感图像应用的一个重要处理步骤.随着遥感图像数据规模与遥感图像配准算法计算复杂度的增大,遥感图像配准面临着处理速度的挑战.最近几年,GPU计算能力得到极大提升,面向通用计算领域得到了快速发展.结合GPU面向通用计算领域的优势与遥感图像配准面临的处理速度问题,研究了GPU加速处理遥感图像配准的算法.选取计算量大计算精度高的基于互信息小波分解配准算法进行GPU并行设计,提出了GPU并行设计模型;同时选取GPU程序常用面向存储级的优化策略应用于遥感图像配准GPU程序,并利用CUDA(compute unified device architecture)编程语言在nVIDIA Tesla M2050GPU上进行了实验.实验结果表明,提出的并行设计模型与面向存储级的优化策略能够很好地适用于遥感图像配准领域,最大加速比达到了19.9倍.研究表明GPU通用计算技术在遥感图像处理领域具有广阔的应用前景.     

基于社会网络动态反馈的Web服务信任度计算

在当前服务计算背景下,针对用户难以获得满足需求的可信服务问题,提出基于社会网络动态反馈的Web服务信任度模型.基于用户使用经验设计服务直接信任度算法,对服务交易情况进行动态跟踪和监测.当用户缺乏使用某服务的直接经验时,基于社会网络中服务使用者信任度,聚合其他服务使用者对服务的直接信任度,计算该服务的间接信任度.采用修正因子进行修正,以提高社会网络节点及关联服务可信性.算法分析表明,该方法是可行和有效的.     

Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system

Batch processing systems are commonly used in many different environments such as chemical and semiconductor industries. In this research, a just-in-time scheduling problem in a batch processing system is investigated. Minimization of total earliness and tardiness of the jobs with respect to a common due date is considered as the objective function. First, the research problem is formulated as a mixed integer linear programming model. Then, to find the optimal schedule for a predetermined set of batches, a dynamic programming algorithm is proposed. Based on the proposed dynamic programming algorithm, several heuristics are also developed. A lower bounding method is presented, and then a branch and bound algorithm is proposed to solve the problem optimally. To demonstrate the performance of the proposed algorithms, several computational experiments are conducted.     

PRAM和LARPBS模型上的近似串匹配并行算法

近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用((m+1)个处理器和O(n/(+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.     

MPI动态负载平衡策略的研究与实现

集群环境下的并行计算越来越被广泛应用,MPI是集群系统中最重要的编程工具。在并行处理过程中,负载平衡起着很重要的作用,它直接影响到整个算法的效率。文中结合MPI编程环境下的具体特点,提出了基于负载益处估价的方法来判断是否进行任务迁移,给出了负载实时监测和调度的算法,并在每个节点机上间隔性地进行测试。最后在搭建的MPI环境下,运用并行排序方法进行了验证。实验结果表明采用负载前后有了很明显的提高,特别是随着任务量不断增大的情况下提高的效果更加明显。