元计算环境下的支持依赖任务的OGS算法研究

一个应用程序只有经过分解，产生若干任务后才能在元计算系统上调度和运行，论文提出了基于ＤＡＧ的，优化的分代任务调度算法ＯＧＳ，该算法为每个ＤＡＧ结点指派一个固定优先数，根据优先数过滤出互不依赖的任务，然后对这些独立任务使用先辈算法进行调度，ＯＧＳ算法不仅考虑机器就绪时间，还考虑每个任务全部先导的完成时间，这样可以减少全部参与调度的节点的空闲时间，从而优化Ｍakespan,实现表明，ＯＧＳ算法的性能优于ＧＳ和Ｂeam算法。     

不连续生产系统的最大加工能力与最优生产安排的强多项式算法

不连续生产系统的最大加工能力与最优生产安排的强多项式算法杨承恩，梁枢里（长沙铁道学院）ＴＨＥＭＡＸＩＭＵＭＰＲＯＣＥＳＳＩＮＧＣＡＰＡＣＩＴＹＡＮＤＯＰＴＩＭＡＬＳＣＨＥＤＵＬＥＯＦＡＤＩＳＣＯＮＴＩＮＵＯＵＳＰＲＯＤＵＣＴＩＯＮＳＹＳＴＥＭ￥Ｙａｎ...     

内点方法下线性规划分解算法及其并行计算

内点方法下线性规划分解算法及其并行计算魏紫銮，吴力（中国科学院计算中心）ＡＤＥＣＯＭＰＯＳＩＴＩＯＮＡＬＧＯＲＩＴＨＭＡＮＤＩＴＳＰＡＲＡＬＬＥＬＣＯＭＰＵＴＡＴＩＯＮＦＯＲＬＩＮＥＡＲＰＲＯＧＲＡＭＭＩＮＧＵＮＤＥＲＴＨＥＩＮＴＥＲＩＯＲＰＯＩＮＴ...     

对DAG-MAP算法的研究

ＤＡＧ－ＭＡＰ是一个面向延迟优化的ＦＰＧＡ工艺映射算法,其中的标记过程中该算法的核心。文章对原算法中的标记过程进行了研究,并且提出了一个改进的标记方法。通过对ＭＣＮＣ标准测试电路的实验结果表明该算法比原算法更为有效,并且算法所用时间没有明显的增加。     

含过程任务图的调度

我们在Ｆｏｒｔｒａｎ程序并行转换系统ＨＺＰＡＲＡ－Ⅱ的研究中遇到了含过程任务图的情形，对此我们提出了一种有效的调度方法。该方法可在Ｏ（ｎ＊ｅ）的时间内完成调度，调度结果可以与ＣＰ调度法相比     

一种应用于多专家会诊系统的调度专家机制

提出了一种于多专家会诊系统的调度专家机制,它是针对在微机上建造的用于诊断人体肺病的多专家会诊系统ＭＥＭＳＰＤ而设计的。调度机制用ＭＡＣＲＯＬＩＳＰ语言实现。     

基于BDI模型构建信息Agent

本文提出一种用于分布式多Ａｇｅｎｔ环境的以ＢＤＩ模型为基础构建信息Ａｇｅｎｔ的方法,给出了ＰＥＲＦＯＲＭ（ＰＥＲｓｏｎａｌ ｉｎＦＯＲｍａｔｉｏｎ Ｍａｎａｇｅｒ）系统的模型和算法。     

热轧加热炉联机计算机系统的设计与实现

在宝钢２０５０ 热轧加热炉完善工程新的计算机系统设计中,为了节约资金,并在该项技改过程中尽可能少地影响生产,作者采用了将原来加热炉计算机ＳＩＣＯＭＰＭ７０ 作为新增的主在线机ＡＬＰＨＡ２１００ 的异机种备用机的设计新尝试,并成功地进行了设计和实现。     

面向多领域的可视化应用开发平台MOVADP

ＭＯＶＡＤＰ是一个面向多领域的可视化应用开发平台，文中主要介绍了该平台的软件结构和实现技术，ＭＯＶＡＤＰ以数据流机制为核心，采用可视编程技术，为用户开发可视化应用提供了一个文凭交互的模块级图形编程环境，与同类平台相比，ＭＯＶＡＤＰ的特点在于，引入了ＩＦＴＨＥＮ－ＥＬＳＥ，ＷＨＩＬＥ－ＬＯＯＰ等控制结构，支持用户构建复杂的可化应用流图；支持“ｌａｚｙｅｖａｌｕａｔｉｏｎ”命令驱动方式下的流图局部运行     

