基于多目标粒子群算法的混合流水车间调度方法研究

混合流水车间调度问题HFSP是一种具有很强应用背景的生产调度问题。本文给出了一种HFSP多目标调度模型,提出了一种针对该类问题的多目标粒子群算法。该算法采用基于Pareto支配关系的极值更新策略;采取对自适应惯性权重递减和对种群变异的方法以保持种群多样性;设置Pareto解池保存计算中出现的Pareto最优解,并提出了一种基于适应度拥挤度的聚类算法优化解的分布特性。实验结果表明,本文算法是求解HFSP问题的一种有效方法。     

一种合约构件的测试数据生成方法磁

针对构件质量受测试数据影响较大的问题,提出了一种合约构件测试数据生成方法。首先,对合约类型进行划分;对简单合约采取等价类划分、边界值选取和取随机值相合的方法,对复杂合约采取复杂合约联立组成线性方程组,利用高斯消元法求解线性方程组,得到相关测试数据;最后,对所有参数采用笛卡尔乘积的形式生成最终测试数据。实践证明,该方法提高构件测试效率,保证构件测试质量。     

A Hybrid Method for the Planning and Scheduling

We combine mixed integer linear programming (MILP) and constraint programming (CP) to solve planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. Tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). We solve minimum cost problems, as well as minimum makespan problems in which all tasks have the same release date and deadline. We obtain computational speedups of several orders of magnitude relative to the state of the art in both MILP and CP.     

基于混沌优化和最速下降法的一种混合算法

将混沌优化和最速下降法有机地结合起来,构造出一种混合优化算法,该算法既具有混沌优化算法的全局收敛性,又有最速下降法的快速收敛性,数值试验表明算法是有效的。     

基于使用剖面的软件可靠性测试用例生成方法

为了获得软件的可靠性指标,需要设计操作剖面来仿真用户实际使用软件的情况,并基于操作剖面来进行可靠性测试.传统的基于操作剖面的可靠性测试方法难以适用于航天软件,为了解决此问题,描述了一种具有层次化网络体系结构特征的使用剖面的形式化定义,阐述了构造这种使用剖面的系统化方法,给出了根据使用剖面生成用于软件可靠性测试操作序列的算法,以及基于操作序列生成可靠性测试用例的方法.提出的方法经过实验验证表明是可行的.     

分布式博弈树搜索算法

本文提出了分布式博弈树搜索ＤＤＳ算法，从通信开销、存储开销、加速比等方面分析了算法性能，并与ＳＳＳ和α－β算法在搜索结点个数方面作了比较，模拟实验表明ＤＤＳ是一种高效实用的分布式搜索算法。     

A Lamarckian Approach for Neural Network Training

In Nature, living beings improve their adaptation to surrounding environments by means of two main orthogonal processes: evolution and lifetime learning. Within the Artificial Intelligence arena, both mechanisms inspired the development of non-orthodox problem solving tools, namely: Genetic and Evolutionary Algorithms (GEAs) and Artificial Neural Networks (ANNs). In the past, several gradient-based methods have been developed for ANN training, with considerable success. However, in some situations, these may lead to local minima in the error surface. Under this scenario, the combination of evolution and learning techniques may induce better results, desirably reaching global optima. Comparative tests that were carried out with classification and regression tasks, attest this claim. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Pattern Recognition Approach for Speculative Firing Prediction in Distributed Saturation State-Space Generation

The saturation strategy for symbolic state-space generation is particularly effective for globally-asynchronous locally-synchronous systems. A distributed version of saturation, SaturationNOW, uses the overall memory available on a network of workstations to effectively spread the memory load, but its execution is essentially sequential. To achieve true parallelism, we explore a speculative firing prediction, where idle workstations work on predicted future event firing requests. A naïve approach where all possible firings may be explored a priori, given enough idle time, can result in excessive memory requirements. Thus, we introduce a history-based approach for firing prediction that recognizes firing patterns and explores only firings conforming to these patterns. Experiments show that our heuristic improves the runtime and has a small memory overhead.     

基于Petri网的混合动态系统接口层设计方法及其在热连轧中的应用

接口的设计是整个混合动态系统实现的关键。模拟模块化的思想，提出了基于Ｐｅｔｒｉ网转换器的实现方法，并且设计了热连轧过程从数值到符号的转换接口，为下一步实现实时调度奠定了基础。     

A Stylized Approach for Pencil Drawing from Photographs

We present a stylized scheme that produces pencil drawings in a range of styles from an image. To produce controllable pencil drawing effects and remedy the problems of existing convolution‐based schemes, we develop a swing bilateral LIC (SBL) filter. Our first approach to express the styled pencil drawings is to control the directions of pencil strokes that depicts both shapes and smooth tone. Another approach is to produce colors of pencil drawings by sampling colors from real color pencils. The third approach is to mimic the artistic technique that increases the details of drawings in a progressive manner. We present drawings in several styles and compare some of them directly with illustrations taken from an artists' work.     

