Parallel Algorithm for Unconstrained Optimization Based on Decomposition Techniques

We present a numerical implementation of the parallel gradient distribution (PGD) method for the solution of large-scale unconstrained optimization problems. The proposed parallel algorithm is characterized by a parallel phase which exploits the portions of the gradient of the objective function assigned to each processor; then, a coordination phase follows which, by a synchronous interaction scheme, optimizes over the partial results obtained by the parallel phase. The parallel and coordination phases are implemented using a quasi-Newton limited-memory BFGS approach. The computational experiments, carried out on a network of UNIX workstations by using the parallel software tool PVM, show that parallelization efficiency was problem dependent and ranged between 0.15 and 8.75. For the 150 problems solved by PGD on more than one processor, 85 cases had parallelization efficiency below 1, while 65 cases had a parallelization efficiency above 1.     

Modelling Techniques for Simulation of Submarine Engagements

The process of designing complex, costly military systems benefits substantially from analyses of performance as predicted by some form of model of the system and its operating environment. In this paper, techniques are described that have been implemented in a suite of computer programs to represent the tactical situations that can develop between two opposing submarines. The kernel of the program suite is the Submarine Interactive Attack Model (SIAM). This is sufficiently versatile that a wide range of scenarios can be simulated, and meaningful statistics for expected submarine performance obtained. Emphasis is placed on the modelling of both the dynamic tactical situations that can evolve in underwater warfare and the tactical decision-making that influences the outcome of submarine operations. Although the techniques have been applied to a specific domain it is believed that they are applicable to a wide range of complex problems.     

Parallel integer relation detection: Techniques and applications

Let be a vector of real numbers. An integer relation algorithm is a computational scheme to find the integers , if they exist, such that . In the past few years, integer relation algorithms have been utilized to discover new results in mathematics and physics. Existing programs for this purpose require very large amounts of computer time, due in part to the requirement for multiprecision arithmetic, yet are poorly suited for parallel processing.

This paper presents a new integer relation algorithm designed for parallel computer systems, but as a bonus it also gives superior results on single processor systems. Single- and multi-level implementations of this algorithm are described, together with performance results on a parallel computer system. Several applications of these programs are discussed, including some new results in mathematical number theory, quantum field theory and chaos theory.

     

考虑加工速率相互干扰的平行机调度最优策略研究

随着智能互联网的应用深入、个性化消费时代的来临,制造服务企业开始注重利用网络平台为客户提供个性化的定制服务,在此过程中派生出了产品设计师可与多名客户在线同步交互的一种新型服务模式。本文根据设计师服务效率受并行服务客户数量影响的特征,将问题刻画为机器处理速度相互影响的一类平行机调度模型,以最小化总完工时间为优化目标,研究设计最优调度方案。首先,对于只有两名设计师且各自同时处理最多两个任务的情形,提出了改进的SPT调度规则,运用归纳法证明了该规则可以生成最优加工方案。其次,对改进的SPT规则进行任务分配方式的适当松驰以便更加易于操作,并证明松驰后的新分配方案保持了解的最优性。最后,将相关结论推广至多名设计师的一般情形。上述研究为个性化在线定制服务模式下的有效调度策略制定提供了良好的理论支撑。     

A Simulation of Techniques for Forecasting Shipments Using Firm Orders-to-Date

Many companies use firm orders-to-date to make forecasts of units to be shipped at a future time t that is j periods away, j = 1, 2,..., h. A number of methods for making these forecasts were developed and evaluated using simulation. The time series for bookings was decomposed into a shipment time series and a time series for factors representing the fraction of shipments booked j periods ahead. Separate techniques were used for the shipments series (namely, naive, exponential smoothing and Bayesian procedures) and for the factors (naive and exponential smoothing procedures). The accuracy of these approaches, as well as an ARIMA model that ignored orders-to-date, was evaluated by using several simulated patterns of bookings. No approach was dominant, but one of the simplest approaches (naive/smoothing) did comparatively well.     

A Simulation Analysis of Advanced Concepts for Semi-automated Mail Processing

Over the last decade, much attention has been given to the development of automated mail processing systems for postal operations. Optical character readers and bar-code sorters have begun to augment the mechanized equipment in use since the mid-1960s. Current automation programmes are aimed at minimizing the growth in labour costs which, at $30.5 billion in the United States, accounted for 83% of the U.S. Postal Service's operating budget in 1988. In this paper, a SLAM II simulation model is developed to assist postal managers in evaluating and implementing new technologies at general mail facilities (GMFs). The Northern Virginia Area GMF, located just outside Washington, D.C., serves as the baseline. Results are presented for a proposed design embodying a variety of new concepts and equipment, including carrier route sequencing. Annual savings of over $6 billion are estimated to accompany nation-wide implementation of this design. Alternative scenarios involving changes in mail volume and address quality are also investigated. The analysis demonstrates the system's sensitivity to relatively modest increases in traffic, and points up the need for integrative long-range planning.     

