有限制条件的单台机器的排序问题

根据给定n个工件在一台机器上加工时工件间的先后关系 ,定义了一个n个顶点的有向图D ,简化图D得排序图D ,通过穷举图D 的顶点的拓扑序列 ,搜索出了n个工件完工时间之和最小、机器加工完n个工件总时间最少和延误损失最少的加工顺序 .     

恶化工件具有p-s-d安装时间的非同类机排序

主要讨论了恶化工件具有p-s-d安装时间的非同类机排序问题.工件的实际加工时间与开工时间有关,安装时间是依赖于所在机器上已加工完的工件的加工时间的简单函数,即p-s-d形式.本文所考虑的问题是如何确定工件在非同类机上的加工顺序使得所有工件的总完工时间最小.在每台机器上加工的工件数确定的情况下,将该排序问题转化为一个指派...     

排序问题中求工时矩阵最大可行和的一种算法

本文通过引进一种关于斜阵的某些概念提出了同顺序m×n排序问题中总工时的一种计算方法。同时,文中指出的空闲时间矩阵说明了对于最优序和较优序,仍存在可以利用这m台机器再进一步加工这n个工件以外的工件的机会。并且,从该方法出发可以进一步提出一种解决关于m×n排序问题的方法。     

流水车间排列排序专家系统—PFSCH

流水车间排列排序问题可以简单表示为:n/m/p/F_(max),其含义为,n个不同的工件(J_1,J_2,…,J_n)要经m台机器(M_1,M_2…,M_m)加工;加工路线为M_1—M_2—…—M_m,n个工件在每台机器上的加工顺序都一样;p表示排列排序;目标函数是使最长流程时间F_(max)(加工周期)最短.n个工件有n!种不同的加工顺序.现已证明,n/m/p/F_(max)(m≥3)问题属于NP难题,找不到多项式时间算法.因此,人们提出了若干个启发式算法,其中最著名的是Campbell等人提出的启发式算法(简称为CDS法).Dannenbring曾比较过11种不同的启发式算法的效果,指出“快速接近扩展搜索法(RAES法)”的结果最好.但是,RAES法实质上还是一种列举法,它不从问题本身的结构出发,具有很大的盲目性.虽     

一类计划排序问题确定相邻两零件次序的条件

文中考虑n个零件在m台机器上加工且在每两台机器加工时段之间存在停歇时段,以总加工时间最小为目标当零件加工同顺序的排序问题。其主要结果是将同顺序m×n排序问题中著名的越——韩条件推广到有停歇时间的问题中,得到两个确定相邻两零件次序的条件(定理4,定理5)。     

带运输时间和单自动机的流水作业排序

本文研究n个工件在2台机器上加工的流水作业排序问题。同一工件在一台机器上完工后在下一台机器加工之前有一个时间间隔即运输时间,所有运输时间都是由单自动机来完成运输,同一时间自动机只能运输一个工件,本文主要研究所有加工时间均匀等于1的情况下该问题的复杂性,并给出新的启发式算法,证明该算法的最坏性能比是3/2,且上界是紧的。     

调整时间可分离的FlowShop调度问题F3|s|C_(max)

研究了三台机器调整时间可分离的FlowShop调度问题,目标函数为极小化最大完工时间·证明了最优调度可能不是排列调度,但是工件在前两台机器上具有相同加工顺序的调度中至少存在最优调度·在排列调度范围内,对于工件在第二台机器上的调整时间与加工时间之和的最大值不超过工件在第一台或第三台机器上的调整时间与加工时间之和的最小值的情况,给出了求解最优调度分派规则,并以分派规则为基础给出了多项式最优算法     

F2|rj,tj|Cmax问题的多项式时间近似算法

针对具有到达时间和运输延迟的两机器流水车间排序问题F2|rj,tj|Cmax,证明了有运输时间约束的条件下,该问题最优排序是同顺序的,并给出了一种基于动态规划的多项式时间近似算法.     

带有可变加工时间和可用性限制的排序问题

研究带有恶化效应、学习效应和可用性限制的单机和2台平行机的排序问题。在这个模型中,工件的实际加工时间与其基本加工时间、加工过程中所排位置及开始加工时间有关;同时由于维修、保养等原因,使得机器在某段时间不能加工工件,即机器具有可用性限制,且维修之后机器性能完全恢复,讨论的目标函数为总完工时间。对于可以在任意时间只维修一次的单机问题,以及只有一台机器具有可用性限制的2台平行机问题,分别给出了拟多项式时间的动态规划算法。特别对于一台机器只在零时刻开始维修另一台机器无可用性限制的特殊情况,通过将其转化为指派问题,给出了复杂性为O(n4)的多项式时间最优算法,并通过一个数值例子说明了其计算过程。     

