基于一致性排序的动态评价方法研究

主要工作是通过Copealand重排序方法构建动态评价模型,研究动态评价中的一致性排序问题,并通过实证研究验证模型的有效性.首先,利用基尼系数赋权法建立评价模型,确定静态评价结果和排名;然后,通过Copealand法确定出一个综合不同年份排序的一致性排序;最后,根据评价对象不同年份排名的发展趋势对一致性排序进行修正,得到最终的排序.主要特色一是通过Copealand法集合不同年份的排序确定最终的一致性排序,避免了通过引入时间权向量确定动态权重时人为主观因素太强的问题,解决了动态综合评价中的一致性排序问题;二是通过对一致性排序的修正,保证了最终的排序能够体现不同年份的发展趋势.     

模糊算子排序

完成了几种常用的模糊算子的排序工作.     

数学规划与约束规划整合下的多目标分组排序问题研究

分组排序问题属于NP-难题, 单纯的数学规划模型或约束规划模型都无法在有效时间内解决相当规模的此类问题. 控制成本、缩短工期和减少任务延迟是排序问题的三个基本目标, 在实际工作中决策者通常需要兼顾三者, 并在 三者之间进行权衡. 多目标分组排序问题 的研究增强了排序问题的实际应用价值, 有利于帮助决策者处理复杂的多目标环境. 然而, 多目标的引入也增加了问题求解难度, 针对数学规划擅长寻找最优, 约束规划擅长排序的特点, 将两类方法整合起来, 提出一个基于Benders分解算法, 极大提高了此类问题的求解 效率.     

模糊一致矩阵排序方法的集成

基于文献[3]和文献[6]的模糊一致矩阵的排序方法,研究了这两种排序方法及排序向量的共性问题,给出了一种新的模糊一致矩阵排序方法的集成模型,得到了模糊一致矩阵排序方法及排序向量的相关结论和性质,丰富了模糊一致矩阵排序方法的理论和应用。     

区间数排序法在多属性决策中的应用与研究

针对不确定多属性决策问题中区间数排序方法的讨论,首先给出了正区间数排序的公理化定义,然后基于公理化定义提出了区间数几何平均排序法;其次,将优势矩阵排序法、离差最大化排序法、基于相对关联系数的区间数排序法与几何平均排序法进行了比较,并指出了基于相对关联系数的区间数排序法的不足;最后,通过实例分析,得出几何平均排序法可以弥补基于相对关联系数的区间数排序法的不足,且拥有计算简便,运算量少的优点,验证了几何平均排序法的合理性及有效性.     

基于替代航路的进场航班排序优化方法

针对机场终端区航班延误日益严重的现状,为减轻空中交通管制员工作负荷,缓解航班延误,研究了进场航班排序优化问题.通过引入替代进近航路和时间偏差成本的概念,建立了进场航班排序模型;基于调度窗口和冻结范围概念,提出了动态优化方法;结合进场航班排序模型与动态优化方法,以国内某机场的运行数据进行了仿真验证.仿真结果表明:与实际运行相比,基于替代航路的进场航班排序优化方法优化效果显著,减少了约25%的进场航班延误,提高了机场终端区航空器的运行效率.优化方法可以即时获得最优方案,辅助空中交通管制员做出决策.     

单机排序中关于完工前总损失的应急管理

该文研究了扰动环境下的关于完工前总损失的单机排序问题, 也就是这样一个问题: 在时刻 t , 一部分工件已经完工了, 一个扰动发生了, 在这种情形下, 原来的排序已经不是最优排序甚至是不可行排序了. 因此就需要对未完成的工件找一个新的排序. 作者采用的方法与大多数重新排序问题所不同的是: 模型里包含了原始排序与新排序之间的偏差所造成的损失. 作者主要研究了在原始排序中加权最短加工时间规则(WSPT)是最优排序的情形. 根据扰动的类型, 应急管理策略的类型以及目标函数, 研究了几个问题. 对于每个问题, 作者找到了最优排序或者得出了一些重要结果.     

单油罐修理线的天车运送周期性排序问题的求解

