改进二元分布估计算法求解置换流水车间调度问题

针对置换流水车间调度这类组合最优化问题的求解,提出了一种改进二元分布估计算法(Improved binary estimation distribution algorithm, I-EDA)。算法以二元分布估计算法为架构,使用NEH(Nawaz-Enscore-Ham)启发式算法生成初始解,提高了初始解的质量;通过对优势解的统计采样构建位置矩阵模型和链接矩阵模型,依照两个矩阵模型的合并概率组合链接区块产生子代。提出了NEH插入式重组策略和基于位置概率的交换策略和两种全新局部搜索机制替代原二元分布估计算法的相邻交换法,以进一步筛选优势解。最后通过对Reeves标准测试集的仿真实验和算法比较验证了所提出算法的有效性。     

A co-opetitive framework for the hub location problems in transportation networks

In this paper, we present the first model of co-opetition for a Hub Location Problem between two logistics service provider (LSPs) companies where the mother company is the owner of infrastructure. The LSPs would like to cooperate with each other by establishing joint edges with limited capacities connecting their service networks. Such services are in form of pendulum services (a direct service between two points) between nodes of different networks. Additional market can be generated as a result of joining the two networks. At the same time, a competition is taking place between the two operators to increase their share from the additional market generated. In order to solve this problem, we propose a matheuristic approach combining a local search algorithm and a Lagrangian relaxation-based approach. In our matheuristic algorithm, the neighbourhood solutions are evaluated using a Lagrangian relaxation-based approach. Numerical results of applying the proposed algorithm on a real case study of the problem are presented.     

An Efficient Algorithm for the Knapsack Sharing Problem

The Knapsack Sharing Problem (KSP) is an NP-Hard combinatorial optimization problem, admitted in numerous real world applications. In the KSP, we have a knapsack of capacity c and a set of n objects, namely N, where each object j, j = 1,...,n, is associated with a profit p _j and a weight w _j. The set of objects N is composed of m different classes of objects J _i, i = 1,...,m, and N = ^m _i=1 J _i. The aim is to determine a subset of objects to be included in the knapsack that realizes a max-min value over all classes.In this article, we solve the KSP using an approximate solution method based upon tabu search. First, we describe a simple local search in which a depthparameter and a tabu list are used. Next, we enhance the algorithm by introducing some intensifying and diversifying strategies. The two versions of the algorithm yield satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach.     

极大化提前完工总量平行机排序问题的LPT算法

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断, 目标是极大化所有工件的提前完工量, 即在交货期前所加工工件(或部分) 的总加工时长。由于该问题是NP-难问题, 本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为$\frac{15}{13}$, 并给出实例说明最坏情况界的下界为$\frac{27}{25}$。     

多商品分批次取送货的模糊需求车辆路径问题

为解决连锁企业库存不平衡问题,本文研究了考虑多商品多批次取送货的模糊需求车辆路径问题。该问题综合考虑了多货混装、多次访问、供需未匹配、客户需求不唯一以及需求不确定等因素。本文以运营成本最小为目标,构建MCVRPSPDFD数学模型,模型利用可信测度理论应对决策环境中的不确定因素,通过改进的禁忌搜索算法进行求解。为适应模型需求和提升运算效率,算法设计了合理的初始种群形成过程及编码解码方式,并通过参数测试选取合适的参数。算例结果显示,本文成果能有效解决连锁企业库存不平衡问题,决策者偏好值的变动会对运营成本产生影响。     

基于定量结构-性质关系方法预测氨基酸的比旋光度

运用定量结构-性质关系(quantitative structure-property relationsh ip,QSPR)方法对人体必需的氨基酸比旋光度进行了预测,同时运用交互检验(LOO)方法对所建立的模型进行了检验。应用启发式算法对描述符进行筛选并建立线性回归模型,所建立的模型的相关系数(R2)为0.918,但分别用 1、-1代表左旋和右旋的分子手性后,重新建立多元线性回归模型,其相关系数(R2)变为0.970。本研究所建立的QSPR模型为预测手性化合物比旋光度提供了一种有效的新方法。     

直观推导式演进特征投影法对环境样本中多环芳烃的定性定量分析

基于新近发展的直观推导式演进特征投影法(HELP), 本文提出了一个对二维数据进行同时定性定量的分析方法, 并将其成功地用于环境样本中多环芳烃化合物定量解析。对于一维色谱难以定量的重叠峰, HELP方法充分利用色谱、光谱两方面的选择性信息, 得到了具有真实物理意义的唯一解。在定性分辨结果的基础上, 本文还提出了三种可能的定量方法。这种二维数据的解析新方法, 能大幅度地降低对色谱分离条件的要求, 可直接用于复杂实际样本的定性定量分析。     

可压缩格子Boltzmann模型的启示性稳定理论

１引言格子Ｂｏｌｔｚｍａｎｎ方法（ＬＢＭ）是近几年发展起来的一种模拟复杂系统的新方法［１］［２］［３］这种方法已经在流体力学各领域得到应用．最近,许多研究工作集中于用ＬＢＭ模型计算可压缩流体流动．Ａｌｅｘａｎｄｅｒ和Ｃｈｅｎ等［４］提出了可以计算激波的等温模型,模型中的音速是可以选择的．Ｑｉａｎ和Ｏｒｓｚａｇ［５］分析了ＬＢＧＫ模型在可压缩区域内的非线性偏差,给出了激波结构的ＬＢＭ结果．Ｑｉａｎ和Ｏｒｓｚａｇ［６］也计算了弱可压缩的高Ｒｅ数问题,并用于计算Ｋｏｌ－ｍｏｇｏｒｏｖ流．Ａｎｃｏｎａ［…     

资源有限网络计划启发式方法的评价（上）：理论分析与试验设计

在对网络计划问题分析的基础上,提出了两个衡量资源约束网络计划问题复杂性特征的度量指标-网络复杂性系数CNC及有资源约束网络的复杂性系数CRNC,并基于此设计了一种产生给定网络复杂性要求的随机活动网络发生器GRAN,最后针对资源约束的网络计划问题设计了一种评价与分析其启发式算法效果的试验模型。     

Applying GIS and Combinatorial Optimization to Fiber Deployment Plans

A decision-support system for the Fiber Deployment Plan problem is developed for the telephone cable network design in the telecommunications industry. The system employs a Geographic Information System (GIS) and uses combinatorial optimization techniques as its components. A mathematical combinatorial optimization model is formulated for the problem and a heuristic solution procedure is developed for the model. A GIS within the ESRI Arc/INFO and ArcView environment is used to provide data needed to build the mathematical combinatorial optimization model and to furnish an interface between the users and computers in data input and in solution result display. Combinatorial optimization techniques are used in the heuristic solution procedure to find good solutions for the optimization model. The developed decision-support system has been used to real life problems and has resulted in tremendous improvements in the telephone cable network design process. The user is completely satisfied with the performance of the system.