负载均衡问题

自Ron Graham20世纪60年代发表第一篇负载均衡算法的论文以来,平行机排序作为组合优化近似算法理论的首个问题引起了学界的广泛兴趣,其本身研究的不断深化也一路见证了该领域的发展历程.介绍负载均衡问题的来龙去脉,特别是作者所在团队在相关问题的研究进展,从算法和复杂性不同的视角分析经典问题的计算本质,并对未来的研究提出一些建议.     

基于SMAA和公共权重的决策单元效率评价与排序

在数据包络分析(DEA)中,公共权重模型是决策单元效率评价与排序的常用方法之一。与传统DEA模型相比,公共权重模型用一组公共的投入产出权重评价所有决策单元,评价结果往往更具有区分度且更为客观。本文考虑决策单元对排序位置的满意程度,提出了基于最大化最小满意度和最大化平均满意度两类新的公共权重模型。首先,基于随机多准则可接受度分析(SMAA)方法,计算出每个决策单元处于各个排名位置的可接受度;然后,通过逆权重空间分析,分别求得使最小满意度和平均满意度最大化的一组公共权重;最后,利用所求的公共权重,计算各决策单元的效率值及相应的排序。算例分析验证了本文提出的基于SMAA的公共权重模型用于决策单元效率评价与排序的可行性。     

单机上带有可变前瞻区间的分批在线排序问题

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$（t,t+\Delta（t）]$内到达工件的信息,这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长,其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in（0,1）$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。     

基于在线评价且考虑消费者类型的酒店排序方法

针对在线评价的发布时间、获得的“有用”的投票数以及是否被贴上“砖家”点评标签对在线评价信息可信度和消费者购买决策具有重要影响,提出一种基于在线评价信息且考虑评价信息可信度及消费者类型的酒店排序方法。首先,将不同类型消费者群体给出的在线评价信息转换成考虑在线评价信息可信度的区间中智数;其次,依据区间中智数距离测度公式确定针对目标群体的各消费者群体权重,进而依据INLNPA集成算子集结各消费者群体评价信息确定针对目标群体的酒店-属性决策矩阵;再次,依据区间中智集熵测度方法确定各属性权重,在此基础上,基于VIKOR方法得到针对目标群体的酒店排序结果;最后,通过一个实例分析说明该方法的有效性和可行性。     

具有老化效应的单机共同工期安排和工件可拒绝排序问题

研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。     

模糊量排序综述

对模糊量排序研究作一个全面回顾 ,包括排序问题的描述、应用背景、排序指标综述及分类、排序方法的合理性、排序方法之间的联系等方面。     

成组加工中的加工全程和延误工件数问题

本文在同组工件连续加工的条件下考虑了单机加工中的二个排序问题,其目标函数分别为极小加工全程和延误工件数。文中在不同的条件下对它们给出了多项式时间算法。     

具有专用机与通用机的多组工件的Cmax问题

本文讨论了一类特殊的排序问题；具有专用机与通用机的多组工件的Ｃｍａｘ问题。文中给出了“ＬＰＴ－ＬＳＭＴ”算法，并对最差情况下的性能指标给出了严格的界。     

组合数学与数论间的一些交叉问题初探

我们证明了有限域上的一类方程组解的个数与图的顶点着色数有密切关系，而这又对许多着色问题的产生了许多应用。另外，我们也用图论的一些技巧解决了数论中一些问题。     

基于模糊语言判断矩阵和FIOWA算子的有限方案决策法

定义一种模糊的导出有序加权平均(FIOWA)算子，给出方案之间比较的模糊语言标度。运用模糊语言标度构造出模糊语言判断矩阵，并提出一种基于模糊语言判断矩阵和FIOWA算子的有限方案决策方法。该法利用FIOWA算子对模糊语言信息进行集结，并利用已有的三角模糊数排序公式求得决策方案的排序。