作为机车油罐修理中的一个重要资源,天车的排序直接影响系统的生产率.本文研究了产品在系统的一边装载、而在另一边卸载的油罐单修理线的天车周期性排序问题.工件在每个工作台需要加工一定的时间,工作台之间没有缓冲工作台,一台天车用于工作站之间工件的运送,目标是对运送进行排序以极小化生产周期.为了求解这个问题,本文提出了一个混合整数线性规划模型,量化示例表明所提出的方法是有效的.     

模糊数双指标排序的结构元方法

针对现有模糊数排序存在的一些问题,提出了双指标的模糊数排序方法。给出了模糊数隶属函数与其单调变换函数相互转化方法。定义波动数与特征数两个指标,利用这两个指标对模糊数进行排序,并给出了排序原则。该方法可以对各种模糊数进行排序,通过该排序原则常能够简化计算,同时,一定程度上能够弥补一些排序方法不能反映模糊数"波动"情况的问题。通过算例对比分析,本文的方法求解简单,并具有广泛适用性。     

最小化误时损失的一台设备排序问题

排序问题是组合最优化理论中应用很广的课题。据统计,在将近九千个排序模型中,大约9%已有好算法,77%是NP难度的,14%仍未知其计算复杂性。属于最后一种情况的著名例子就是本文讨论的一台设备排序问题(但在加权情况已知是NP难度的)。目前,国内外一系列重要工作均是在Emmons的判定原则基础上进行的。本     

An optimization approach to the reconstruction of positional DNA sequencing by hybridization with errors

Positional DNA sequencing by hybridization (PSBH) is a recently proposed enhancement of DNA sequencing by hybridization (SBH, potentially a powerful alternative to the DNA sequencing by gel electrophoresis). It has been discussed in many papers and applied to large scale sequencing by hybridization. However, the computational part of PSBH reconstruction is a difficult problem, especially for the occurrence of hybridization errors. So far the problem has not been solved well. Taking PSBH as a combinatorial optimization problem, a novel reconstruction approach to PSBH is presented in this paper. The proposed approach accepts both the negative and positive errors and can greatly reduce ambiguities in the reconstruction of PSBH. The computational experiment shows that our algorithm works satisfactorily and correctly on the test data, especially for the positive errors and k-tuple repetitions.     

Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion

In this paper, the single machine sequencing problem with maximum lateness criterion is discussed. The parameters of the problem are imprecise and they are specified as intervals. The maximal regret criterion is applied to calculate the optimal sequence. A polynomial algorithm for the studied problem is constructed.     

Resequencing of mixed-model assembly lines: Survey and research agenda

Nowadays, mixed-model assembly lines are applied in a wide range of industries to mass-produce customized products to order, e.g., in automobile industry. An important decision problem in this context receiving a lot of attention from researchers and practitioners is the sequencing problem, which decides on the succession of workpieces launched down the line. However, if multiple departments with diverging sequencing objectives are to be passed or unforeseen disturbances like machine breakdowns or material shortages occur, a resequencing of a given production sequence often becomes equally essential. This paper reviews existing research on resequencing in a mixed-model assembly line context. Important problem settings, alternative buffer configurations, and resulting decision problems are described. Finally, future research needs are identified as some relevant real-world resequencing settings have not been dealt with in literature up to now.     

An algorithm for mapping short reads to a dynamically changing genomic sequence

Next-generation sequencing technologies have redefined the way genome sequencing is performed. They are able to produce tens of millions of short sequences (reads), during a single experiment, and with a much lower cost than previously possible. Due to the dramatic increase in the amount of data generated, a challenging task is to map (align) a set of reads to a reference genome. In this paper, we study a different version of this problem: mapping these reads to a dynamically changing genomic sequence. We propose a new practical algorithm, which employs a suitable data structure that takes into account potential dynamic effects (replacements, insertions, deletions) on the genomic sequence. The presented experimental results demonstrate that the proposed approach can be extended and applied to address the problem of mapping short reads to multiple related genomes.     

Simultaneous price and due date settings for multiple customer classes