一类多机排序问题算法及其计算复杂性研究

在经典排序论中，一般都假设每个工件在任一时刻仅被一台机器加工，且每台机器至多仅加工一个工件。在这篇文章中，研究这样一类排序问题：每个工件可以被多个不同的机器子集加工，其加工速度对于不同的机器子集是不同的，被加工的工件假定是可以间断且是独立的。排序问题的性能测度是排序长度。在以上条件下求解这类问题算法被给出，对其计算复杂性也作了研究。     

一类复合并行机排序问题的多项式时间算法

在经典排序论中，一般都作以下两条假设：每台机器在任一时刻至多加工一个零件，每个零件在任一时刻至多被一台机器加工。本文研究在并行加工中多台机器可同时加工一个零件的排序问题，且每个零件可在固定的一个机器的子集上加工。在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究这种问题的计算复杂性。     

具时间依赖源的双非线性抛物方程的Cauchy问题

研究了方程ut-div(|Dum|p-2Dum)=t-σuq的Cauchy问题, 其中m>0, p>1。此方程为双非线性抛物方程,根据参数m, p的不同取值,方程主部会发生双重退化或双重奇异性。本文利用先验估计和紧性方法以及对参数m, p作精细划分,得到了测度初值解的最优存在性。     

An efficient parallel algorithm for shortest paths in planar layered digraphs

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.     

矩阵元〈n|x~k|m〉通式的推导

本文给出矩阵元〈n|xk|m〉通式的最简推导方法。     

三角Stein方程的systolic算法

提出一种新的ｓｙｓｔｏｌｉｃ实现方法计算三角Ｓｔｅｉｎ方程．可将原复杂性为Ｏ（ｍ２ｎ２）的串行算法在处理器为Ｏ（ｍ２）的ｓｙｓｔｏｌｉｃ阵列上并行计算，时间复杂性降为Ｏ（ｍｎ），而处理器具有很高的利用率．利用文中给出的方法，可以并行求解一大类最优控制中有关矩阵运算的问题，如Ｌｙａｐｕｎｏｖ方程、Ｓｙｌｖｅｓｔｅｒ方程等     

多序列比对问题的并行近似算法

基于中心方法的思想,采用分治策略,在SIMD-CREW模型上设计了一个使用O(k2m)个处理器(其中k为序列个数,m为最长的序列长度),时间复杂度为O(m logk)的并行近似算法.在实际情况中,由于logk远远小于m,相对于时间复杂度为O(m2k2)的串行中心方法,该算法在理论上达到线性加速.与现有的并行算法相比,它可以适用于任意情况,且易于分析时间复杂度.利用LARPBS模型的特点和并行求前缀和的方法,调用LARPBS模型上求和与最大(小)值的并行算法,首次给出了在LARPBS模型上的多序列比对问题的并行近似算法.该算法使用O(k2m)个处理器,时间复杂度为O(m log log D),其中D为序列两两比对的代价值的最大值.该算法同样适用于任何情况,由于log log D通常远小于m,所以它在理论上也是线性加速的.     

一种同步流水算术编码器的设计

针对JPEG2000标准中的算术编码器实现时,在上下文(CX)表更新、归一化及字节输出过程中具有返回或等待路径问题,提出一种新的同步流水算术编码器设计方案．该方案采用4步流水线设计,通过流水线操作的时序分析,得到了CX表的单步更新方法,并设计了一种树型搜索的寄存器的短延时0位检测电路．引入多路选择器来加速实现任意位左移,在提高主关键路径并行性的同时,采用了多种方法对寄存器传输级代码进行优化．实验表明,在EP1S258672C7上,最高工作时钟可达107．91MHz．     

带有临界Sobolev-Hardy指数的奇异非齐次双调和问题

设Ω是RN(N≥5)中的有界光滑区域,0∈Ω,0≤s＜4,2*(s):=2(N-s)/N-4是临界Sobolev-Hardy指数,f(x)是一个给定的函数.利用变分原理,证明了当f(x),λ,μ满足一定条件时,带有Dirichlet边值条件的奇异临界非齐次问题△2u-μu|x|4=|u|2*(s)-2/|x|su λu f(x)解的存在性.     

角动量阶梯算符的一种构造方法

本文以角动量的对易关系出发,推导出一组阶梯算符,它可使角动量本征矢的量子数j(或ι)、m同时升降、并找出这组算符之间的关系,给出了这些算符作用于轨道角动量本征态|ιm>上的系数。