Nonpreemptive scheduling of independent tasks with prespecified processor allocations

In this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. We propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weighted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented. © 1994 John Wiley & Sons, Inc.     

Makespan minimization for m parallel identical processors

We introduce an algorithm, called TMO (Two-Machine Optimal Scheduling) which minimizes the makespan for two identical processors. TMO employs lexicographic search in conjunction with the longest-processing time sequence to derive an optimal schedule. For the m identical parallel processors problem, we propose an improvement algorithm, which improves the seed solution obtained by any existing heuristic. The improvement algorithm, called Extended TMO, breaks the original m-machine problem into a set of two-machine problems and solves them repeatedly by the TMO. A simulation study is performed to evaluate the effectiveness of the proposed algorithms by comparing it against three existing heuristics: LPT (Graham, [11]), MULTIFIT (Coffman, Garey, and Johnson, [6]), and RMG (Lee and Massey, [17]). The simulation results show that: for the two processors case, the TMO performs significantly better than LPT, MULTIFIT, and RMG, and it generally takes considerably less CPU time than MULTIFIT and RMG. For the general parallel processors case, the Extended TMO algorithm is shown to be capable of greatly improving any seed solution. © 1995 John Wiley & Sons, Inc.     

A note on the optimal scheduling of two parallel processors

The problem of minimizing mean flow time of two parallel processors is discussed. Prior results are briefly reviewed. A dynamic programming algorithm is presented which minimizes mean flow time for a set of n preordered jobs on two nonequivalent parallel processors. The algorithm is illustrated with an example problem. The computational experience is presented which illustrates the efficiency of the algorithm.     

A generalized-indices transportation problem

A generalized-indices transportation problem is formulated and an algorithm is presented for its solution. The algorithm is an extension of the modi-method. A theorem on the number of independent variables in the generalized-indices transportation problem is proved. An example problem is solved for the four-indices transportation problem. A computer program has been written to solve any four-indices problem.     

A face search heuristic algorithm for optimizing over the efficient set

The problem of optimizing a linear function over the efficient set of a multiple objective linear program is an important but difficult problem in multiple criteria decision making. In this article we present a flexible face search heuristic algorithm for the problem. Preliminary computational experiments indicate that the algorithm gives very good estimates of the global optimum with relatively little computational effort. © 1993 John Wiley & Sons, Inc.     

A heuristic procedure for allocating tasks in fault-tolerant distributed computer systems

One way of achieving the increased levels of system reliability and availability demanded by critical computer-based control systems is through the use of fault-tolerant distributed computer systems. This article addresses the problem of allocating a set of m tasks among a set of n processors in a manner that will satisfy various task assignment, system capacity, and task scheduling constraints while balancing the workload across processors. We discuss problem background, problem formulation, and a known heuristic procedure for the problem. A new solution-improving heuristic procedure is introduced, and computational experience with the heuristics is presented. With only a modest increase in the amount of computational effort, the new procedure is demonstrated to improve dramatically solution quality as well as obtain near-optimal solutions to the test problems.     

Single- and multiple-processor models for minimizing completion time variance

This article concerns the scheduling of n jobs around a common due date, so as to minimize the average total earliness plus total lateness of the jobs. Optimality conditions for the problem are developed, based on its equivalence to an easy scheduling problem. It seems that this problem inherently has a huge number of optimal solutions and an algorithm is developed to find many of them. The model is extended to allow for the availability of multiple parallel processors and an efficient algorithm is developed for that problem. In this more general case also, the algorithm permits great flexibility in finding an optimal schedule.     

Requirements of an “optimizer” for computer simulations

Computer simulation has many advantages. However, one major disadvantage is that, in all too many cases, the attempt to use computer simulation to find an optimum solution to a problem rapidly degenerates into a trial-and-error process. Techniques for overcoming this disadvantage, i. e., for making optimization and computer simulation more compatible, are applicable at two points in the development of the overall computer simulation. Techniques which are used within actual construction of the mathematical models comprising the simulation will be labeled as internal methods, while those which are used after the simulation has been completely developed will be termed external methods Because external methods appear to offer the largest potential payoff, discussion is restricted to these methods, which are essentially search techniques. In addition, the development of an “Optimizer” computer program based on these techniques is suggested Although drawbacks to the use of search techniques in the computer simulation framework exist, these techniques do offer potential for “optimization.” The modification of these techniques to satisfy the requirements of an “Optimizer” is discussed.     

坦克实体智能机动路径模型

根据坦克机动作战的一般原则,首先对影响坦克实体机动的因素进行了分析和合理的假设;充分考虑战术模拟中的实际情况,将数字地图中各点间的空间距离转化为以各点间机动时间为权边的网图,通过求任意两点间的最短距离的方法,建立坦克实体机动最短时间路径的数学模型。并给出了人工智能算法,把问题求解过程简化,从而解决战术模拟系统中智能机动中的路径选择问题。     

Scheduling with parallel processors and linear delay costs

This paper deals with the sequencing problem of minimizing linear delay costs with parallel identical processors. The theoretical properties of this m-machine problem are explored, and the problem of determining an optimum scheduling procedure is examined. Properties of the optimum schedule are given as well as the corresponding reductions in the number of schedules that must be evaluated in the search for an optimum. An experimental comparison of scheduling rules is reported; this indicates that although a class of effective heuristics can be identified, their relative behavior is difficult to characterize.     