Extending the model of [Eur. J. Oper. Res. 116 (2) (1999) 305] that, under contingent capacity, simultaneously optimizes the bidding price and due date for each incoming order, we propose a bidding model with multiple customer segments classified based on parameters of willingness to pay, sensitivity to short delivery time, quality level requirement, and intensity of competition. The winning probability function was also modified to be of more practical and robust model in reflecting stochastic nature of customer's decision. Two sequencing rules, namely the early-due-date (EDD) for time-critical orders and first-come-first-serve (FCFS) for regular orders, were applied to determine the sequencing position of each incoming order, and a simplified pattern search algorithm was used to improve the efficiency in searching for optimal price and due date. The simulation results show that, in general, our proposed model and method can significantly increase the marginal revenue to the firm.     

Analysis and design of sequencing rules for car sequencing

This paper presents novel approaches for generating sequencing rules for the car sequencing (CS) problem in cases of two and multiple processing times per station. The CS problem decides on the succession of different car models launched down a mixed-model assembly line. It aims to avoid work overloads at the stations of the line by applying so-called sequencing rules, which restrict the maximum occurrence of labor-intensive options in a subsequence of a certain length. Thus to successfully avoid work overloads, suitable sequencing rules are essential. The paper shows that the only existing rule generation approach leads to sequencing rules which misclassify feasible sequences. We present a novel procedure which overcomes this drawback by generating multiple sequencing rules. Then, it is shown how to apply both procedures in case of multiple processing times per station. For both cases analytical and empirical results are derived to compare classification quality.     

Some effects of aircraft arrival sequence algorithms

Although various airport landing sequencing algorithms have been considered in the literature, little work has been done in comparing their effects on Air Traffic Control, especially against first-come first-served (FCFS) runway sequences, the method most widely used in practice. This paper compares a number of such algorithms using a discrete-event simulation model of an airport with a single landing runway. Statistical methods are used to test for effects of sequencing algorithm, delay-sharing strategy, arrival rate and wake-vortex mix. Little benefit to delay, or stability of sequencing advice, is found from advanced sequencing when small changes are made to inputs calibrated to a specific airspace. Advanced sequencing improves landing rate, compared with FCFS sequencing, only when aircraft arrival rate is greater than maximum runway landing rate, and wake-vortex mix is sufficiently varied. Constrained position shifting constraints limit these improvements and it is shown that deterministic optimal techniques may actually be sub-optimal in a dynamic environment. Our main conclusion is that FCFS is a robust method under many conditions.     

排序对策的一个新的收益分配准则

针对一个机器的排序问题,给出了排序问题中成本增加量的表达式,提出了收益分配的不小于成本增加量准则。针对一类特殊的排序问题,给出一个符合不小于成本增加量分配准则的解,并证明了它满足有效性,哑元性和单调性。结合一个算例,对本文的提出的方法进行了分析验证。     

A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem

In this paper, a particle swarm optimization algorithm (PSO) is presented to solve the permutation flowshop sequencing problem (PFSP) with the objectives of minimizing makespan and the total flowtime of jobs. For this purpose, a heuristic rule called the smallest position value (SPV) borrowed from the random key representation of Bean [J.C. Bean, Genetic algorithm and random keys for sequencing and optimization, ORSA Journal of Computing 6(2) (1994) 154–160] was developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems. In addition, a very efficient local search, called variable neighborhood search (VNS), was embedded in the PSO algorithm to solve the well known benchmark suites in the literature. The PSO algorithm was applied to both the 90 benchmark instances provided by Taillard [E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research, 64 (1993) 278–285], and the 14,000 random, narrow random and structured benchmark instances provided by Watson et al. [J.P. Watson, L. Barbulescu, L.D. Whitley, A.E. Howe, Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance, ORSA Journal of Computing 14(2) (2002) 98–123]. For makespan criterion, the solution quality was evaluated according to the best known solutions provided either by Taillard, or Watson et al. The total flowtime criterion was evaluated with the best known solutions provided by Liu and Reeves [J. Liu, C.R. Reeves, Constructive and composite heuristic solutions to the P∥∑C_i scheduling problem, European Journal of Operational Research 132 (2001) 439–452], and Rajendran and Ziegler [C. Rajendran, H. Ziegler, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155(2) (2004) 426–438]. For the total flowtime criterion, 57 out of the 90 best known solutions reported by Liu and Reeves, and Rajendran and Ziegler were improved whereas for the makespan criterion, 195 out of the 800 best known solutions for the random and narrow random problems reported by Watson et al. were improved by the VNS version of the PSO algorithm.