On‐line algorithms for minimizing makespan on batch processing machines

We consider problem of scheduling jobs on‐line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on‐line algorithms with worst‐case ratio (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst‐case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on‐line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001     

超声速飞行器流场的并行数值计算及效率分析

基于有限体积方法、TVD差分格式和显式Runge-Kutta迭代方法的框架,针对超声速/高超声速飞行器绕流流场,在超级并行计算机上完成了2~64个CPU并行数值计算工作。通过测试程序在超级计算机上的并行效率,并将并行程序应用于航天飞机绕流流场计算,检验了计算程序进行大规模并行计算的性能。结果表明,在负载平衡的条件下,程序在该超级并行计算机上达到了不同程度的超线性加速比,并行效率最高达到了126%,远远高于微机Cluster并行平台上的结果,适合复杂流场的大规模并行计算。     

基于去除函数预测模型的磁流变抛光工艺优化研究

在分析磁流变抛光加工过程的基础上,建立了磁流变抛光的去除函数预测模型,该模型利用加工前后的面形误差分布和仿真计算的面形残差分布,针对不同材料间的去除函数模型效率系数进行辨识,能够实现去除函数模型的准确预测.以该模型为基础,通过在传统磁流变抛光工艺中加入去除函数效率系数实时辨识的工艺环节,可以对磁流变抛光的加工工艺进行优化.利用该优化工艺对一块口径202mm的HIP SiC进行9次循环迭代加工,采用子孔径拼接测量技术进行测量,面形误差由初始的PV 0.72μm,RMS 0.108μm提升到最终的PV0.13μm,RMS0.012μm.实验表明,去除函数预测模型能够优化磁流变抛光工艺,提高加工的确定性和增强工艺的适用性,实现光学镜面的高精度确定性磁流变抛光加工.     

二维激波/湍流边界层干扰的混合LES/RANS模拟

为了降低高雷诺数条件下大涡模拟方法的计算量,将两方程k-ωSST湍流模型与Yoshizawa一方程亚格子模型通过一个衔接函数相结合,构造一种混合大涡/雷诺平均NS方程模拟方法(混合LES/RANS)。使用这种方法及AUSM+-up格式对20°压缩斜坡的马赫2.85流动进行模拟,并考察了固定入口和在入口添加白噪声两种湍流入口边界条件对于结果的影响。模拟结果再现了边界层的分离、再附以及分离激波等现象,计算得到的分离区要显著大于试验结果,对于这种混合模拟方法的缺点进行了分析,并提出了可能的改进方法。     

一种基于低扩散通量分裂方法的WENO格式研究

将低扩散通量分裂格式(LDFSS)和加权基本无振荡格式(WENO)相结合,构造出一种混合格式,其中WENO格式用于物理量重构,而LDFSS用于通量分裂。采用这种格式对Riemann问题、钝头体高超声速无粘绕流流场进行了计算,并对超声速平板湍流边界层进行了混合LES/RANS模拟,计算结果表明:相对于采用Lax-Fridrichs分裂的WENO格式来说,这种混合格式对于激波和接触间断的分辨率更高,并且在标量保正性方面更优,收敛性更好;而相对于采用带有Minmod限制器的MUSCL方法进行物理量高阶重构的LDFSS格式来说,这种混合格式在混合模拟的计算中能够更好地反映湍流流场的脉动特性,计算得到的湍流速度脉动量的统计值更加准确。     

长方体类光学元件形位误差高精度测量方法

如何实现长方体元件光学面形位误差的高精度测量以及怎样利用测量数据对这些误差进行修正加工是制造过程中的主要问题。提出一种基于波面干涉的长方体类光学元件形位误差测量方法,借助大口径干涉仪和高精度端齿盘搭建测量系统,实现了长方体类光学元件1μm/400mm精度的平行度和垂直度测量,获得了高精度的形位误差综合分布数据,并利用磁流变、小磨头数控抛光等现代光学加工手段实现了此类光学元件的高精度加工。     

Deterministic and stochastic scheduling with teamwork tasks

We study a class of new scheduling problems which involve types of teamwork tasks. Each teamwork task consists of several components, and requires a team of processors to complete, with each team member to process a particular component of the task. Once the processor completes its work on the task, it will be available immediately to work on the next task regardless of whether the other components of the last task have been completed or not. Thus, the processors in a team neither have to start, nor have to finish, at the same time as they process a task. A task is completed only when all of its components have been processed. The problem is to find an optimal schedule to process all tasks, under a given objective measure. We consider both deterministic and stochastic models. For the deterministic model, we find that the optimal schedule exhibits the pattern that all processors must adopt the same sequence to process the tasks, even under a general objective function GC = F(f₁(C₁), f₂(C₂), … , f_n(C_n)), where f_i(C_i) is a general, nondecreasing function of the completion time C_i of task i. We show that the optimal sequence to minimize the maximum cost MC = max f_i(C_i) can be derived by a simple rule if there exists an order f₁(t) ≤ … ≤ f_n(t) for all t between the functions {f_i(t)}. We further show that the optimal sequence to minimize the total cost TC = ∑ f_i(C_i) can be constructed by a dynamic programming algorithm. For the stochastic model, we study three optimization criteria: (A) almost sure minimization; (B) stochastic ordering; and (C) expected cost minimization. For criterion (A), we show that the results for the corresponding deterministic model can be easily generalized. However, stochastic problems with criteria (B) and (C) become quite difficult. Conditions under which the optimal solutions can be found for these two criteria are derived. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

一个知识辅助的视频语义概念探测框架

视频语义概念探测是视频语义内容分析研究领域的热点和难点问题.语义概念探测方法的性能取决于其是否能够有效地建模和匹配视频语义内容特征.将视频内容抽象为感知概念和语义概念以及概念间的关系,提出了知识辅助的视频语义概念探测框架,利用本体建模概念间关系和上下文知识,从低层特征匹配和上下文匹配两个方面综合考虑语义概念的探测.通过线性融和策略,对匹配结果进行融合得到最终的探测结果.实验结果表明提出的方法探测性能良好.     

三维超声速隔离段湍流内流场旋涡结构的数值模拟

从基于雷诺平均的N S方程出发 ,采用有限体积方法离散控制方程 ,数值模拟了三维超声速隔离段湍流内流场。计算中采用了二阶OC TVD差分格式、LU隐式算法和Baldwin Lomax代数湍流模型。数值结果与实验做了对比 ,并结合隔离段中的激波串结构分析了其横截面上旋涡结构的发展过程及不同外形条件下旋涡的不同结构。计算结果表明采用本文发展的方法模拟隔离段湍流流场是可行的 ,截面为正方形与长方形的隔离段内的涡旋结构截然不同     

回转对称非球面光学零件磁流变成形抛光的驻留时间算法

介绍了一种基于代数算法的回转对称非球面计算机控制表面成形的驻留时间算法。该算法将驻留时间转化为工件自转的整数圈数,并且将抛光模对工件的材料去除效率体现到材料去除矩阵上进行计算。利用非负最小二乘法求解驻留时间向量。最后,利用该算法在自研的磁流变抛光实验装置上对一回转对称光学零件进行3次迭代加工,使其面形精度从8μm提高到0.5μm以内。