Path problem simplification with desired bounded lengths in acyclic networks

Path determination is a fundamental problem of operations research.Current solutions mainly focus on the shortest and longest paths.We consider a more generalized problem;specifically,we consider the path problem with desired bounded lengths(DBL path problem).This problem has extensive applications;however,this problem is much harder,especially for large-scale problems.An effective approach to this problem is equivalent simplification.We focus on simplifying the problem in acyclic networks and creating a path length model that simplifies relationships between various path lengths.Based on this model,we design polynomial algorithms to compute the shortest,longest,second shortest,and second longest paths that traverse any arc.Furthermore,we design a polynomial algorithm for the equivalent simplification of the DBL path problem.The complexity of the algorithm is 0(m),where m is the number of arcs.     

资源均衡问题的峰值最小化模型

将资源峰值作为资源均衡程度的一种度量,以资源峰值最小化为优化目标,分别建立了工序不可分拆、可分拆和有条件分拆的资源均衡问题的整数线性规划模型,通过算例和工程案例验证了模型的有效性,并给出了多种资源情形下资源均衡问题的序贯解法.所建模型不涉及关键路线的确定和非关键工序浮时的计算,且各种资源峰值表述相互独立,因而对部分资源用量受限和对工序开(完)工时间有特殊要求的广义资源均衡问题也有较好的适应性.     

搭接网络的新表示方法与奇异现象研究

针对搭接网络,设计了新的表示方法,将工序之间的所有搭接关系(时距)都等效地用经典的关键路线法(critical path method,CPM)双代号网络表示,并且能直接运用CPM法计算搭接网络的各类时间参数,使搭接网络具有和CPM双代号网络一样的直观性和便利性,更使建工行业规定的计算程序大为简化.另外,利用搭接网络的新表示方法,发现了搭接网络中的奇异现象,例如,某些关键工序的工期缩短,总工期反而延长,而某些非关键工序的工期无论如何变动,其机动时间总保持不变,等等,为项目调度等问题的解决提出新的挑战,开拓了搭接网络在研究和应用上的新领域.     

Minimal feasible sets in variable resource constrained projects

To determine the reasonable resource dependent relations between activities for the purpose of exactly computing the total floats and the free floats of activities, correctly identifying critical activities and critical sequences in a project schedule with variable resource constraints, the concept of the minimal feasible set (MFS) is proposed and the properties of MFS are discussed. The methods to identify optimal MFSs and resource links are then studied. Furthermore, MFS is generalized to the situation that the preconditions of MFS are not satisfied. Contrastive results show that in establishing resource links and resolving floats, MFS is at least not inferior to other methods in all cases and is superior in most situations.     

基于蚁群算法的施工项目工期-成本优化

工期-成本优化是施工项目计划的一个重要方面.它从实质上属于一类多目标优化问题.结合近年来提出的一种新的进化算法-蚁群算法(ACO),尝试对工期成本问题(TCTP)进行求解.通过与改进自适应权重方法(MAWA)的结合,ACO算法不仅可以找到最优解,还可以得到问题的帕雷托前沿.通过一个算例验证了算法的有效性,并和枚举法和遗传算法的计算结果进行了比较.结果表明蚁群算法对于工期成本优化问题的求解是十分适用的.     

SOLVING RESOURCE—CONSTRAINED PROJECT SCHEDULING PROBLEMS WITH BI—CRITERIA HEURISTIC SEARCH TECHNIQUES

In this paper we formulate a bi-criteria search strategy of a heuristic learning algorithm forsolving multiple resource-constrained project scheduling problems. The heuristic solves problems intwo phases. In the pre-processing phase, the algorithm estimates distance between a state and the goalstate and measures complexity of problem instances. In the search phase, the algorithm uses estimatesof the pre-processing phase to further estimate distances to the goal state. The search continues in astepwise generation of a series of intermediate states through search path evaluation process withbacktracking. Developments of intermediate states are exclusively based on a bi-criteria new stateselection technique where we consider resource utilization and duration estimate to the goal state. Wealso propose a variable weighting technique based on initial problem complexity measures.Introducing this technique allows the algorithm to efficiently solve complex project schedulingproblems. A numerical example illustra     

基于随机活动工期的资源约束项目鲁棒性调度优化

