新工件到达锁定初始调度的单机重调度问题

研究了新工件到达锁定初始调度的单机重调度问题.即有一组带有不同释放时间的初始工件已经按照最小化完成时间和的优化目标调度完毕,形成初始调度且已锁定,此时有一组释放时间为零的新工件到达,且需要插入初始调度进行加工,其优化目标为最小化新工件的完工时间和.文中研究了新工件的加工过程可中断和新工件的加工过程不可中断,共2类新工件到达锁定初始调度的单机重调度问题.分析了重调度问题的复杂性,针对第一类重调度问题提出了多项式算法并证明了其最优性.证明了第二类重调度问题为NP完全问题,提出了一个多项式算法,并证明了该算法的有效性和最优解的特征,解决了企业实际问题并进一步丰富了重调度理论.     

锁定初始调度的紧急工作单机重调度问题

对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(reschedulingrushjobswithloadslockedonsinglemachine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.     

基于离散蜂群的应急物流车辆调度算法

为在尽可能满足应急物流时间要求的前提下最大程度的节约运输成本,提出了一种基于离散蜂群的应急物流车辆调度算法.该算法首先综合考虑运输车装载容量和受灾点的单边硬时间窗约束,构建了以最小化配送成本为目标的数学规划模型,然后利用离散蜂群算法进行优化求解,通过引入离散差分搜索强化其领域搜索能力,同时借助侦查蜂进行个体淘汰操作,从而避免算法陷入局部最优.仿真实验表明,与基于蚁群算法的应急物流车辆调度算法相比,该算法具有较强的鲁棒性,能够快速获得应急物流车辆调度问题的优质解.     

无缓存流水线生产系统中AGV调度问题的研究

针对无缓存流水线生产系统中的AGV(automated guided vehicle)调度问题提出了复合评分的启发式调度算法,降低了系统中AGV执行任务的间隔等候时间.首先,通过建立数学模型,对目前主流的AGV规模估计方法做出了改进.其次,提出了一种新的基于复合评分禁忌搜索的AGV前瞻调度算法.不同于目前主流的以空驶距离为优化目标的调度算法,该算法能够以最小化工件延误时间、最小化AGV空驶距离等多目标来统筹调度AGV.最后,为验证所提算法的有效性,从多个角度与已有算法进行了实验对比.仿真实验结果表明,相较于其他算法,提出的前瞻调度算法能够更有效地解决无缓存流水线生产系统这一新场景的AGV调度问题.实车实验也证明了该算法在实际生产中的有效性.     

Petri网的遗传算法在Job-Shop问题中的应用研究

提出了一种基于扩展时间Petri网（ETPN）的单亲遗传算法,并利用该算法对Job-Shop调度问题进行了求解．首先定义一种扩展时间Petri网,然后利用定义的扩展时间Petri网对Job-Shop调度问题进行建模,最后应用单亲遗传算法对模型进行优化调度．通过实例证明了该建模方法和优化算法的有效性和正确性．     

一种智能仓库车辆调度问题的新算法

将调度问题与遗传算法相结合,提出一种用于解决智能仓库车辆运输调度问题的一种新算法,并用计算实例证明了该调度算法的正确性,并能适应大规模车辆的调度问题．本算法计算量小,具有很强的鲁棒性．     

交换机中周期流优化调度问题的复杂性

研究了交换机中周期流量的优化调度问题,着重讨论了该问题的复杂性.依据呼损率定义了交换机周期流量调度的最优化问题,并对其子问题,嵌套周期流优化调度的复杂性进行了研究.证明了一种受限Max2Sat问题的NP完全性,并通过将该问题多项式归约到交换机周期流量调度的最优化问题,由此证明了仅有1和2周期的交换机周期流优化调度问题是强NPC问题.并利用该结果证明了任意嵌套周期的优化调度问题也是强NPC的.这表明对于任意嵌套周期流优化调度问题不存在伪多项式算法.     

多Agent系统中的任务可调度问题

为了将Agent方法应用于应急系统等新领域,在对该类系统研究的基础上提炼出它们的公共特征,根据这些特征设计出一种MAS系统模型,并在该模型的基础上定义了相应的任务可调度问题.利用网络流模型对可调度问题进行了建模,证明了最大流算法可以求解该可调度问题,由此说明该问题是可多项式时间求解的.并且对于给定该问题的一个可调度实例,利用最大流算法还可在系统中找到一组Agent完成所有任务.通过对该网络流模型的进一步分析,得出并且证明了任务可调度判定的充分必要条件,利用这个结论可以快速判断当前任务是否可调度.     

基于基因表达式编程的网格调度节点选取算法

为了在网格的动态分域调度机制中,更前瞻性地动态选取域内“计算结点”,解决原传统算法中需要依赖专业知识,而使选取过程具有主观性和盲目性的问题,提出了基于基因表达式编程(GEP)的网格调度域计算结点的选取算法.并通过对基于传统遗传算法进行选取和基于GEP进行选取的算法的比较,实验证明了该算法的优越性与实用性.     

钢卷仓库中的吊机调度问题

研究了钢铁企业冷轧原料库中的吊机调度问题.将吊机的运输和倒垛操作集成考虑,目标函数为将全部需求板卷运输到指定位置的时间最小化.对于该问题,首先提出了一个混合整规划模型,进一步证明了该问题是强NP难的.基于对问题性质的分析,针对无倒垛操作的特殊情况,提出了多项式时间可解的最优算法.对于问题的一般情况,提出了一个启发式算法并分析了它的最坏情况.     

度、直径约束最小生成树问题及其算法

提出了度、直径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法,其时间复杂性为O(mn).分析和实例实验表明,该算法有良好的效果.     

度、半径约束最小生成树问题及其算法

提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果.     

一类非线性条件稳定奇摄动系统的Dirichlet 问题

用边界函数法讨论了一类非线性条件稳定的具有Dirichlet边界条件的奇摄动系统, 构造了它的形式渐近解,并证明了该形式渐近解的一致有效性. 解的存在唯一性也得到了证明.     

抛物型方程的O(h4)精度新交替分段显隐格式

给出了对流扩散方程的一种高精度新的交替分段显隐格式。它可以用于并行计算,且无条件稳定,空间的精确度可以达到O(h4)阶,最后的数值实验也证实了这一点。     

Hamming距离下的最短路逆问题

针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.     

点赋权图上固定顶点的树划分问题

考虑了点赋权图上固定k个顶点的树划分问题.首先证明了点赋树图上固定k个顶点的最小最大树划分问题是NP-难的,然后给出了该问题的一个启发式算法,最后证明了该算法是点赋权完全图上固定k个顶点的最小最大树划分问题的一个2-1k近似算法.     

求解非线性互补问题的非单调自适应信赖域算法

利用FB-NCP函数将求解非线性互补问题等价转化为求解无约束问题的一个全局极小值.提出一种非单调自适应信赖域算法,并在FB正则的条件下得到该算法是全局收敛性结果.在适当的假设下,进一步证明了该算法的局部超线性收敛和二次收敛性.     

超图在树环中的嵌入问题

H为定义在树环G上的一个超图,将H的每条超边映射为G中不同的树,称为超边在G中的嵌入问题．超图在树环中的嵌入问题即为寻找H在G中的最优嵌入使得G中任一边被H所有超边的嵌入经过的最大次数最小．将超图嵌入圈(MCHEC)问题的算法简化可得EHTR问题的一个PTAS算法,且可证明EHTR问题为NP-完全的．     

二维RLW方程的差分方法

给出了二维RLW方程的初边值问题的差分格式,并证明了该差分格式的解以L∞范数收敛到初边值问题的解,收敛阶为O（τ＋h）,并且得出二维RLW方程的该差分格式以L∞范数稳定。     

梁横向振动方程解的Ritz方法

考虑计算梁横向振动方程解的Ritz方法.主要结果的证明运用变分法.首先,证明变分问题（2）与问题（1）等价;其次,采用坐标函数系来构造适当的近似解;最后,将问题（1）的解的近似计算问题离散化为线性方程组解的计算问题,获得了计算问题（1）解的近似值的Ritz方法,而且可以用第n次近似值来估计第n-1次的近似值的精确度.随着n的增大,解的精确度逐步提高,只要适当选取n,就可以求得所要精确度解的近似值,这个算法具有广泛的实用价值和理论价值.