用于语音合成的PSOLA算法简介

本文介绍了基于波形编辑的语音合成中，用于改善合成语音的自然度的ＰＳＯＬＡ算法的一般过程，及具体的ＴＤ－ＰＳＯＬＡ，ＬＰ－ＰＳＯＬＡ和ＦＤ－ＰＳＯＬＡ算法。分析了时域和频域的算法分别在宽带和窄带条件下的谱特性和它们之间的关系，最后比较了这三种算法的适用范围及其在语音合成中的应用。     

基于订单更改的间歇多产品厂调度在线调整研究

针对间歇化工厂产品市场变化快的特点,提出了基于订单更改的多产品厂调度在线调整模型：该模型根据生产进度对产品进行分类,并结合原调度采取相应的调整策略,得到满意的调整方案。模型基于原调度,不需增加太多变量,故在建模和实际应用中易于实现。文中将该模型用于无限中间储罐的间歇多产品厂调度在线调整实例,并通过调度调整方案对订单更改时刻的灵敏度分析找出了目标函数的影响因素。     

基于到达时间两台并行机上在线批调度

考虑两台同构并行机上在线批调度问题．每个批具有不确定的到达时间,一旦机器可以利用,要在当前可以利用的批中选择出合适的批,并将其中的工件调度到机器上,且工件在加工过程中不允许中断．目标函数是使调度的最大完成时间最小．给出了一个批在线调度ＲＢＬＰＴ算法,即选择当前批中加工时间之和最大的批按ＬＰＴ 规则调度．另外,利用反证法,对算法的最坏情况进行了分析．     

极小化最大完工时间的单机连续型批调度问题

从钢铁工业中加热炉对管坯的加热过程,提出一种新的连续型批处理机调度问题,与传统批处理机调度问题的批进批出方式不同,其主要特征为批中工件的进入、处理和离开都连续进行,批B_i的处理时间与该批的大小|B_i|、批中工件T_j的处理时间p_j及机器的容量C都有关,表示为p^{(i)}=\dmax_{T_j\in B_i}\{p_j\}(1+\displaystyle\frac{|B_i|-1}{C}).对于极小化最大完工时间问题,给出了一个复杂性为O(n^2)的动态规划算法,并证明了这个算法的最优性.     

间歇生产调度优化模型的分周期逼近算法

间歇生产调度过程中存在许多不确定因素,其中最重要的是需求不确定.考虑需求不确定的多周期间歇生产调度优化模型采用离散或连续时间表达方式,将调度时间域分割成大量与调度决策相关的时间段,导致模型中存在大量整数变量,给模型求解造成很大困难.本研究对已有求解方法进行了分析,提出分周期逼近算法.将多周期间歇生产调度决策问题分解为第一周期调度决策问题和其余周期调度决策问题,简化结构,加快求解速度.通过方案树聚集将表达需求不确定信息的方案树转化成若干方案文件,针对每个方案文件应用确定性方法获得调度决策,但只保留第一周期调度决策,可以减小最小利益方案对期望利益的影响,提高第一周期调度决策水平;获得若干第一周期候选调度决策后,以时间收缩三阶段方法确定其余周期较优调度决策,同时应用时间收缩策略和补偿策略,提高其余周期调度决策水平;最后用期望利益评估第一周期候选调度决策并确定全部周期调度决策.实例研究证明了本文提出的算法能够提高间歇生产调度决策水平,同时加快求解速度,能够有效求解多周期间歇生产调度优化模型.     

基于改进型批决策与调度建模的生产计划调度系统的研究

热轧型钢生产工艺复杂,其生产中极易出现由于计划调度安排不当而产生的交货期延误、库存超负荷等问题。针对以上问题研究设计了MES生产计划调度系统,改进了批决策调度策略用于数学建模,利用自适应遗传算法求解生产调度计划。以此为基础,为某热轧企业设计实现了生产计划调度系统,并通过真实的热轧型钢订单、原料、设备等数据,对模型改进前后的计划编制方法进行模拟与比较,验证了利用该改进型批决策与调度模型编制的热轧型钢生产调度计划可节省生产时间、降低设备调度时间,以此来指导热轧型钢的生产可切实减少交货延误和减少库存占用率,并提高企业利润率。     

An Enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes

This paper addresses a sequence- and machine-dependent batch scheduling problem on a set of unrelated-parallel machines where the objective is to minimize a linear combination of total weighted completion time and total weighted tardiness. In particular, batch scheduling disregards the group technology assumptions by allowing for the possibility of splitting pre-determined groups of jobs into batches with respect to desired lower bounds on batch sizes. With regard to bounds on batch sizes, the MILP model is developed as two integrated batching and scheduling phases to present the problem. A benchmark of small-size instances on group scheduling shows the superior performance of batch scheduling up to 37% reduction in the objective function value. An efficient meta-heuristic algorithm based on tabu search with multi-level diversification and multi-tabu structure is developed at three levels, which moves back and forth between batching and scheduling phases. To eliminate searching in ineffective neighborhoods and thus enhance computational efficiency of search algorithms, several lemmas are proposed and proven. The results of applying lemmas reflect up to 40% reduction in computational times. Comparing the optimal solutions found by CPLEX and tabu search shows that the tabu search algorithm could find solutions, at least as good as CPLEX but in incredibly shorter computational time. In order to trigger the search algorithm, two different initial solution finding mechanisms have been developed and implemented. Also, due to lack of a qualified benchmark for unrelated-parallel machines, a comprehensive data generation mechanism has been developed in a way that it fairly reflects the real world situations encountered in practice. The machine availability times and job release times are considered to be dynamic and the run time of each job differs on different machines based upon the capability of the machines.     

A Bayesian Approach to Batch Process Scheduling

The problem of decision timing in the context of batch scheduling is addressed in this paper. The representation of time in any scheduling model affects the number of integer variables and the convexity of the model. The usual procedure in batch process scheduling is to divide the scheduling horizon into equal size intervals to achieve the required accuracy. This construction generates a formulation with a potentially large number of binary variables. In this paper, the time events arising in the schedule are modeled directly, and thus the use of binary variables over periods during which no changes in system state occur is avoided. The problem is formulated as a mixed integer nonlinear program (MINLP). The Bayesian heuristic (BH) approach is used to implement a global optimization algorithm which effectively solves the resulting model. Computational comparisons using two text examples are made against a UDM (uniform discretization model) formulation. The results suggest that the BH approach combined with the nonuniform time discretization formulation shows promise for the solution of batch scheduling problems.     

面向Dataflow的异构集群混合式资源调度框架研究

Dataflow模型的使用,使得大数据计算的批处理和流处理融合为一体.但是,现有的针对大数据计算的集群资源调度框架,要么面向流处理,要么面向批处理,不适合批处理与流处理作业共享集群资源的需求.另外,GPU用于大数据分析计算时,由于缺乏有效的CPU-GPU资源解耦方式,降低了资源使用效率.在分析现有的集群资源调度框架的基础上,设计并实现了一种可以感知批处理/流处理应用的混合式资源调度框架HRM.它以共享状态架构为基础,采用乐观封锁协议和悲观封锁协议相结合的方式,确保流处理作业和批处理作业的不同资源要求.在计算节点上,提供CPU-GPU资源的灵活绑定,采用队列堆叠技术,不但满足流处理作业的实时性需求,也减少了反馈延迟并实现了GPU资源的共享.通过模拟大规模作业的调度,结果显示,HRM的调度延迟只有集中式调度框架的75%左右;使用实际负载测试,批处理与流处理共享集群时,使用HRM调度框架,CPU资源利用率提高25%以上;而使用细粒度作业调度方法,不但GPU利用率提高2倍以上,作业的完成时间也能够减少50%     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

Minimizing makespan for multi-spindle head machines with a mobile table

This paper presents a novel application of operational research techniques in Manufacturing. This concerns scheduling of multi-spindle head machines with a mobile table to minimize the makespan. We show that this problem can be formulated as scheduling for a single max-batch processing machine with inclusion, exclusion and precedence constraints between jobs. What makes this study unique from others in literature is that the batch processing time can exceed that of the longest job in the batch. The job compatibility and the batch time depend on the batch content, i.e. which jobs constitute the batch. This problem is transformed into finding the constrained shortest path in a specially constructed digraph. Dominance properties are developed to decrease the digraph's size. An industrial example is presented to illustrate the effectiveness of the proposed techniques.