面向流程工业的批在线调度问题

从钢铁生产热轧流程中提炼出了在同构并行机上的批在线调度问题,它是流程工业中MES的重要环节。从理论上给出算法并研究了算法的性能。工件以批的形式到达,目标函数是使工件的最大完成时间最小。当一个批到达时,将这一批中的工件分成若干组,要求在同一组中的工件可以具有不同的开始加工时间但必须具有相同的完成时间。通过将批调度与在线调度的结合,给出了最坏情况比（竞争率）分别为m／（1＋（m-1）ε）,m（1-ε）／（1-ε）,m／（1＋gε）的批在线调度算法。     

具有线性恶化加工时间的调度问题

讨论了工件具有线性恶化加工时间的调度问题.在这类问题中,工件的恶化函数为线性 函数.对单机调度问题中目标函数为极小化最大完工时间加权完工时间和,最大延误以及最大费 用等问题分别给出了最优算法.对两台机器极小化最大完工时间的Flowshop问题,证明了利用 Johnson规则可以得到最优调度.对于一般情况,如果同一工件的工序的加工时间均相等,则 Flowshop问题可以转化为单机问题.     

带有线性恶化工件和释放时间的两个代理单机调度问题

研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题. 所有工件在一台机器上加工, 每个代理有各自依赖于自己工件的优化目标. 针对工件释放时间相同与不同两种情况, 研究了有约束的优化模型, 即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界. 当工件具有相同的释放时间, 我们主要考虑的目标函数有: 总加权完工时间和总加权拖期工件数. 当工件具有不同释放时间, 我们考虑的目标函数有: 最大完工时间、总完工时间以及拖期工件数. 对于每一个问题, 我们分析了问题的计算复杂性. 此外, 对于NP难问题的一些特殊情况本文分析了最优解性质, 基于这些性质给出了最优算法.     

带尺寸约束的二机流水车间生产运输协调博弈调度问题

研究二机流水车间生产运输协调调度问题,当工件在第1台机器加工完成后,由1台带有容量限制的运输车分批次运输到第2台机器加工,运输过程考虑工件尺寸约束,目标函数为最小化最大完工时间.考虑到源于不同客户的工件对机器及运输设备的竞争,以工件为博弈方,工件在生产运输过程中等待时间为策略,各工件完工时间为收益,建立非合作博弈模型.通过将问题转化为马尔可夫决策过程,设计线性逼近值函数的Q-learning算法求解纳什均衡调度.实验结果表明Q-learning算法求得的纳什均衡调度具有较好的全局最优性,从而能够在满足客户的利益下,提高企业的生产效率,实现客户与企业的双赢.     

两机无等待流水车间调度问题的性质

针对两机无等待流水车间调度问题,提出目标函数最大完工时间最小化的快速算法,并给出算法的复杂度。分析两机无等待流水车间调度问题的排列排序性质,证明了两机无等待流水车间调度问题的可行解只存在于排列排序中,排列排序的最优解一定是两机无等待流水车间调度问题的最优解。最后研究了同时包含普通工件和无等待工件的两机流水车间调度问题的复杂性,为进一步研究两机无等待流水车间调度问题提供了理论依据。     

基于到达时间两台并行机上在线批调度

考虑两台同构并行机上在线批调度问题．每个批具有不确定的到达时间,一旦机器可以利用,要在当前可以利用的批中选择出合适的批,并将其中的工件调度到机器上,且工件在加工过程中不允许中断．目标函数是使调度的最大完成时间最小．给出了一个批在线调度ＲＢＬＰＴ算法,即选择当前批中加工时间之和最大的批按ＬＰＴ 规则调度．另外,利用反证法,对算法的最坏情况进行了分析．     

缓冲区有限的流水车间调度问题的启发式算法

针对缓冲区有限的流水车间调度问题,分析了目标函数的特征,及目标函数与工件空闲时间之间的关系,设计开发了启发式算法。算法将以Makespan为目标函数转化成以最小化机器空闲时间为目标函数,并以此为基础构造初始加工序列,再通过贪婪排序与插入寻优消除缓冲区受限约束并寻找问题的近优解。仿真实验结果表明,算法在求解质量和计算时间方面明显优于其他几种排序规则,并体现了目标函数表达式结构的特性及对解的适应性。     

