约束优先边值固定最优控制嵌套优化方法

针对边值固定的最优控制问题,提出一种约束优先嵌套优化方法,将边值固定问题转化为嵌套的2个边值无约束最优控制问题.将两点步长梯度法实行内层优化求解满足边值约束的可行控制策略,与无记忆拟牛顿法实行外层优化求解最优目标函数相结合,避免了罚函数法的不足,提高了优化算法收敛的稳定性和高效性.同时引入一种特殊的控制变量转换方法,通过中间变量和函数转换消除控制边界约束.经典实例的研究结果表明,该算法在收敛性能和求解效率方面具有显著的优越性.

基于遗传算法的考虑优先约束和负载平衡的多任务调度

文章研究了考虑负载平衡、有优先约束的n个任务在m个同等处理机上处理,使总完成时间最小的分布式任务调度问题。对两个以上处理机的这类问题便是NP难题,因此以往都是用启发式算法来求解。文章首次提出了使用遗传算法来解决该类问题,设计了相应的编码方法和适应值评估方法,并用一个一维向量来表示任务间的优先关系。仿真结果证实了算法的有效性。

链优先约束工件单机随机排序问题

讨论单机随机排序问题 ,目标函数为确定工件的排列顺序使工件的加权完工时间和的数学期望最小。设工件间具有平行链优先约束 ,机器发生随机故障。考虑两种情况 ,第一种情况是链不允许中断 ,第二种情况是链允许中断 。

基于受约束区优先处理的城市配网规划变电站选址方法

在分析国内外变电站选址文献的基础上提出了一种改进型变电站自动选址方法,该方法以地理信息系统(GIS)为数据操作平台,在自动选址模型中提出了一种对城市受地理环境约束的负荷区域进行优先处理的方法,该方法免去了传统选址方法中后期对受约束区的繁琐处理过程,提高了变电站选址模型的自动化选址程度,同时考虑了专家意见对选址方案的影响。实例应用表明,该方法能满足城市配网规划的要求。

在Pro/E中自动生成零件拆卸优先约束矩阵

拆卸优先约束矩阵为建立产品的拆卸层次信息图模型提供了基础信息,保证了拆卸序列规划结果的正确性和有效性。在Pro/E中用C语言完成了零件拆卸优先约束矩阵自动生成的二次开发,包括模型调入和预处理、简单拆卸路径生成和包容盒逐级分解的干涉检验等3个模块。解决了自动判别节点可拆卸性的关键问题,为机电产品基于拆卸层次信息图建模的自动化提供了有力的支持。

一种启发式与/或优先约束任务调度算法

系统描述了与或网模型及与或优先约束任务调度的可行性判定算法.以顶点覆盖问题为基础,证明与或优先约束任务调度最小完成时间问题是NP完全的.提出一种启发式调度算法,解决与或优先约束任务调度最小完成时间问题.仿真结果表明,该算法在降低算法复杂度的同时较其它相关算法具有更好的调度性能,从而证明在实时优先约束任务调度中引入图优化的理论是解决优先约束任务调度问题的一个有效途径.

基于顶点覆盖问题解的与/或优先约束任务调度算法

系统描述了与/或网模型及与/或优先约束任务调度的可行性判定算法.以顶点覆盖问题为基础,证明与/或优先约束任务调度最小完成时间问题是NP完全的.提出一种启发式调度算法,解决与/或优先约束任务调度最小完成时间问题.通过算法示例表明,该算法对与/或优先约束任务图具有良好的调度性能,能够得到一个最优唯与任务图,从而证明在实时优先约束任务调度中引入图优化的理论,是解决优先约束任务调度问题的一个有效途径.

基于优先约束关系的装配序列规划研究

利用联结图方法建立设备的装配关系模型,生成联结矩阵,并利用子装配体的概念对模型进行简化。利用联结图模型分析零件间的优先约束关系生成优先关系矩阵,利用优先约束矩阵生成设备的可行装配序列,为设备装配序列选优提供基础。

考虑任务优先约束的同类岸桥作业调度优化

分析了以箱组为任务对象QCSP与以整贝为任务对象QCSP的异同,指出前者更能均衡各岸桥作业负荷,并减少船舶装卸作业时间。考虑到岸桥具有作业效率差异的特点,将其视为同类平行机调度问题,同时结合任务优先约束、岸桥作业不可相互穿越与安全距离等特有约束,建立了更加符合实际的以箱组为任务对象的岸桥作业调度混合整数规划模型,其优化目标是最小化装卸作业的makespan。针对模型求解的复杂度,设计了一种遗传算法,对算法搜索空间进行了讨论,并推导了问题的低界。实验算例表明所建立的模型能够反映岸桥作业调度过程中作业效率差异及任务优先约束现象,其算法能够在允许的运算时间内获得稳定的满意解,并且优化结果要全面优于以整贝为任务对象QCSP的调度方案。

