一种实用的所有点对之间最短路径并行算法

针对有向图中每对顶点之间的最短路径问题,在基于扩充了路径矩阵的串行Floyd算法上,提出了二维网格结构上的并行算法。选用的任务划分方法为二维均匀块分配方法。该并行算法已经在NOW上的MPI平台上实现,理论分析和数值实验表明它具有较高的扩展性和并行效率。     

Research on the Optimal Parallel Algorithms of Broadcast-Class Problems

Speedup is considered as the criterion of determining whether a parallel algorithm is optimal.But broadcast-class problems,existing only on parallel computer system,have no sequential algorithms at all.Speedup standard becomes invalid here.Through this research on broadcast algorithms under several typical prallel computation models,a model-independent evaluation standard min C^2 is developed,which can be not only used to determine an optimal broadcasting algorithm,but also normalized to apply to any parallel algorithm.As a new idea,min C^2 will lead to a new way in this field.     

解不同交货期并行机调度问题的并行遗传算法

为有效地解决不同交货期窗口下的非等同并行多机提前/拖后调度问题,设计了一种分段编码的混合遗传算法。此编码方式能反映工件的分配序列,并利用调度优先级规则和最好适应值规则相结合的启发式算法对其顺序进行了调整,加快了收敛速度。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于遗传算法,有着较高的并行性,并能适用于大规模不同交货期窗口下非等同并行多机提前/拖后调度问题。     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。     

Optimizing layer‐based scheduling algorithms for parallel tasks with dependencies

Programming with parallel tasks leads to task graphs with dependencies representing a parallel program. Scheduling algorithms are employed to find an efficient execution order of the parallel tasks. A large variety of scheduling algorithms exist, including layer‐based scheduling algorithms for homogeneous target platforms that build consecutive layers of independent parallel tasks and schedule each layer separately. Although these scheduling algorithms provide good results in terms of scheduling algorithm runtime and schedule execution time, the resulting schedules leave room for optimization. This article proposes an optimization for arbitrary layer‐based scheduling algorithms, which is called Move‐blocks algorithm. Given a layer‐based schedule of the parallel tasks, this algorithm moves blocks of parallel tasks into preceding layers in order to reduce the overall execution time of a task‐based application. Suitable blocks of parallel tasks are identified by the algorithm Find‐blocks, which is employed together with the Move‐blocks algorithm. The algorithm Move‐blocks is applied to four well‐known scheduling algorithms. A detailed evaluation for a wide range of test cases is given. Copyright © 2010 John Wiley & Sons, Ltd.     

Soft computing for scheduling with batch setup times and earliness-tardiness penalties on parallel machines

A model for scheduling grouped jobs on identical parallel machines is addressed in this paper. The model assumes that a set-up time is incurred when a machine changes from processing one type of component to a different type of component, and the objective is to minimize the total earliness-tardiness penalties. In this paper, the algorithm of soft computing, which is a fuzzy logic embedded Genetic Algorithm is developed to solve the problem. The efficiency of this approach is tested on several groups of random problems and shows that the soft computing algorithm has potential for practical applications in larger scale production systems.     

Heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties

In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose several dispatching heuristics, and analyse their performance on a wide range of instances. The heuristics include simple and widely used scheduling rules, as well as adaptations of those rules to a quadratic objective function. We also propose heuristic procedures that specifically address both the earliness and the tardiness penalties, as well as the quadratic cost function. Several improvement procedures were also analysed. These procedures are applied as an improvement step, once the heuristics have generated a schedule.     

Two branch-and-bound algorithms for the robust parallel machine scheduling problem

Uncertainty is an inevitable element in many practical production planning and scheduling environments. When a due date is predetermined for performing a set of jobs for a customer, production managers are often concerned with establishing a schedule with the highest possible confidence of meeting the due date. In this paper, we study the problem of scheduling a given number of jobs on a specified number of identical parallel machines when the processing time of each job is stochastic. Our goal is to find a robust schedule that maximizes the customer service level, which is the probability of the makespan not exceeding the due date. We develop two branch-and-bound algorithms for finding an optimal solution; the two algorithms differ mainly in their branching scheme. We generate a set of benchmark instances and compare the performance of the algorithms based on this dataset.     

A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties

In this paper, we consider the k-prize-collecting minimum vertex cover problem with submodular penalties, which generalizes the well-known minimum vertex cover problem, minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties. We are given a cost graph G=(V,E;c) and an integer k. This problem determines a vertex set S\subseteq V such that S covers at least k edges. The objective is to minimize the total cost of the vertices in S plus the penalty of the uncovered edge set, where the penalty is determined by a submodular function. We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem. When the submodular penalty cost function is normalized and nondecreasing, the proposed algorithm has an approximation factor of 3. When the submodular penalty cost function is linear, the approximation factor of the proposed algorithm is reduced to 2, which is the best factor if the unique game conjecture holds.     