一种柔性车间快速启发式调度算法

柔性作业车间调度问题比传统的Job-shop问题更复杂也更符合实际生产实际.为了快速有效地求解这类问题,设计出一种基于综合分派规则的快速启发式调度算法.基于综合分派规则的调度算法,以一批工件总完工时间最短为目标,在调度过程中通过动态调整工件的加工优先级并为每道工序分配最适合的机器进行加工,可迅速求得满意的较优解.与其他方法进行对比实验结果证实了算法的有效性,在实际调度系统的应用中也证明了算法的实用性.     

工件带到达时间并具有成组约束的车间排序算法

针对模具制造过程的特点,在工件不同时到达的情况下,研究了前阶段带有成组约束的两阶段柔性同序加工车间的调度问题,建立了目标函数为最小化最大完成时间的调度数学模型,基于Potts的RJ’算法提出解决此类问题的启发式算法,并将该算法应用到轮胎模具企业的生产实例中,通过仿真说明数学模型和求解方法的可靠性和有效性。     

基于到达时间两台并行机上在线批调度

考虑两台同构并行机上在线批调度问题．每个批具有不确定的到达时间,一旦机器可以利用,要在当前可以利用的批中选择出合适的批,并将其中的工件调度到机器上,且工件在加工过程中不允许中断．目标函数是使调度的最大完成时间最小．给出了一个批在线调度ＲＢＬＰＴ 算法,即选择当前批中加工时间之和最大的批按ＬＰＴ 规则调度．另外,利用反证法,对算法的最坏情况进行了分析．

     

基于流形距离的迭代聚类算法路面裂缝提取

针对现有算法检测精度不高和边缘定位不准确的问题,提出一种基于流形距离的迭代聚类路面裂缝提取算法。通过计算2个数据点之间的流形距离,设计聚类目标准则函数,利用迭代最优方法解决准则函数的优化问题,将所有数据点划分为背景和目标2个聚类,并结合图像分割算法提取路面裂缝信息。实验结果表明,该算法能稳定有效地提取出图像中的连续裂缝边缘,可用于路面裂缝的自动检测。     

蜂群算法在带时间窗的车辆路径问题中的应用*

根据带时间窗车辆路径问题的实际情况,通过考察车辆数和总行程两个目标函数,给出了该问题的一种新的算法——蜂群算法。通过计算若干benchmark问题,并将结果与其他算法相比较分析,验证了算法的有效性。目前关于蜂群算法的文献较少,故不仅是拓宽蜂群算法应用范围的有效尝试,同时也给带时间窗车辆路径问题提供了一种新的解决方法。     

Improved Approximation Bounds for Planar Point Pattern Matching

We analyze the performance of simple algorithms for matching two planar point sets under rigid transformations so as to minimize the directed Hausdorff distance between the sets. This is a well studied problem in computational geometry. Goodrich, Mitchell, and Orletsky presented a very simple approximation algorithm for this problem, which computes transformations based on aligning pairs of points. They showed that their algorithm achieves an approximation ratio of 4. We introduce a modification to their algorithm, which is based on aligning midpoints rather than endpoints. This modification has the same simplicity and running time as theirs, and we show that it achieves a better approximation ratio of roughly 3.14. We also analyze the approximation ratio in terms of a instance-specific parameter that is based on the ratio between diameter of the pattern set to the optimum Hausdorff distance. We show that as this ratio increases (as is common in practical applications) the approximation ratio approaches 3 in the limit. We also investigate the performance of the algorithm by Goodrich et al. as a function of this ratio, and present nearly matching lower bounds on the approximation ratios of both algorithms. This work was supported by the National Science Foundation under grants CCR-0098151 and CCF-0635099.     

蜂群优化算法在车辆路径问题中的应用

