加工时间线性递减的平行机排序问题

主要讨论了具有两台处理机的平行机排序问题和每批恰为k个工件的串行工件同时加工排序的平行机排序问题。在这两个问题中,工件加工时间均为开工时间的线性递减函数,目标函数为极小化总完工时间。对于第一个问题,证明了其最优排序可由工件按基本加工时间不减排列得到,由此得出其最优算法,并指出了该结论对于加工时间随开工时间线性递增的情况并不成立。对于第二个问题,根据其与第一个问题在某些性质上的相似性,给出了其最优算法。最后指出所讨论的两个问题的结论均可推广到m台处理机的情况。     

N：K系统可靠度及备件量的仿真计算方法

采用基于排队网络的仿真模型来描述n:k(m)交叉储备系统，并给出了系统可靠度及备件最优储备量的仿真计算方法。本文的方法能适用于具有多个维修台的非马尔科夫型n:k(m)交叉储备系统。各种算例检验了本文方法的适用性。文末用解析的方法和本文的方法计算了马尔科夫型n:k(m)系统的可靠度及备件最优储备量，二者符合的很好。     

极小化加权总完工时间的同时加工排序问题

讨论了平行机串联工件同时加工排序问题。目标函数是极小化加权总完工时间,并假设满足每批均含有k个工件,并且每批的加工时间为该批中所有工件的加工时间之和。对平行机的情况,该问题是强NP难的。本文主要针对该问题的两种特殊情况:(1)所有工件的权相等;(2)所有工件的加工时间相等,分别给出了最优算法,分析了算法的时间复杂性,同时用数值例子作了说明。     

ON-LINE SCHEDULING WITH REJECTION ON IDENTICAL PARALLEL MACHINES

In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 （2 ＋√3） ≈ 1.86602.     

VERTEX-DISJOINT QUADRILATERALS IN BIPARTITE GRAPHS

H. Wang considered the minimum degrees condition that G has large vertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjoint cycles in bipartite graphs in this paper. We prove the following result: Let m > 3, n > 2 and k >1 be three integers. Let G = (V1,V2;E) be a bipartite graph with | V1| = | V2| =n > 2k 1. If the minimum degreefor any cycle C of G with length 2m, then G contains k vertex-disjoint cycles of length 4. Moreover, the degrees condition is sharp.     

MULTILEVEL CORRECTION FOR COLLOCATION SOLUTIONS OF VOLTERRA NONL INEARINTEGRO-DIFFERENTIAL EQUATIONS

1. IntroductionWe consider a Volterra integro-differential equationwith initial condition u(0) = not where f, P, k are continuous on their respective domainsJ, JxR and axs (n:~ {(t,s): 05s5t5T}) such that (1.l) possesses a unique solutionu E C'(J).It has been shown in [1] that the collocation approximation for (1.1) by discolltinuous piece--wise polynomial spline collocation at the Gauss points restore optimal local superconvergenceat the knots but does not yield global superconvergence on…     

多元超立方体交换结构信元丢失率仿真分析

研究了多元超立方体交换结构(MHSF)的信元丢失率性能。分析表明，当各交换节点的流量均匀地发送到各个目的节点时，MHSF的信元丢失率d与MHSF的元数k、链路加速因子s、链路缓冲大小m以及节点内部端口数M等因素有关；同时仿真结果显示，在可应用参数范围内，d明显有随着s、m或k(通常M固定)的增加呈指数规律下降的趋势，并且在较小参数条件下MHSF就具有较低的信元丢失率。     

视情维修条件下k/N(G) 系统备件供需联合优化

针对传统m视情维修策略下k/N(G)系统维修决策模型对备件可获取性考虑不足的问题,提出了(m,Q)维修策略及备件订购与生产的联合决策优化方法,建立了两种视情维修条件下k/N(G)系统备件供需联合优化模型。证明了在满足约束条件的同时,(m,Q)维修策略下的联合模型((m,Q, n) 策略模型)具有使目标函数最小的订购阈值m、订货量Q和订货次数n,m维修策略下的联合模型((m,n)策略模型)存在最优订货量m和订货次数n使目标值最小。此外,比较分析了不同模型参数对两种模型决策的影响,结果表明, (m,Q,n)策略模型得到的成本始终小于(m,n) 策略模型,而系统使用可用度始终高于(m,n)策略模型。     

基于MapReduce模型带准备时间的平行机调度优化

研究了一类基于MapReduce模型的平行机调度问题.每个工件包含Map和Reduce两道加工工序,Map工序可以分割为若干个子任务,并且在多台平行机上同时并行加工,Reduce工序只有在该工件的所有Map工序的子任务加工完成后才能进行,而且Reduce只能在一台机器上加工且不可中断.结合工件具有释放时间和加工准备时间等约束,以最小化最大完工时间为目标,构建了混合整数规划模型,并设计了采用差分变异策略和逐维Levy扰动机制的改进正弦余弦算法来求解该模型.最后,利用数值仿真实验与标准正弦余弦算法及遗传算法进行对比,实验结果表明,运用改进正弦余弦算法求解的结果与下界值的平均相对偏差GAP为3.02%,较标准正弦余弦算法以及遗传算法的效果提升显著,显示了该改进算法的有效性.     

基于混合迁移的OpenStack虚拟机在线迁移改进方案

