Exact algorithms for scheduling multiple families of jobs on parallel machines

In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 823–840, 2003.     

NEPE类推进剂燃烧模拟

在分析、研究硝胺和AP CMDB推进剂燃烧模型的基础上,结合NEPE类推进剂的配方和燃烧性能特点,建立了NEPE类推进剂燃烧的物理模型,并进行了燃速和压强指数的理论计算。结果表明,几乎100%的计算结果都在实验值的±10%范围内。这说明所建立的模型基本合理,编制的NEPE类推进剂燃速计算程序基本可行。     

大圆航线导航与控制律设计

随着无人机(UAV)应用范围的扩大,要求无人机能精确跟踪预定航线.预定的飞行任务可以有两种规划方式,一是近似在当地切平面上的直线或曲线;二是飞行距离较长时在地球表面的大圆航线.第二种规划相对复杂,研究较少,因此,介绍了某型无人机的动力学模型,提出了一种全新的大圆航线导航解算算法,设计了大圆导航控制律,此外,还分析了常值风及突风干扰对导航的影响.经计算机仿真验证和部分的实际飞行试验结果表明:与预定航线的距离偏差较小,航迹精度较高,新算法及设计较好地满足了实际大圆航线飞行要求.     

巨型机通用数学库软件与并行算法

本文介绍了巨型机通用数学库软件的概念和意义,指出了巨型机数学软件开发的技术途径与发展趋势,讨论了并行算法在其中的关键性作用,结合实例分析了巨型机通用数学库软件研制中的并行算法设计与实现。     

分阶段执行策略及其查询处理技术的研究

针对面向对象数据库及其查询的特点 ,提出了查询处理的分阶段执行策略及其数据操作并行执行算法 ,理论分析和模拟结果都验证了它们的实用性和有效性。     

基于YH-F2 系统的一般算术表达式的并行成分识别

本文深入研究了基于ＹＨ－Ｆ２系统的算术表达式的并行计算特点,提出了嵌套层次树的概念和相应的计算模式。这种模式充分利用了ＹＨ－Ｆ２系统的并行计算能力,完满地解决了基于ＹＨ－Ｆ２的算术表达式的并行编译问题     

一种开发逻辑程序中AND并行性的静态编译方法

逻辑程序AND并行性的开发是逻辑程序并行执行研究中的一个重要课题。文中提出了一种开发逻辑程序中AND并行性的静态编译方法。该方法分成三个阶段:第一阶段,进入模式(entry mode) 的分析;第二阶段,退出模式(exit mode) 的生成;第三阶段,执行图表达式(execution graphexpression) 的确定。通过运行一些基准程序可知,与其它方法相比,该方法能在“生产者一消费者”原则(producer-consumer scheme) 下最大限度地开发AND并行性,且只需很小的动态开销。     

YH-GKS的设计与实现

图形核心系统GKS是二维图形软件的唯一的国际标准,且为我国采纳为国家标准。YH-GKS是基于GKS,为银河机设计的图形软件系统。文中介绍了YH-GKS的设计特色与实现方法。     

离散 Hartley 变换的 MIMD 并行算法

本文把长为N=N_1N_2(N_1为奇数)的离散Hartley变换(DHT)分解成N_1个长N_2的DHT及一些附加运算,附加运算也可以变成N_2个长N_1的DHT。由此得到计算它的一种MIMD并行算法,若用N_1台处理机并行计算,只需(?)个乘法步和(?)个加法步,这里M(N_2)和A(N_2)分别表示计算一个长N_2的DHT所需的乘法数及加法数。并行机的有效利用率接近于1。     

流化H.264编码的数据并行方法

流模型是一种源于媒体处理的新型并行计算模型.然而H.264编码作为媒体处理领域中的重要应用,在与流模型适配时,却出现重要障碍,主要是由于相关性问题极大地限制了流化过程中数据级并行的开发.针对这个问题,首先根据编码算法分析了编码过程中遇到的相关性问题,然后为各主要编码模块分别提出解除相关性限制的数据并行编码方法.采用这些...