车辆路径问题（VRP）是组合优化中典型的NP难题。根据车辆路径问题的实际情况,考察车辆数和总行程两个目标函数,给出了该问题的一种新的算法,蜂群算法。通过计算若干benchmark问题,并将结果与其他算法相比较与分析,验证了算法的有效性。蜂群算法是刚刚起步的智能优化算法,目前国内外关于蜂群算法的文献较少,故不仅是拓宽蜂群算法的应用范围的有效的尝试,同时也给车辆路径问题提供了一种新的解决方法。     

基于搭配对的汉语形容词—名词聚类

本文提出了一个双向分级聚类的算法同时对不同词性的词进行聚类。在聚类过程中,不同词性的词的聚类交替进行,相互影响。我们以最小描述长度的原理为基础构造了目标函数。为了减小数据稀疏的影响,又提出了修饰度的与修正距离的概念。将此算法应用于汉语形容词- 名词的搭配对,对形容词与名词进行聚类,实验结果显示该算法是有效的。     

基于自适应马氏距离的模糊c均值算法

经典的模糊c均值（FCM）算法是基于欧氏距离的,它只适用于球型结构的聚类,且在处理高维的数据集时,分错率增加。针对以上两个问题,提出了一种新的聚类算法（FCM-M）,它将马氏距离与模糊c均值相结合,并在目标函数中引进一个协方差矩阵的调节因子,利用马氏距离的优点,有效地解决了FCM算法中的缺陷,并利用特征值、特征矢量及伪逆运算来解决马氏距离中遇到的奇异问题。通过数据聚类和图像分割两组实验,证实了该方法的可行性和有效性。     

Joint learning of cross-modal classifier and factor analysis for multimedia data classification

In this paper, we study the problem of learning from multiple model data for the purpose of document classification. In this problem, each document is composed of two different models of data, i.e., an image and a text. We propose to represent the data of two models by projecting them to a shared data space by using cross-model factor analysis formula and classify them in the shared space by using a linear class label predictor, named cross-model classifier. The parameters of both cross-model classifier and cross-model factor analysis are learned jointly, so that they can regularize the learning of each other. We construct a unified objective function for this learning problem. With this objective function, we minimize the distance between the projections of image and text of the same document, and the classification error of the projections measured by hinge loss function. The objective function is optimized by an alternate optimization strategy in an iterative algorithm. Experiments in two different multiple model document data sets show the advantage of the proposed algorithm over state-of-the-art multimedia data classification methods.     

电磁智能车循迹算法

提出了一种智能车竞赛电磁组的循迹算法——比值法,针对现有的常用循迹算法差值法和归一化法中存在计算所得偏差值和偏离距离的函数存在极值点并且在两极值点外距离与偏差值的关系变为负相关的问题,采用对电动势分别开根号作差再比上它们的和值的方法去除极值点,使得距离与电势差在整个取值范围内都呈正相关,去除了错误判断.通过实验验证该方法比常用方法有更好的效果.解决了智能车竞赛中的一个实际问题.     

二维点模式图像的仿射变换配准

提出了一种图像特征点配准算法．该算法为二维点模式图像仿射配准建立了新的求解模型,此模型对参考图像的特征点集和浮动图像的特征点集分别进行Whitening变换,将点集间的一般仿射变换问题转换为刚性变换问题;在对刚性变换求解时,采用平滑性好、局部极值较少的新的目标函数;并引入了形变程度分量,使该算法更能符合实际应用．结合文中提出的新的仿射不变量,目标函数只需在平分法的基础上加入随机因素便能快速求解．实验结果证明,该算法在处理特征点仿射配准问题上具有速度快、精度高的特点．     

一种改进的模板匹配眼睛定位方法

针对眼睛定位问题,文章提出了一种改进的模板匹配方法。在使用一种合成的眼睛模板对图像进行匹配得到多个相似眼睛点的基础上,利用人脸库部分图像中两眼相对位置关系的统计值来构造一个分段距离函数,并计算相似眼睛点的两两距离,根据此距离信息来同时定位双眼。实验结果表明,与传统模板匹配方法相比,该文方法能够同时定位双眼,并显著提高了定位准确率和定位速度。