Parallel Markov chain Monte Carlo Simulation by Pre-Fetching

In recent years, parallel processing has become widely available to researchers. It can be applied in an obvious way in the context of Monte Carlo simulation, but techniques for “parallelizing” Markov chain Monte Carlo (MCMC) algorithms are not so obvious, apart from the natural approach of generating multiple chains in parallel. Although generation of parallel chains is generally the easiest approach, in cases where burn-in is a serious problem, it is often desirable to use parallelization to speed up generation of a single chain. This article briefly discusses some existing methods for parallelization of MCMC algorithms, and proposes a new “pre-fetching” algorithm to parallelize generation of a single chain.     

具有学习效应和加工时间可控的平行机排序问题

本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(n^m+2),最后也给出了相应的数值例子来阐述该问题。     

目标拦截模拟系统中的造型方法

对目标拦截模拟系统中的造型技术作了研究.包括飞行器造型、地形造型、火焰喷射模拟等.提出了蒙皮技术造型中存在的三个问题及相应改进措施.给出了一个基于蒙皮技术的地形生成新算法.利用嵌套圆台扰动的思想较好地实现了导弹飞行时的火焰喷射模拟.     

加工时间可控和简单线性增长的平行机排序

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.     

Balancing Workloads and Minimizing Set-up Costs in the Parallel Processing Shop

This paper presents an optimal scheduling algorithm for minimizing set-up costs in the parallel processing shop while meeting workload balancing restrictions.There are M independent batch type jobs which have sequence dependent set-up costs and N parallel processing machines. Each of the M jobs must be processed on exactly one of the N available machines. It is desirable to minimize total changeover costs with the restriction that each machine workload assignment T _n be within P units of the average machine assignment. The paper describes a static problem in which all jobs are available at time zero. The sequence dependent change over costs are identical for each machine. An extension of the algorithm handles nonidentical processor problems.A combinatorial programming approach to the problem is used. For the special case of identical processors, the problem can be treated as a multi-salesman travelling salesman problem. A general branch and bound algorithm and numerical results are given.     

多服务台并联排队系统的随机模拟

针对多服务台并联排队系统,提出了计算机随机模拟的方法.分别研究了基本和非基本排队系统中,诸如排队人数、排队时间、平稳分布、忙期及其忙期服务人数等各项排队指标的模拟求解方法.通过模拟例子和实际数据分析,显示了本文所提模拟方法的有效性、灵活性和实用性.     

封闭容器中二维自然对流直接数值模拟的一个并行算法

本文对具有不同温度竖壁的封闭容器中二维自然对流问题进行了直接数值模拟,控制方程在非均匀网络上使用空间二阶精度和时间一阶精度进行离散,程序是在国家高性能计算中心（武汉）的并行计算机“曙光１０００Ａ”上实现的,使用４个结点,获得的加速比和效率分别约为２．８９和０．７２。     

Modelling a Solid-Waste Processing System by Discrete Event Simulation

This paper describes a discrete event simulation model for a solid-waste processing system which is to be installed in Zagreb, Croatia. The conceptual model was developed by activity cycle diagrams, and the computer model was developed using the program generation software package VS6. This paper describes the validation and verification of such a model, the design of simulation experiments and the selection of the system's configuration.     

Approximate Simulation Techniques and Distribution of an Extended Gamma Process

In reliability theory, many papers use a standard Gamma process to model the evolution of the cumulative deterioration of a system over time. When the variance-to-mean ratio of the system deterioration level varies over time, the standard Gamma process is not convenient any more because it provides a constant ratio. A way to overcome this restriction is to consider the extended version of a Gamma process proposed by Cinlar (J Appl Probab 17:467–480, 1980). However, based on its technicality, the use of such a process for applicative purpose requires the preliminary development of technical tools for simulating its paths and for the numerical assessment of its distribution. This paper is devoted to these two points.     

Pantograph-Catenary Dynamics: An Analysis of Models and Simulation Techniques

In this paper we analyze models and simulation techniques for the interaction of pantograph and catenary. Detailed models for catenary and pantograph and the propagation of waves are first investigated. Next, the semi discretization by the finite element method and the time integration are described. In this context numerical techniques like GGL-stabilization and superconvergent patch recovery are applied. The latter yields an error estimation for the finite element grid and shows the critical points of the system.     

Parallel methods for ODEs

Advances in Computational Mathematics -