为了提高虚拟机备份（包括运行时状态、存储、配置）的效率,提高虚拟机运行的稳定性和平衡物理机的负载,提出一种基于混 合迁移的OpenStack云平台虚拟机在线迁移方案. 该方案对虚拟机迁移采取共享存储迁移和存储块迁移相互结合的方式,以平衡 OpenStack云平台虚拟机在线迁移速度及备份有效性.结果表明：所提出的混合迁移方案能有效地提高OpenStack备份效率,同时减 少虚拟机在线迁移的时间和提高虚拟机迁移容错能力.     

半导体生产线批加工设备调度规则

批加工设备调度是半导体生产线调度的重要组成部分,对半导体生产线性能有重要影响。在综述批加工设备调度研究成果的基础上,提出了同时考虑即将到来工件与下游设备负载情况的半导体生产线批加工设备调度规则(Scheduling Rule for Batch Processing Machines in Semiconductor Wafer Fabrication Facilities,SRB)。基于三种不同规模的半导体生产线模型,在非批加工设备使用不同的调度规则的情况下,对提出的SRB进行了仿真验证。仿真结果表明,与目前常用的固定加工批量调度规则相比,SRB能够更好的改善半导体生产线性能,获得较高的工件移动步数、产量和准时交货率,以及较低的加工周期。     

基于支持向量机的压气机低转速特性研究

针对建立起动过程数学模型的过程中压气机低转速特性难以获取的问题，提出了对传统压气机特性目的一种转换方法，并在此基础上研究了基于支持向量机的压气机低转速特性获取方法。通过对某型涡扇发动机压气机低转速特性的推理，并结合发动机低转速部件特性的合理性判据可知，这种低转速部件特性的获取方法具有一定的精度，能够满足建立发动机起动过程数学模型的需要。     

重载双波冲击试验机正波系统建模与仿真

为使冲击试验机的模拟试验过程尽可能的贴近于实际的水下爆炸环境,满足最新抗冲击标准的要求,同时把传统中型冲击试验机的最大测试能力从2,700kg提高到5,000kg,对双波冲击试验机中用于产生正波的液压驱动系统、波形发生系统和基础隔振系统分别构建了动力学模型。根据模型分别针对设备在冲击速度为5.0m/s、4.0m/s和3.3m/s测试条件进行了系统仿真。仿真结果表明,该系统可以产生与最新抗冲击标准BV043/85和MIL-S-901D相吻合的冲击加速度波形。     

精确计算派系网络的Mandelbrot系数

研究了派系连接生成的复杂网络的拓扑性质。解析得到了m-派系网络的度分布和累积度分布函数,发现最小度的概率总是1/2。在度较大时,度分布的近似解析解服从Zipf-Mandelbrot分布律,度分布的幂律指数为(2m-1)/(m-1),Mandelbrot系数为m(5-2m)/(2m-2)。累积度分布为(k+ccum)-γ+1,Mandel-brot系数为c+1/2。数值模拟发现,所得Mandelbrot系数和幂律指数与理论值符合得很好。     

关于带有传输时间的F2|perm|Cmax排序问题的一个新算法

考虑传输时间的同顺序排序问题是在机器人设计及柔性制造系统中有着广泛应用的一类排序问题。     

一种针对大规模数据集的快速分组算法

基于空间点集的连通性构造的等价关系,提出一种针对大规模数据集的快速分组算法。该算法的本质仍是基于等价关系的集合划分算法,但在关系矩阵传递闭包的构造算法中,提出一种快速的实现方法。与传统等价关系的构造方法相比,新算法需要较少的存储空间,而且算法复杂度由O(n3)降为O(km2)(k n,m≈n)。在医学断层图像表面重建的应用中证实,新算法具有重要的应用价值。     

关于一类两台机器自由作业的排序问题

以工件完工时间的总和为优化目标的两台机器自由作业问题是NP-hard问题.本文针对加工时间仅依赖于机器并且机器连续加工的问题,给出了机器排序是可行排序的充分必要条件,引入可行排列的极小子排列的概念,运用组合优化方法,研究了最优排序中极小子排列的性质,并由此得到了该问题的最优时间表的一般构造方法.     

An optimal online algorithm for fractional scheduling on uniform machines with three hierarchies

This paper is concerned with the fractional version of online hierarchical scheduling problem on uniform machines. In the problem, the jobs and machines have several different hierarchies and each job can be arbitrarily split between the machines with hierarchies not above the hierarchy of the job. The objective is to minimize the makespan. The authors present an optimal algorithm for the problem with three hierarchies.     

具有阻塞影响的柔性制造系统排队网络模型

用有限容量局部库区的开排队网络模拟柔性制造系统，模型中，机床加工工件的时间服从指数分布，运送台车按照静态Ｍａｒｋｏｖ方式运送工件且运送时间服从指数分布，被阻塞的工件按照ＢＡＲ机理被处理，静态Ｍａｒｋｏｖ工件运送方式中的概率值受工件被阻塞的影响。     

平行机及自由作业的排序与转包

研究工件排序与转包相联的模型,即制造商从客户处接受一批工件,这些工件既可以由制造商加工,也可以一定费用转包给承包商加工.制造商需要确定被转包的工件集及工件的加工顺序,使得加工费用和转包费用之和为最小.研究制造商为平行机及自由作业,承包商为单机情况下的排序与转包模型,基于动态规划算法给出了近似算法,并分析了该算法的性能比.