GMPLS网络中基于约束的最短路径优先算法

对多种基于约束的最短路径优先算法设计思想进行了分析对比,选择了一种适用于GMPLS网络的路由算法,而且阐述了满足我们需求的设计方案。

具有优先约束的不完全恒速机排序问题

讨论了任务具有优先约束的可中断不完全恒速机排序问题，若处理机具有不同开始加工时间的可中断排序问题存在最优算法，则相应的不完全恒速机排序问题也有最优算法。

带有链优先约束的分批排序

研究了工件有不同的到达时间和平行链约束(也就是每一个工件至多有一个前驱和一个后继)的情形.考虑有m条链,其中一条链上包含n个工件,其余的m-1条链上的工件数总和为常数,给出了一个多项式算法.同时指出,对于其他正则单目标函数也是多项式可解的.

具有优先链约束的网格作业多资源调度问题

网格计算是网络并行计算的发展新趋势,网格系统中的分布式资源管理和调度一直是研究的热点和难点。对于网格应用作业的多资源调度问题,一个网格作业往往要分成多步骤进行,每个步骤都需要占用多个资源。首先将该问题抽象为典型的多处理机任务调度模型Pm|fix,p=1,chain|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行,而且每个任务都需要一个单位的处理时间,并根据优先关系形成链约束。该问题被证明为NP难问题。利用宽度优先技术和首次满足方法,构建了几个多项式时间近似算法,并通过模拟实验分析算法性能,实验结果显示算法是实用的。

GMPLS网络中基于约束的最短路径优先算法

对多种基于约束的最短路径优先算法设计思想进行了分析对比,阐述GMPLS网络的主要链路约束条件,提出了算法的准确度、算法的效率、约束处理能力三个标准,研究CSPF基于剪枝算法,选择了一种适用于GMPLS路由算法,优化了网络设计方案。

继承和优先约束驱动的柔性授权机制研究

针对权限系统中存在角色授权策略单一和授权冲突的问题,设计IPC_URBAC模型,在RBAC模型的基础上增加继承约束的用户直接授权机制和优先约束的用户角色分配机制,提出基于个体和优先的授权冲突解决策略,并给出用户权限和角色权限的求解算法。运用IPC_URBAC,构造二进制授权掩码进行复杂权限设置,应用Web Service完成细粒度权限检查,达到权限与业务的剥离,实现一种与业务无关的柔性授权系统。

工件有优先约束和尺寸的单机分批排序问题

研究了工件有优先约束和尺寸大小关系的分批排序问题,这里目标函数为工件的极大完工时间,这类问题是NP—完备的.对工件加工时间相同和有特殊到达时间的情况给出了它的近似算法,并证明其最差性能比不超过2.

工件加工随机调度中优先约束问题的研究

讨论工件加工时间为任意随机分布的随机变量的单机随机调度问题,设工件间的约束为树优先约束,目标函数为极小化加权完工时间和的数学期望。这一模型在机械设计与制造行业中的多个元器组件加工,以及钢铁板坯轧制等众多实际生产制造领域中都具有广泛的应用背景。证明了工件加工时间为任意随机分布的随机变量的情况下,最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的调度为最优调度,给出了最优多项式算法,该算法可以被推广应用于实际的生产中,具有较强的实际应用性。

优先约束的混合实时任务动态调度算法

为了对较大规模问题在短时间内给出满意的解并调度随机到达的非周期任务,提出了一种动态混合调度算法。在第一个截止期限错失时刻,通过分析系统的运行情况,推导出具有优先约束的实时任务可调度的充分条件。在系统运行前,判定周期任务的可调度性,预分配足够的处理机。当非周期任务到达系统时,在保证周期任务可调度的前提下重新给周期任务和非周期任务分配处理机。该算法具有多项式时间复杂性,适合解决较大规模的多处理机调度问题。实验结果表明,该算法有效提高了处理机的利用率和非周期任务的接收率。

混合优先约束下带模糊交货期的单机调度问题的研究

讨论了一类模糊交货期和混合优先约束下的单机调度问题.模糊交货期表示对任务完成时间的满意程度;混合优先约束包括普通优先关系和模糊优先关系,模糊优先关系反映了对任务间优先次序的满意程度.调度的目的是同时最大化模糊交货期和混合优先约束的最小满意程度.对于上述双目标函数调度问题,通过搜索非支配解,得到最优调度.

匹配算法在带链优先约束的分批排序中的应用

本文首次就带有链优先序的分批排序问题进行了讨论.优先约束是:包含有n个工件的一条链,另外有m个孤立点工件(即工件之间无任何优先约束).根据B与m的大小关系,分别讨论了它们的最优算法.优先约束为:工件之间有m条链T1,…,Tm,并且每条链是满足一致的.则对于B=2的情形,我们把这一问题多项式转化成了组合最优化中求解非二部图赋权匹配问题,并相应地提出了一个运算次数为O(n4)的多项式算法.