The graph association problem: Mathematical models and a lagrangian heuristic

Graph association is the problem of merging many graphs that collectively describe a set of possibly repetitive entities and relationships into a single graph that contains unique entities and relationships. As a form of data association, graph association can be used to identify when two sensors are observing the same object so information from both sensors can be combined and analyzed in a meaningful and consistent way. Graph association between two graphs is related to the problem of graph matching, and between multiple graphs it is related to the common labeling of a graph set (also known as multiple graph matching) problem. This article contribution is to formulate graph association as a binary linear program and introduce a heuristic for solving multiple graph association using a Lagrangian relaxation approach to address issues with between‐graph transitivity requirements. The algorithms are tested on a representative dataset. The developed model formulation was found to accurately solve the graph association problem. Furthermore, the Lagrangian heuristic was found to solve the developed model within 3% of optimal on many problem instances, and found better solutions to large problems than is possible by directly using CPLEX. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A finite algorithm for concave minimization over a polyhedron

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.     

基于遗传算法的湿陷性黄土地基灰土挤密桩优化设计

利用Visual C＋＋语言，定义了一个面向对象的基于实数编码遗传算法类。运用可最大限度保证遗传算法搜索到问题的全局最优解的深度搜索策略，编制了灰土挤密桩的优化设计和造价估算遗传算法程序，并针对兰州某地灰土挤密桩复合地基进行了计算分析，并与原有方案比较，结果表明：两种优化方案在满足承载力和变形的条件下，在降低造价成本方面优势非常明显。     

应用有限元混合法分析两弹性接触体的动力响应（理论部分）

本文将动力分析中的直接积分法与有限元混合法结合起来对两弹性接触体的摩擦动力求解问题进行了理论分析,推导了有关的有限元公式,设计了计算框图,为计算程序的实现提供了理论依据。     

A partitioning technique for obtaining solutions to the modularization problem

A significant problem in electronic system design is that of partitioning the functional elements of an equipment schematic into subsets which may be regarded as modules. The collection of all such subsets generated by a particular partitioning forms a potential modular design. The specific problem is to determine that partitioning of the schematic that minimizes a cost function defined on the subsets subject to specified hardware, design, packaging, and inventory constraints. This problem is termed the modularization problem. This paper presents a method for obtaining restricted solutions to the modularization problem by employing some recent developments in linear graph theory obtained by one of the coauthors. Numerical results from the solution of several typical problems are presented.     

一种基于多核并行计算的目标分配算法设计

随着计算机多核处理器的高速发展,多核并行计算在各领域发展研究的重要性已逐渐突显,分析了当前典型的并行编程模型,在PCAM设计过程的基础上提出了多核并行算法的设计过程,运用OpenMP编程模型完成了一种目标分配算法的多核并行化设计,通过实验及性能分析,验证了并行目标分配算法相较于传统串行算法在计算效率上的优势。     

基于局部评估的分布式图模式匹配算法

为了在分布式存储的大规模数据图上进行快速图模式匹配，提出了基于局部评估的分布式图模式匹配算法disGPM-PE。首先各计算节点并行地执行本地匹配，然后协调器节点收集局部匹配结果、计算边界点的匹配状态并发送给相应的计算节点，接着计算节点根据边界点的匹配状态确定与边界点相连的节点的匹配情况，最后协调器节点组合得出最大匹配集。实验结果表明：与已有的分布式图模式匹配算法相比，disGPM-PE算法都能够在不显著增加通信量的前提下避免数据片段间的依赖关系对执行时间的影响，减少了图模式匹配的时间。     

并行计算的数据重分配

为提高算法的并行计算性能 ,许多并行程序必须进行数据重分配。数据重分配是在并行计算过程中实现的 ,其开销影响算法的并行性能 ,高效的数据重分配对提高并行计算的性能有重要意义。本文阐述了数据重分配的环形算法 ;提出了数据重分配的蝶网算法 ,并证明了其正确性 ;设计了结构性数据交换方法 ;通过理论和数值实验分析了两种算法的性能     

多智能体系统的二阶一致性跟踪问题

为了解决通信时延下关于参考状态的二阶一致性问题,提出了一种一致性算法。该算法利用Lya-punov稳定性理论,首先给出多智能体系统在固定时延下达到一致性的充分的线性矩阵不等式(LMI)判据;再给出满足一定条件的多智能体系统在时变时延下达到一致性的判据;最后,以水下无人航行器(UUV)集结为应用背景进行算法验证。运算结果表明了所提出的一致性算法和判据的有效性。该算法适用于具有时延的有向通信网中多智能体系统关于参考状态的二阶一致性问题。     

高性能路由器并行转发技术

随着线路传输速率的快速提高,报文线速转发面临极大挑战。基于并行处理技术,提出分布式并行转发引擎结构,实现高速报文转发。针对并行转发引擎负载分配问题,设计AHDA(Adaptive Hashing DispatchAlgorithm)算法,该算法为综合考虑负载均衡和报文保序提供支持。模拟结果表明,AHDA算法均匀分配负载,保证很低的报文乱序率,对网络处理器规模具有良好的可扩展性。