项目进度计划的鲁棒性对于不确定条件下项目的顺利实施具有重要影响. 作者研究具有随机活动工期的资源约束项目鲁棒性调度问题, 目标是在可更新资源和项目工期约束下安排活动的开始时间, 以实现项目进度计划鲁棒性的最大化. 首先对所研究问题进行界定并用一个示例对其进行说明. 随后构建问题的优化模型, 设计禁忌搜索、多重迭代和随机生成三种启发式算法. 最后在随机生成的标准算例集合上对算法进行测试, 分析项目活动数、 项目工期和资源强度等参数对算法绩效的影响, 并用一个算例对研究进行说明, 得到如下结论: 禁忌搜索的满意解质量明显高于其他两种算法; 当资源强度或项目工期增大时, 平均目标函数值上升, 禁忌搜索的求解优势增强. 研究结果可为不确定条件下项目进度计划的制定提供决策支持.     

改进的模糊网络关键路径法

提出一种改进的模糊取最大运算和模糊减运算以确定模糊网络中的模糊时间参数. 改进的基于区间数距离测度的模糊取最大运算,通过枚举不同α-cut值,计算活动的模糊最早开始时间并确定项目可能变化的关键路径,从而解决了现有的研究中忽视了在活动工期模糊的情况下关键路径可能会发生变化的问题. 用改进的模糊减运算来计算活动的模糊最晚开始时间,有效避免了在传统的逆向递推计算中可能出现负的或者不可行解的情况. 通过一个实例验证了所提出的方法求解模糊网络时间参数的有效性和优越性. 所提出的方法不仅可用于模糊网络时间参数计算,也可以用于模糊资源受限项目调度问题.     

模糊指派问题求解方法研究

讨论了模糊指派问题的求解方法 ,并给出了求解两模糊数差值的模糊方程解的定义 .基于此定义将传统指派问题的匈牙利法进行了推广 .并结合一算例进行了说明 .本文所讨论的模糊方程解 ,可用于确定模糊工序时间的工程项目网络计划计划问题中的关键路线 .     

抛物问题中面向圆柱扫掠面的模型简化策略研究

在有限元计算中,随着模型复杂程度的增加,消耗的计算资源成几何级数增长,若模型过度复杂甚至可能导致计算失败。为了提高计算效率,确保计算顺利进行,简化模型十分必要。而模型简化前后的分析解将产生一定的偏差,为使计算精度达到分析要求,必须首先保证模型简化前后的理论解差异可控。以抛物问题中几何模型的圆柱扫掠面为研究对象,通过对初始模型进行初步简化并计算,辅助用户合理设定模型中各个圆柱扫掠面特征的简化阈值,并结合网格划分算法的特点设计算法产生面向特征的简化策略,使得模型简化前后的理论解差异在可控范围内,为进一步估计两者的分析解差异打下理论基础。最后以热分析为切入点进行了仿真实验,验证了结论的有效性。     

给定限制期条件下最小风险路径的选取算法

讨论在给定限制期情况下，边的长度（权值）为区间数的赋权图最小风险路径的选取算法，该算法将非线形比例路径问题的求解转化为最短路问题的变权迭代，算例及实际应用取得了令人满意的效果。     

Multi-Objective Cooperative Salvo Attack Against Group Target

This paper proposes a solution for the problem of cooperative salvo attack of multiple cruise missiles against targets in a group. Synchronization of the arrival time of missiles to hit their common target, minimizing the time consumption of attack and maximizing the expected damage to group targets are taken into consideration simultaneously. These operational objectives result in a hierarchical mixed-variable optimization problem which includes two types of subproblems, namely the multi-objective missile-target assignment(MOMTA) problem at the upper level and the time-optimal coordinated path planning(TOCPP) problems at the lower level. In order to solve the challenging problem, a recently proposed coordinated path planning method is employed to solve the TOCPP problems to achieve the soonest salvo attack against each target. With the aim of finding a more competent solver for MOMTA, three state-of-the-art multi-objective optimization methods(MOMs),namely NSGA-II, MOEA/D and DMOEA-εC, are adopted. Finally, a typical example is used to demonstrate the advantage of the proposed method. A simple rule-based method is also employed for comparison. Comparative results show that DMOEA-εC is the best choice among the three MOMs for solving the MOMTA problem. The combination of DMOEA-εC for MOMTA and the coordinated path planning method for TOCPP can generate obviously better salvo attack schemes than the rule-based method.     

Self-evident Automated Proving Based on Point Geometry from the Perspective of Wu’s Method Identity