A branch and price algorithm for the SS/TDMA problem with cardinality constraint

In this paper, we consider a square n×n traffic matrix D   and a satellite having l≤n$l\le n$ receiving and transmitting antennas. Transmissions are allowed by interconnecting pairs of receiving–transmitting antennas, through an on-board switch. We also assume that no preemption of the communications is allowed, and that changing the configuration of the switch requires a negligible time. We ask for a set of switch configurations that minimizes the total time occurring for transmitting the entire traffic matrix. In the literature, an exact method has been already proposed for the SS/TDMA optimization problem without cardinality constraint (i.e. for instances having l=n), but only heuristics have been proposed for the general case. In this paper, from a known MILP formulation we derive an extended formulation, and we use a column generation method to obtain its LP-relaxation. We address the derived pricing problem through a polynomial time algorithm based on solvers for the k-cardinality assignment problem. We insert this lower bound method in a two-phase branch and price algorithm in order to obtain the optimal solutions. To compare our new exact method with the one proposed in literature to solve the SS/TDMA optimization problem without cardinality constraint, we extend this older method to consider the cardinality constraint. The final computational experiments, comparing our new method with other already known methods, show the efficiency of our algorithms.     

基于粗精调技术的求解带平衡约束圆形Packing问题的拟物算法

带平衡约束的圆形Packing问题是以卫星舱布局为背景的具有NP难度的布局优化问题.文中建立了此问题相应的数学模型,同时提出了两个新的物理模型,并受工艺加工过程中“粗精加工”现象的启发,提出了基于粗精调技术的拟物算法QPCFA.该算法既兼顾了搜索空间的多样性以利于全局搜索,又能对有前途的局部区域进行精细搜索以找到相应的局部最优解.同时,在计算过程中引入禁忌技术和跳坑策略,以提高算法的求解质量.对国际上11个代表性的算例进行了计算,QPCFA更新了其中7个算例的最好记录,其余4个与目前的最好记录基本持平,且与目前的最好结果相比在计算精度上均有较大的提高.     

求解卸装一体化的车辆路径问题的混合启发式算法

提出一种结合蚁群系统(Ant Colony System,ACS)和变邻域下降搜索(Variable Neighborhood Descent,VND)的混合启发式算法ACS_VND,求解卸装一体化车辆路径问题.利用基于插入的ACS解构造方法产生多个弱可行解,再逐个转换成强可行解,并选择其中最好的作为VND的初始解.在VND过程中使用三种不同的邻域结构:插入、交换和2-opt依次对解进行迭代优化.对55个规模为22~199的benchmark算例的求解结果表明,算法ACS_VND能在较短时间内获得52个算例的已知最好解,并且更新了其中44个算例的已知最好解,求解性能优于现有算法.     

Performance comparison of enhanced PSO and DE variants for dynamic energy/reserve scheduling in multi-zone electricity market

During the last decade, energy regulatory policies all over the globe have been influenced by the introduction of competition. In a multi-area deregulated power market, competitive bidding and allocation of energy and reserve is crucial for maintaining performance and reliability. The increased penetration of intermittent renewable generation requires for sufficient allocation of reserve services to maintain security and reliability. As a result the market operators and generating companies are opting for market models for joint energy and reserve dispatch with a cost minimization/profit maximization goal. The joint dispatch (JD) problem is more complex than the traditional economic dispatch (ED) due to the additional constraints like the reserve limits, transmission limits, area power balance, energy-reserve coupling constraints and separate sectional price offer curves for both, energy and reserve.The present work proposes a model for the joint static/dynamic dispatch of energy and reserve in deregulated market for multi-area operation using enhanced versions of particle swarm optimization (PSO) and differential evolution (DE). A parameter automation strategy is employed in the classical PSO and DE algorithms (i) to enhance their search capability; (ii) to avoid premature convergence; and (iii) to maintain a balance between global and local search. The performance of enhanced PSO and DE variants is compared for single/multi-area power systems for static/dynamic operation, taking both linear and non-smooth cost functions. The proposed approach is validated on two test systems for different demands, reserve requirements, tie-line capacities and generator outages.     

A Graph‐based Approach to Continuous Line Illustrations with Variable Levels of Detail

This paper introduces a method for automatically generating continuous line illustrations, drawings consisting of a single line, from a given input image. Our approach begins by inferring a graph from a set of edges extracted from the image in question and obtaining a path that traverses through all edges of the said graph. The resulting path is then subjected to a series of post‐processing operations to transform it into a continuous line drawing. Moreover, our approach allows us to manipulate the amount of detail portrayed in our line illustrations, which is particularly useful for simplifying the overall illustration while still retaining its most significant features. We also present several experimental results to demonstrate that our approach can automatically synthesize continuous line illustrations comparable to those of some contemporary artists.