The Lazy Cook Problem, or Scheduling Two Parallel Machines to Optimize Vehicle Utilization

A cook has to prepare n cakes using an oven with two racks. According to the recipe, the i-th cake has to be baked for exactly a _i minutes. Cakes to be cooked are taken from a table and carried to the oven, and once cooked are carried back to the table by means of a trolley that can carry two cakes at a time. What is the minimum number q ^* of round trips required of the cook? This problem has application to the operation scheduling of transportation systems and to material cutting. A different problem arises according to whether the cook accepts or not to stay near the oven for awhile with the trolley. If the trolley cannot be idle at the oven, an optimum schedule with no oven idle-time always exists: consequently, the trolley schedule is trivial, and the problem is transformed into a set packing. For this case, we propose and test a heuristic method which generates all of the promising columns of the set packing, and solves the resulting problem by branch-and-bound. Instead, if the trolley can be idle at the oven for a limited amount of time, a problem arises to find an optimal schedule of the trolley: in this case we show how to use a scaling technique in order to obtain a very good feasible solution by the method above.     

Experiences with a parallel algorithm for data flow analysis

We have designed a family of parallel data flow analysis algorithms for execution on distributed-memory MIMD machines, based on general-purpose, hybrid algorithms for data flow analysis [Marlowe and Ryder 1990]. We exploit a natural partitioning of the hybrid algorithms and explore a static mapping, dynamic scheduling strategy. Alternative mapping-scheduling choices and refinements of the flow graph condensation used are discussed. Our parallel hybrid algorithm family is illustrated on Reaching Definitions, although parallel algorithms also exist for many interprocedural (e.g., Aliasing) and intraprocedural (e.g., Available Expressions) problems [Marlowe 1989]. We have implemented the parallel hybrid algorithm for Reaching Definitions on an Intel iPSC/2. Our empirical results suggest the practicality of parallel hybrid algorithms.An earlier version of this paper was presented at Supercomputing '90.The research reported here was supported, in part, by the New Jersey Commission on Science and Technology and the CAIP Center's Industrial Members, by Siemens Research Corporation and by National Science Foundation grant CCR-8920078.     

Application of parallelized analogical planning to engineering design

Analogical planning provides a means of solving engineering problems where other machine learning methods fail. Unlike many machine learning paradigms, analogy does not require numerous previous examples or a rich domain theory. Instead, analogical planners adapt knowledge of solved problems in similar domains to the current problem. Unfortunately, the analogical planning task is an expensive one. While the process of forming correspondences between a known problem and a new problem is complex, the problem of selecting a base case for the analogy is virtually intractable.This paper addresses the issue of efficiently forming analogical plans. The Anagram planning system is described, which takes advantage of the massively parallel architecture of the Connection Machine to perform base selection and map formation. Anagram provides a tractable solution to analogical planning, with a complexity that is sublinear in the size of the plans.This paper describes the Anagram system and its parallel algorithms. The paper also presents theoretical analyses and empirical results of testing the system on a large database of plans from the domain of automatic programming.     

Wavetracing层析成像方法及其在井间地震中的应用

层析成像技术被广泛应用于矿产勘查、油气开发及工程勘查和检测领域。基于运动学特征的走时层析成像方法计算效率较高,但精度较低。基于动力学特征的波动方程层析成像方法精度较高,但计算时间较长。Wavetracing层析成像方法在射线追踪方面简单、高效,能够提供与有限频率实际资料相一致的传播路径和旅行时。应用该方法对胜利油田垦71地区多对井间地震资料进行的层析成像速度反演取得了良好结果。     

不甩线圈的多星形移相变极

对于某些槽数和极数比的多星形移相变极电机,提出与前人不同的是在两种极数下均不甩去线圈的绕组方案,使绕组利用率高,且线圈及其联接都较简单.这种绕组方案在一种极数下并联支路略有不平衡,其所引起的电机定子铜耗的增加是极其有限的,不致影响电机的正常运行.     

叠前深度偏移中的旅行时并行计算技术

旅行时计算技术是基于波动方程叠前深度偏移方法的核心内容，射线跟踪的数值计算精度和效率直接影响着介质成像质量和实用化。基于三维射线跟踪的微变网络方法和波前重建思路，提出一种适用于三维复杂介质地震波走时的快速算法。但它所需计算量巨大。采用并行计算技术，设计出基于“任务缓冲池”的动态负载平衡策略，在现有的分布式计算机上，实现了三维射线追踪和叠前深度偏移的并行计算。     

常速度梯度射线追踪与二维层速度反演

速度问题是勘探地震学的核心 ,可以借助常速度梯度射线追踪方法 ,从反演的角度探讨速度建模问题。在射线追踪方面 ,从程函方程出发 ,将复杂的速度场剖分成小的矩形单元 ,并假设在每个矩形单元内速度具有常速度梯度 ,由此导出的一组常速度梯度射线追踪公式 ,可实现非均匀介质的射线追踪 ,具有适应性强、精度高和快速的优点。在层速度反演方面 ,采用相干速度反演的思想 ,根据各向同性介质中 ,零偏移距射线在界面处是法向入射的原理 ,建立了合成共中心点道集与射线深度偏移的正反演关系 ,由此利用合成共中心点道集与观测的共中心点道集逼近 ,采用层剥离方法进行层速度反演。通过理论推导与模型试算得到如下的认识与结论 :常速度梯度射线追踪具有较高的计算精度与效率 ,公式采用向量形式很容易推广到三维 ;确定层速度采用的是正反演相结合的方法 ,可得到稳定的速度场 ;该方法屏弃了基于双曲时矩关系确定层速度场的假设 ,使其能适应任意的速度分布。     

K-230B镗床万向护板的设计

介绍了大型机床地坑移动盖板的一般设计思想,根据机床原有功能和结构特点,设计兼顾防尘防屑和美观大方两大特点的活动盖板,为同类设计提供一些参考。     

计算几何与并行算法

本文首先介绍了计算几何的基本概念,论述了计算几何的四个基本问题,即几何搜索问题、相交问题、邻接问题及凸壳问题。然后重点分析了凸壳构造问题,介绍了其最佳串行算法、及相应的并行算法。接着对一些计算几何的串行及并行算法进行了分析比较。最后提出了笔者对新一代并行计算机系统上设计计算几何并行算法的看法。     

Parallel associative combinator evaluation II

A new evaluation model for SK combinator expressions is presented and used as a basis for the design of a novel processor. The resulting machine architecture resembles a dataflow ring, but executions are constrained to be fully lazy. An automatic dynamic load sharing mechanism for a distributed multiprocessor architecture is suggested, and initial simulation results are presented.