The algebraic methods represented by Wu’s method have made significant breakthroughs in the field of geometric theorem proving. Algebraic proofs usually involve large amounts of calculations, thus making it difficult to understand intuitively. However, if the authors look at Wu’s method from the perspective of identity,Wu’s method can be understood easily and can be used to generate new geometric propositions. To make geometric reasoning simpler, more expressive, and richer in geometric meaning, the authors establish a geometric algebraic system (point geometry built on nearly 20 basic properties/formulas about operations on points) while maintaining the advantages of the coordinate method, vector method, and particle geometry method and avoiding their disadvantages. Geometric relations in the propositions and conclusions of a geometric problem are expressed as identical equations of vector polynomials according to point geometry. Thereafter, a proof method that maintains the essence of Wu’s method is introduced to find the relationships between these equations. A test on more than 400 geometry statements shows that the proposed proof method, which is based on identical equations of vector polynomials, is simple and effective. Furthermore, when solving the original problem, this proof method can also help the authors recognize the relationship between the propositions of the problem and help the authors generate new geometric propositions.

     

DNA计算在组合优化中的应用及其复杂性

在过去几年里,一些富有卓见的研究人员已经衔接了生物计算和实际的DNA计算之间的间隙。他们使用机灵的编码技术和聪明的分子生物学操作,找到了计算复杂问题的简单方案,并且解决了许多组合优化中的NP-完全问题。然而,计算的执行期间(生物反应过程中),技术的问题已经揭示了对于解决实际问题来说,DNA计算机作为硅计算机的竞争对手目前仍将是不可能的。主要介绍了目前利用DNA计算已经解决的组合优化中的NP-完全问题,并简单地分析了它们的复杂性。     

地空多元复杂网络用频优选模型研究

针对地空多元复杂网络用频规划和指配问题,提出了一种地空多元复杂网络用频优选模型。首先,将地空多元复杂网络节点以及节点之间关系进行抽象,从角色功能、移动能力和网络结构三方面提出了表现节点重要性的属性指标;然后,将节点作为决策的基本对象,并将节点属性作为影响决策方案的核心要素,利用灰关联投影多属性决策方法对每个决策方案距离理想决策方案的接近程度进行计算,得出决策方案的重要度序列;最后,通过对地空多元复杂用频网络进实例计算,验证了模型的有效性和合理性。     

基于活动重叠的随机活动网络时间费用模型仿真研究

活动重叠是压缩项目工期的手段之一,也是并行工程思想的重要体现。针对活动重叠模式特性进行了深入分析,在重叠机理研究的基础上,运用仿真工具分析了活动重叠条件下的时间费用模型。通过对仿真结果的分析,将活动重叠时的时间费用交换问题与活动压缩时的时间费用交换问题统一起来。     

多分辨率模型生成中颜色和纹理属性的处理

现有的图形处理系统难以对非常复杂的模型进行实时的存储，传输，显示等，一种有效的方法是根据要求生成一系列的多分辨率的简化模型。本文实现一种算法，不仅能进行几何简化，还能简化模型的表面属性，包括：颜色和纹理。本文对这个算法进行了详细介绍，并用图例显示了各种属性简化的结果。该方法可用在虚拟现实，计算机辅助设计和科学可视化领域。     

Some inverse optimization problems on network

In this paper, the authors consider some inverse problems on network, such as the inverse transport problems with gains (IGTP) and the inverse linear fractional minimum cost flow problem (IFFP). Firstly, the authors give the mathematics model of (IGTP) and an efficient method of solving it under l ₁ norm; Secondly, taking advantage of the optimality conditions, the authors consider the (IFFP) and give a simple method of solving it. Finally, an numerical example test is also developed.     

动态加强CPT解job-shop调度约束满足优化问题

带有相同到达期与交货期的job-shop调度问题(JSSP)作为多种实际生产调度问题简化模型,是一类典型强NP-hard问题.对优化目标是最小化最大完工时间的JSSP问题,建立了约束满足优化问题模型(JSSC-SOP).利用弧一致约束传播算法和深度优先启发式构造活动调度,逐步加入新约束,实现活动调度集的部分列举与寻优.提出3种动态加强约束传播技术(CPT),嵌入搜索过程,提高求解效率.最后通过随机生成的实例,验证了各方法可行性与有效性.     

资源受限项目调度中缓冲区的设定方法

基于资源受限项目调度(RCPS)的理论与方法,设计了一种项目计划中非关键链上工作缓冲区的设定方法.该方法综合考虑了工作在资源约束下的自由时间和根据根方差法计算的输入缓冲区的尺寸,分别针对每项非关键链上的工作设置时间缓冲区,既起到了保护关键链工作按计划执行的作用,又降低了项目净成本,同时避免了简单关键链管理方法因缓冲区设置而产生的工作间资源冲突.文中通过对资源受限项目调度问题(RCPSP)的标准问题库PSPLIB中典型案例的求解过程对算法的应用过程进行了描述.