Dispatching heuristics for the single machine early/tardy scheduling problem with job-independent penalties

In this paper, we consider the single machine earliness/tardiness scheduling problem with job-independent penalties, and no machine idle time. Several dispatching heuristics are proposed, and their performance is analysed on a wide range of instances. The heuristics include simple scheduling rules, as well as a procedure that takes advantage of the strengths of each of those rules. We also consider early/tardy dispatching procedures, and a heuristic method based on existing adjacent precedence conditions. An improvement procedure that can be used to improve the schedules generated by the heuristics is also proposed.

The computational tests show that the best results are given by the early/tardy dispatching rules. These heuristics are also quite fast, and are capable of quickly solving even very large instances. The use of the improvement procedure is recommended, since it improves the solution quality, with little additional computational effort.     

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。     

一种基于k-均值的DBSCAN算法参数动态选择方法

为解决DBSCAN聚类算法的Eps及MinPts参数选择问题,提出一种领域无关的参数动态选择方法。首先,基于k-均值算法对数据集进行初步聚类,聚类中采用最大最小距离方法确定初始聚类中心。其次,针对k-均值聚类结果,计算统计各聚类中样本间距离的分布情况,选择使得具有最大样本对数的距离值作为对应类的Eps值,并通过Eps获得MinPts值。最后,对DBSCAN算法进行改进,使其可根据当前核心点所属k-均值聚类对应的Eps对其运行值进行自适应调整。将上述思想运用于未知协议条件下的比特流聚类分析,结果表明,在无需用户指定Eps及MinPts的条件下,即可获得满意的聚类结果,提高了算法的适用性和准确率。     

蚁群算法求解非等同并行机调度问题的研究

针对非等同并行机服务调度问题,以机场除冰调度服务为背景并以最小化旅客延误数为目标,提出了一种改进的蚁群算法。该算法根据调度模型的特点,充分考虑模型的约束条件并运用了一种改进的信息素更新策略求解并行机调度问题。仿真结果表明,改进的蚁群算法收敛速度快且结果较优,明显优于FIFO算法,适合求解非等同并行机调度问题。     

工厂地址集中的k-种产品选址问题的近似算法

k-种产品工厂选址问题是：给定一个客户集合和一个可以建立工厂的地址集合,每个客户需要k-种产品,一个工厂只能为客户提供一种产品。考虑的工厂假设相对集中,即假设任何工厂之间的距离都不大于工厂与客户之间的距离。对于没有建厂费用的问题,当k=2时证明了它是一个NP完全问题,对任意的k给出了一个最坏性能比不大于2-1/k的近似算法。对于有建厂费用的问题,给出了一个最坏性能比不大于2的近似算法。     

Symplectic algorithms with mesh refinement for a hypersensitive optimal control problem

A symplectic algorithm with nonuniform grids is proposed for solving the hypersensitive optimal control problem using the density function. The proposed method satisfies the first-order necessary conditions for the optimal control problem that can preserve the structure of the original Hamiltonian systems. Furthermore, the explicit Jacobi matrix with sparse symmetric character is derived to speed up the convergence rate of the resulting nonlinear equations. Numerical simulations highlight the features of the proposed method and show that the symplectic algorithm with nonuniform grids is more computationally efficient and accuracy compared with uniform grid implementations. Besides, the symplectic algorithm has obvious advantages on optimality and convergence accuracy compared with the direct collocation methods using the same density function for mesh refinement.     

三层并行遗传算法及装箱问题中的应用

提出了一个新的基于线程构建模块(TBB)的三层并行遗传算法(TPGA)。与传统遗传算法相比,在保证了算法正确性的前提下提高了运行效率,并将遗传算法的数据编码、任务处理和数据解码分别进行并行化,提高了收敛速度。TBB是Intel提供的能够完整表现并行性的代码库。采用C++语言实现了基于TBB的TPGA和串行遗传算法(SGA),通过大量实验证明,TPGA同SGA相比,不但提高了收敛速度,而且能够取得一致的最优解。     

A parallel algorithm for the 0–1 knapsack problem

Research efforts on parallel exact algorithms for the 0–1 knapsack problem have up to now concentrated on solving small problems (at most 1,000 objects) and in many cases results have only been obtained by simulation of the parallel algorithm. After a brief review of a well known sequential branch-and-bound algorithm we discuss a new parallel algorithm for the 0–1 knapsack problem which exploits the potential parallelism that exists during the backtracking steps of the branch-and-bound algorithm. We report results for our parallel algorithm on a transputer network for problems with up to 20,000 objects. The speedup obtained is nearly linear for 2, 4, and 8 processors except when there is a strong correlation between the profit and weight of the objects.